For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 2004/04/01
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)>>
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.