Distance Vector & Link state Routing Algorithm

Difference between Distance Vector & Link State routing algorithms

1. COMPARE DISTANCE VECTOR & LINK STATE ROUTING ALGORITHM MADE BY MOHIT AGARWAL – 161080107026 SUBJECT – COMPUTER NETWORKS

2. DISTANCE VECTOR ROUTING Each router maintains a routing table, where each node in the network has an entry in the table. Each entry contains two parts, the outgoing line for the destination (node) and the distance (time, cost) to the destination. Each router knows the distance to its neighbors. In a certain period of time, each router sends the table to each of its neighbors. When a router receives a table from each of its neighbors, it updates its routing table, determines the new minimum distance and the outgoing link for the destination.

3. Routing table for A To cost via A - B 12 B C 25 B D 40 B E 14 E F 23 E G 18 B H 17 J I 21 E J 9 J K 24 J L 29 J EXAMPLE

4. A B C D E A B C D E # # # # 1 2 3 4 1 # # # 3 2 3 4 1 2 # # 3 4 3 4 1 2 3 # 5 4 5 4 1 2 3 4 5 6 5 6 7 6 7 6 7 8 7 8 : : : : Count to infinity problem shows that good news propagates fast, bad news propagates slow. COUNT TO INFINITY

5. LINK STATE ROUTING In link state routing each node follows certain steps : Discover its neighbors Measure the cost to its neighbors Broadcast a packet with this information to all other nodes Compute the shortest paths to every other router

6. 1. Each router establishes a relationship with its neighbors 2.Each router generates Link State Advertisements (LSAs) which are distributed to all routers LSA = (link id, state of the link, cost, neighbors of the link) 3. Each router maintains a database of all received LSAs (topological database or link state database), which describes the network has a graph with weighted edges 4. Each router uses its link state database to run a shortest path algorithm (Dijkstra's algorithm) to produce the shortest path to each network BASIC PRINCIPLES

7. Received LSAs IP Routing Table Dijkstra’s Algorithm Link State Database LSAs are flooded to other interfaces OPERATION

8. DISTANCE VECTOR ROUTING LINK STATE ROUTING It is used to calculate shortest cost path. It is used to calculate link state cost. Sends message to their neighbors. (As we see in count to infinity problem) Sends message to every other node in the network. It is decentralized routing algorithm. It is centralized global routing algorithm. Sends larger updates only to neighboring routers. Sends small updates everywhere. Requires less CPU power and less memory space. Requires more CPU power and more memory space. Simple to implement and support. Expensive to implement and support.

9. With distance vector routing, each node has information only about the next hop: Node A: To reach F go to B Node B: To reach F go to D Node D: To reach F go to E Node E: Go directly to F Distance vector routing makes poor routing decisions if directions are not completely correct (e.g., because a node is down). If parts of the directions incorrect, the routing may be incorrect until the routing algorithms has re-converged. A B C D E F DVR vs. LSR

10. In link state routing, each node has a complete map of the topology If a node fails, each node can calculate the new route Difficulty: All nodes need to have a consistent view of the network A B C D E F A B C D E F A B C D E F A B C D E F A B C D E F A B C D E F A B C D E F

11. THANKYOU