What is Distance Vector Routing (DVR)?

Introduction

The goal of a network is to enable nodes to exchangeA packet is a parcel of data sent over a network, packets if a path exists between them. If this exchange has to be done while incurring the least cost, routing algorithms such as Distance Vector Routing (DVR) are used.

Distance Vector Routing is an intra-domain routing protocol that enables routers within an autonomous systemAn autonomous system is a network or collection of networks governed by a single routing policy. to exchange information.

How it works

In DVR, routers share information about the network with their immediate neighborsNodes that are directly connected via links. periodically. As the name implies, the information shared amongst the nodes and their immediate neighbors is in the form of distance vectors.

Eventually, every node has an updated view of the entire network, thereby allowing it to know the shortest (least cost) path to every other node.

Methodology

Nodes store information about every other node in the network in their local routing tables. These routing tables contain:

• Destination node
• Distance from the current node to the destination node
• Next hop

An example network consisting of 4 nodes accompanied by their routing tables is illustrated below.

While initially empty, these routing tables are populated and updated periodically in various rounds of distance vector exchanges.

First Round

When the first round begins, the routing tables for every node are empty as illustrated above. The following rules are then used to populate them:

• The distance from a node to itself is always 0.
• The next hop for a node to itself is always the node itself.
• The distance from a node to its immediate neighbors is given by the weight of the links.
• The distance from a node to nodes, that aren't immediate neighbors, is $\infty$.

Using the aforementioned rules, we can populate the routing table for node A as follows:

Applying these rules to the other nodes, we conclude the first round with the following results:

Subsequent Rounds

Once the first round is concluded, every node broadcasts its distance vector (the second column of the routing table) to its immediate neighbors only.

Once broadcasted, every node uses the distance vectors that it has received to update its local routing table by applying the Bellman-Ford algorithm. All of the nodes in the network update their routing table in parallel. Once updated, these nodes then exchange their updated distance vectors with their immediate neighbors again and this process repeats.

Note: The current routing table is not used to calculate the values for the updated routing table at all.

The number of rounds in which the distance vectors are exchanged through the network can be computed using the following formula:

After the distance vectors have been exchanged for $n-1$ rounds, and the routing tables are updated locally, every node can send out packets to every other node using the least cost.

For our example network, after a total of 3 rounds, the network has the following routing table:

So, if node A wants to send out a packet to node B, it won't use the direct link between them with $cost=15$. Instead, it's going to refer to its routing table and send out the packet to node D with $cost=10$. Node D will forward the packet to node C with $cost=4$, and finally node C will forward the packet to node B with $cost=1$. This route costs less, for a total cost of 10.