Quickest Paths for Different Network Router Mechanisms

Rao, NSV

Oak Ridge National Laboratory

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

DOI  :  10.2172/814290
RP-ID  :  ORNL/TM-2000/208
RP-ID  :  AC05-00OR22725
RP-ID  :  814290

美国|英语

来源: UNT Digital Library

【 摘 要 】

The quickest path problem deals with the transmission of a message of size {sigma} from a source to a destination with the minimum end-to-end delay over a network with bandwidth and delay constraints on the links. We consider four basic modes and two variations for the message delivery at the nodes reacting the mechanisms such as circuit switching, Internet protocol, and their combinations. For each of first three modes, we present O(m{sup 2} + mn log n) time algorithm to compute the quickest path for a given message size {sigma}. For the last mode, the quickest path can be computed in O(m + n log n) time.