Routing Algorithms Notes | EduRev

: Routing Algorithms Notes | EduRev

 Page 1


Dept. of CSE, IIT KGP
Routing Algorithms
Routing Algorithms
CS60002: CS60002: Distributed Systems Distributed Systems
Pallab Pallab Dasgupta Dasgupta
Dept. of Computer Sc. & Dept. of Computer Sc. & Engg Engg., .,
Indian Institute of Technology Kharagpur Indian Institute of Technology Kharagpur
Page 2


Dept. of CSE, IIT KGP
Routing Algorithms
Routing Algorithms
CS60002: CS60002: Distributed Systems Distributed Systems
Pallab Pallab Dasgupta Dasgupta
Dept. of Computer Sc. & Dept. of Computer Sc. & Engg Engg., .,
Indian Institute of Technology Kharagpur Indian Institute of Technology Kharagpur
Dept. of CSE, IIT KGP
Main Features
Main Features
• • Table Computation Table Computation
– – The routing tables must be computed when the network is The routing tables must be computed when the network is 
initialized and must be brought up initialized and must be brought up- -to to- -date if the topology of date if the topology of 
the network changes the network changes
• • Packet Forwarding Packet Forwarding
– – When a packet is to be sent through the network, it must be When a packet is to be sent through the network, it must be 
forwarded using the routing tables forwarded using the routing tables
Page 3


Dept. of CSE, IIT KGP
Routing Algorithms
Routing Algorithms
CS60002: CS60002: Distributed Systems Distributed Systems
Pallab Pallab Dasgupta Dasgupta
Dept. of Computer Sc. & Dept. of Computer Sc. & Engg Engg., .,
Indian Institute of Technology Kharagpur Indian Institute of Technology Kharagpur
Dept. of CSE, IIT KGP
Main Features
Main Features
• • Table Computation Table Computation
– – The routing tables must be computed when the network is The routing tables must be computed when the network is 
initialized and must be brought up initialized and must be brought up- -to to- -date if the topology of date if the topology of 
the network changes the network changes
• • Packet Forwarding Packet Forwarding
– – When a packet is to be sent through the network, it must be When a packet is to be sent through the network, it must be 
forwarded using the routing tables forwarded using the routing tables
Dept. of CSE, IIT KGP
Performance Issues
Performance Issues
Correctness Correctness: : The algorithm must deliver every packet to its The algorithm must deliver every packet to its 
ultimate destination ultimate destination
Complexity Complexity: : The algorithm for the computation of the tables The algorithm for the computation of the tables 
must use as few messages, time, and storage as possible must use as few messages, time, and storage as possible
Efficiency Efficiency: : The algorithm must send packets through The algorithm must send packets through good good
paths paths 
Robustness Robustness: : In the case of a topological change, the algorithm In the case of a topological change, the algorithm 
updates the routing tables appropriately updates the routing tables appropriately
Fairness Fairness: : The algorithm must provide service to every user in The algorithm must provide service to every user in 
the same degree the same degree
Page 4


