A Loop-Free Extended Bellman-Ford Routing Protocol Without Bouncing Effect

One-line summary: Routing loops and counting-to-infinity behaviors are possible with distance-vector routing; this paper shows how to eliminate them, with minimal performance hit for the routers.

Overview/Main Points

• Standard algorithm: Bellman-Ford distance vector routing. Each node maintains the shortest distance to all destinations through all of its neighbors. From time to time, each node creates a vector containing the shortest distance to each destination, and sends this vector to its neighbors. Upon receiving a vector from a neighbor, a node updates its minimum distances to all destinations via this neighbor.
• Bad behavior: routing loops. Imagine: A,B,C are connected in a triangle. A's preferred route to C is via B; B's is direct. Now the B->C link fails; B will see that A is advertising a route to C, and so B's new preferred route to C will be via A. So we get the routing loop A->B->A->B->... if A tries to send a packet to C. (Each time a distance vector update is performed, A's and B's perceived distance to C increases; once that perceived distance becomes greater than the weight on the A->C link, the routing loop will fix itself.)
• Bad behavior: counting-to-infinity. Imagine: the A->C link fails before the routing loop fixes itself. Now A's and B's perceived distance to C will increase forever, and the routing loop will never go away.
• Underlying problem: routes can end up going in loops.
• Naive fix: when sending a distance vector update, include the full path to a destination along with that destination's minimum distance. Now when you update your minimum distances based on vectors from neighbors, make sure you don't update in a way that introduces loops.
• Disadvantage: naive fix requires significantly increased communication and memory costs.
• Enhancement: instead of storing the entire (best) path to a destination, just store the penultimate hop in that path. Now you can recover the entire (implicit) path to a destination just by tracing the chain of penultimate hops (e.g. find the penultimate hop, then look at the route to that penultimate hop and find that one that immediately precedes it, etc.); in this way, you can still avoid loops when updating. Gives much better performance.
• Problem: update algorithm becomes incorrect. Imagine: imagine implicit path A->B->C->D->E; now if route B->C changes, then can screw up the longer path. The (bad) end result is that the implicit path to a destination may no longer match the true best distance you have to that destination. They include a small fix to the algorithm to avoid this badness; I don't entirely understand it, but I don't think it's crucial.
• Performance: not much worse than standard Bellman-Ford; can even require less work & communication from the routers. And avoid routing loops or counting-to-infinity. (But can have temporary routing loops if you're unlucky enough to have two separate links fail nearly instantaneously, though this is much less likely in practice, I'd expect.)

Relevance

Flaws