Algebra and algorithms for QoS path computation and hop-by-hop routing in the Internet

Abstract

Prompted by the advent of QoS routing in the Internet, we investigate the properties that path weight functions must have so that hop-by-hop routing is possible and optimal paths can be computed with a generalized Dijsktra's (1959) algorithm. For this purpose we define an algebra of weights which contains a binary operation, for the composition of link weights into path weights, and an order relation. Isotonicity is the key property of the algebra. It states that the order relation between the weights of any two paths is preserved if both of them are either prefixed or appended by a common, third, path. We show that isotonicity is both necessary and sufficient for a generalized Dijkstra's algorithm to yield optimal paths. Likewise, isotonicity is also both necessary and sufficient for hop-by-hop routing. However, without strict isotonicity, hop by-hop routing based on optimal paths may produce routing loops. They are prevented if every node computes what we call lexicographic-optimal paths. These paths can be computed with an enhanced Dijkstra's algorithm that has the same complexity as the standard one. Our findings are extended to multipath routing as well. As special cases of the general approach, we conclude that shortest-widest paths can neither be computed with a generalized Dijkstra's algorithm nor can packets be routed hop-by-hop over those paths. In addition, loop free hop by hop routing over widest and widest-shortest paths requires that each node computes lexicographic-optimal paths, in general.