Algebra and algorithms for QoS path computation and hop-by-hop routing in the Internet
Tóm tắt
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 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 each node to compute lexicographic-optimal paths, in general.
Từ khóa
#Algebra #Quality of service #Delay #Circuits #Computer networks #Web and internet services #Routing protocols #Telecommunication traffic #Telecommunication computing #ThroughputTài liệu tham khảo
10.1109/35.809382
10.1109/49.536364
10.1109/INFCOM.2000.832180
10.1109/ICNP.1997.643714
apostolopoulos, 1998, quality-of-service based routing: a performance perspective, Proc ACM SIGCOMM 98, 17
shaikh, 1998, efficient precomputation of quality-of-service routes, Proc 7th Int Workshop Network and Operating System Support for Digital Audio and Video, 15
10.1109/INFCOM.1999.751454
hao, 2000, on scalable qos routing: performance evaluation of topology aggregation, Proc IEEE Infocom 2000, 147
10.1007/BF01386390
10.1109/PRMNET.1997.638876
10.1109/90.222913
10.1109/26.48894
10.1098/rsta.1991.0129
10.1109/INFCOM.1997.635118
moy, 1998, OSPF Anatomy of an Internet Routing Protocol
10.1109/90.650138
10.1109/49.464712
10.1109/65.752646
10.1109/65.397043
10.1109/TCOM.1977.1093711
10.1109/4236.769425
10.1109/65.793691
10.1007/978-0-387-35388-3_15
metz, 2000, differentiated services, IEEE Multimedia, 7, 84
10.1109/65.768484
cormen, 1990, Introduction to Algorithms
carrécarre, 1979, Graphs and Networks
vutukury, 1999, a simple approximation to minimum-delay routing, Proc ACM SIGCOMM 99, 227
10.1007/BF02592101