Dept. of CSE, IIT KGP
Routing Algorithms
Routing Algorithms
CS60002: CS60002: Distributed Systems Distributed Systems
Pallab Pallab Dasgupta Dasgupta
Dept. of Computer Sc. & Dept. of Computer Sc. & Engg Engg., .,
Indian Institute of Technology Kharagpur Indian Institute of Technology Kharagpur
Dept. of CSE, IIT KGP
Main Features
Main Features
• • Table Computation Table Computation
– – The routing tables must be computed when the network is The routing tables must be computed when the network is 
initialized and must be brought up initialized and must be brought up- -to to- -date if the topology of date if the topology of 
the network changes the network changes
• • Packet Forwarding Packet Forwarding
– – When a packet is to be sent through the network, it must be When a packet is to be sent through the network, it must be 
forwarded using the routing tables forwarded using the routing tables
Dept. of CSE, IIT KGP
Performance Issues
Performance Issues
Correctness Correctness: : The algorithm must deliver every packet to its The algorithm must deliver every packet to its 
ultimate destination ultimate destination
Complexity Complexity: : The algorithm for the computation of the tables The algorithm for the computation of the tables 
must use as few messages, time, and storage as possible must use as few messages, time, and storage as possible
Efficiency Efficiency: : The algorithm must send packets through The algorithm must send packets through good good
paths paths 
Robustness Robustness: : In the case of a topological change, the algorithm In the case of a topological change, the algorithm 
updates the routing tables appropriately updates the routing tables appropriately
Fairness Fairness: : The algorithm must provide service to every user in The algorithm must provide service to every user in 
the same degree the same degree
Dept. of CSE, IIT KGP
Good paths …
Good paths …
Minimum hop Minimum hop: : The cost of a path is the number of hops The cost of a path is the number of hops
Shortest path Shortest path: : Each channel has a non Each channel has a non- -negative cost negative cost – – the path the path 
cost is the sum of the cost of the edges. Packets are routed cost is the sum of the cost of the edges. Packets are routed 
along shortest paths. along shortest paths.
Minimum delay/congestion Minimum delay/congestion: : The bandwidth of a path is the The bandwidth of a path is the 
minimum among the bandwidths of the channels on that path. minimum among the bandwidths of the channels on that path. 
Most robust path Most robust path: : Given the probability of packet drops in each Given the probability of packet drops in each 
channel, packets are to be routed along the most reliable channel, packets are to be routed along the most reliable 
paths. paths. 
Page 5


Dept. of CSE, IIT KGP
Routing Algorithms
Routing Algorithms
CS60002: CS60002: Distributed Systems Distributed Systems
Pallab Pallab Dasgupta Dasgupta
Dept. of Computer Sc. & Dept. of Computer Sc. & Engg Engg., .,
Indian Institute of Technology Kharagpur Indian Institute of Technology Kharagpur
Dept. of CSE, IIT KGP
Main Features
Main Features
• • Table Computation Table Computation
– – The routing tables must be computed when the network is The routing tables must be computed when the network is 
initialized and must be brought up initialized and must be brought up- -to to- -date if the topology of date if the topology of 
the network changes the network changes
• • Packet Forwarding Packet Forwarding
– – When a packet is to be sent through the network, it must be When a packet is to be sent through the network, it must be 
forwarded using the routing tables forwarded using the routing tables
Dept. of CSE, IIT KGP
Performance Issues
Performance Issues
Correctness Correctness: : The algorithm must deliver every packet to its The algorithm must deliver every packet to its 
ultimate destination ultimate destination
Complexity Complexity: : The algorithm for the computation of the tables The algorithm for the computation of the tables 
must use as few messages, time, and storage as possible must use as few messages, time, and storage as possible
Efficiency Efficiency: : The algorithm must send packets through The algorithm must send packets through good good
paths paths 
Robustness Robustness: : In the case of a topological change, the algorithm In the case of a topological change, the algorithm 
updates the routing tables appropriately updates the routing tables appropriately
Fairness Fairness: : The algorithm must provide service to every user in The algorithm must provide service to every user in 
the same degree the same degree
Dept. of CSE, IIT KGP
Good paths …
Good paths …
Minimum hop Minimum hop: : The cost of a path is the number of hops The cost of a path is the number of hops
Shortest path Shortest path: : Each channel has a non Each channel has a non- -negative cost negative cost – – the path the path 
cost is the sum of the cost of the edges. Packets are routed cost is the sum of the cost of the edges. Packets are routed 
along shortest paths. along shortest paths.
Minimum delay/congestion Minimum delay/congestion: : The bandwidth of a path is the The bandwidth of a path is the 
minimum among the bandwidths of the channels on that path. minimum among the bandwidths of the channels on that path. 
Most robust path Most robust path: : Given the probability of packet drops in each Given the probability of packet drops in each 
channel, packets are to be routed along the most reliable channel, packets are to be routed along the most reliable 
paths. paths. 
Dept. of CSE, IIT KGP
Destination
Destination
-
-
based Forwarding
based Forwarding
// A packet with destination d was received or generated at node // A packet with destination d was received or generated at node u u
if if d = u d = u
then then deliver the packet locally deliver the packet locally
else else send the packet to send the packet to table_lookup table_lookup
u u
( (d d) )
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!