As WANs expand and become more complex, the importance of controlling the traffic flow increases.
|
There may be many different routes from source to destination across an internetwork over which traffic can flow.
|
The problems of avoiding congestion on these routes and assigning available bandwidth effectively are handled by intermediary devices called ^Rrouters^r.
|
A router is a device that relays packets from one network to another.
|
Routers are often contrasted with ^Rswitches^r.
|
The primary difference between routing and switching is that switching occurs at the data-link layer of the OSI model while routing occurs at the network layer.
|
This distinction provides routers and switches with different information to use in the process of moving information from source to destination. As a result they accomplish their tasks in different ways.
@@
Routing involves two basic activities:

• path determination
|
• switching
|
Path determination enables the router to evaluate available paths to a destination and determine which to use.
|
For example, if one path is congested, the router may send the data along a different path to its destination.
|
Routers determine the path to a destination using ^Rrouting algorithms^r.
|
Routing algorithms initialize and maintain ^Rrouting tables^r which contain route information.
|
Route information varies depending on the routing algorithm being used.
|
For example, destination/next hop associations tell a router that the final destination can be reached by sending the packet to a particular router representing the "next hop" on the way.
|
When a router receives an incoming packet, it checks the destination address and attempts to associate this address with a next hop.
|
Routers communicate with each other and maintain their routing tables by transmitting messages.
|
For example, routers transmit routing update messages.
|
A routing update message generally consists of all or a portion of a routing table.
|
Each router in an internetwork analyzes routing update messages from other routers.
|
In this way each router can build up a detailed knowledge of the network topology.
|
Once the topology is understood, the router can determine the path to a network destination.
@@
The exact way in which a router determines which of the available paths to a destination is the optimal one depends on the metrics used by its routing algorithm.
|
Some of the metrics used by routing algorithms are

• path length
|
• reliability
|
• delay
|
• ticks
|
• hop count
|
• bandwidth
|
• load
|
• communication cost
|
Path length is the most common routing metric.
|
What exactly is measured in determining path length depends on the routing protocol being used.
|
Some routing protocols allow you to assign costs to each network link.
|
In this case, the path length is the sum of the costs associated with each link traversed.
|
The routing algorithm compares the cost of each route to the destination and deems the one with the least cost to be the most desirable.
|
Other routing protocols determine the path length by performing a hop count to the destination.
|
Every time the route passes through an internetwork node, such as a router, it is deemed to be a hop.
|
The selected route is the one containing the least number of hops.
|
Reliability, another routing metric, refers to the reliability of each network link.
|
The reliability of a link is usually described in terms of its bit-error rate.
|
Some network links may "go down" more often than others.
|
Once down, some may be repaired more easily or quickly than others.
|
Reliability ratings are usually assigned to network links by network administrators.
|
Typically they are arbitrary numeric values.
|
A router can then compare the reliability of routes to the destination and choose the most reliable.
|
For example, one route could be over fiber optic while another could be over copper wires. The fiber optic route would be deemed more reliable.
|
Delay is a common routing metric.
|
Routing delay refers to the length of time required to move a packet from source to destination through the internetwork.
|
Delay depends on many factors such as

• the bandwidth of 
  intermediary links
|
• the port queues at each 
  router along the way
|
• the physical distance 
  to be travelled
