Distance vector versus link-state

By stretch | Thursday, October 2, 2008 at 3:36 a.m. UTC

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 the 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 the vector, 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 posses 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.png

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_DV.png

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_DV.png

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.

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_LS.png

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

R4_LS.png

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.

About the Author

Jeremy Stretch is a network engineer living in the Raleigh-Durham, North Carolina area. He is known for his blog and cheat sheets here at Packet Life. You can reach him by email or follow him on Twitter.

Posted in Routing

Comments


Dude (guest)
October 2, 2008 at 9:02 a.m. UTC

I remember when we had to count out excersises using Dijkstra-algorithm at college years ago. On a piece of paper..another useless thing I tought, and just realized OSPF uses the same math to build the shortest-path tree.


Tarun (guest)
October 2, 2008 at 11:30 a.m. UTC

As usual neat & clear write-up. +1 to your fan's list :-)


Kevin (guest)
October 2, 2008 at 2:27 p.m. UTC

It's funny how even some link-state protocols still act like link-state in certain scenarios.


Venkatesan (guest)
October 2, 2008 at 6:53 p.m. UTC

Nice information. Thanks. I like to add one more point. If a network is huge its better to use link state than distance vector,because there are more limitations in distance vector like Hop count limit etc


Michael (guest)
October 2, 2008 at 10:44 p.m. UTC

A 'vector' has both direction and distance already. So then why did they call it 'distance vector'? Those crazy network guys..


usaf (guest)
October 18, 2008 at 10:16 a.m. UTC

I like the blog theme :p


Joao (guest)
January 27, 2009 at 7:43 p.m. UTC

Thank you!
This helped a lot, better than my teachers pdf´s, and all he had to do was translate the cisco notes.

anyways... as said above, very clear & neat


mayank (guest)
April 11, 2009 at 2:25 p.m. UTC

it is a boon for the learner........thanks a lot


tomtom (guest)
April 21, 2009 at 2:10 p.m. UTC

never came across a definitive explanation untill now! More grease to your elbow... Thanks!


wirefree (guest)
May 3, 2009 at 3:56 a.m. UTC

QUOTE " Venkatesan commented on 2 Oct 2008 at 6:53 p.m.

Nice information. Thanks. I like to add one more point. If a network is huge its better to use link state than distance vector,because there are more limitations in distance vector like Hop count limit etc"

The intuition seems appropriate at first glance but further investigation reveals that large networks are best supported using DV-centric approach instead of LS. Imagine a large network with 1000's of routers having to keep track of all the others.

Hence, it is clear why the networks of network - the Internet - adopts a path-vector approach in its usage of BGP.


Arunkumar RG (guest)
June 19, 2009 at 10:06 a.m. UTC

I searched through google to understand the difference between link state and distance vector and out of all the sites I have reffered, this blog was the one which cleary helped me to understand the difference!! Thanks for providing the clarity!!

Cheers,
Arun


tichworld (guest)
July 8, 2009 at 2:00 p.m. UTC

Clear and absorbed thanks for the day.


Simon (guest)
January 26, 2010 at 1:06 p.m. UTC

Good Explanation dude, brief and easy to understand!! Nice one!!


Kesav (guest)
May 2, 2010 at 1:40 a.m. UTC

Good Information,

After seeing this difference. I think that its better to use Distance vector Routing for large networks. Because If a router uses Distance vector algo.. the router will come to know only the details of neighbouring router. But If a router uses Link state Routing then each router will find is own shortest path. I Think this not good for larger networks like (1000 routers).

This is my assumption. Any other guys you can clarify on this and please let me know, am I right?


Colby
July 2, 2010 at 7:24 p.m. UTC

@those of you speaking of DV vs LS for large networks, don't forget about AREAS. In OSPF the link states are only known within an area, outside of that OSPF acts like a DV protocol. Therefore, LS protocols are fine for large networks if designed properly.


mayjune
August 16, 2010 at 3:12 p.m. UTC

Very nice, Very informative....


Husain (guest)
September 8, 2010 at 1:46 a.m. UTC

The information provided is really superb !

Thank you


saiph (guest)
December 5, 2010 at 10:11 p.m. UTC

nice post! thanks!


lordhusnain (guest)
December 27, 2010 at 3:37 p.m. UTC

