Stability and non-stability of the FIFO protocol

J. Díaz; D. Koukopoulos; S. Nikoletseas; M. Serna; P. Spirakis; D. M. Thilikos

doi:10.1145/378580.378588

Stability and non-stability of the FIFO protocol

J. Díaz, D. Koukopoulos, S. Nikoletseas, M. Serna, P. Spirakis, D. M. Thilikos

Computer Science

Research output: Contribution to conference › Paper › peer-review

Abstract

In this paper, we analyze the stability properties of the FIFO protocol in the Adversarial Queueing model for packet routing. We show a graph for which FIFO is stable for any adversary with injection rate r ≤ 0.1428. We generalize this results to show upper bounds for stability of any network under FIFO protocol, answering partially an open question raised by Andrews et al. in [2]. We also design a network and an adversary for which FIFO is non-stable for any r ≥ 0.8357, improving the previous known bounds of [2].

Original language	English (US)
Pages	48-52
Number of pages	5
DOIs	https://doi.org/10.1145/378580.378588
State	Published - 2001
Event	13th Annual Symposium on Parallel Algorithms and Architectures (SPAA 2001) - Crete Island, Greece Duration: Jul 3 2001 → Jul 6 2001

Conference

Conference	13th Annual Symposium on Parallel Algorithms and Architectures (SPAA 2001)
Country/Territory	Greece
City	Crete Island
Period	7/3/01 → 7/6/01

ASJC Scopus subject areas

Software
Safety, Risk, Reliability and Quality

Access to Document

10.1145/378580.378588

Cite this

@conference{ae961ad561d341aaaa4d5b19ae3ec2c9,

title = "Stability and non-stability of the FIFO protocol",

abstract = "In this paper, we analyze the stability properties of the FIFO protocol in the Adversarial Queueing model for packet routing. We show a graph for which FIFO is stable for any adversary with injection rate r ≤ 0.1428. We generalize this results to show upper bounds for stability of any network under FIFO protocol, answering partially an open question raised by Andrews et al. in [2]. We also design a network and an adversary for which FIFO is non-stable for any r ≥ 0.8357, improving the previous known bounds of [2].",

author = "J. D{\'i}az and D. Koukopoulos and S. Nikoletseas and M. Serna and P. Spirakis and Thilikos, {D. M.}",

year = "2001",

doi = "10.1145/378580.378588",

language = "English (US)",

pages = "48--52",

note = "13th Annual Symposium on Parallel Algorithms and Architectures (SPAA 2001) ; Conference date: 03-07-2001 Through 06-07-2001",

}

TY - CONF

T1 - Stability and non-stability of the FIFO protocol

AU - Díaz, J.

AU - Koukopoulos, D.

AU - Nikoletseas, S.

AU - Serna, M.

AU - Spirakis, P.

AU - Thilikos, D. M.

PY - 2001

Y1 - 2001

N2 - In this paper, we analyze the stability properties of the FIFO protocol in the Adversarial Queueing model for packet routing. We show a graph for which FIFO is stable for any adversary with injection rate r ≤ 0.1428. We generalize this results to show upper bounds for stability of any network under FIFO protocol, answering partially an open question raised by Andrews et al. in [2]. We also design a network and an adversary for which FIFO is non-stable for any r ≥ 0.8357, improving the previous known bounds of [2].

AB - In this paper, we analyze the stability properties of the FIFO protocol in the Adversarial Queueing model for packet routing. We show a graph for which FIFO is stable for any adversary with injection rate r ≤ 0.1428. We generalize this results to show upper bounds for stability of any network under FIFO protocol, answering partially an open question raised by Andrews et al. in [2]. We also design a network and an adversary for which FIFO is non-stable for any r ≥ 0.8357, improving the previous known bounds of [2].

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

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

U2 - 10.1145/378580.378588

DO - 10.1145/378580.378588

M3 - Paper

AN - SCOPUS:0034818972

SP - 48

EP - 52

T2 - 13th Annual Symposium on Parallel Algorithms and Architectures (SPAA 2001)

Y2 - 3 July 2001 through 6 July 2001

ER -

Stability and non-stability of the FIFO protocol

Abstract

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this