ROUTING ALGORITHMS: THE OPTIMALITY PRINCIPLE

To learn about these routing algorithms we need to know about network layer.
The network layer performs two functions which are:
[Link]: moving of packets from input’s router to the appropriate output’s router.

[Link]: It is the process of finding the best route when travelling from source to destination.
Routing Algorithm:
Routing algorithms are used in computer networks to determine the best path for data packets to travel
from the source to the destination. Since networks are dynamic, routing algorithms play a key role in
ensuring efficient, reliable, and cost-effective communication.
Routing algorithms can be grouped into two major classes:
[Link] Adaptive (Static Routing)
[Link] (Dynamic Routing)
Non-Adaptive (Static) Routing:
 Routes are fixed and do not change automatically with network conditions.
 Decisions are made manually by the network administrator.
 Simple and less overhead.
Ex: Fixed routing tables.
Adaptive (Dynamic) Routing:
 Routes are updated automatically based on changes in network topology, traffic, or failures.
 Algorithms adjust paths according to metrics like delay, bandwidth, or hop count.
 More efficient but requires more processing and communication overhead.
Ex: Distance Vector, Link State.
Fairness vs Optimality:
Fairness and efficiency may sound obvious—surely no reasonable person would oppose them—but as
it turns out, they are often contradictory goals. As a simple example of this conflict, look at Fig. 5-5.
Suppose that there is enough traffic between A and A′, between B and B′, and between C and C′ to saturate
the horizontal links. To maximize the total flow, the X to X′ traffic should be shut off altogether.
Unfortunately, X and X′ may not see it that way. Evidently, some compromise between global efficiency and
fairness to individual connections is needed.

Lokeshnath K Asst Prof CSE

Optimality Principle:
The optimality principle was introduced by “Bellman” in 1957.
• It’s states that if router J is on the optimal path from router I to router K , then the optimal path from
router J to K also falls along the same route.
• To see this , call the part of the route from I to J is r1 and the rest of the route r2.
• If the route better than r2 existed from J to K ,it could be concatenated with r1 to improve the route
from I to K ,contradicting our statement that r1r2 is optimal.

• The set of optimal routes from all sources to a given destination form a tree routed at the destination.
• Such a tree is called a sink tree.
• The distance metric is the number of hops.
• The goal of all routing algorithms is to discover and use the sink trees for all routers.
From fig; (a) which represents a network which consists of multiple routers where there exists an
optimal path between two routers, and (b) which represents a sink tree from router B where there is path
exists between two routers without any loops, traffic jam and inconvenience and the sink tree also called as
Directed Acyclic Graph(DAC).
 The optimality principle and sink tree provide a benchmark against which routing algorithms
that can be measured.

Lokeshnath K Asst Prof CSE

 Link state routing

 Link state routers in computer networks use a protocol where each router builds a complete map of
the network and independently calculates the shortest path to every destination—examples
include OSPF and IS-IS protocols.

 What is Link State Routing?

 Link state routing is a technique in which every router shares information about its direct
connections (neighbors) with all other routers in the network, allowing each to have a global view of
the network topology. Unlike distance-vector algorithms (which exchange entire routing tables), link
state routers only communicate the state of their own links to their neighbors, reducing unnecessary
traffic.

 How Link State Routing Works

 Each router discovers its neighbors and the link costs to those neighbors.
 Routers generate link state advertisements (LSAs), which include their link information and costs.
 LSAs are flooded across the network, so all routers have the same topology database.
 Routers use Dijkstra's algorithm to independently determine the shortest path to all nodes, forming
their routing tables.
 Here is an example of how Dijkstra's algorithm is used with a graph for link state routing, illustrating
the shortest path calculation from a source node:

Lokeshnath K Asst Prof CSE

 Consider a network with nodes A, B, C, D, E and the following link costs:
Step 0: Initialization
Start at node A with distance 0.
All other nodes distances are set to infinity (∞).
No nodes visited yet.
Graph reflects initial state:
A: 0, B: ∞, C: ∞, D: ∞, E: ∞

Step 1: Visit Node A

Current node: A
Update distances to neighbors:
A→B=2
A→C=5
Distances: A: 0, B: 2, C: 5, D: ∞, E: ∞
Mark A as visited.

