Quickest Paths for Different Network Router Mechanisms

[摘要] 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.

[发布日期] 2000-10-16 [发布机构] Oak Ridge National Laboratory

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