Oct 2, 2008

Distance vector versus link-state

Posted by stretch in Networking on Thursday, 2 Oct 2008 at 3:36 a.m. GMT

There are two major classes of routing protocol: distance vector and link-state. It's easy to remember which protocols belong to either class, but comprehending their differences between the two classes takes a bit more effort.

Distance vector routing is so named because it involves two factors: the distance, or metric, of a destination, and thevector, or direction to take to get there. Routing information is only exchanged between directly connected neighbors. This means a router knows from which neighbor a route was learned, but it does not know where that neighbor learned the route; a router can't see beyond its own neighbors. This aspect of distance vector routing is sometimes referred to as "routing by rumor." Measures like split horizon and poison reverse are employed to avoid routing loops.

Link-state routing, in contrast, requires that all routers know about the paths reachable by all other routers in the network. Link-state information is flooded throughout the link-state domain (an area in OSPF or IS-IS) to ensure all routers posess a synchronized copy of the area's link-state database. From this common database, each router constructs its own relative shortest-path tree, with itself as the root, for all known routes.

Consider the following topology.

Lab topology

Both distance vector and link-state routing protocols are suitable for deployment on this network, but each will go about propagating routes in a different manner.

Distance Vector

If we were to run a distance vector routing protocol like RIP or EIGRP on this topology, here's how R1 would see the network, assuming each link has a metric of 1 (locally connected routes have been omitted):

R1's view running distance vector

Notice that although R1 has connectivity to all subnets, it has no knowledge of the network's structure beyond its own links. R4 has even less insight:

R4's view running distance vector

Because they do not require routers to maintain the state of all links in the network, distance vector protocols typically consume less overhead at the expense of limited visibility. Because routers have only a limited view of the network, tools like split horizon and poision reverse are needed to prevent routing loops.

Link-State

Now, let's look at the same topology running a link-state routing protocol (in a single area). Because each router records the state of all links in the area, each router can construct a shortest-path tree from itself to all known destinations. Here's what R1's tree would look like:

R1's view running link-state

R4 has constructed its own shortest-path tree, different from that of R1:

R4's view running link-state

Although maintaining link-state information for the entire area typically requires more overhead than does processing advertisements only from direct neighbors, but provide more robust operation and scalability.

Post a Comment