Step 2: Visit Node B (nearest unvisited)

Current node: B
Update distances to neighbors of B:
B → C = min(5, 2 + 1) = 3 (updated)
B → D = 2 + 3 = 5 (new)
Distances: A: 0, B: 2, C: 3, D: 5, E: ∞
Mark B as visited.

Step 3: Visit Node C

Current node: C
Update distances to neighbors of C:
C → D = min(5, 3 + 2) = 5 (unchanged)
C → E = 3 + 3 = 6 (new)
Distances: A: 0, B: 2, C: 3, D: 5, E: 6
Mark C as visited.

Step 4: Visit Node D

Current node: D

Lokeshnath K Asst Prof CSE

 Update distances to neighbors of D:
D → E = min(6, 5 + 1) = 6 (unchanged)
Distances remain: A: 0, B: 2, C: 3, D: 5, E: 6
Mark D as visited.

Step 5: Visit Node E

Current node: E
No further neighbors.
Distances finalized: A: 0, B: 2, C: 3, D: 5, E: 6
Mark E as visited.

Below is the CSV data summary of the process:

Step Visited Current Distances (A, B, C, D, E)
0 - (A: 0, B: ∞, C: ∞, D: ∞, E: ∞)
1 A (A: 0, B: 2, C: 5, D: ∞, E: ∞)
2 B (A: 0, B: 2, C: 3, D: 5, E: ∞)
3 C (A: 0, B: 2, C: 3, D: 5, E: 6)
4 D (A: 0, B: 2, C: 3, D: 5, E: 6)
5 E (A: 0, B: 2, C: 3, D: 5, E: 6)

 This process ensures that router A knows the minimum cost path to all other routers, enabling
efficient data packet routing.
 Link state routing protocols like OSPF implement this concept to achieve fast convergence and
scalable, accurate routing decisions in real-world networks.

HIERARCHICAL ROUTING
 Early networks used Flat Routing.
Flat Routing:
A routing method where every router has complete information about all other routers in the network and
treats the whole network as a single unit (without dividing it into parts).

Challenges in Flat Routing:

1. Large routing tables – Every router must store info about all others routers.

Lokeshnath K Asst Prof CSE

[Link] scalable – Works only for small networks, becomes messy in big ones.
3. High overhead – Too many updates and too much communication.
4. Slow convergence – Takes time for all routers to update after changes.
5. Hard to manage – Can't divide the network into smaller, easy-to-handle parts.

To overcome these challenges Hierarchical Routing came into the picture.

HIERARCHICAL ROUTING
Definition: Hierarchical routing in computer networks is a strategy for managing large networks by
dividing them into smaller, manageable regions or hierarchies.
This approach reduces the complexity of routing tables and improves scalability by allowing routers to
focus on routing within their specific region and only knowing about the existence of other regions.
In hierarchical routing, the routers are divided into regions. Each router has complete details about how to
route packets to destinations within its own region. But it does not have any idea about the internal structure
of other regions.
As we know, in both LS and DV algorithms, every router needs to save some information about other
routers. When network size is growing, the number of routers in the network will increase. Therefore, the
size of routing table increases, then routers cannot handle network traffic as efficiently. To overcome this
problem we are using hierarchical routing.
In hierarchical routing, routers are classified in groups called regions. Each router has information about the
routers in its own region and it has no information about routers in other regions. So, routers save one record
in their table for every other region.
For huge networks, a two-level hierarchy may be insufficient hence, it may be necessary to group the
regions into clusters, the clusters into zones, the zones into groups and so on.

Example-1:

Fig. 1: A network with Hierarchical Routing

Lokeshnath K Asst Prof CSE

When routing is done hierarchically then there will be only 7 entries as shown below.

Explanation:
Step 1 : For example, the best path from 1A to 5C is via region 2, but hierarchical routing of all traffic to
region 5 goes via region 3 as it is better for most of the other destinations of region 5.
Step 2 : Consider a subnet of 720 routers. If no hierarchy is used, each router will have 720 entries in its
routing table.
Step 3 : Now if the subnet is partitioned into 24 regions of 30 routers each, then each router will require 30
local entries and 23 remote entries for a total of 53 entries.

