Distance vector vs. link state routing

Distance vector and link state are two major classes of intra-AS routing protocol. In simpler words, they are two ways of routing happening inside an autonomous system where an autonomous system is a collection of IP networks and routers belonging to the control of a single entity.

Let's consider the following as our AS for this post. Let's assume all the distances are 1.

Distance vector routing

Distance vector as the name suggests, keeps track the 'distance' to a destination and the vector or 'direction' of the destination. This is individually done by all routers to every other destination and a router does not know or care about the topology beyond its neighbors. It uses Bellman-Ford algorithm to calculate paths and it is also known as routing by rumor since a router contacts its neighbors to get the information.

Here's how A would keep track of other destinations.

Finally A would be having an information base similar to the following. 

It will contain the distance and direction to a destination from A's point of view.

Let's take a look at another node. This is how B would retrieve information.

And finally B will end up with a result like this.

Link state routing

Link state is a method where a node will be aware of all the other destinations in the AS. Each node will use Dijkstra's algorithm to calculate paths to other nodes and will maintain a tree representing the paths.

Here's how A will calculate paths to other nodes.

After calculating the distances and parent nodes relevant to each destination, the information will be saved in a tree structure similar to the following.

Similarly let's look at how B will do this.

This is B's result.

As you would see, maintaining the results obtained from link state mechanism requires more effort, causing it to have more overhead than distance vector routing. However link state is proven to be a robust  routing operation.