Computing Path Tables for Quickest Multipaths In Computer Networks

Grimmell, W.C.

Oak Ridge National Laboratory

关键词: Time Dependence;    Computer Networks;    Algorithms;    Data Transmission;    99 General And Miscellaneous//Mathematics, Computing, And Information Science;   

DOI  :  10.2172/885861
RP-ID  :  ORNL/TM-2004/3
RP-ID  :  DE-AC05-00OR22725
RP-ID  :  885861

美国|英语

来源: UNT Digital Library

【 摘 要 】

We consider the transmission of a message from a source node to a terminal node in a network with n nodes and m links where the message is divided into parts and each part is transmitted over a different path in a set of paths from the source node to the terminal node. Here each link is characterized by a bandwidth and delay. The set of paths together with their transmission rates used for the message is referred to as a multipath. We present two algorithms that produce a minimum-end-to-end message delay multipath path table that, for every message length, specifies a multipath that will achieve the minimum end-to-end delay. The algorithms also generate a function that maps the minimum end-to-end message delay to the message length. The time complexities of the algorithms are O(n{sup 2}((n{sup 2}/logn) + m)min(D{sub max}, C{sub max})) and O(nm(C{sub max} + nmin(D{sub max}, C{sub max}))) when the link delays and bandwidths are non-negative integers. Here D{sub max} and C{sub max} are respectively the maximum link delay and maximum link bandwidth and C{sub max} and D{sub max} are greater than zero.