Distance Vector Versus Link State

This section highlights the similarities and differences between two types of widely used routing protocols: distance vector and link state.

Distance Vector Overview

A distance vector routing protocol sends all or part of its route table across the network, but only to its neighbors. The route table contains the distance and direction to any network within its domain. Figure 7.3 provides an overview of the distance vector process.

Figure 7.3. Illustration of the distance vector process.

Periodically, router A broadcasts its entire route table to its neighbors, router B and router C. Router B updates the route information it received by increasing the metric value, which is usually the hop count, by 1. Router B then compares the route information it just received and updated with the existing route information from its route table. Router B replaces existing route information with an updated entry only if the updated route information has a lower calculated metric. Router B then broadcasts its route table to its direct neighbors, router D and router A. This process occurs regularly and in all directions for all directly connected neighbors. Although this process enables routers to accumulate network distance information, the routers do not know the network's exact topology.

Link State Overview

A link state routing protocol (sometimes referred to as shortest path first ) sends only the state of its own network links across the network, but it sends this information to every router within its domain. This process enables routers to learn and maintain full knowledge of the network's exact topology and how it is interconnected . Figure 7.4 provides an overview of the link state process.

Figure 7.4. Illustration of the link state process.

Link state routing protocols rely on several components to acquire and maintain knowledge of the network. The following process is typical of routers using a link state protocol:

• A router broadcasts and receives link state packets to and from other routers via the network. Link state packets contain the status of a router's links or network interfaces.

• The router then builds a topology database of the network.

• After building a topology database the router runs a Shortest Path First (SPF) algorithm against the database to generate an SPF tree of the network, with itself as the root of the tree.

• Lastly, the router populates its route table with optimal paths and ports to transmit data through to reach each network.

Network Discovery

When a router starts up, it must undergo a network discovery process, which enables the router to begin communicating with other routers on the network. Figure 7.5 illustrates the network discovery process for distance vector protocols. Router A has just started up and is configured to run a distance vector.

Figure 7.5. Illustration of the network discovery process.

Router A begins the discovery process by identifying its neighbor, router B. Router A begins populating its route table with its directly connected networks, networks 1 and 2, which receive a metric of 0. It passes its route table to router B and receives router B's entire route table. Router A increases the distances of each entry by one hop. After the distances have been updated, router A will already have better routes to networks 1 and 2, but not network 3. Router A increases the distance to network 3 by one hop and stores this in its route table.

The network discovery process for link state protocols is similar to that of distance vector protocols. Instead of route tables, routers exchange link state packets and use that information to build their topology databases, SPF trees, and route tables.

Regardless of whether a router uses a distance vector or link state routing protocol, the router dynamically discovers its network environment. It can then use its route table to perform the packet-switching function.

Topology Changes

After the router has discovered the network, it must also keep up with network topology changes. Depending on the protocol used, a router transmits route information periodically or when a network event occurs. Routers detect changes in the network topology via these updates.

Most distance vector protocols handle topology changes through regularly scheduled updates. After a specified interval, a router broadcasts its route table to its neighbor. Route recalculation occurs, if necessary, and updates in the network topology are broadcast. The route distribution timers are not synchronized across routers.

Link state protocols rely on network events to address topology changes. If a router detects a network event (such as one of its neighbors is no longer reachable or a new neighbor appears), it triggers an update. The router broadcasts the state of its links to all other routers within the domain. Upon receiving the update, other routers update their topology database and broadcast the state of their links also. When all updates have been received, each router updates its SPF tree and route tables accordingly . At this point, the network has converged . Event-triggered updates have a ripple effect within a network.

Distance Vector Problems

The fact that route updates with a distance vector protocol occur after a specified interval can become problematic . With RIP, route updates are broadcast every 30 seconds by default. As a result, distance vector protocols converge slowly. Routing loops and the problems they create were discussed previously in this chapter. Routing loops create a condition known as counting to infinity , where the distance metric is continually increased because the network has not fully converged.