Lokeshnath K Asst Prof CSE

Example-2:
If the same subnet of 720 routers is partitioned into 8 clusters, each containing 9 regions and each region
containing 10 routers. Then what will be the total number of table entries in each router.
Solution:
10 local entries + 8 remote regions + 7 clusters = 25 entries
Challenges in Hierarchical Routing:
1. Hard to design – Need to carefully divide the network into areas.
2. More complex – Routers must handle routing inside and between areas.
3. Not always shortest path – Sometimes data takes a longer route.
4. If backbone fails, problem – Areas can’t talk to each other.
5. Needs skilled management – More difficult to set up than flat routing.

After hierarchical routing, SDN-based routing and policy-based/hybrid routing protocols are considered
more advanced to overcome its challenges (better scalability, flexibility, and easier management).

BROADCAST ROUTING ALGORITHM

Introduction:
Broadcast routing is a network routing technique where a message is sent from one source node to all other
nodes in the network.
Example: weather reports , stock market updates ,or live media programs
Consider unicasting we can send a message
to only single computer at a [Link],
that send can send each message
to each computer, but in broadcast
sender will send data to all connected
computer at once
“Sending data to all its connected computers at once is called broadcasting “
Broadcast Routing Algorithms
1. Point to point protocol :
A source node creates a separate copy of the packet for each destination and sends them one by one.
Example
Imagine router A wants to send a broadcast to B, C, D, and E.
 A → B (one packet)

Lokeshnath K Asst Prof CSE

  A → C (another packet)
 A → D (another packet)
 A → E (another packet)
 Total = 4 separate transmissions
If there are N destinations, then N separate transmissions are needed.
Advantages
 Very simple to implement.
 Works with existing unicast routing tables
Disadvantages
 Wastes bandwidth (multiple copies travel across the same links).
 Not scalable for large networks.

2. Flooding :
Flooding is a simple routing method where a packet is sent to all possible paths without caring about the
destination
it does not check the destination, It just copies the packet and sends it to all neighbors.
Advantages
 Simple –no routing table required
 Useful in small networks
 Good for broadcast/multiple communication.
Disadvantages
 Creates too many duplicates packets
 Wastes bandwidth
 Not scalable for large networks.

3. Multidestination routing :
Each packet carries a list of detinations. The router checks and forwards only to required outputs
Advantages
 More efficient than sending separate packets for each destination.
 Saves bandwidth
Disavantages

 Complexity grows if the group of destinations is large

Lokeshnath K Asst Prof CSE

 4. Reverse path forwarding (RPF):
A router forwards a packet only if it arrived on the link that is normally used to reach the source
It is based on the principle of using the reverse of the shortest path from each router to the source
Advantages
 Simple and elegant
 No need for routers to store sequence numbers or detination lists
Disavantages
 Some duplicate packets may still be generated
5. Spanning tree :
Uses a spanning tree to cover all routers without loops(no cycles)
Advantages
 No infinite loops
 No duplication of packets
Disadvantages
 Non optimal paths
 Wasted links

Multicast Routing
Definition
Multicast routing is the process of delivering data packets from one source to multiple destinations
simultaneously across a network, in an efficient way. It follows a one-to-many or many-to-many
communication model and ensures that data is transmitted only once over any network link, regardless of
the number of receivers. This conserves bandwidth and reduces unnecessary duplication of traffic.
How Multicast Routing Works
Routers in a multicast-enabled network build multicast distribution trees to forward packets only to those
parts of the network where receivers have explicitly requested the data. Protocols like Internet Group
Management Protocol (IGMP) and Multicast Listener Discovery (MLD) are used by hosts to signal their
interest in receiving multicast traffic.
Example
A common example of multicast routing is live video streaming. Suppose a company wants to broadcast a
live training session to employees in multiple branch offices. Instead of sending a separate unicast stream to
each employee (which would waste bandwidth), the server sends a single multicast stream. Routers then
replicate and forward the stream only to those branch offices where employees have joined the multicast
group. This ensures efficient delivery of the video to all interested participants without flooding the entire
network.

Lokeshnath K Asst Prof CSE

