Abstract

We know and love shortest-path algorithms. But these only represent the most well-behaved corner of a wide class of methods for finding “good” paths. The current and future Internet gives examples of the remainder of this class, but at the same time, shows that correct solutions can sometimes be obtained even in these adverse conditions.

This talk will present work on the correctness of a best-path algorithm that has the following characteristics:

• Asynchronously safe; tolerant of fair message loss and reordering, but always converging to a unique fixed point.
• Can find multiple best paths for each source-destination pair.
• Allows arbitrary filtering of disallowed paths.
• Allows neighbours to have incompatible preferences (so the fixed point is a Nash equilibrium rather than a global optimum).
• Allows per-adjacency refinements to path preferences.

On the down side, there is no a priori upper bound on execution time without making additional restrictions.