Stability of adversarial routing with feedback

Bogdan S. Chlebus; Vicent Cholvi; Dariusz R. Kowalski

doi:10.1007/978-3-642-40148-0_15

Stability of adversarial routing with feedback

Bogdan S. Chlebus, Vicent Cholvi, Dariusz R. Kowalski

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

4 Scopus citations

Abstract

We consider the impact of scheduling disciplines on the performance of routing in the framework of adversarial queuing. We propose an adversarial model which reflects stalling of packets due to transient failures and explicitly incorporates the feedback produced by the network when packets are stalled. This adversarial model provides a methodology to study stability of routing protocols when flow-control and congestion-control mechanisms affect the volume of traffic. We show that any scheduling policy that is universally stable, in the regular model of routing that additionally allows packets to have two priorities, remains stable in the proposed adversarial model.

Original language	English (US)
Title of host publication	Networked Systems - First International Conference, NETYS 2013, Revised Selected Papers
Pages	206-220
Number of pages	15
DOIs	https://doi.org/10.1007/978-3-642-40148-0_15
State	Published - 2013
Externally published	Yes
Event	1st International Conference on Networked Systems, NETYS 2013 - Marrakech, Morocco Duration: May 2 2013 → May 4 2013

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7853 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	1st International Conference on Networked Systems, NETYS 2013
Country/Territory	Morocco
City	Marrakech
Period	5/2/13 → 5/4/13

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-40148-0_15

Cite this

Chlebus, B. S., Cholvi, V., & Kowalski, D. R. (2013). Stability of adversarial routing with feedback. In Networked Systems - First International Conference, NETYS 2013, Revised Selected Papers (pp. 206-220). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7853 LNCS). https://doi.org/10.1007/978-3-642-40148-0_15

Stability of adversarial routing with feedback. / Chlebus, Bogdan S.; Cholvi, Vicent; Kowalski, Dariusz R.
Networked Systems - First International Conference, NETYS 2013, Revised Selected Papers. 2013. p. 206-220 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7853 LNCS).

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

Chlebus, BS, Cholvi, V & Kowalski, DR 2013, Stability of adversarial routing with feedback. in Networked Systems - First International Conference, NETYS 2013, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7853 LNCS, pp. 206-220, 1st International Conference on Networked Systems, NETYS 2013, Marrakech, Morocco, 5/2/13. https://doi.org/10.1007/978-3-642-40148-0_15

@inproceedings{16f8ea0e26044fb4a10498e8a7300528,

title = "Stability of adversarial routing with feedback",

abstract = "We consider the impact of scheduling disciplines on the performance of routing in the framework of adversarial queuing. We propose an adversarial model which reflects stalling of packets due to transient failures and explicitly incorporates the feedback produced by the network when packets are stalled. This adversarial model provides a methodology to study stability of routing protocols when flow-control and congestion-control mechanisms affect the volume of traffic. We show that any scheduling policy that is universally stable, in the regular model of routing that additionally allows packets to have two priorities, remains stable in the proposed adversarial model.",

author = "Chlebus, {Bogdan S.} and Vicent Cholvi and Kowalski, {Dariusz R.}",

year = "2013",

doi = "10.1007/978-3-642-40148-0_15",

language = "English (US)",

isbn = "9783642401473",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "206--220",

booktitle = "Networked Systems - First International Conference, NETYS 2013, Revised Selected Papers",

note = "1st International Conference on Networked Systems, NETYS 2013 ; Conference date: 02-05-2013 Through 04-05-2013",

}

TY - GEN

T1 - Stability of adversarial routing with feedback

AU - Chlebus, Bogdan S.

AU - Cholvi, Vicent

AU - Kowalski, Dariusz R.

PY - 2013

Y1 - 2013

N2 - We consider the impact of scheduling disciplines on the performance of routing in the framework of adversarial queuing. We propose an adversarial model which reflects stalling of packets due to transient failures and explicitly incorporates the feedback produced by the network when packets are stalled. This adversarial model provides a methodology to study stability of routing protocols when flow-control and congestion-control mechanisms affect the volume of traffic. We show that any scheduling policy that is universally stable, in the regular model of routing that additionally allows packets to have two priorities, remains stable in the proposed adversarial model.

AB - We consider the impact of scheduling disciplines on the performance of routing in the framework of adversarial queuing. We propose an adversarial model which reflects stalling of packets due to transient failures and explicitly incorporates the feedback produced by the network when packets are stalled. This adversarial model provides a methodology to study stability of routing protocols when flow-control and congestion-control mechanisms affect the volume of traffic. We show that any scheduling policy that is universally stable, in the regular model of routing that additionally allows packets to have two priorities, remains stable in the proposed adversarial model.

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

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

U2 - 10.1007/978-3-642-40148-0_15

DO - 10.1007/978-3-642-40148-0_15

M3 - Conference contribution

AN - SCOPUS:84883163345

SN - 9783642401473

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 206

EP - 220

BT - Networked Systems - First International Conference, NETYS 2013, Revised Selected Papers

T2 - 1st International Conference on Networked Systems, NETYS 2013

Y2 - 2 May 2013 through 4 May 2013

ER -

Stability of adversarial routing with feedback

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this