Link State Versus Distance Vector Routing Protocols

This section describes the two most common and relevant routing protocols that TCP/IP has available for use, namely RIP and OSPF. Controversy surrounds the debate over link-state versus distance vector routing algorithms regarding which is better.

NOTE Link-State and distance vector routing protocols are also known as interior gateway protocols (IGPs); this concept is discussed later in the discussion of OSPF and border gateway protocol (BGP) interoperability. Chapter 7, "Summarization," discusses OSPF/ BGP interoperability in greater detail.

An IGP is a classification that describes the use of a dynamic routing protocol to exchange routing information within an autonomous system (AS). Examples of common IGPs include IGRP, OSPF, Intermediate System-to-Intermediate System (IS-IS), and RIP. You can contrast an IGP with an exterior gateway protocol (EGP) such as BGP.

52 Chapter 2: Introduction to OSPF

Link-State Routing Protocols

Link-state algorithms (also known as shortest path first algorithms) flood only incremental changes that have occurred since the last routing table update. During this incremental update, each router sends only that portion of the routing table that describes the state of its own links, as opposed to its entire routing table.

Link-state routing protocols require routers to periodically send routing updates to their neighboring routers in the internetwork. In addition, link-state routing protocols are quick to converge their routing updates across the network in comparison to distance vector protocols.

The speed at which they converge makes link-state protocols less prone to routing loops than distance vector protocols. However, link-state protocols also require more CPU power and system memory. One of the primary reasons that additional CPU power and memory are needed is that link-state protocols are based on the distributed map concept, which means that every router has a copy of the network map that is regularly updated. In addition to the size of the routing table, the number of routers in an area and the number of adjacencies amongst routers also has an affect on router memory and CPU usage in linkstate protocols. These factors were obvious in the old fully meshed asynchronous transfer mode (ATM) networks, where some routers had 50 or more OSPF adjacent peers and performed poorly.

Link-state protocols are based on link-state algorithms, which are also called shortest path first (SPF) algorithms or Dijkstra algorithms. "SPF in Operation," later in this chapter, covers the SPF algorithm in more detail.

A simple way to understand how link-state technology operates is to picture the network as a large jigsaw puzzle; the number of pieces in your puzzle depends on the size of your network. Each piece of the puzzle holds only one router or one LAN. Each router "draws" itself on that jigsaw piece, including arrows to other routers and LANs. Those pieces are then replicated and sent throughout the network from router to router (via link-state advertisements [LSAs]), until each router has a complete and accurate copy of each piece of the puzzle. Each router then assembles these pieces by using the SPF algorithm.

NOTE The principle of link-state routing is that all the routers within an area maintain an identical copy of the network topology. From this map, each router performs a series of calculations that determine the best routes. This network topology is contained within a link-state database, where each record represents the links to a particular node in the network.

Each record contains the following pieces of information:

• Interface identifier

• Metric information regarding the state of the link

Armed with that information, each router can quickly compute the shortest path from itself to all other routers.

The SPF algorithm determines how the various pieces of the puzzle fit together. Figure 2-3 illustrates all of these pieces put together in operation.

Figure 2-3 Link-State Operation

LSAs are the foundation of the link-state database.

Figure 2-3 Link-State Operation

LSAs are the foundation of the link-state database.

Link-State Database (LSDB)

SPF Algorithm

SPF Algorithm

Shortest Path First Tree Each router builds one with itself as the root.

Link-state protocols such as OSPF flood all the routing information when they first become active in link-state packets. After the network converges, they send only small updates via link-state packets.

OSPF Characteristics

OSPF is a link-state protocol in which all routers in the routing domain exchange information and thus know about the complete topology of the network. Because each router knows the complete topology of the network, the use of the SPF algorithm creates an extremely fast convergence. Other key characteristics of OSPF are as follows:

• Provides routing information to the IP section of the TCP/IP protocol suite, the most commonly used alternative to RIP.

• Sends updates to tables only, instead of entire tables, to routers.

• Is a more economical routing protocol than RIP over time because it involves less network traffic.

• Is a more economical routing protocol than RIP over time because it involves less network traffic.

54 Chapter 2: Introduction to OSPF

The "It Depends Rule"

I occasionally invoke a rule I invented that I call the "It Depends Rule," and I am invoking it now! OSPF is usually more efficient than RIP in exchanging routing information when a network is stable; however, for this rule to hold true, it depends on network events. For example, during an external convergence event, OSPF could flood more traffic than RIP. Consider that RIP carries 25 routes per update; on the other hand, OSPF floods a single LSA per external route that is affected by the convergence event. So, provided that you have a (relatively) stable environment, OSPF involves less traffic, and over time, it is statistically more economical than RIP. Using a single LSA per external route is inefficient, but OSPF was never designed to be an EGP. Therefore, I recommend an OSPF/BGP deployment when large numbers of external routers are present.

