Scribd
Upload
2 views2 pages

Assignment3 Routing Algorithm

The document discusses routing algorithms, which determine the best paths for data packets in networks. It classifies routing algorithms into static and dynamic categories, with further distinctions between distance vector and link state routing. The document highlights the importance of these algorithms in network efficiency, reliability, and their applications in various network scales.

Uploaded by

seetharamans327
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
2 views2 pages

Assignment3 Routing Algorithm

The document discusses routing algorithms, which determine the best paths for data packets in networks. It classifies routing algorithms into static and dynamic categories, with further distinctions between distance vector and link state routing. The document highlights the importance of these algorithms in network efficiency, reliability, and their applications in various network scales.

Uploaded by

seetharamans327
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Assignment 3

Routing Algorithm
1. Introduction
Routing is the process of selecting a path for data packets to travel across a network from source to destination. A routing
algorithm decides which path is best, based on metrics such as distance, hop count, delay, or bandwidth.

2. Classification of Routing Algorithms


• Static Routing - routes are manually configured by a network administrator; does not adapt to network changes
automatically.
• Dynamic Routing - routers automatically exchange information and adjust routes based on current network
conditions.
• Distance Vector Routing - each router shares its routing table (distance to each destination) with directly connected
neighbors (e.g., RIP - Routing Information Protocol, based on the Bellman-Ford algorithm).
• Link State Routing - each router builds a complete map of the network topology by flooding link-state information,
then computes shortest paths independently (e.g., OSPF - Open Shortest Path First, based on Dijkstra's algorithm).

3. Dijkstra's Shortest Path Algorithm (Link State)


Dijkstra's algorithm finds the shortest path from a source node to all other nodes in a weighted graph:
• Initialize distance to source = 0, all others = infinity.
• Select the unvisited node with the smallest distance.
• Update distances of its neighbors if a shorter path is found through it.
• Mark the node as visited; repeat until all nodes are visited.

Fig 1: Example network graph - numbers on edges represent link cost/distance used by routing algorithms
4. Distance Vector vs Link State
Basis Distance Vector Link State
Information shared Only distance to neighbors Complete topology (link states)
flooded to all routers
Algorithm Bellman-Ford Dijkstra's shortest path
Convergence Slower, prone to routing loops Faster, more accurate
Example protocol RIP OSPF

5. Applications / Uses
• Used by routers on the Internet to determine the best path for forwarding packets.
• RIP is used in small/simple networks; OSPF and BGP are used in large enterprise and Internet-scale networks.
• Routing algorithms are essential for load balancing, avoiding congestion, and ensuring reliable delivery in dynamic
networks.

6. Conclusion
Routing algorithms are the backbone of packet-switched networks, determining how efficiently and reliably data reaches its
destination. The choice between distance vector and link state routing depends on network size, complexity, and required
convergence speed.

You might also like