Abstract: Prompted by the advent of quality-of-service 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 generalization of E.W. Dijkstra's algorithm (see Numer. Math., vol.1, p.269-71, 1959). 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...
(read more)
Topics: 
Algorithm
Computer network