Protocols Used in Multicast Routing
Some common protocols used in multicast routing include:
- Distance Vector Multicast Routing Protocol (DVMRP)
- Protocol Independent Multicast (PIM)
- Multicast Open Shortest Path First (MOSPF)

These protocols help routers manage multicast group memberships and construct efficient paths for
delivering multicast traffic.
Techniques to Prevent Duplicate Packets in Multicast Routing
1. Reverse Path Forwarding (RPF) Check
 The most important technique.
 A router forwards a multicast packet only if it is received on the interface that lies on the shortest
path back to the source.
 If the packet arrives on any other interface, it is discarded — preventing loops and duplicates.
2. Pruning and Grafting
 Pruning: Routers that have no receivers for a group send prune messages upstream so they stop
receiving unnecessary multicast packets.
 Grafting: If a new receiver joins, routers can rejoin the tree.
 This avoids unnecessary duplicate flows.
3. Tree-Based Distribution
 Using Shortest Path Trees (SPT) or Shared Trees ensures that each packet follows a unique tree path.
 Prevents the same packet from taking multiple redundant routes.
4. Protocol-Specific Control
 DVMRP: Uses flood-and-prune along with RPF checks to avoid duplicates.
 PIM (Sparse/Dense Mode): Relies on RPF checks and controlled joins to avoid packet duplication.
 MOSPF: Uses link-state information to calculate loop-free multicast paths.
5. Duplicate Packet Detection (in some implementations)
 Routers may track packet identifiers (like source + group + sequence number) to detect and discard
duplicates if they slip through.
Advantages of Multicast Routing
1. Efficient Bandwidth Usage – Sends a single copy of data across each network link, no matter how
many receivers there are.
2. Reduced Network Congestion – Avoids flooding the network with duplicate packets like in
broadcast communication.
3. Scalability – Supports thousands (or even millions) of receivers without overwhelming the source or
network.

Lokeshnath K Asst Prof CSE

 4. Better Performance for Real-Time Applications – Ideal for streaming video, audio, and online
gaming where the same data must reach many users simultaneously.
5. Lower Server Load – The source only sends one stream instead of multiple unicast streams,
reducing CPU and bandwidth usage at the sender side.
Disadvantages of Multicast Routing
1. Complex Configuration – Requires special protocols (e.g., PIM, IGMP, MLD) and router support,
making setup harder than unicast.
2. Limited Deployment – Not all networks (especially across the internet) support multicast routing
widely.
3. Difficult Traffic Management – Managing group memberships, security, and Quality of Service
(QoS) is more challenging.
4. Security Concerns – Any device that joins the group can receive the stream, which can be a
problem if sensitive data is sent.
5. Debugging Issues – Troubleshooting multicast traffic is harder compared to unicast, due to dynamic
group memberships and tree structures.

Anycast Routing
Anycast routing is a way of sending data over the network to the destination. It has multiple possible
locations. For example, suppose you want to access a website that has servers in different countries. Anycast
routing can help you connect to the server that is closest and best for you. Instead of sending you to a fixed
location, web browsing is faster and more reliable.

Figure 1:Anycast Routing: Searching for nearest server

Basic Terms
These are important basic terms related to Anycast routing:

Lokeshnath K Asst Prof CSE

1. Anycast Address
This is IP address. It is not unique to one device. It is shared by multiple devices in different locations. For
example, suppose there are three web servers with same anycast address: [Link] in New Delhi,
London, and Mumbai. When you send a request to this address, the routers will direct your packets to the
nearest and best web server according to some criteria. These are number of hops, latency, and load. So, you
can access web content faster and more reliably.
2. Anycast Network
This is a network that supports anycast routing. These two types are native and tunnelling techniques.
Native anycast network is network that uses anycast routing protocol. It uses to advertise and forward
anycast addresses. Whereas, tunnelling anycast network is network that uses unicast routing protocol. It
creates tunnels between anycast nodes and then forward anycast addresses to tunnels. For example, suppose
there are two DNS resolvers with same anycast address [Link] in different continents. Native anycast
network would use Broader Gateway Protocol. It uses to announce and route this address to nearest.
Tunnelling anycast network would use Open Shortest Path First to create tunnels between resolvers and then
route this address over these tunnels.
3. Anycast Service
This is service. It is provided by multiple nodes in anycast network. Such as web server and DNS resolver.
This service improves performance, availability, and scalability. Because it distributes load and traffic
among many nodes. It also improves security and resilience. It mitigates DDoS attacks and handling failures
and changes in the network topology.
4. Anycast Routing Protocol
This is a protocol. It uses Border Gateway Protocol (BGP) and Open Shortest Path First (OSPF). It
advertises and forwards anycast addresses in the network. Metrics such as hop count, bandwidth, and load to
select the best path for each packet.
Benefits of Anycast Routing
 Improved performance: Anycast routing can reduce distance and delay between source and
