0-7803-7016-3/01/$10.00 ©2001 IEEE 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 algorithm. For this purpose we define an alge-bra 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 general-ized Dijkstra’s algorithm to yield optimal paths. Likewise, isotonicity is also both necessary and sufficient for hop-by-hop routing. However, with-out strict isotonicity, hop-by-hop routing based on optimal paths may pro-duce routing loops. They are prevented if every node computes what we call lexicographic-optimal paths. These paths can be computed with an en-hanced 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 algo-rithm nor can packets be routed hop-by-hop over those paths. In addi-tion, loop-free hop-by-hop routing over widest and widest-shortest paths requires that each node computes lexicographic-optimal paths, in general. I