[RAM] IDR tutorial and shortest path

[Iljitsch van Beijnum <iljitsch at muada.com>]

Geoff,

Some musings about shortest path determination algorithms that came  
to mind while listening to your IDR tutorial this afternoon. I think  
that they're relevant for a wider audience so I'm CCing the RAM list.

But first: Bellman wrote a paper in 1956:

http://stinet.dtic.mil/oai/oai? 
&verb=getRecord&metadataPrefix=html&identifier=AD0606258

You can even buy it from the RAND corporation half a century later:

http://www.rand.org/pubs/papers/P1000/

[explanation of both algorithms, skip if known]

The Bellman-Ford algorithm and the Dijkstra / shortest path first  
algorithm are often presented as two different approaches to routing.  
I recently had occasion to read up on those algorithms, and in their  
pure form, they actually do the exact same thing: determine the  
shortest path from a certain starting point to another point or all  
other points. I.e., the problem that they both solve is the "shortest  
path" problem.

The Bellman-Ford approach is communicate known information to  
neighbors and iterate this process until all information has  
propagated everywhere, where the number of iterations is the maximum  
number of hops, either in the topology or supported by the protocol  
executing the algorithm.

Dijkstra's algorithm starts at the starting point and then hunts for  
short paths from known places towards yet unknown places or over yet  
unused links. Hence the name "shortest path first".

[/end explanation]

End result: both algorithms do the exact same thing, but the SPF  
algorithm is much faster than the Bellman-Ford algorithm, under the  
same circumstances.

So why do we use Bellman-Ford if it's so much slower? Because it is  
essentially a distributed algorithm where each node only has to do a  
simple computation over the information that is available locally at  
that point in time, while the SPF optimizations pretty much require  
all information to be present before the algorithm can be run.

So in the case of distance vector or distance path routing protocols,  
where only the minimum information required to perform routing is  
exchanged, Bellman-Ford is great, because you can simply do an  
iteration as new information becomes available. The downside is the  
count to infinity problem, which leads to loops in distance vector  
and the exploration of all loopfree paths in order of increasing  
length in distance path. And as we've learned with BGP, delays in  
sending updates slow down convergence while having multiple parallel  
paths tends to amplify updates, causing additional unnecessary  
iterations of the route selection process.

In link state protocols, all information is flooded to all nodes  
which then all individually solve the shortest path problem. This  
means that a fast algorithm like Dijkstra's SPF is preferable over a  
slower one like Bellman-Ford, and the presence of all information  
before the algorithm is executed nicely fulfills the requirements of  
SPF.

So the important difference is link state on the one hand versus  
distance vector and distance path on the other, not Dijkstra versus  
Bellman-Ford.

_______________________________________________
RAM mailing list
RAM at iab.org
https://www1.ietf.org/mailman/listinfo/ram