Distance Vector Remedies

One technique to remedy a count-to-infinity situation involves a maximum hop count. Although this count will not prevent a routing loop, it does reduce the time that the routing loop exists. A maximum hop count, when reached, forces a router to mark a network unreachable rather than increase the distance metric.

Routing loops also occur when information that contradicts information sent previously is broadcast back to a router. Router A sends information about network 5 to router B. Split horizon prevents a router from sending information it received about a network back to the neighbor that originally sent the information. For example, split horizon prohibits router B and router C from sending any information about network 5 back to router A.

Route poisoning occurs when a router detects that a network is down and immediately marks it as unreachable. This route update is broadcast throughout the network. While the other routers slowly converge, the router maintains this poisoned route in its route table and ignores updates from other routers about better routes to the network. The poisoned route is removed after several update cycles. Route poisoning works well with hold-down timers.

A hold-down timer indicates that no updates to a particular route should be accepted until the timer expires. A hold-down condition is triggered when a router receives an update from its neighbor indicating that a reachable network has just gone down. The router marks the network as unreachable and starts its hold-down timer. While the timer is active, updates from any other router are ignored. Updates about the unreachable network are accepted only from the neighboring router that initially indicated the unreachable network while the timer is active. If the neighboring router indicates that the network is reachable again, the router stops the hold-down timer and updates its route table. When the hold-down timer expires , the router marks the network reachable and receives updates from any router.

Link State Problems

Because link state routing protocols have knowledge of the entire network and converge quickly, they do not suffer from the same problems as distance vector protocols. One problem that affects link state protocols is the significant memory and processor resources required from the router itself when acquiring and maintaining full knowledge of large networks. As updates move through the network, each router must receive the update, recalculate its information, and send its own link information. Of course, this type of overhead affects the ability of the router to move user data packets through the network.

A second shortcoming of link state protocols is the amount of network bandwidth that can be consumed while the network converges. Routers flood updates about the state of their links to every other router in the network, so the amount of bandwidth consumed is significant. As routers collect link information from each other, the amount of bandwidth available for end-user communications is reduced. This high level of bandwidth utilization typically occurs on initialization of the network or when several routers start up simultaneously .

Additional problems can occur during the link state update process itself. It is imperative that each router receive all the packets in a timely manner and that the updates are synchronized. For example, if one part of the network receives route information before another part, convergence may take longer, or SPF trees and route tables may store inaccurate information. Additionally, as routers attempt to move link state packets through the network, they may be doing so without fully constructed SPF trees or route tables.

Link State Remedies

One remedy for link state problems involves minimizing the resources required to build and maintain route tables. The time between periodic updates can be lengthened to reduce the processing resources required. Also, routers can be identified to serve as border routers. The border routers can then exchange route summaries with other border routers and each core router to reduce the bandwidth consumed during the update process, and to isolate update processes to hierarchical areas. The border router then passes updates to the routers within its area.

Another technique involves coordinating link state updates. Timestamps and sequence numbers can be attached to the link state packet. Routers then realize when they receive inaccurate or old link state packets.

The following techniques help to stabilize link state protocols:

• Minimize router resource usage by lengthening the update frequency or exchanging route summaries.

• Coordinate updates with timestamps or sequence numbers.

Both distance vector and link state routing protocols have demonstrated their worth over time. Each has advantages that may suit a particular network design perfectly . Several factors must be considered when choosing a routing protocol, including business policies and operational issues. Table 7.2 provides a quick comparison of distance vector and link state routing protocols.

Table 7.2. Distance Vector Versus Link State Routing Protocols

Distance Vector	Link State
Sees the network from its neighbor's perspective	Sees the entire network from its own perspective
Distance metrics accumulate from router to router	Calculates shortest path to other routers
Route updates occur periodically	Route updates are event-triggered
Convergence is slow	Convergence is fast
Broadcasts entire route table to neighbors	Broadcasts link status information to all other routers