- Internet Routing
- Shortest-Path Graph Problems
- Distance-Vector Routing and the Bellman–Ford Algorithm
- Dijkstra and Link-State Routing
Shortest-Path Graph Problems
It turns out that this routing problem corresponds to the shortest-path graph problem. To find the best path between two routers, you need to find the path with the least cumulative transmission delay. Abstractly, the cumulative transmission delay is referred to as the path weight; a shortest path is defined to be a path whose path weight is less than or equal to the path weight of any other path between the source and destination vertices. The single-pair shortest-path problem is to find the shortest path between two vertices. The single-source shortest-path problem is to find a shortest path from a source vertex to every other vertex in the graph. The set of shortest paths emanating from the source vertex is called a shortest-path tree. The all-pairs shortest-paths problem is to find a shortest path from every vertex to every other vertex in the graph.
It so happens that no algorithms for solving the single-pair problem are asymptotically faster than algorithms for solving the single-source problem. In any event, to construct a routing table, each router must figure out the shortest paths to all the other routers, so you need to solve the single-source problem. The BGL includes two classical methods for solving the single-source problem: Dijkstra's algorithm and the BellmanFord algorithm. The BGL also includes Johnson's algorithm for all-pairs shortest paths.
One of the first Internet routing protocols to be defined was the Routing Information Protocol (RIP) (see RFC 1058), also known as distance-vector routing.