3.2 Routing algorithms

On any internetwork, packets may traverse many networks and router hops in order to reach their final destination, and many forwarding decisions must be made en route. For this purpose, a routing algorithm is required to determine the best path for each source-destination pair (s, d), and a routing protocol is required to enable intermediate systems to exchange topology and state information, so that a routing table can be formulated.

3.2.1 Distance-vector routing algorithms

Routing protocols that incorporate distance-vector algorithms are often called minimum hop. RIP is perhaps the best-known example in use today, although other examples include the original ARPANET routing protocol, AppleTalk RTMP, and Cisco's IGRP. Distance-vector provides a straightforward and effective routing mechanism, in that shortest path lengths are calculated by simply adding up hop counts between routers [1]. This relative simplicity leads to several significant drawbacks for modern internetwork design.

Protocols that implement distance-vector typically lack sensitivity to delays induced on a network. Distance-vector protocols do not generally support load balancing. Another issue is that convergence around routing failures tend to be very slow (often minutes), and even normal operation can cause routing loops. Overall these protocols scale badly—first in that they are typically constrained in diameter (i.e., the number of hops) of the network and second in that they generally broadcast entire routing tables at regular intervals, and so the protocol overhead grows linearly O(N) with the number of networks. Cisco's proprietary adaptation of RIP, called IGRP, does offer workarounds for several of these problems; however, in general, this class of protocol is considered unsuitable for large internetworks (Cisco's EIGRP uses a hybrid routing algorithm, which, although based on the distance-vector, results in convergence times similar to that of OSPF).

3.2.2 Link-state routing algorithms

Link-state algorithm is a term synonymous with Shortest Path First (SPF) and Dijkstra (a shortest path algorithm described in [1]). The term "link" in this context refers to an interface on the router. The term "state" means a description of that interface and of its relationship to its neighboring routers. For example, this might include the IP address of the interface, the mask, the type of network it is connected to, and a list of neighboring routers connected to that interface. The repository that holds all of these link states is called a link-state database.

In a link-state network each router knows the complete topology of its local domain, since all routers maintain a complete copy of the topology database. Link-state routing protocols use a much richer set of metrics than hop-based protocols and consequently are much better suited to Type of Service (TOS)—based routing. The other major benefit of this class of protocols is that once routing databases are synchronized, only link-state updates are propagated throughout the network, significantly reducing background routing traffic. The first link-state routing protocol was developed for use in the ARPANET back in the 1980s, and this work was the springboard for a new generation of link-state routing protocols such as OSPF and IS-IS.

3.2.3 Link-state versus distance-vector routing

The most important differences between the different routing algorithms from the network designer's perspective are scalability, bandwidth and protocol efficiency, stability, and convergence time. Scalability is a key factor in your choice of routing protocol. Distance-vector protocols have the reputation of scaling badly, largely because they tend to distribute the entire routing table at regular intervals. This can represent a significant overhead for low-speed WAN links and is amplified by the lack of hierarchy in many of these protocols. Distance-vector protocols also tend to use broadcasts (RIPv2 supports the option of multicast distribution). With these protocols regular broadcasts occur regardless of whether the routing table has changed.

Changes in LSAs cause each router within the area to recalculate the forwarding table. The fact that LSAs need to be flooded throughout the area in failure mode and the fact that all routers recalculate routing tables constrain the number of neighbors that can be in an area. Link-state protocols tend to be more CPU and RAM intensive, but their background bandwidth requirements are much less of an overhead than distance-vector traffic (although the startup requirements for link-state routers tends to be higher due to synchronization traffic). Figure 3.2 graphically illustrates the scalability issues for distance-vector protocols as compared with link-state protocols.

click to expand
Figure 3.2: Scalability of link-state protocols versus distance-vector protocols as the number of routes increase.

Distance-vector protocols typically use flooded updates that are sent to all routers. Link-state protocols such as OSPF also flood routing information but use bounded updates to their nearest neighbors (by setting the TTL to 1). When the network is stable, distance-vector protocols behave well but waste bandwidth because of the periodic transmission of complete routing table updates, even when no change has occurred. When a failure occurs in the network, distance-vector protocols do not add excessive load to the network, but they generally take a long time to reconverge and provide an alternate path or to flush a bad path from the network.

