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.
【 预 览 】
Files | Size | Format | View |
---|---|---|---|
885861.pdf | 946KB | download |