Dynamic Routing Protocols: Distance Vector and Link State

If you're working towards your CCNP, CCIP, or CCDP certifications then you'll need to know about advanced IP addressing and routing. The certifications test your knowledge and skills on implementing scalability for Cisco Integrated Services Routers (ISR) connected to LANs and WANs.

To be successful on these exams, you'll want to understand

•  Advanced IP addressing
•  Routing principles
•  Multicast routing 
•  IPv6 
•  Manipulating routing updates
•  Configuring basic BGP
•  Configuring EIGRP, OSPF, and IS-IS

We have covered some of the above mentioned topics, but today we'll concentrate on Dynamic Routing Protocols. More specifically, I'll introduce you to the two major classes of Dynamic Routing Protocols: Distance Vector and Link State routing protocols.

Before we get started, if you need to refresh your memory on static and default routing concepts, then take a look at my article on Default and Static Routing Basics.

Now let's begin with a description of the operational principles of the two routing classes and afterwards, I'll get into the details on their actual operation and design.

There are different routing classes available for providing a more spherical solution packet. Different networks have special individual needs and different routing protocols have been designed to meet the individual needs of these networks.

There is no straightforward answer on the right routing protocol to use. A variety of parameters need to be investigated before deciding on that. Your investigations should include bandwidth prerequisite, reliability, convergence speed, network architecture and much more.

I won't concentrate on the details of the best routing decision process, but I will try to illustrate the details behind the operation of the different routing classes so that you can make the appropriate decisions yourself.

Distance Vector routing protocols base their decisions on the best path to a given destination based on the distance. Distance is usually measured in hops, though the distance metric could be delay, packets lost, or something similar.

If the distance metric is hop, then each time a packet goes through a router, a hop is considered to have traversed. The route with the least number of hops to a given network is concluded to be the best route towards that network.

The vector shows the direction to that specific network. Distance vector protocols send their entire routing table to directly connected neighbors. Examples of distance vector protocols include RIP - Routing Information Protocol and IGRP - Interior Gateway Routing Protocol.

If you're interested in finding out more information on RIP, check out my articles on how to configure Routing Information Protocol RIPv1 and RIPv2.

Link state protocols are also called shortest-path-first protocols. Link state routing protocols have a complete picture of the network topology. Hence they know more about the whole network than any distance vector protocol.

Three separate tables are created on each link state routing enabled router. One table is used to hold details about directly connected neighbors, one is used to hold the topology of the entire internetwork and the last one is used to hold the actual routing table.

Link state protocols send information about directly connected links to all the routers in the network. Examples of Link state routing protocols include OSPF - Open Shortest Path First and IS-IS - Intermediate System to Intermediate System.

There are also routing protocols that are considered to be hybrid in the sense that they use aspects of both distance vector and link state protocols. EIGRP - Enhanced Interior Gateway Routing Protocol is one of those hybrid routing protocols.

To illustrate the routing updating process for Distance Vector routing protocols, let's say that we have routers that have been set in service at the same time and all run a distance vector routine protocol. Each router sends its distance vector to its neighbor. Also, each router receives distance vectors from each neighbor as well. Combining the information learned from neighbors with each router's own information, the best estimate route to a given destination is inserted into the routing table.

Upon receiving the routing updates from all neighbors, the final router, which we’ll call RouterH, performs its calculation for estimating the best route to any given destination. 

The result of this process is that the first to the penultimate routers, RouterA and RouterG, informed RouterH how far away RouterD is. RouterH knows that both routers (A and G) are neighbor routers; hence it adds 1 to the hop metric and concludes that it can reach RouterD via both RouterA and RouterG with an overall distance of 2 hops.

As already mentioned, Link State routing protocols hold 3 distinctive tables: a neighbor table, a topology table, and an actual routing table. Link state routing operation follows four simple steps; each link state enabled router must perform the following:

1.  Discover its neighbors and build its neighbor table

2.  Measure the cost (delay, bandwidth, etc) to each of its neighbors

3.  Construct and send a routing update telling all it has learned to all routers in the network

 Apply the Dijkstra algorithm to construct the shortest path to all possible destinations

Below you'll find more details on the four step process.

Each Link State enabled router periodically sends a HELLO message on each of its links. Neighbor routers respond to these HELLO messages identifying themselves. Within the replies, network addresses of the routers are attached and are used by the HELLO initiator to build up its neighbor table.

A set of tests is performed on each router to measure the cost to each of its neighbors. The cost could be a measure of the end-to-end delay, throughput, or a combination of these metrics. How these tests are performed is out of the scope of this article. The important thing to know is that each link state enabled router has to somehow possess an estimate of the cost for each of its links.

Each router builds up a packet containing its neighbors and the corresponding link costs to these neighbors. At the beginning of the packet, each router adds its identity along with a sequence number and an age parameter, the latter being used to ensure no packet will wander around for an indefinite period of time. After the construction process, the packet is flooded in the network.

Using all the details from its link state table, a router is able to compute, using the Dijkstra algorithm, the shortest path to any given destination.

•  Distance vector protocols send their entire routing table to directly connected neighbors.
•  Link state protocols send information about directly connected links to all the routers in the network.
•  Distance vector protocols have slow convergence and suffer from the count-to-infinity problem.
•  Link state routing protocols are widely used in large networks due to their fast convergence and high reliability.