Dynamic Routing Protocols: Distance Vector and Link State Protocols
If you’re working towards your CCNP, CCIP, or CCDP certifications then the BSCI – Building Scalable Cisco Internetworks exam (642-901) applies to all three of these certifications. The BSCI exam is all about advanced IP addressing and routing and it tests your knowledge and skills on implementing scalability for Cisco Integrated Services Routers (ISR) connected to LANs and WANs.
Some of the topics that the BSCI exam covers include:
- Advanced IP addressing
- Routing principles
- Multicast routing
- 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.
Link State Routing Protocols
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.
Distance Vector Routing Protocols – Operation
To illustrate the routing updating process for Distance Vector routing protocols I will use the following subnet diagram:
Let’s say that all routers 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.
Let’s take a look at how Router H builds up its routing table after receiving Hop Distance Vectors from its neighbors (Routers A, B, F, G and I). For each neighbor router, a separate vector table is shown:
Upon receiving the routing updates from all neighbors, RouterH performs its calculation for estimating the best route to any given destination. The result of this process is the following:
To give you an idea of how this calculation process is performed consider the following:
RouterA and RouterG informed RouterH that RouterD is 1 hop away. 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.
Link State Routing Protocols – Operation
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:
- Discover its neighbors and build its neighbor table
- Measure the cost (delay, bandwidth, etc) to each of its neighbors
- 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.
Step 1: Neighbor Discovery
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.
Step 2: Measuring Link Cost
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.
Step3: Building and Distributing Link State Packets
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.
Based on the same subnet diagram presented above the equivalent link state packets for each of the routers are presented below. Random link cost values have been assumed. Also for simplicity, sequence and age values are omitted.
Step 4: Evaluating Shortest Paths
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.
For example, the best path for RouterA to reach RouterI would be the following:
Things to Keep in Mind about Dynamic Routing Protocols
- 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 details of which you can find here.
- Link state routing protocols are widely used in large networks due to their fast convergence and high reliability.