Rapid Routing with Guaranteed Delay Bounds

Sanjoy Baruah

doi:10.1109/RTSS.2018.00012

Rapid Routing with Guaranteed Delay Bounds

Sanjoy Baruah

Department of Computer Science & Engineering

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

13 Scopus citations

Abstract

We consider networks in which each individual link is characterized by two delay parameters: a (usually very conservative) guaranteed upper bound on the worst-case delay, and an estimate of the delay that is typically encountered, across the link. Given a source and destination node on such a network and an upper bound on the end-to-end delay that can be tolerated, the objective is to determine routes they typically experience a small delay, while guaranteeing to respect the specified end-to-end upper bound under all circumstances. We formalize the problem of determining such routes as a shortest-paths problem on graphs, and derive algorithms for solving this problem optimally.

Original language	English
Title of host publication	Proceedings - 39th IEEE Real-Time Systems Symposium, RTSS 2018
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	13-22
Number of pages	10
ISBN (Electronic)	9781538679074
DOIs	https://doi.org/10.1109/RTSS.2018.00012
State	Published - Jan 4 2019
Event	39th IEEE Real-Time Systems Symposium, RTSS 2018 - Nashville, United States Duration: Dec 11 2018 → Dec 14 2018

Publication series

Name	Proceedings - Real-Time Systems Symposium
Volume	2018-December
ISSN (Print)	1052-8725

Conference

Conference	39th IEEE Real-Time Systems Symposium, RTSS 2018
Country/Territory	United States
City	Nashville
Period	12/11/18 → 12/14/18

Keywords

adaptive routing
end-to-end deadlines
on-line algorithm
Real-time routing
shortest paths in graphs

Access to Document

10.1109/RTSS.2018.00012

Cite this

@inproceedings{fa942ee5eac8422f882583d6388a82ef,

title = "Rapid Routing with Guaranteed Delay Bounds",

abstract = "We consider networks in which each individual link is characterized by two delay parameters: a (usually very conservative) guaranteed upper bound on the worst-case delay, and an estimate of the delay that is typically encountered, across the link. Given a source and destination node on such a network and an upper bound on the end-to-end delay that can be tolerated, the objective is to determine routes they typically experience a small delay, while guaranteeing to respect the specified end-to-end upper bound under all circumstances. We formalize the problem of determining such routes as a shortest-paths problem on graphs, and derive algorithms for solving this problem optimally.",

keywords = "adaptive routing, end-to-end deadlines, on-line algorithm, Real-time routing, shortest paths in graphs",

author = "Sanjoy Baruah",

note = "Publisher Copyright: {\textcopyright} 2018 IEEE.; 39th IEEE Real-Time Systems Symposium, RTSS 2018 ; Conference date: 11-12-2018 Through 14-12-2018",

year = "2019",

month = jan,

day = "4",

doi = "10.1109/RTSS.2018.00012",

language = "English",

series = "Proceedings - Real-Time Systems Symposium",

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

pages = "13--22",

booktitle = "Proceedings - 39th IEEE Real-Time Systems Symposium, RTSS 2018",

}

Baruah, S 2019, Rapid Routing with Guaranteed Delay Bounds. in Proceedings - 39th IEEE Real-Time Systems Symposium, RTSS 2018., 8603188, Proceedings - Real-Time Systems Symposium, vol. 2018-December, Institute of Electrical and Electronics Engineers Inc., pp. 13-22, 39th IEEE Real-Time Systems Symposium, RTSS 2018, Nashville, United States, 12/11/18. https://doi.org/10.1109/RTSS.2018.00012

Rapid Routing with Guaranteed Delay Bounds. / Baruah, Sanjoy.
Proceedings - 39th IEEE Real-Time Systems Symposium, RTSS 2018. Institute of Electrical and Electronics Engineers Inc., 2019. p. 13-22 8603188 (Proceedings - Real-Time Systems Symposium; Vol. 2018-December).

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

TY - GEN

T1 - Rapid Routing with Guaranteed Delay Bounds

AU - Baruah, Sanjoy

PY - 2019/1/4

Y1 - 2019/1/4

N2 - We consider networks in which each individual link is characterized by two delay parameters: a (usually very conservative) guaranteed upper bound on the worst-case delay, and an estimate of the delay that is typically encountered, across the link. Given a source and destination node on such a network and an upper bound on the end-to-end delay that can be tolerated, the objective is to determine routes they typically experience a small delay, while guaranteeing to respect the specified end-to-end upper bound under all circumstances. We formalize the problem of determining such routes as a shortest-paths problem on graphs, and derive algorithms for solving this problem optimally.

AB - We consider networks in which each individual link is characterized by two delay parameters: a (usually very conservative) guaranteed upper bound on the worst-case delay, and an estimate of the delay that is typically encountered, across the link. Given a source and destination node on such a network and an upper bound on the end-to-end delay that can be tolerated, the objective is to determine routes they typically experience a small delay, while guaranteeing to respect the specified end-to-end upper bound under all circumstances. We formalize the problem of determining such routes as a shortest-paths problem on graphs, and derive algorithms for solving this problem optimally.

KW - adaptive routing

KW - end-to-end deadlines

KW - on-line algorithm

KW - Real-time routing

KW - shortest paths in graphs

UR - https://www.scopus.com/pages/publications/85061530641

U2 - 10.1109/RTSS.2018.00012

DO - 10.1109/RTSS.2018.00012

M3 - Conference contribution

AN - SCOPUS:85061530641

T3 - Proceedings - Real-Time Systems Symposium

SP - 13

EP - 22

BT - Proceedings - 39th IEEE Real-Time Systems Symposium, RTSS 2018

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 39th IEEE Real-Time Systems Symposium, RTSS 2018

Y2 - 11 December 2018 through 14 December 2018

ER -

Rapid Routing with Guaranteed Delay Bounds

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this