Link-state protocols do have some drawbacks. Each time there is a topology change, each link-state router must rerun the SPF algorithm locally to recalculate its forwarding database; while in this state no forwarding is taking place, so this must be achieved quickly. On a large network the processing and memory requirements can be significant, and an SPF tree must be created for each area supported on a router. Another issue with SPF protocols is that they are much more sensitive to changes in topology. While this is inherently a good thing, and precisely what you would want from a routing protocol, in some circumstances this is undesirable. On a network that has unstable links, this can lead to frequent reconvergences, and this affects users and network services directly. Some implementations, therefore, implement interface or path-dampening techniques, so that unstable links are taken offline and monitored (using some form of hysteresis or hold-down timer) until they are classed as stable.

Link-state protocols tend to support network hierarchy.

DUAL algorithm

Cisco's EIGRP routing protocol implements a hybrid distance-vector algorithm with a Diffusing Update Algorithm (DUAL), which exhibits some of the attractive properties of link-state protocols (such as very fast convergence and lower bandwidth consumption in a steady-state network). EIGRP uses a hello mechanism to determine neighbor reachability and sends updates only when topology changes occur. In failure conditions EIGRP looks for feasible successors by sending messages to its neighbors. To achieve rapid convergence, however, a significant amount of traffic can be generated during the search for feasible successors (i.e., updates, queries, and responses). This behavior constrains the number of neighbors that are possible and, therefore, affects scalability. For further information, the interested reader is referred to reference [4].

In multiprotocol environments (such as enterprise networks) it may be necessary either to run multiple protocols on the router simultaneously (so-called ships in the night mode) or use a routing protocol such as Cisco's EIGRP, which is capable of supporting several protocol types concurrently. Fortunately the networking industry is now focusing all efforts on the common IP protocol, and this is the protocol of choice for backbone networks. This means that several of these legacy protocols are already starting to die out. In this book we will focus primarily on the routing protocols that support IP traffic. For reference, the stack also includes the multicast routing protocols IGMP, MOSPF, PIM, and DVMRP, which are discussed in detail in Chapter 4.

Table 3.1 lists the classification of routing protocols. These protocols broadly fall into those using distance-vector (DV) algorithms, or link-state (SPF) algorithms. Cisco's EIGRP uses a hybrid algorithm based on distance-vector. ES-IS is the OSI standard for gateway discovery and offers similar functionality to ARP plus ICMP redirect. GGP is an old protocol design by the BBN for use on LS/11 gateways (it has some serious drawbacks). The hello protocol was also developed for LS/11 gateways and attempted to use available bandwidth by monitoring round-trip delay but was not especially successful.

Table 3.1: Classification of Routing Protocols
Routing Protocol	Description	Type	Rout Alg	Open Std	Encap	Metric	Mcast Distrib	Update Timer	VLSM
BGP	Border Gateway Protocol	EGP	PV	yes	ip		no	trig
EGP	Exterior gateway Protocol	EGP	na	yes	ip		no
EIGRP	Enhanced Integrated Gateway Routing Protocol	IGP	DV+	no	ip	chd	Y	trig	yes
GGP	Gateway to Gateway Protocol	IGP	DV	yes	ip		no
Hello	Hello Protocol	IGP	DV	yes	ip	d	no
IGRP	Interior Gateway Routing Protocol	IGP	DV	no	ip	chd	no	90sec	no
Int IS-IS	OSI Integrated IS-IS	IGP	SPF	yes	ip, osi	c	no	trig	yes
Novell NLSP	Netware Link State Protocol	IGP	SPF	no	ipx,ip		no	trig
Novell RIP	Novell's implementation of RIP	IGP	DV	yes	ipx		no
OSI ES-IS	OSI End System to Intermediate System	IGP	na	yes	osi		yes
OSI IS-IS	OSI Intermediate System to Intermediate System	IGP	SPF	yes	osi	c	no	trig	yes
OSPF	Open Shortest Path First	IGP	SPF	yes	ip	c	yes	trig	yes
RIPv1	Routing Information Protocol Version 1	IGP	DV	yes	ip	h	no	30sec	no
RIPv2	Routing Information Protocol Version 2	IGP	DV	yes	ip	h	no	30sec	yes
RTMP	Apple RouterTable Maintenance Protocol	IGP	DV	no	atalk		no	10sec

Fundamental to the routing table is the concept of the best path. The table of best paths is computed using a distributed routing algorithm. Paths may be weighted according to a simple hop count or a more sophisticated metric (such as the real tariff or a function influenced by congestion, throughput, etc.). Hop-based paths are closely associated with a class of algorithms called distance-vector. Cost-based paths are generally associated with link-state algorithms. Exterior Gateway protocols such as BGP use a class of algorithm called path vector.