- Internet Routing
- Shortest-Path Graph Problems
- Distance-Vector Routing and the Bellman–Ford Algorithm
- Dijkstra and Link-State Routing
- Conclusion
Distance-Vector Routing and the BellmanFord Algorithm
The basic idea behind RIP is for each router to maintain an estimate of distance (not geographic distance, but cumulative transmission cost) to all other routers and to periodically compare notes with its neighbors. If a router learns of a shorter path to some destination from one of its neighbors, it will update its distance record to that destination and change its routing table to send packets to that destination via that neighbor. After enough time, the estimated distances maintained in this distributed fashion by multiple routers are guaranteed to converge to the true distance, therefore giving the routers accurate information about the best path. The RIP is a distributed form of the BellmanFord single-source shortest-paths algorithm. In this article, I will skip forward to implementing the OSPF protocol.