|
Some routing algorithms maintain a tick count, for example NetWare or IP.
|
Here, a tick is the delay on a data-link counted using IBM PC clock ticks (approximately 55ms).
|
Routing algorithms can also keep track of the hop count to a particular destination.
|
The hop count is the number of passages of a packet through the output port of one router.
|
Bandwidth can also be used as a routing metric.
|
Bandwidth refers to the available traffic capacity of a link.
|
For example, in terms of the bandwidth metric, a 1.544 Mbps T1 link would be preferable to a 64 Kbps leased line.
|
The route with the highest bandwidth is not always the best route to choose.
|
For example, if a fast link is much busier than a slower link, the actual time taken to send a packet to the destination may be greater using the fast link.
|
Load refers to the degree to which a network resource, such as a router, is busy.
|
It can be calculated in a variety of ways including CPU utilization and packets processed per second.
|
Monitoring network load as a metric can itself be resource-intensive.
|
The router may determine that the route with the least load is an optimal one.
|
Communication cost is another important metric.
|
Some companies may not care about performance as much as they care about operating expenses.
|
Even though line delay might be longer, they might send packets over their own lines rather than through public lines that will cost money for usage time.
|
Many routing metrics are interdependent.
|
Sophisticated routing algorithms can base route selection on multiple metrics, combining them in a single hybrid metric.
@@
The switching function of a router allows it to accept a packet on one interface and forward it on a second interface.
|
Switching algorithms are relatively simple and are basically the same for most routing protocols.
|
Assume that a host on one network has a packet to send to a device on another network.
|
The host addresses the packet with the physical (MAC) address of a router on its network and the network address of the destination device, and sends it to the router.
|
When the router receives the packet it examines the packet's destination network address.
|
If the router does not know how to forward the packet it typically ignores it.
|
If it knows how to forward the packet it changes the data-link address of the packet to that of the next hop and transmits the packet.
|
The next hop may or may not be the ultimate destination host.
|
If not, the next hop executes the same switching decision process.
|
As the packet moves through the internetwork, its data-link address changes but its network address remains the same.
@@
In order to be able to route packets across an internetwork, it is essential to be able to locate the different devices on an internetwork.
|
Each device on an internetwork should have a unique node address.
|
If two devices on an internetwork have the same node address, a conflict will arise.
|
Similarly, each network on an internetwork should have a unique network address.
|
The node address refers to a device's specific port on the network.
|
The node address is also known as the ^Rhost^r address, the ^Rlink-layer^r address, the ^Rphysical^r address or the ^Rhardware^r address.
|
For most LANs, node addresses are resident in the interface circuitry and are assigned by the organization that defined the protocol standard used by the interface.
|
Node addresses use a flat addressing structure.
|
The node address part of an address is generally checked only when the packet is on the source or destination network.
|
On LANs, the node address can reflect the real MAC address of the destination device.
|
Because most network devices have one physical network connection, they need only a single node address.
|
However, routers and other devices physically connected to more than one network can have multiple node addresses.
|
Node addresses exist at the data-link layer of the OSI reference model.
|
Network addresses exist at the network layer.
|
The network address identifies a particular network within the internetwork.
|
Network addresses are also known as ^Rvirtual^r, or ^Rlogical^r, addresses.
|
Network addresses are used by routers to identify the source or destination network of a packet.
|
For some network layer protocols, a system administrator assigns network addresses according to a preconceived internetwork addressing plan.
|
For others, assigning addresses is partially or completely dynamic.
|
Unlike data-link addresses, network addresses are usually hierarchical.
|
They differ depending on the protocol being used.
|
Generally they use logical divisions to find devices.
|
For example, logical divisions could be based on physical characteristics such as the network segment a device is located on, or logical groupings such as a zone that uses a particular LAN protocol.
@@
There are various addressing schemes used depending on the protocol being used.
|
For example, AppleTalk addressing is different from TCP/IP addressing, which in turn is different from OSI addressing, and so on.
|
The two-part node and network addressing scheme extends across many protocols.
|
These protocols include

• TCP/IP
|
• Novell IPX
|
• AppleTalk
|
However, how the address parts are interpreted and what authority allocates them, differs from protocol to protocol.
|
Cisco routers can handle all of these and many other protocol-specific addressing schemes.
@@
Internetwork addresses consist of a network part and a host part.
|
In the original IP specification, described by RFC 760, the network address was defined by the first octet.
|
With only eight bits determining the network address this allowed for a total of 254 networks on the internetwork.
|
With the advent of the Internet, a need arose to be able to address more than 254 networks within an internetwork.
|
A new IP specification described in RFC 791, introduced the concept of classes.
|
Having both classless, and classful addressing gave rise to a need for routers which could deal with both addressing methods.
|
Some routing protocols use classless addressing while others use classful addressing.
@@
Classless routers accept a prefix of any length.
|
An indication of the length of the prefix is carried with the IP address.
|
This is conventionally done using a mask.
|
More recently, a length indication has followed the address and a slash, for example 192.168.168.0/21.
|
Classful routers accept only a few specified prefix lengths, modified (extended) by the use of subnet masks.
|
The three customary IP address classes define prefix lengths as follows:

• class A has a prefix length 
  of 8 bits
|
• class B has a prefix length 
  of 16 bits
|
• class C has a prefix length 
  of 24 bits
|
When a router examines an IP address it can tell the prefix length by the first few bits of the address:

• class A addresses always start 
  with 0
|
• class B addresses always start 
  with 10
|
• class C addresses always start 
  with 110
|
For more information on classless and classful addressing see the CBT Systems course ^RTCP/IP Routing Protocols and Cisco Routers^r.
@@
Let's look for example at TCP/IP addressing.
|
TCP/IP networks represent addresses as 32-bit entities.  They are usually displayed as four octets separated by dots, for example 10.8.2.48.  This is called "dotted decimal" format.
|
The IP address is accompanied by a ^Rmask^r number, for example 255.0.0.0.
|
The mask number identifies for the router which part of the IP address it should interpret as the network number.
|
The remainder is interpreted as the host address inside the network.
|
In TCP/IP addressing the node address is known as the ^Rhost^r address.
|
The first number, in this instance 10, is the network part of the address.
|
The last three numbers, in this instance 8.2.48, make up the host address.
|
The Internet Request for Comment (RFC) 1020 divides the TCP/IP address into network classes with classless InterDomain Routing (CIDR).
|
RFC is a document series used as the primary means for communicating information about the Internet.
|
Network and node division is arbitrary and specified with a suffix /n where 1<n<32.
|
Network addresses are assigned by a central authority, the Network Information Centre (NIC) and in Europe by RIPE.
|
The three classes commonly used to identify networks are

• class A - using 8 bits for the
  network address and the remaining
  24 bits for the node address
|
• class B - using 16 bits for the 
  network address and the remaining 
  16 bits for the node address
|
• class C - using 24 bits for the 
  network address and the remaining 
  8 bits for the node address
|
Typically TCP/IP networks are divided into subnetworks.
|
When a TCP/IP address has been subnetted, the network part of the address is described by two elements

• the network number (still 
  assigned by the NIC)
|
• the subnetwork number 
  (assigned by the local 
  network administrator)
@@
Novell IPX addressing also uses a two-part addressing scheme.
|
The network address is a hexadecimal, up to 32 bits long.
|
This network address refers to the media, for example Ethernet or Token Ring.
|
The node address, also a hexadecimal number, is a fixed 48 bits long.
|
The node address is derived automatically from the MAC address of the specific LAN device.
|
AppleTalk addressing also uses a two-part addressing scheme.
|
The network address is 16 bits and the node address is 8 bits.
|
The 16 bit network addresses are assigned to physical links either individually or in ranges called ^Rcable ranges^r.
|
This approach makes it possible for many network addresses to use the same LAN media.
|
The node address is usually acquired dynamically by an Apple station when it boots up onto the network.
|
Within the X.25 protocol suite, the X.121 protocol covers the international numbering plan for public data networks (PDNs).
|
The network portion of the address is three or four decimal digits.
|
These are known as the data network identification code (DNIC).
|
The DNIC includes a data country number (DCC).
|
For example, for the USA the DNIC could be 3106, where 310 is the DCC and 6 represents Tymnet, one of the major PDNs.
|
The node portion of the address is called the network terminal number (NTN).
|
The X.25 network administrator usually obtains these NTNs from an authority within the X.25 data network service provider.
@@
Routing algorithms vary depending on what they are designed to achieve.
|
The particular design goals of the algorithm affect the operation of the resulting routing protocol.
|
Routing algorithms often have one or more of the following goals:

