Back to index
A Loop-Free Extended Bellman-Ford Routing Protocol Without Bouncing Effect
Cheng, Riley, and Kumar
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.
- 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
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
(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.)
A better algorithm for distance-vector routing.
Routing loops really do happen quite often; assymetric routing should
only make them worse, I'd expect.
All theory; no implementation.
Also, distance-vector routing is inherently painful in large networks.
Back to index