destination. So data transmission faster and smoother.
 Load balancing: Anycast routing can distribute the traffic among multiple servers. So it prevents
any single server from being congested.
 Resilience: Anycast routing can increase availability and reliability of the service. It automatically
switching to another server if one server fails and becomes unreachable.
 Scalability: Anycast routing can easily add and remove servers from the network. It done without
affecting the service.
Challenges of Anycast Routing
 Routing consistency: Anycast routing can cause packets to take different paths. It depends on
network conditions and routing protocols. But there can be issue. Such as TCP connections and
video streaming.
 Security: Anycast routing can expose the service to more potential attacks. It increases number of
entry points and exit points for the data. This need encryption and authentication.
 Management: Anycast routing can complicate monitoring and troubleshooting of the network. This
needs tools and techniques.

Lokeshnath K Asst Prof CSE

Applications of Anycast routing
 Content delivery networks (CDNs): CDNs use anycast routing to deliver web content faster and
efficiently to users to world. It caches on multiple servers with same anycast address.
 Domain name system (DNS): DNS uses anycast routing to resolve domain names faster and
reliably. It distributes queries among multiple resolvers with the same anycast address.
 Distributed denial-of-service (DDoS) mitigation: DDoS mitigation services use anycast routing to
protect websites and networks from large-scale attacks. It diverts traffic to scrubbing centers with the
same anycast address.

FLOODING
DEFINITION : Flooding is used in computer routing algorithms in which every incoming packet is sent
through every outgoing link except the one it arrived on.
How Flooding Works
The basic principle of flooding is straight forward:
1. A source node receives a packet to be sent to a destination node.
2. Instead of determining a single path, the source node sends a copy of the packet out on every single
one of its outgoing links, except for the one it was received on.
3. Each receiving node, upon getting the packet for the first time, does the same thing: it forwards a
copy of the packet on all its outgoing links, excluding the one from which the packet arrived.
4. This process continues until the packet has reached all nodes in the network.
Because the packet is forwarded on all possible paths, it is guaranteed to find a path to the destination,
provided a path exists.
Example:

Flooding Algorithm Recap

Flooding = when a node receives a packet, it sends it to all neighbors except the one it came from.
Without control, it may cause duplicates, so in practice:

Lokeshnath K Asst Prof CSE

  Nodes keep track of packets (using sequence numbers)
 A node forwards a packet only once.
Step-by-Step Flooding Example
Suppose A wants to send a packet to B using flooding:
1. A → sends packet to all its neighbors: C, D, E.
(A will not send directly to B, since in the graph A-B is not directly connected).
2. C receives from A → forwards to neighbors (B) since it will not return to A.
o So C → B.
3. D receives from A → forwards to neighbors (B) but not A.
o So D → B.
4. E receives from A → forwards to neighbors (B) but not A.
o So E → B.
5. Now B receives the packet from C, D, and E.
o Since B already got the packet once, it discards duplicates.
Result
 B receives the packet successfully.
 The message traveled through multiple paths:
o A→C→B
o A→D→B
o A→E→B
 This ensures reliability (since if one path fails, others still deliver), but also causes duplicate packets
and network overhead.
 So, flooding in this network ensures B always gets the packet from A, but B may get duplicates via
multiple routes.
 So the disadvantage is vast number of duplicate packets are generated. It produce infinite number of
packets unless we know how to prevent/stop the duplicate packets.
Techniques to Prevent Duplicate Packets in Flooding
1. Hop Count / Time-to-Live (TTL):
o Each packet carries a hop counter (like TTL in IP).
o Each router decrements the counter before forwarding.
o When the counter reaches 0, the packet is discarded.
o Prevents infinite looping of duplicates.
2. Packet Sequence Numbering (Unique Identifiers):
o The source assigns a unique sequence number to each packet.

