On Algorithms for Quickest Paths under Different Routing Modes

摘要

In the emerging networks, routing may be performed at various levels of the TCP/IP stack, such as datagram, TCP stream or application level, with possibly different message forwarding modes. We formulate an abstract quickest path problem for the transmission of a message of size σ 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 six modes for the message forwarding at the nodes reflecting the mechanisms such as circuit switching, store and forward, and their combinations. For each of first five modes, we present O(m~2 + mn log n) time algorithms to compute the quickest path for a given message size σ. For the last mode, the quickest path can be computed in O(m + n log n) time.