An Overview Of Distance Vector & Link State Routing Protocol

A Routing Protocol is a method of negotiation between two routers to select a route between two nodes based on different conditions. Different categories of the routing protocols exist today. Most of the routing protocols that exist can be assigned to any of these categories mentioned below based on their properties.

• Interior Gateway Protocol (IGP)
• Exterior Gateway Protocol (EGP)

Interior Gateway Protocol (IGP)

As its name suggests, Interior Gateway Protocol, also known as IGP, is used to exchange information among the routers/ gateways within an autonomous system. An autonomous system is a designated network area which is managed by a single network administrator and can have different routing devices.

There are mainly two broad types of interior gateway protocol:

• Distance Vector Routing Protocol
• Link State Routing Protocol

Distance Vector Routing Protocol

As its name suggests, the distance vector routing protocol utilizes two of its features in the routing process.

• Direction
• Distance

How does distance vector routing protocol work?

Based on the bellman-ford algorithm, this routing protocol builds up a table at the router which contains a table of distance to different routers from a particular router. The table also contains the distance vector to all the routers in the networks via all the other router.

For example, if there are three routers in the network, then the table for one of the routers, let’s say router 1, will look something like this:

The above lists out the distance from the router 1 to router 2 and 3. As you can see the shortest path to all of the routers from router 1 (except itself) is via router 2.

Question: Can you find the distance between router 2 and router 3?

Route Calculation

In the beginning, when all the routers are booted up, they discover their immediate neighbors which are directly connected to them. They make a table out of it and broadcast their distances to other directly connected routers on the network.

Upon receiving a broadcast, the router compares their tables and update for any shortest path. Here is a very nice visual example of this protocol on Wikipedia.

Countdown to infinity problem

One of the major loopholes of the distance vector routing protocol is that it suffers from the countdown to infinity problem.

Scenario

Let us say there are four routers in a network Router A, B, C, and Router D. Let us assume that router A is down. After some time, when the router B does not receive any update from the router A, it marks the router down. But router C still has the path to A via router B in its table.

So, router C broadcasts to router B that it knows a path to router A and, let us say, that is two hops away. In this scenario, though the router C has counted the path via router B, router B is not aware of it. So, router B broadcasts its table by adding one more hop (for itself) and says that router A is three hops away from me.

When router C receives the broadcast and it finds out that router B has updated its distance, it also increments its distance accordingly and broadcasts the new distance again to router B. In turn, router B again broadcasts the new distance. This way, the distance keeps on increasing forever in a loop. This problem is called countdown to infinity problem.

Question: Can you guess the solution to countdown to infinity problem? If you have found one, then mention in the comments at the end of the article.

Examples of Distance vector routing protocols:

• RIP (Routing Information Protocol)
• IGRP
• EIGRP

Link State Routing Protocol

Imagine a situation when there would be tens of routers inside an autonomous system. The route calculation would take a lot of time to converge when the distance between the routers are not stable and keeps on changing frequently. This was the problem with the Distance vector routing protocol and was addressed in the link state routing protocol.

Link state routing protocol works in two phases.

• Phase one: Reliable flooding
  • Initial state and,
  • final state
• Phase two: Route calculation

Reliable flooding

When the routers are booted up, the first thing that the routers do is determining which ports they are connected to. So they reach each neighboring routers personally. Once the router has the idea of what all ports they are connected to, they start advertising their connectivity and distribute it across the network so that each other node can receive the advertisement and build the network topology.

This flooding/ broadcast has been called here “reliable” because if any of the nodes advertise any false information, that will lead to false network topology diagram.

Link Discovery Challenges

As already mentioned above, the first challenge is the reliability. Other prominent challenges are avoiding loops and minimizing the packet exchanges so as to avoid the network over flooding. 

Solutions

The solutions to the above problem are:

• Each packet needs to have a unique ID
• Do not reply on the port from where you receive a broadcast. It is managed using a flag.

Thus, in the final state of the reliable flooding, all the nodes have information about the entire topology.

Route Calculation

Route calculation in the link state protocol uses some variant of the Dijkstra algorithm. Once a node has the topology, it runs the Dijkstra algorithm to find the shortest path to all the other nodes in the network.

Just like the Distance Vector Routing Protocol, this routing protocol also has some limitations, though it tries to resolve some of the issues arising in the former one.

• Link state routing protocol reduces the network data overhead, unlike distance vector routing protocol, by using partial computation when a link metrics changes in the network.

Examples of Link state routing protocol

• Open Shortest Path First (OSPF) and,
• IS-IS (Intermediate System to Intermediate System)

Exterior Gateway Protocol (EGP)

Exterior Gateway protocols are used to communicate to the different networks unline IGPs which work only for an autonomous system.

Original source: fossbytes