Router technology must include an automated mechanism that facilitates the building and maintenance of a routing table. The routing table tells a router what to do with a packet addressed to a given network. A router must have a defined “next hop” for every destination network, or it will discard the packet as undeliverable, unless there is a default route.
The visual shows Router 2’s routing table, which tells it what to do with packets addressed to network A, B, or C. Networks B and C require no routing protocol, as Router 2 directly connects to both networks and thus knows how to reach them inherently. Router 2 had to “learn” Network A, however, in order to forward packets addressed to Network A. It is the job of the routing protocol to build and maintain a router’s routing table. Notice that the routing table indicates a next hop for a given destination network (as opposed to an individual host), along with an associated cost.
Contrast the routing protocol with the routed protocol. The routed protocol is an Internet protocol that specifies the source, target networks, and hosts, and is forwarded according to information found in the routing table. The routing protocol, on the other hand, builds and manages the routing table.
There are many approaches to teaching a router about networks to which it does not directly connect. The most common routing protocols are “distributed, nonisolated, and dynamic” in nature. This means that no single node makes routing decisions on behalf of other nodes (distributed), that the routing nodes communicate with one another to exchange routing information (nonisolated), and that routing information is subject to change based on current network conditions (dynamic).
Within the above classification there are two families of routing protocols, the Distance Vector (DV) and Link State (LS). DV protocols such as the Routing Information Protocol (RIP), and Interior Gateway Routing Protocol (IGRP) are simple in nature and normally involve swapping a router’s entire routing table with its peers. Cost in a DV protocol is normally a simple hop count that indicates how many routers lie along the path to the target network. Link State protocols are newer and more complex but offer the advantages of faster convergence, reduced network loading, and the ability to support complex metrics (route costs) which can include delay, link speed, reliability, etc. Examples of LS routing protocols include Open Shortest Path First (OSPF), and intermediate system to intermediate system (IS-IS).
Fast convergence is an important aspect of a routing protocol, because during the convergence phase packets may be routed in loops or into “black holes.” The network is “converged” when all routers have consistent information that will route a packet correctly along an optimal path to its destination network.
Evaluating Routing Protocols
The efficiency of routing protocols can vary widely, and in a number of areas. Some routing protocols require routers to periodically share information concerning the underlying internetwork. The specific information being shared, the frequency of the exchanges, and the manner in which the exchange is executed could result in higher or lower bandwidth demands on the underlying network. If every router exchanges small portions of information locally and infrequently, the bandwidth demands will be modest. If the exchanges are larger, more frequent, or broadcast throughout the internetwork, the resulting load can be significant. Whatever load the routing protocol introduces consumes bandwidth that is now unavailable to transmit user data.
If the routing protocol is making route selections on behalf of the Network Layer software, and storing them in the routing table, then the basis of those decisions is important. The item of information on which a router bases decisions is called a metric. For example, a router that can only select routes on the basis of the fewest hops to the destination may not select particularly good paths in a network where subnetworks have widely varying bandwidths.
In addition, a router that can only support a single routing metric cannot support type of service (TOS) routing. If the Network Layer defines a TOS service (e.g., the Internet Protocol version 4 permits the end station to request services based on delay, throughput, reliability, and cost), the routing protocol must be able to calculate different routes based on different types of service. This implies the ability to manage multiple metrics. If the routing protocol cannot support multiple metrics, it cannot support TOS routing.
Routing protocols can vary widely in their convergence characteristics. A network has converged when all of the devices making routing decisions have been updated as to the underlying network’s actual nature. Until this happens, the routing tables in the internetwork will not be correct.
This is an important issue when assessing a routing protocol’s quality. So long as a routing table remains incorrect, packets can be misdirected, which results in application failures or retransmissions. We might see this when we use directory assistance. If the strategy for keeping the directory assistance database current is not effective, the operator consulting that database passes on information that is incorrect or incomplete. As a result, we may receive the wrong number or no number at all. In a network, this condition cannot persist for any appreciable amount of time, usually measured in seconds or a few minutes.
Finally, the routing protocol is typically implemented as yet another portion of software. Software requires a processor to execute and memory to execute in. The memory is required not only for the routing protocol itself, but for any data it may need to store. Routing protocols can vary widely in their demands on the computer system. For platforms dedicated to the routing function, this is usually not a major consideration. Such platforms are engineered to meet any potential demand they may encounter. The software router (usually found within a server) may be impacted by heavy processing and memory loads introduced by the routing protocol. These systems need their processing and memory resources to support end-user applications.
Classifying Routing Protocols
The visual depicts one way of classifying routing protocols. At the top level, routing protocols can be classified by their flexibility as static or dynamic. Static routing protocols (nonadaptive) are those that only permit manual configuration of the routing information. This type of routing protocol is not used as much in today’s internetworks. The sole exception is the IBM Systems Network Architecture (SNA) environment.
Dynamic routing protocols are adaptive and can automatically update in response to network changes. These are the routing protocols most commonly implemented in modern internetworks, although all routers and end stations retain the ability to store statically configured routes.
Dynamic routing protocols can be further classified as distributed or centralized. This classification is based on which devices in the internetwork are making the routing decisions. Centralized routing protocols concentrate all routing decisions at a central node. This approach has many problems, including a defined single point of failure and the tendency for the network to become congested around the central node. Such limitations make it unpopular for internetworks.
Distributed routing protocols make each device in the internetwork responsible for making its own routing decisions. Dynamic, distributed routing protocols are by far the more commonly used.
Distributed routing protocols can be further classified as isolated or nonisolated. This classification is based on the degree to which the routing devices intercommunicate. As the name implies, isolated routing protocols do not require (or allow) devices to share network information with one another. This approach is useful for some tasks, but it is not the type of routing protocol that serves as the primary routing protocol for an internetwork.
Most internetworks implement nonisolated routing protocols, where information exchange between routing devices is required. The information shared can take a number of forms and be shared in a number of ways. However, the information exchanged directly or indirectly reflects the network topology.
Finally, dynamic, distributed, nonisolated routing protocols fall into two broad classes differentiated by the manner in which routing information is exchanged and routes are calculated. The two most commonly implemented types of routing protocol are distance vector and link state.
In brief, a distance vector routing protocol involves the exchange of destination (by address) and cost (or distance) information between neighboring systems. Distance vector routing protocols tend to generate updates at regular intervals, although some of the newer protocols generate updates on an as-needed basis. A link state routing protocol is based on flooding link status information throughout the network, permitting each device to build a “map” of the network and select appropriate routes accordingly. Link state protocols tend to generate updates on an as-needed basis.
|<mp3>http://podcast.hill-vt.com/podsnacks/2007q1/routing_protocol.mp3%7Cdownload</mp3> | Routing Protocol|