Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Distance Vector Routing Protocol?
3.
Explanation of Distance Vector Routing Algorithm
4.
How Does DVR Protocol Work?
5.
Example of Distance Vector Routing
5.1.
Step 1:
5.2.
Step 2:
5.3.
Step 3:
6.
Three Keys to understand the working of Distance Vector Routing Algorithm
6.1.
Distance Metric
6.2.
Routing Table
6.3.
Bellman-Ford Algorithm
7.
Advantages of Distance Vector Routing
8.
Disadvantages of Distance Vector Routing
9.
Frequently Asked Questions
9.1.
What are the problems associated with distance vector routing?
9.2.
What are the different types of distance vector routing algorithm?
9.3.
What is the purpose of the distance vector routing algorithm?
9.4.
Which type of network is distance vector protocol best suited for?
10.
Conclusion
Last Updated: Mar 27, 2024
Medium

Distance Vector Routing Algorithm

Author Muskan Sharma
3 upvotes
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Did you know that modern computer networks generally use dynamic routing algorithms rather than static protocols?

Yes, modern computer networks generally use dynamic routing protocols because static protocols do not take the load of the current network into account. The distance vector routing protocol and Link state routing algorithm are among the most popular dynamic routing protocols.

Distance Vector Routing Algorithm

This blog includes the Distance vector routing algorithm in detail. Now, let's understand what Distance vector routing algorithms are.

Also, read Basic Networking Commands

What is Distance Vector Routing Protocol?

The Distance vector routing (DVR) operate by having each router maintain a table (i.e., a vector), giving the best-known distance to each destination and which path to use to get there.

These tables are updated by exchanging information with the neighbors. 

Bellman-Ford Basics: The distance vector routing algorithm is also known as the distributed Bellman-Ford routing algorithm and the Ford-Fulkerson algorithm, which Bellman developed in 1957 and Ford-Fulkerson in 1962.

Information kept by DV router: The DV (Distance Vector) router keeps the information about the distance (cost) required to reach each destination.

Distance Vector Table Initialization: During initialization, the distance of each router to itself is set to 0, and to other routers is set to infinity.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Explanation of Distance Vector Routing Algorithm

It is used in computer networks to choose the optimal path for data to travel between nodes is the distance vector routing algorithm.

  • It works by exchanging data with its nearby nodes that are directly linked in order to compile a table of the most direct paths to every other node in the network.
     
  • Every node in the network keeps a routing table that details the distance to each target node as well as the subsequent hop node on the way there.
     
  • Normally, the distance is expressed in terms of the number of hops or the travel duration to the destination.
     
  • The Bellman-Ford algorithm is used by the Distance Vector Routing Algorithm to update the routing database. Each node sends its routing table to its neighbours on a regular basis, and they use the data they receive to update their own tables. Until every node has access to the most recent routing information, this procedure is repeated.

How Does DVR Protocol Work?

DVR (Distance Vector Routing) protocol is a routing algorithm used in networks to determine the best path for data packets to reach their destination. Here's a breakdown of its operation in bullet points:

  • Routing Tables: Each router in the network maintains a routing table. This table contains information about other routers in the network, specifically:
    • Destination network address
    • Distance (cost) to reach that network (usually measured in hops)
    • Next hop router on the path to the destination
  • Information Exchange: Routers periodically exchange their routing tables with their neighboring routers. This exchange typically happens using routing update messages.
  • Distance Calculation: The "distance" in the routing table entry refers to the administrative cost (metric) associated with reaching a particular network. This metric can be based on factors like number of hops, bandwidth, or delay.
  • Path Selection: Based on the information in its routing table, each router selects the next hop router with the least cost (distance) for a particular destination network. This ensures packets are forwarded along the most efficient path.
  • Updates and Loops: When a router receives an update from a neighbor, it recalculates its own routing table. If the cost to a destination changes (e.g., due to a link failure), the router updates its table and propagates the change to its neighbors. However, DVR protocols are susceptible to routing loops, which require additional mechanisms to prevent.
  • Simple and Scalable: DVR protocols are relatively simple to implement and are well-suited for smaller networks. However, their reliance on periodic updates and limited loop prevention can make them less efficient for large, dynamic networks.

Example of Distance Vector Routing

Consider the following network; three routers are there: A, B, and C with AB=1, BC=2, and CA=5.

