Link State Routing Part-2
Duration: 8 min
This video lesson is available to enrolled students.
AI Summary
An AI-generated summary of this video lecture.
This lecture explains the process of building routing tables in link state routing protocols. The instructor outlines four essential actions: creating Link State Packets (LSPs), disseminating them via flooding, forming a shortest path tree, and calculating the final routing table. The session then transitions to a detailed explanation of Dijkstra's algorithm, which is used to construct the shortest path tree. Visual aids include network diagrams, cost matrices, and step-by-step algorithm iterations to illustrate how nodes determine the least-cost paths to all other nodes in the network.
Chapters
0:00 – 2:00 00:00-02:00
The instructor introduces the topic "Building Routing Tables" by listing four required actions in link state routing. The slide displays a numbered list: 1. Creation of Link State Packets (LSPs), 2. Dissemination via flooding, 3. Formation of a shortest path tree, and 4. Calculation of a routing table. He explains that each node must create an LSP showing the state of its links. The slide also features a network diagram with nodes labeled A through G and associated cost tables, illustrating the initial state before routing tables are fully built. The instructor emphasizes that these steps ensure every node has the least-cost path to every other node. He points to the text "link state packet (LSP)" and "flooding" to highlight key terms. The slide header reads "Building Routing Tables" and the first bullet point states "In link state routing, four sets of actions are required to ensure that each node has the routing table showing the least-cost node to every other node."
2:00 – 5:00 02:00-05:00
The lecture shifts to the "Formation of Shortest Path Tree" using Dijkstra's Algorithm. The slide text states that after receiving all LSPs, a node has the topology but needs a tree to find shortest paths. Definitions are provided: a tree has a root and single routes to other nodes, while a shortest path tree ensures the path between the root and any other node is the shortest. The instructor points to a weighted graph diagram and a "Link state database" matrix, which shows costs between nodes (e.g., A to B is 2, B to C is 5). He explains that this database is a two-dimensional array where each cell defines the cost of the corresponding link, serving as the input for the algorithm. The matrix includes values like infinity (∞) for non-connected nodes. The slide text explicitly defines a tree: "A tree is a graph of nodes and links; one node is called the root. All other nodes can be reached from the root through only one single route."
5:00 – 7:53 05:00-07:53
The instructor details the execution of Dijkstra's algorithm. The slide text explains that the algorithm divides nodes into "tentative" and "permanent" sets. It finds neighbors of a current node, makes them tentative, and makes them permanent if they pass criteria. Visuals show a sequence of diagrams labeled "Initialization" through "Iteration 6". The instructor explains that cumulative cost from the root to each node is tracked. He walks through the iterations, showing how the path is built step-by-step, updating costs and marking nodes as permanent until all nodes are reached. The final iteration shows the complete shortest path tree rooted at node A. The legend indicates "Root node", "Node in the path", and "Potential path". The slide text states: "To find the shortest path in each step, we need the cumulative cost from the root to each node, which is shown next to the node."
The video provides a comprehensive overview of link state routing table construction. It begins with the high-level workflow of LSP creation and flooding, then drills down into the specific mathematical process of Dijkstra's algorithm. By combining theoretical definitions with visual step-by-step iterations, the lecture clarifies how a node transforms raw topology data into a functional routing table that minimizes path costs. The progression from LSP creation to the final routing table calculation is clearly mapped out. The instructor uses the network diagram with nodes A-G to demonstrate the practical application of the algorithm, showing how costs are updated in each iteration.