Its simple and easy to understand. It really help me a lot.


Kannan.G (guest)
May 14, 2011 at 3:36 p.m. UTC

Its help me to understand the real difference,Thankyou!


Sakayaraj2000 (guest)
August 9, 2011 at 7:57 p.m. UTC

Very nice explanation.

Raj


AnuJ (guest)
November 25, 2011 at 6:33 p.m. UTC

Very nice sharing & explanation....
I alwayz prefer internet 4 reading & understandin' rather than books :))
Thumbs Up


Imran (guest)
May 20, 2012 at 3:35 p.m. UTC

Very straight forward explanation....nice way to learn...rather than books..


Dipesh Upadhyaya (guest)
May 30, 2012 at 5:00 a.m. UTC

nice article...clear and simple ...thanks....even i enjoyed the comments as well ...very logical people they are ..specially one who said vector already have distance and direction...for him i need to say..vector has magnitude and direction not magnitude always must not be distance....i think so.....for that reason protocol is named distance vector routing protocol...


ArcanjoV8
September 5, 2012 at 1:45 p.m. UTC

Great article! Thank you!


axe (guest)
November 19, 2012 at 8:59 a.m. UTC

vector refers to the array-like data structure, doesnt mean vector literally...


satya (guest)
December 1, 2012 at 3:56 p.m. UTC

Best Notes on Distance & Link State Protocol,Very Clearly Understood


Jay (guest)
January 7, 2013 at 7:20 a.m. UTC

Thank you, Jeremy! You made it real simple for me.. :D


ppel (guest)
February 22, 2013 at 8:47 p.m. UTC

Very well explained. Thanks man!


Hollandprojects (guest)
November 8, 2013 at 4:11 p.m. UTC

Interesting!
Distance Vector creates the fastest path.
Link State creates the shortest path.

"R4 has constructed its own shortest-path tree, different from that of R1:"
The shortest path doesn't necessarily mean the fastest path.
It could be quicker to go (R4->R3->R2->R1), but we don't know that because there are no costs associated with link state.

I am going to come up with a Link State Distance Vector Protocol (LSDVP). (You heard it here first) Why not provide the best of both protocols? To optimize the route, it might not take the shortest path. All you would have to do is provide a distance vector along (Router path cost) with the link state protocol. Done.

CJH


Conrad (guest)
April 2, 2014 at 12:32 p.m. UTC

I think vector actually refers to the arrays or table that DUAL uses when calculating possible paths to a destination.

Source: DUAL algorithm white paper


A guest
April 27, 2014 at 8:47 a.m. UTC

Great! Thank you!


Yvette Walker (guest)
May 9, 2014 at 9:58 p.m. UTC

Awesome explanation. Really good for people just learning this stuff. I wonder if the military would use Distance Vector....seems like too many router for Link State, but I am just learning so I can be wrong.


shahed (guest)
October 18, 2014 at 7:18 a.m. UTC

Thank you Jeremy, very easy and nice explanation. Much better than cisco books.


Guest (guest)
March 16, 2015 at 1:31 a.m. UTC

Thank you for very short and clear explanation


DTNP (guest)
April 28, 2015 at 4:05 p.m. UTC

Great!!!!!!


Varsh (guest)
July 22, 2015 at 6:37 p.m. UTC

Thanks for the explanation!!!


Dwight (guest)
August 11, 2015 at 7:56 p.m. UTC

Scary how easy to understand this explanation was for me. Definitely helped me study for my CCENT exam.


Akshay (guest)
September 5, 2015 at 6:45 p.m. UTC

thank you, wonderful explanation


A guest
May 18, 2016 at 1:35 p.m. UTC

very good i understand it now


A guest
August 18, 2016 at 8:49 a.m. UTC

Big interview.. brain going in t melt down.. cant remember simple concepts from years back.. thanks for making this short and clear.


Philip Prindeville (guest)
August 18, 2016 at 8:02 p.m. UTC

Minor nit: I believe it's called "distance vector" because the magnitude may be measured in several dimensions, not just a scalar hop-count which RIP uses.

In EIGRP for example, link delay, minimum path bandwidth, reliability, utilization, path MTU, etc. are all reported to compute a complex vector measurement.

Comments have closed for this article due to its age.