Let's see the following steps to understand it better.

Example of Distance Vector Routing Algorithm

Step 1:

Each router shares its routing table with every neighbor in this distance vector routing network. As A will share its routing table with neighbors B and C, neighbors B and C will share their routing table with A.

Routing table A:

FORM A

A

B

C

A

0

1

5

B

     

C

     

Routing table B:

FORM A

A

B

C

A

     

B

1

0

2

C

     

Routing table C:

FORM A

A

B

C

A

     

B

     

C

5

2

0

Step 2:

If the path via a neighbor has a lower cost, the router updates its local table to forward packets to the neighbor. In this table, router A will be updated.

Routing table A:

FORM A

A

B

C

A

0

1

3

B

     

C

     

Routing table B:

FORM A

A

B

C

A

     

B

1

0

2

C

     

Routing table C:

FORM A

A

B

C

A

     

B

     

C

3

2

0

Step 3:

The following is the final routing table for all the routers A, B, and C with lower-cost distance vector routing protocols.

Router for table A:

FORM A

A

B

C

A

0

1

3

B

1

0

2

C

3

2

0

Router for table B:

FORM A

A

B

C

A

0

1

3

B

1

0

2

C

3

2

0

Router for table C:

FORM A

A

B

C

A

0

1

3

B

1

0

2

C

3

2

0

Three Keys to understand the working of Distance Vector Routing Algorithm

The three keys to understanding the working of the Distance Vector Routing Algorithm are:

  1. Distance Metric
  2. Routing Table
  3. Bellman-Ford Algorithm

Distance Metric

To find the best route to a destination node, the Distance Vector Routing Algorithm employs a distance metric. The number of hops, the bandwidth, or the latency are some examples of different ways to measure the distance metric. 

Routing Table

Every node in the network keeps a routing table, which includes details on the most efficient route to take to get to each destination node. The next hop node and the travel time to the target node are both listed in the routing table. Nodes communicate with the neighbours with whom they are directly linked to update their routing tables on a regular basis.

Bellman-Ford Algorithm

To determine the best route to a target node, the Distance Vector Routing Algorithm employs the Bellman-Ford algorithm. Until convergence is achieved, the algorithm iteratively updates the distance to each network node.

Advantages of Distance Vector Routing

  • For a typical LAN setting, bandwidth requirements are minimal.
  • compared to other routing techniques, requires less hardware and computing power.
  • reliable and tested approach (distance vector was the original routing algorithm)
  • Simple to use and administer

Disadvantages of Distance Vector Routing

  • Time to convergence is relatively slow (updates sent at specified intervals)
  • Before making any modifications to forwarding, routers must recalculate their routing tables.
  • vulnerability to routing loops (count-to-infinity)
  • For WAN or complex LAN situations, bandwidth requirements may be excessive.


Also Read - Kadanes Algorithm

Frequently Asked Questions

What are the problems associated with distance vector routing?

Although distance vector routing has many advantages, it also has some disadvantages. DVR has a slow convergence time, high processing time due to frequent recalculations, increased bandwidth requirements, and vulnerability to routing loops.

What are the different types of distance vector routing algorithm?

  1. Bellman-Ford Algorithm: Minimizes total distance using exchanged routing info.
  2. Routing Information Protocol (RIP): Chooses paths based on hop count.

What is the purpose of the distance vector routing algorithm?

The primary purpose of the distance vector routing algorithm (DVR) is to find the most efficient path for transferring data in the form of packets between nodes in the computer network.

Which type of network is distance vector protocol best suited for?

Distance vector Routing protocols are best suitable for small-sized computer networks. As the number of nodes in the network increase, the data transfer becomes slow due to the slow convergence rate of the DVR algorithm.

Conclusion

In this article, we have extensively discussed the Distance vector routing algorithm. We learned the working of the Distance vector routing (DVR) protocol, and we understand this protocol with the help of an example.

Recommended Readings:

Check out some of the amazing Guided Paths on topics such as Data Structure and AlgorithmsCompetitive ProgrammingBasics of C, Basics of JavaOperating SystemsComputer Networks, etc., along with some Contests and Test Series only on Coding Ninjas StudioEnrol in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations. 

Do upvote our blog to help other ninjas grow. 

Happy Learning, Ninja!🥷✨

Live masterclass