On Algorithms for Quickest Paths under Different Routing Modes

Nageswara S.V. RAO  William C. GRIMMELL  Young-Cheol BANG  Sridhar RADHAKRISHNAN  

IEICE TRANSACTIONS on Communications   Vol.E87-B    No.4    pp.1002-1006
Publication Date: 2004/04/01
Online ISSN: 
Print ISSN: 0916-8516
Type of Manuscript: LETTER
Category: Fundamental Theories
quickest path problem,  message forwarding mechanisms,  end-to-end delay,  path computation,  

Full Text: PDF(142.5KB)>>
Buy this Article

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( m2 + 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.