Djikstra's Link State Routing Algorithm & Bellman Ford

University:
York University
Course:
AP/ITEC 1610 | Introduction to Computer Programming
Academic year:

2023
Views:

228

Pages:

3
Author:

Nick T.

Dijkstra's Link State Routing Algorithm: Centralized/Global: Link cost is known to all nodes. Computes: Least cost paths from one node ("source") to all other nodes, providing a forwarding table for that node. Iterative: After k iterations, knows the least cost path to k destinations. Notation: c(x,y): Direct link cost from x to y (0 if not direct neighbors) D(v): Current estimate of the cost of the least-cost-path from the source to destination 'v' p(v): Predecessor node along the path from the source to 'v' N': Set of nodes whose least cost path is definitely known Routing Algorithm: Initialization: Assign a distance value to every node in the network. Initial node = 0, all others to ∞. Create an empty set to keep track of visited nodes. Create a priority queue to store nodes and their distance from the source node. Select Source Node: Choose the source node and set its distance to 0. Main Loop: While the priority queue is not empty: Extract the node with the shortest distance from the priority queue. This node is now considered visited. Update the distance of its adjacent nodes by considering the sum of the current distance to the extracted node and the link cost to the adjacent node. Dijkstra's Algorithm: Steps: Initialize distances and previous nodes. Select the source node and set its distance to 0. Repeat until all nodes are visited or the destination node is reached: Find the node with the smallest distance that hasn't been visited. Update the distances of its neighbors if the new calculated distance is smaller. Output: Shortest path and its calculated distance. Bellman-Ford Algorithm: Description: Each node periodically sends its distance vector estimate to its neighbors. Neighbors use this information to update their distance vectors using the Bellman-Ford equation. Notation: x: Node y: Neighbor v: Destination c: Direct link cost D_x(y): Estimated cost from node x to node y Computation at Nodes: D_x(y) = min{c(x,v) + D_v(y) for all v}