Link State Routing Protocol presentation.pptx

presentation

1. Link State Routing Protocol

2. 20XX presentation title 2 Link-State Routing

3. Broadcasting the Link State:

4. 20XX presentation title 4

5. 20XX presentation title 5

6. 20XX presentation title 6 Iterative algorithm After k iterations, know least-cost path to k nodes S : nodes whose least-cost path definitively known Initially, S = {u} where u is the source node Add one node to S in each iteration D(v) : current cost of path from source to node v Initially, D(v) = c(u,v) for all nodes v adjacent to u … and D(v) = ∞ for all other nodes v Continually update D(v) as shorter paths are learned

7. Dijsktra’s Algorithm

8. 20XX presentation title 8

9. 20XX presentation title 9 3 2 2 1 1 4 1 4 5 3 3 2 2 1 1 4 1 4 5 3 3 2 2 1 1 4 1 4 5 3

10. 20XX presentation title 10 Shortest-path tree from u link

11. 20XX presentation title 11 Convergence

12. 20XX presentation title 12

13. 20XX presentation title 13

14. 20XX presentation title 14 Overhead of link-state routing Flooding link-state packets throughout the network Running Dijkstra’s shortest-path algorithm Introducing hierarchy through “areas” Area 1 Area 0 Area 3

15. 20XX presentation title 15

16. thank you