OSPF Dijkstra Algorithm in Link State Routing
"Learn about the operation of a link state routing protocol using Dijkstra's shortest path algorithm. Explore examples and calculate shortest paths for nodes in the network. Understand how LSAs are flooded and IP routing tables updated to optimize routing efficiency."
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Open Shortest Path First (OSPF) Appendix: Dijkstra s Algorithm ECE 461 Professor Jorg Liebeherr 1
Operation of a link state routing protocol Operation of a link state routing protocol Dijkstra s Algorithm Received LSAs Link State Database IP Routing Table LSAs are flooded to other interfaces 2
Dijkstras shortest path algorithm for a graph Input:Graph(N,E)with Output: the set of nodes andE N N the set of edges link cost(dvw = if(v,w) E, dvv = 0) source node. cost of the least-cost path from node s to each other node N dvw s Dn M = {s}; for each n M Dn = dsn; while (M all nodes) do Find w M for which Dw = min{Dj ; j M}; Add w to M; for each n M Dn = minw [ Dn, Dw + dwn ]; Update route; enddo 3
Example Example 5 2 3 3 5 2 2 1 1 6 3 1 2 4 5 1 4
5 Example Example 2 3 3 5 2 2 1 1 6 3 Example: Calculate the shortest paths for node 1. 1 2 4 5 1 IterationM D2 D3 D4 D5 D6 Init 5
Example Example Result is a shortest-path tree rooted at node 1: 2 3 1 6 4 5 Node Next hop Cost ... which results in the routing table (of node 1): 6