Another popular type of dynamic routing protocol that is based on the Dijkstra SPF algorithm is IS-IS. The use of IS-IS versus OSPF has been hotly debated.

Integrated Intermediate System-to-Intermediate System

IS-IS is an OSI link-state hierarchical routing protocol that is based on work originally done at Digital Equipment Corporation for DECnet/OSI (DECnet Phase V). This protocol floods the network with link-state information to build a complete, consistent picture of network topology.

The International Organization for Standardization (ISO) has developed the following routing protocols for use in the Open System Interconnection (OSI) protocol suite:

• Intermediate System-to-Intermediate System (IS-IS) protocol

• End System-to-Intermediate System (ES-IS) protocol

• Interdomain routing protocol (IDRP)

For more information on IDRP or ES-IS, start with the RFCs, which can be found at www.ietf.org.

The American National Standards Institute (ANSI) X3S3.3 (network and transport layers) committee was the motivating force behind ISO standardization of IS-IS, which was originally developed to route in ISO connectionless network protocol (CLNP) networks. A version has since been created that supports both CLNP and IP networks. It is usually referred to as integrated IS-IS; this is the version discussed here.

OSI routing protocols are summarized in several ISO documents; those dealing with IS-IS are as follows:

• ISO 10589: Standards definition for IS-IS

• RFC 1195: Intermediate IS-IS

Distance Vector Routing Protocols

Distance vector means that information sent from router to router is based on an entry in a routing table that consists of the distance and vector to destination—distance being what it "costs" to get there and vector being the "direction" to get to the destination.

Distance vector protocols are often referred to as Bellman-Ford protocols because they are based on a computation algorithm described by R. E. Bellman; the first description of the distributed algorithm is attributed to Ford and Fulkerson. Distance vector algorithms (also known as Bellman-Ford algorithms) call for each router to send its entire routing table, but only to its neighbors. The neighbor then forwards its entire routing table to its neighbors, and so on. Figure 2-4 illustrates this routing table forwarding process.

Figure 2-4 Distance Vector Operation

Figure 2-4 Distance Vector Operation

Every router must be told of the change when a network goes down.

Every router must be told of the change when a network goes down.

As Figure 2-4 illustrates, whenever a change to the network occurs, this causes the entire routing table to be sent from neighbor to neighbor in order for the network to reconverge in response to the network event (network down). What is not shown is the periodic sending of the routing table between neighbors—a mechanism that double-checks that the routing information each router has is valid.

56 Chapter 2: Introduction to OSPF

Routing Information Protocol Characteristics

RIP v1 is a distance vector protocol designed at Berkeley in the late 1960s that is still widely deployed today. In this protocol, the router only exchanges routing information from the connected neighbors. Key characteristics of RIP are as follows:

• RIP broadcasts every 30 seconds to maintain network integrity.

• RIP maintains routing tables, showing the number of hops between routers, and is limited to a 15-hop count.

• A router using RIP passes its entire routing table to each directly connected neighbor router that it knows of.

A detailed discussion about RIP is not very relevant in a book dedicated to OSPF, but if you want to learn more on RIP v1 and v2, consider the following resources:

• Routing TCP/IP, Volume I, by Jeff Doyle. Chapter 5 is dedicated to RIP.

• Routing information protocol (RIP) at cisco.com:

www.cisco.com/univercd/cc/td/doc/cisintwk/ito_doc/rip.htm

• RFC 2453 RIP Version 2, published in 1998

Conclusion

Link-state algorithms send small updates everywhere; distance vector algorithms send large updates only to neighboring routers. Because they create a consistent view of the internetwork, link-state algorithms are somewhat less prone to routing loops than are distance vector algorithms. When a network is in stable or steady state, link-state protocols allow for smooth routing.

On the downside, link-state algorithms can cause significant, widespread control traffic, for example, when a network event occurs and the event must be flooded throughout the network. The main concern in today's networks is the amount of flooding that can happen as networks grow ever larger.

Link-state algorithms are also computationally difficult compared to distance vector algorithms, requiring more CPU power and memory than distance vector algorithms. However, this has become less of an issue as router-processing capabilities have improved.

Link-state algorithms can therefore be more expensive to implement and support. Despite their differences, both algorithm types perform well in circumstances and networks that suit their strengths and recognize their limitations.

+1 0

Post a comment