9.3. Routing Protocol Basics
9.3.1. Routing and Forwarding
In the context of the Internet, the term “routing” is used loosely to identify both control and data plane functions. It is, however, important to differentiate between these functions. The role of the control plane is to allow nodes to discover the topology of the network and compute routes to other nodes. This is accomplished by running a routing protocol that advertises topology and reachability information throughout the network. The reachability information disseminated by the routing protocol is consolidated in a forwarding table at each node, which contains the identity of the next node and the outgoing interface to forward packets addressed to each destination.
The data plane function at a router consists of forwarding incoming IP packets (or datagrams) toward their destinations, using the information contained in the forwarding table. More specifically, forwarding an IP datagram involves examining the destination IP address of the datagram, searching the forwarding table to determine the next hop and the corresponding outgoing interface, and then forwarding the datagram to the next hop. Forwarding also involves other functions, such as examining and decrementing the time-to-live (TTL) field of the packet and examining and adjusting the header checksum (see Figure 5-11) [Tanenbaum02]. If quality of service (QoS) features are implemented, then the forwarding function may include packet classification based on the source address, destination address and other fields found in the IP header, and perhaps even the IP payload [Braden+97, Wroclawski97].
It should be noted that only the control plane of IP routing is adapted for use in optical networks. The packet forwarding function of IP routing is not relevant in these networks.
9.3.2. Routing Protocol Design Tenets
The following principles are generally followed in the design of IP routing protocols:
Simplicity: Routing algorithms are designed to be as simple as possible. In other words, a routing algorithm is ideally designed to function efficiently, incurring the minimum computational and communication overhead. Efficiency is particularly important when the routing software must run on a processor with limited resources.
Scalability: Scalability is the ability of a routing protocol to accommodate a large number of routers and end-systems without incurring excessive overheads. This is one of the most important design tenets of any IP routing protocol. There are different ways of achieving scalability, such as employing a routing hierarchy or performing route aggregation (see Chapters 10 and 12). Both these techniques help contain the size of the routing databases. Another common technique for achieving scalability is to reduce the number of routing updates using thresholding schemes. This is further described in Chapter 10.
Optimality and accuracy: Optimality refers to the ability of a routing algorithm to select the best route, as defined by some metric (see Chapter 11). As an example, a routing algorithm may use the number of hops and total delay as metrics, but may weight delay more heavily in the calculation of routes. Naturally, routing metrics must be defined precisely for the type of optimization to be performed.
Robustness and stability: Routing algorithms must be robust, which means that they should perform correctly under adverse circumstances, such as when hardware failures, high load conditions or incorrect implementations are encountered. Because routers are located at network junction points, they can cause significant problems when they fail. The best routing algorithms are often those that have withstood the test of time and have proven stable under a variety of network conditions.
Convergence: In addition to being robust, routing algorithms must converge rapidly. Convergence is the process by which all routers agree on optimal routes. When a network event causes existing routes to become unavailable or new routes to become available, routers distribute routing update messages throughout the network. This results in the recalculation of optimal routes by some or all routers. Routing algorithms that converge slowly can cause routing loops or network outages.
Figure 9-3 illustrates the looping problem in a network consisting of eight routers (R1-R8). Here, a packet destined to R8 arrives at R1. The shortest path from R1 to R8 is the direct link. But that link is down as shown. Suppose that R1 has already recomputed the optimal route to R8 as (R2-R3-R4-R8). It therefore forwards the packet to R2. Suppose that R2 has not yet received the information about the failed link and it still has R1 listed as the next hop to R8 (along the path R2-R1-R8). R2 therefore forwards the packet back to R1, and the packet continues to bounce back and forth between the two routers until R2 receives the routing update.
Figure 9-3. Routing Loop Illustration
Flexibility: Routing protocols should be flexible, that is, they should accommodate different metrics, support one or more routes to destinations, multiple routing hierarchies, and most importantly future extensions.
9.3.3. Different Types of IP Routing Protocols
There are two basic types of IP routing protocols: distance-vector and link-state. Under the distance-vector approach, each node maintains the distance (e.g., hop count) to each destination through each of its neighbors. The next hop to a destination is taken to be the neighbor through which the distance to the destination is minimum. Under the link-state approach, each node maintains the complete view of the network topology. To keep this view up-to-date, each node broadcasts the details of its local links to other nodes in the network. Nodes compute paths to different destinations based on the topology view. These routing approaches are described further below.
9.3.3.1. DISTANCE VECTOR ROUTING
Under the distance vector approach, each node maintains the cost (or distance) to each destination through each of its neighbors. A node selects the neighbor through which the cost to a destination is minimum as the next hop for that destination. The intention is that from any node the succession of next hops would lead to the destination. The cost of a path from a source to a destination is the sum of the costs of the links in the path. The network administrator typically provisions link costs, although it is possible to automatically map certain link characteristics into costs. A change in the link cost occurs when the link fails, or when the cost is updated. A change in the cost of the link would result in the change in the cost of all paths that use the link. This change would first be observed by the two end points of the link. These nodes would then update the costs to different destinations that are reachable over the link. If a node determines a change in the minimum cost to a destination, it sends the new minimum distance to its neighbors. If the minimum distances to different destinations maintained by a neighbor change due to these updates, the process is repeated [Tanenbaum02].
It is well known that classical distance-vector algorithms such as distributed Bellman-Ford [Bellman58, Ford+62] may produce both short-lived and long-lived loops (Figure 9-3). Routing Information Protocol (RIP) [Hedrick88] is an example of a routing protocol that uses the distributed Bellman-Ford algorithm (see Chapter 11). New generations of distance vector algorithms, such as Merlin-Segall algorithm [Merlin+79], avoid looping. A variation of the distance vector approach, known as path vector, utilizes information about the entire sequence of “next hops” to a destination (i.e., the nodes in the path) to detect and avoid routing loops [Rajagopalan+91]. The Border Gateway Protocol (BGP) [Stewart99, Rekhter+95] is an example of a path vector protocol.
9.3.3.2. LINK STATE ROUTING
Under the link-state approach, each node maintains a view of the network topology and link costs. When the state of a link changes (up to down or vice versa, or a change in link cost), a notification, called a Link State Advertisement (LSA) is flooded throughout the network. All the nodes note the change and recompute their routes accordingly. Note that a node's view of the link state may not be the same as another node's due to long propagation delays, partitioned networks, and so on. Such inconsistent views of network topology at different nodes may lead to routing loops. These loops, however, are short-lived, and they disappear after the link-state updates are received by all the nodes. Link state routing protocols are more scalable and less bandwidth-intensive than distance vector routing protocols. They are, however, more complex, and more compute- and memory-intensive.
The first link-state routing protocol, called Shortest Path First (SPF), was developed for use in the ARPANET (Department of Defense's Advanced Research Project Agency, now called DARPA) packet switching network. It was the starting point for all other link state protocols developed later. The homogeneous ARPANET environment, that is, single-vendor packet switches connected by synchronous serial lines, simplified the design and implementation of the original protocol. Over time, the protocol matured with many enhancements. These enhancements dealt with improving the fault tolerance and convergence of the routing protocol. Among other things, this included the addition of a checksum to LSAs (thereby detecting database corruption). It also included means for reducing the routing traffic overhead. This was accomplished by introducing mechanisms, which enabled the interval between LSA originations to be increased by an order of magnitude.
The Internet Engineering Task Force (IETF) extended the SPF work to develop the Open Shortest-Path First (OSPF) routing protocol [Moy98]. OSPF is a hierarchical link state routing protocol that supports multiple routing areas. This enables routing scalability through information hiding and summarization. OSPF also includes specific features for efficient operation in internets consisting of broadcast Local Area Networks (LANs) and other multiple access networks. A somewhat similar link state protocol, called IS-IS (Intermediate System to Intermediate System), was specified by the International Standards Organization (ISO), and adopted by the IETF for IP routing [Callon90].