UC Santa Cruz

Algorithms for finding the shortest path between two nodes in a graph have been heavily studied for decades. Half a century ago solutions were found for the specific class of problems that involves finding the path of least length, when edges are weighted with a single metric. For example, although the Bellman-Ford and Dijkstra algorithms use different methodologies, both techniques depend on a single metric where the lengths of paths are found by adding path weights in the conventional way. The situation becomes more complicated when multiple metrics or single metrics other than simple Euclidean distance are involved. In these cases, the definition of ``shortest,'' or ``best'' is not straightforward. In addition, it is not always a simple matter to verify that packets in a distributed network are forwarded on best paths that are guaranteed loop-free.

We call the set of edge weights, plus the rules that determine how paths are concatenated and compared, the path algebra. We find that the structure of a path algebra is the key to understanding how packets will be forwarded in a distributed network; specifically whether they will be forwarded on best, loop-free paths. This is independent of any path-finding algorithm. We show that ``best'' paths and loop-free paths are separate (albeit subtly related) properties, that are dependent on whether or not a path algebra is monotonic and strictly bounded. We examine examples of path algebras that possess various combinations of those two properties in order to illustrate how they affect the construction of forwarding paths. Finally, we prove that if a path algebra is monotonic and strictly bounded, it is guaranteed to produce forwarding paths that are best and loop-free.

Previous works have introduced these ideas in separate contexts. We provide a consistent framework and prove general concepts that have only been introduced or discussed in special cases.