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!