Article

Instability of FIFO in the permanent sessions model at arbitrarily small network loads

Author:

Matthew AndrewsAuthors Info & Claims

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 219 - 228

Published: 07 January 2007 Publication History

Get Access

Abstract

We show that for any r > 0, there is a network of First-In-First-Out servers and a fixed set of sessions such that,

• The network load is r with respect to the Permanent Sessions Model with Bounded Arrivals.

• The network can be made unstable.

References

[1]

C. Alvarez, M. Blesa, and M. Serna. A characterization of universal stability in the adversarial queueing model. SIAM Journal on Computing, 34(1):41--66, 2004.

Digital Library

Google Scholar

[2]

M. Andrews. Instability of FIFO in the permanent sessions model at arbitrarily small network loads. http://cm.bell-labs.com/~andrews/fifo-small-load.ps.

Digital Library

Google Scholar

[3]

M. Andrews. Instability of FIFO in session-oriented networks. Journal of Algorithms, 50(2):232--245, 2004.

Digital Library

Google Scholar

[4]

M. Andrews, B. Awerbuch, A. Fernández, J. Kleinberg, T. Leighton, and Z. Liu. Universal stability results and performance bounds for greedy contention-resolution protocols. Journal of the ACM, 48(1):39--69, January 2001.

Digital Library

Google Scholar

[5]

M. Andrews, A. Fernández, M. Harchol-Balter, T. Leighton, and L. Zhang. General dynamic routing with per-packet delay guarantees of O(distance

Digital Library

Google Scholar

Cited By

View all

Bouillard AJouhet LThierry É(2010)Tight performance bounds in the worst-case analysis of feed-forward networksProceedings of the 29th conference on Information communications10.5555/1833515.1833708(1316-1324)Online publication date: 14-Mar-2010
https://dl.acm.org/doi/10.5555/1833515.1833708
Kiwi MSoto MThraves C(2009)Adversarial queuing theory with setupsTheoretical Computer Science10.1016/j.tcs.2008.09.064410:8-10(670-687)Online publication date: 1-Mar-2009
https://dl.acm.org/doi/10.1016/j.tcs.2008.09.064
Bouillard AJouhet LThierry EBaras J(2008)Computation of a (min,+) multi-dimensional convolution for end-to-end performance analysisProceedings of the 3rd International Conference on Performance Evaluation Methodologies and Tools10.4108/ICST.VALUETOOLS2008.4349(1-7)Online publication date: 20-Oct-2008
https://dl.acm.org/doi/10.4108/ICST.VALUETOOLS2008.4349
Show More Cited By

Instability of FIFO in the permanent sessions model at arbitrarily small network loads
1. Theory of computation
  1. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Instability of FIFO in the permanent sessions model at arbitrarily small network loads

We show that for any r > 0, there is a network of First-In-First-Out servers and a fixed set of sessions such that:

—The network load is r with respect to the permanent sessions model with bounded arrivals.

—The network can be made unstable.
Stability of Multiclass Queueing Networks Under FIFO Service Discipline

In this paper, we first formally identify a FIFO fluid network that corresponds to the queueing network under a first-in first-out FIFO service discipline, thus complementing the result of Dai Dai, J. G. 1995a. On positive Harris recurrence of ...
Instability of FIFO in a simple queueing system with arbitrarily low loads

We show, using a simple example, that the First-In-First-Out (FIFO) policy can be unstable in a system with arbitrarily low load. Our proof is based on the observation that the special structure of the example we use allows us to establish stability ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

January 2007

1322 pages

ISBN:9780898716245

Conference Chair:
Harold Gabow
University of Colorado, Boulder

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 07 January 2007

Check for updates

Qualifiers

Article

Acceptance Rates

SODA '07 Paper Acceptance Rate 139 of 382 submissions, 36%;

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
149
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bouillard AJouhet LThierry É(2010)Tight performance bounds in the worst-case analysis of feed-forward networksProceedings of the 29th conference on Information communications10.5555/1833515.1833708(1316-1324)Online publication date: 14-Mar-2010
https://dl.acm.org/doi/10.5555/1833515.1833708
Kiwi MSoto MThraves C(2009)Adversarial queuing theory with setupsTheoretical Computer Science10.1016/j.tcs.2008.09.064410:8-10(670-687)Online publication date: 1-Mar-2009
https://dl.acm.org/doi/10.1016/j.tcs.2008.09.064
Bouillard AJouhet LThierry EBaras J(2008)Computation of a (min,+) multi-dimensional convolution for end-to-end performance analysisProceedings of the 3rd International Conference on Performance Evaluation Methodologies and Tools10.4108/ICST.VALUETOOLS2008.4349(1-7)Online publication date: 20-Oct-2008
https://dl.acm.org/doi/10.4108/ICST.VALUETOOLS2008.4349
Bouillard AGaujal BLagrange SThierry í(2008)Optimal routing for end-to-end guarantees using Network CalculusPerformance Evaluation10.1016/j.peva.2008.04.00865:11-12(883-906)Online publication date: 1-Nov-2008
https://dl.acm.org/doi/10.1016/j.peva.2008.04.008
Bouillard AGaujal BLagrange SThierry EGlynn P(2007)Optimal routing for end-to-end guaranteesProceedings of the 2nd international conference on Performance evaluation methodologies and tools10.5555/1345263.1345342(1-10)Online publication date: 22-Oct-2007
https://dl.acm.org/doi/10.5555/1345263.1345342

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

Instability of FIFO in the permanent sessions model at arbitrarily small network loads

Stability of Multiclass Queueing Networks Under FIFO Service Discipline

Instability of FIFO in a simple queueing system with arbitrarily low loads