Lokeshnath K Asst Prof CSE

 o Each node keeps a table (cache) of (source, sequence number) pairs it has already seen.
o If a packet with the same identifier arrives again, the node discards it instead of forwarding.
o This eliminates duplicates efficiently.
3. Selective Flooding:
o Instead of sending on all links, a node forwards the packet only on links that are likely to
lead toward the destination.
o Reduces redundant transmissions.
Advantages of Flooding
1. Simplicity – No need for complex routing algorithms or tables; packets are just forwarded
everywhere.
2. Reliable delivery – Ensures that a packet reaches the destination if a path exists (useful in networks
with unknown or changing topology).
3. Fault tolerance – If one path fails, copies traveling along other paths may still reach the destination.
4. No need for routing information – Works even if nodes have no knowledge of the network
topology.
5. Useful in broadcasting/multicasting – Helpful when sending the same information to all nodes
(e.g., updates, routing protocols, advertisements).
6. Good for highly dynamic networks – In mobile ad hoc networks (MANETs) or sensor networks
where topology changes frequently, flooding guarantees packet delivery.

Disadvantages of Flooding
1. High redundancy – Many duplicate packets are generated, wasting bandwidth.
2. Congestion – Excessive packet copies can overwhelm the network.
3. Collisions – More traffic increases chances of packet collisions and retransmissions.
4. Resource wastage – Wastes processing power, memory, and energy at intermediate nodes.
5. Not scalable – Becomes highly inefficient in large networks due to exponential packet growth.
6. Short loops possible – Without proper control (e.g., hop count/TTL), packets may circulate
indefinitely.

The Shortest Path Algorithm: Dijkstra's Algorithm

The shortest path algorithm is a method for finding the shortest path between nodes in a graph. Dijkstra's
Algorithm is a popular example that finds the shortest path from a starting node to all other nodes in a
graph with non-negative edge weights. It works by repeatedly visiting the unvisited node with the
smallest known distance from the starting point and updating the distances of its neighbors if a shorter
path is found.

Lokeshnath K Asst Prof CSE

 Terms:
Tentative Node: A node whose shortest distance from the source is not yet confirmed. Its distance
value may still be updated.
Permanent Node:A node for which the shortest distance from the source has been found and confirmed.
It will not change anymore.
Working Node:The node currently being processed (i.e., the one with the smallest tentative distance at
the current step of the algorithm).
In shortest path algorithm especially Dijkstra’s Algorithm, nodes (also called vertices) are often labeled
to indicate their current state in the pathfinding process:
Types of nodes:
How They Work in Dijkstra’s Algorithm:
1. Start: All nodes are marked as tentative, and the source node’s distance is set to 0.
2. Working Node: Choose the node with the smallest tentative distance — this is the working node.
3. Update Neighbors: Relax (update) the distances to its neighbors.
4. Mark Permanent: Once a node is processed, it becomes permanent.
5. Repeat: Continue selecting the next working node (lowest tentative distance) until all nodes are
permanent or the destination is found.
Step-by-Step Explanation of the Example

Lokeshnath K Asst Prof CSE

 The provided images demonstrate Dijkstra's algorithm from a starting node A. The values in parentheses
for each node represent (cost, previous node), showing the shortest distance found so far and the node
that led to it.
Figure (b): The algorithm starts at node A, so its cost is 0. Its neighbors B and G are updated with their
direct costs from A: B becomes (2, A) and G becomes (6, A).
Figure (c): The unvisited node with the lowest cost is B (cost 2). The algorithm explores its neighbors C
and E. The path to E via B (2+2=4) is shorter than any known path, so E is updated to (4, B). The path to
C via B (2+7=9) updates C to (9, B).
Figure (d): The next lowest cost node is E (cost 4). Its neighbors C, D, and F are checked. The path to C
via E (4+3=7) is shorter than C's current cost of 9, so C is updated to (7, E). The paths to D (4+2=6) and
F (4+2=6) are also updated.
Figure (e): The next lowest cost is G (cost 6). The path to its neighbor H via G (5+4=10) updates H to
(9, G).
Figure (f): The next lowest cost is F (cost 6). The algorithm checks its neighbors. The path to H via F
(6+2=8) is shorter than H's current cost of 10, so H is updated to (8, F).
This process continues until all nodes have been visited, at which point the final costs and paths are
determined. For example, the final shortest path to H is A -> B -> E -> F -> H, with a total cost of 8.

