Quickest Paths for Different Network Router Mechanisms.

Rao, N. S. V. ; Grimmell, W. C. ; Radhakrishnan, S. ; Bang, Y. C.

Technical Information Center Oak Ridge Tennessee

关键词: Network analysis;    Routing;    Algorithms;    Internet;    Computer networks;   

RP-ID  :  DE2001769289

学科分类：工程和技术（综合）

美国|英语

来源: National Technical Reports 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. The authors consider four basic modes and two variations for the message delivery at the nodes reflecting the mechanisms such as circuit switching, Internet protocol, and their combinations. For each of the first three modes, they 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.