Chapter 2

Routing Algorithms: Shortest Path, Widest Path, and Spanning Tree

“If everybody minded their own business,” the Duchess said in a hoarse growl, “the world would go round a deal faster than it does.”

Lewis Carroll in Alice in Wonderland


In this chapter, we first describe two classes of routing algorithms: shortest path routing and widest path routing. They appear in network routing in many ways and have played critical roles in the development of routing protocols. For example, shortest path routing is used in IP networks is based on the addition cost property. Widest path routing is used for call routing in circuit-switched networks and MPLS networks and is based on the non-additive concave cost property. Widest ...

Get Network Routing, 2nd Edition now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.