Distance Vector Routing (DVR)

Distance Vector Routing (DVR) Protocol is a method used by routers to find the best path for data to travel
across a network. Each router keeps a table that shows the shortest distance to every other router, based on
the number of hops (or steps) needed to reach them. Routers share this information with their neighbors,
allowing them to update their tables and find the most efficient routes. This protocol helps ensure that data
moves quickly and smoothly through the network.
What is the Distance Vector Routing Algorithm?
The protocol requires that a router inform its neighbors of topology changes periodically. Historically
known as the old Historically known as the old ARPANET routing algorithm (or known as the Bellman-
Ford algorithm).
Bellman-Ford Basics
Each router maintains a Distance Vector table containing the distance between itself and All possible
destination nodes. Distances, based on a chosen metric, are computed using information from the neighbors'
distance vectors.
Information kept by DV router:
 Each router has an ID
 Associated with each link connected to a router,
there is a link cost (static or dynamic).
 Intermediate hops

Distance Vector Table Initialization:

Lokeshnath K Asst Prof CSE

  Distance to itself = 0
 Distance to ALL other routers = infinity number.
How Distance Vector Algorithm works?
 A router transmits its distance vector to each of its neighbors in a routing packet.
 Each router receives and saves the most recently received distance vector from each of its neighbors.
 A router recalculates its distance vector when:
o It receives a distance vector from a neighbor containing different information than before.
o It discovers that a link to a neighbor has gone down.
The DV calculation is based on minimizing the cost to each destination

 Dx(y) = Estimate of least cost from x to y

C(x,v) = Node x knows cost to each neighbor v
Dx = [Dx(y): y? N] = Node x maintains distance vector
Node x also maintains its neighbors' distance vectors
– For each neighbor v, x maintains Dv = [Dv(y): y? N]
Note:
 From time-to-time, each node sends its own distance vector estimate to neighbors.
 When a node x receives new DV estimate from any neighbor v, it saves v’s distance vector and it
updates its own DV using B-F equation:
Dx(y) = min {C(x,v) + Dv(y), Dx(y)} for each node y? N
Example:
Consider 3-routers X, Y and Z as shown in figure. Each router have their routing table. Every routing table
will contain distance to the destination nodes.

Consider router X , X will share it routing table to neighbors and neighbors will share it routing table to it to
X and distance from node X to destination will be calculated using bellmen- ford equation.
Dx(y) = min { C(x,v) + Dv(y)} for each node y ? N
As we can see that distance will be less going from X to Z when Y is intermediate node(hop) so it will be
update in routing table X.

Lokeshnath K Asst Prof CSE

Similarly for Z also -

Finally the routing table for all -

Lokeshnath K Asst Prof CSE

Applications of Distance Vector Routing Algorithm
The Distance Vector Routing Algorithm has several uses:
 Computer Networking: It helps route data packets in networks.
 Telephone Systems: It's used in some telephone switching systems.
 Military Applications: It has been used to route missiles.
Advantages of Distance Vector routing
 Shortest Path: Distance Vector Routing finds the shortest path for data to travel in a network.
 Usage: It is used in local, metropolitan, and wide-area networks.
 Easy Implementation: The method is simple to set up and doesn't require many resources.
Disadvantages of Distance Vector Routing Algorithm
 It is slower to converge than link state.
 It is at risk from the count-to-infinity problem.
 It creates more traffic than link state since a hop count change must be propagated to all routers and
processed on each router. Hop count updates take place on a periodic basis, even if there are no
changes in the network topology , so bandwidth -wasting broadcasts still occur.
 For larger networks, distance vector routing results in larger routing tables than link state since each
router must know about all other routers. This can also lead to congestion on WAN links.

Lokeshnath K Asst Prof CSE