Shortest Path routing Each link has a cost that reflects The length of the link Delay on the link Congestion ss cost Cost may change with time The length of the route is the sum of the costs along the route The shortest path is the path with minimum length Shortest Path algorithms Bellman-Ford: centralized and distributed versions Dijkstra’ s algorithm Many othersShortest Path routing • Each link has a cost that reflects – The length of the link – Delay on the link – Congestion – $$ cost • Cost may change with time • The length of the route is the sum of the costs along the route • The shortest path is the path with minimum length • Shortest Path algorithms – Bellman-Ford: centralized and distributed versions – Dijkstra’s algorithm – Many others Eytan Modiano Slide 4