• optimality
|
• simplicity
|
• robustness
|
• rapid convergence
|
• flexibility
|
Optimality refers to the ability of the routing algorithm to select the best route.
|
What constitutes a best route depends on the metrics and metric weightings used to make the calculation.
|
For example, one routing algorithm might use a number of hops and delay, but might weight delay more heavily in the calculation.
|
Routing algorithms are designed to be as simple as possible.
|
They must offer their functionality efficiently with the minimum of software and CPU utilization overhead.
|
Efficiency is particularly important when the software implementing the routing algorithm must run on a device with limited physical resources.
|
Routing algorithms must be robust and stable.
|
They should perform correctly in the face of unusual or unforeseen circumstances such as hardware failure, high load conditions, and incorrect implementations.
|
Because routers are located at network junction points they can cause considerable problems if they fail.
|
The best routing algorithms are often those that have withstood the test of time and proven stable under a variety of network conditions.
|
When a network event causes routes to either "go down" or become available, routers distribute routing update messages.
|
These messages percolate through the internetwork stimulating recalculation of optimal routes.
|
Eventually all routers will agree on optimal routes.
|
This process is known as ^Rconvergence^r.
|
Routing algorithms should converge rapidly.
|
Algorithms that converge slowly can cause routing problems.
|
For example, suppose that Router A receives a packet.
|
Suppose also that Router A has already been updated and so knows that the next hop is Router B.
|
Router B receives the packet but has not yet received the routing update message.
|
It assumes that the old information is still correct and it believes that the next hop to the destination is Router A, so it forwards the packet back there.
|
The packet will continue to bounce back and forth between the two routers until Router B receives the routing update message or until it has been switched the maximum number of times allowed.
|
Routing algorithms should be flexible.
|
They should quickly and accurately adapt to a variety of network circumstances.
|
For example, suppose that a network segment fails.
|
In a situation such as this, many routing algorithms will quickly select the next best path for all routes normally using the failed segment.
|
Routing algorithms can be programmed to adapt to changes in network bandwidth, router queue size, network delay, and other variables.
@@
Many people confuse the terms ^Rrouted protocol^r and ^Rrouting protocol^r.
|
Routed protocols are protocols that are routed over an internetwork.
|
Some examples of such protocols are

• the Internet Protocol (IP)
|
• DECnet
|
• AppleTalk
|
• NetWare
|
• OSI
|
• Banyan VINES
|
• Xerox Network System (XNS)
|
Routed protocols provide enough information in their network layer addresses to allow routers to direct user traffic.
|
They define the format and use of the fields within a packet.
|
Packets are generally conveyed from end-system to end-system.
|
Routing protocols, on the other hand, are protocols that exchange routing information.
|
Implemented in routers, they enable direction of routed protocols through an internetwork.
|
Some examples of intra-domain protocols are

• Interior Gateway Routing 
  Protocol (IGRP)
|
• Enhanced Interior Gateway 
  Routing Protocol (EIGRP)
|
• Open Shortest Path First (OSPF)
|
• Intermediate System to 
  Intermediate System (IS-IS)
|
• Routing Information Protocol 
  (RIP)
|
And inter-domain protocols include

• Exterior Gateway Protocol (EGP)
|
• Border Gateway Protocol (BGP)
|
Routing protocols support routed protocols by providing mechanisms for sharing routing information.
|
They allow routers to communicate in order to maintain and update routing tables.
|
Routing protocol messages do not carry user data - they carry routing information.
|
They use the routed protocol to move between routers.
|
Routers are capable of supporting multiple independent routing and routed protocols.
|
They can operate several routing algorithms and maintaining associated routing tables for several routed protocols concurrently.
|
This allows a router to interleave packets from several routed protocols over the same data-link.
|
In a multiprotocol router the routed and routing protocols usually have no knowledge of other protocols.
|
This concept is called ^Rships-in-the-night^r routing.
