On routing algorithms with end-to-end delay guarantees

Nageswara S.V. Rao; Stephen G. Batsell

doi:10.1109/ICCCN.1998.739912

On routing algorithms with end-to-end delay guarantees

Nageswara S.V. Rao, Stephen G. Batsell

Autonomous and Complex Systems

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

6 Scopus citations

Abstract

We consider the transmission of a message of size r from a source to a destination over a computer network with n nodes and m links. There are three sources of delays: (a) propagation delays along the links, (b) delays due to bandwidth availability on the links, and (c) queuing delays at the intermediate nodes. First, we consider that the delays on various links and nodes are given as functions of the message size. If the delay in (b) is a non-increasing function of the bandwidth, we propose O(m² + mn log n) time algorithm to compute a path with the minimum end-to-end delay for any given message size r. We then consider that the queuing delay in (c) is a random variable correlated with the message size according to an unknown distribution. At each node, the measurements of queuing delays and message sizes are available. We propose two algorithms to compute paths whose delays are close to optimal delays with a high probability, irrespective of the distribution of the delays.

Original language	English
Title of host publication	Proceedings - 7th International Conference on Computer Communications and Networks, ICCCN 1998
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	162-167
Number of pages	6
ISBN (Electronic)	0818690143, 9780818690143
DOIs	https://doi.org/10.1109/ICCCN.1998.739912
State	Published - 1998
Event	7th International Conference on Computer Communications and Networks, ICCCN 1998 - Lafayette, United States Duration: Oct 15 1998 → Oct 15 1998

Publication series

Name	Proceedings - 7th International Conference on Computer Communications and Networks, ICCCN 1998
Volume	1998-October

Conference

Conference	7th International Conference on Computer Communications and Networks, ICCCN 1998
Country/Territory	United States
City	Lafayette
Period	10/15/98 → 10/15/98

Funding

This research is sponsored by the Laboratory Directed Research and Development Program of Oak Ridge National Laboratory. managed by Lockheed Martin Energy Research Corp. for the U. S. Department of Energy under Contract No. DE-XC03-96OR22464.

Access to Document

10.1109/ICCCN.1998.739912

Cite this

Rao, N. S. V., & Batsell, S. G. (1998). On routing algorithms with end-to-end delay guarantees. In Proceedings - 7th International Conference on Computer Communications and Networks, ICCCN 1998 (pp. 162-167). Article 739912 (Proceedings - 7th International Conference on Computer Communications and Networks, ICCCN 1998; Vol. 1998-October). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICCCN.1998.739912

@inproceedings{e4c32a81a0f84e7f85f8d8304d405639,

title = "On routing algorithms with end-to-end delay guarantees",

abstract = "We consider the transmission of a message of size r from a source to a destination over a computer network with n nodes and m links. There are three sources of delays: (a) propagation delays along the links, (b) delays due to bandwidth availability on the links, and (c) queuing delays at the intermediate nodes. First, we consider that the delays on various links and nodes are given as functions of the message size. If the delay in (b) is a non-increasing function of the bandwidth, we propose O(m2 + mn log n) time algorithm to compute a path with the minimum end-to-end delay for any given message size r. We then consider that the queuing delay in (c) is a random variable correlated with the message size according to an unknown distribution. At each node, the measurements of queuing delays and message sizes are available. We propose two algorithms to compute paths whose delays are close to optimal delays with a high probability, irrespective of the distribution of the delays.",

author = "Rao, {Nageswara S.V.} and Batsell, {Stephen G.}",

note = "Publisher Copyright: {\textcopyright} 1998 IEEE.; 7th International Conference on Computer Communications and Networks, ICCCN 1998 ; Conference date: 15-10-1998 Through 15-10-1998",

year = "1998",

doi = "10.1109/ICCCN.1998.739912",

language = "English",

series = "Proceedings - 7th International Conference on Computer Communications and Networks, ICCCN 1998",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "162--167",

booktitle = "Proceedings - 7th International Conference on Computer Communications and Networks, ICCCN 1998",

}

Rao, NSV & Batsell, SG 1998, On routing algorithms with end-to-end delay guarantees. in Proceedings - 7th International Conference on Computer Communications and Networks, ICCCN 1998., 739912, Proceedings - 7th International Conference on Computer Communications and Networks, ICCCN 1998, vol. 1998-October, Institute of Electrical and Electronics Engineers Inc., pp. 162-167, 7th International Conference on Computer Communications and Networks, ICCCN 1998, Lafayette, United States, 10/15/98. https://doi.org/10.1109/ICCCN.1998.739912

On routing algorithms with end-to-end delay guarantees. / Rao, Nageswara S.V.; Batsell, Stephen G.
Proceedings - 7th International Conference on Computer Communications and Networks, ICCCN 1998. Institute of Electrical and Electronics Engineers Inc., 1998. p. 162-167 739912 (Proceedings - 7th International Conference on Computer Communications and Networks, ICCCN 1998; Vol. 1998-October).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On routing algorithms with end-to-end delay guarantees

AU - Rao, Nageswara S.V.

AU - Batsell, Stephen G.

PY - 1998

Y1 - 1998

N2 - We consider the transmission of a message of size r from a source to a destination over a computer network with n nodes and m links. There are three sources of delays: (a) propagation delays along the links, (b) delays due to bandwidth availability on the links, and (c) queuing delays at the intermediate nodes. First, we consider that the delays on various links and nodes are given as functions of the message size. If the delay in (b) is a non-increasing function of the bandwidth, we propose O(m2 + mn log n) time algorithm to compute a path with the minimum end-to-end delay for any given message size r. We then consider that the queuing delay in (c) is a random variable correlated with the message size according to an unknown distribution. At each node, the measurements of queuing delays and message sizes are available. We propose two algorithms to compute paths whose delays are close to optimal delays with a high probability, irrespective of the distribution of the delays.

AB - We consider the transmission of a message of size r from a source to a destination over a computer network with n nodes and m links. There are three sources of delays: (a) propagation delays along the links, (b) delays due to bandwidth availability on the links, and (c) queuing delays at the intermediate nodes. First, we consider that the delays on various links and nodes are given as functions of the message size. If the delay in (b) is a non-increasing function of the bandwidth, we propose O(m2 + mn log n) time algorithm to compute a path with the minimum end-to-end delay for any given message size r. We then consider that the queuing delay in (c) is a random variable correlated with the message size according to an unknown distribution. At each node, the measurements of queuing delays and message sizes are available. We propose two algorithms to compute paths whose delays are close to optimal delays with a high probability, irrespective of the distribution of the delays.

UR - http://www.scopus.com/inward/record.url?scp=33749205844&partnerID=8YFLogxK

U2 - 10.1109/ICCCN.1998.739912

DO - 10.1109/ICCCN.1998.739912

M3 - Conference contribution

AN - SCOPUS:33749205844

T3 - Proceedings - 7th International Conference on Computer Communications and Networks, ICCCN 1998

SP - 162

EP - 167

BT - Proceedings - 7th International Conference on Computer Communications and Networks, ICCCN 1998

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 7th International Conference on Computer Communications and Networks, ICCCN 1998

Y2 - 15 October 1998 through 15 October 1998

ER -

Rao NSV, Batsell SG. On routing algorithms with end-to-end delay guarantees. In Proceedings - 7th International Conference on Computer Communications and Networks, ICCCN 1998. Institute of Electrical and Electronics Engineers Inc. 1998. p. 162-167. 739912. (Proceedings - 7th International Conference on Computer Communications and Networks, ICCCN 1998). doi: 10.1109/ICCCN.1998.739912

On routing algorithms with end-to-end delay guarantees

Abstract

Publication series

Conference

Funding

Access to Document

Other files and links

Fingerprint

Cite this