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

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: Carme Àlvarez , Maria Blesa , Maria Serna, A Characterization of Universal Stability in the Adversarial Queuing Model, SIAM Journal on Computing, v.34 n.1, p.41-66, 2005 [doi>10.1137/S0097539703435522]
• 2: Matthew Andrews, Instability of FIFO in session-oriented networks, Journal of Algorithms, v.50 n.2, p.232-245, February 2004 [doi>10.1016/S0196-6774(03)00096-8]
• 3: Matthew Andrews , Baruch Awerbuch , Antonio Fernández , Tom Leighton , Zhiyong Liu , Jon Kleinberg, Universal-stability results and performance bounds for greedy contention-resolution protocols, Journal of the ACM (JACM), v.48 n.1, p.39-69, Jan. 2001 [doi>10.1145/363647.363677]
• 4: Matthew Andrews , Antonio Fernández , Mor Harchol-Balter , Tom Leighton , Lisa Zhang, General Dynamic Routing with Per-Packet Delay Guarantees of O(Distance + 1/Session Rate), SIAM Journal on Computing, v.30 n.5, p.1594-1623, 2000 [doi>10.1137/S009753979935061X]
• 5: Rajat Bhattacharjee , Ashish Goel , Zvi Lotker, Instability of FIFO at Arbitrarily Low Rates in the Adversarial Queueing Model, SIAM Journal on Computing, v.34 n.2, p.318-332, 2005 [doi>10.1137/S0097539703426805]
• 6: Jean-Yves Le Boudec , Patrick Thiran, Network calculus: a theory of deterministic queuing systems for the internet, Springer-Verlag New York, Inc., New York, NY, 2001
• 7: Bramson, M. 1994a. Instability of FIFO queueing networks. Ann. Appl. Probab. 4, 2, 414--431.
• 8: Bramson, M. 1994b. Instability of FIFO queueing networks with quick service times. Ann. Appl. Probab. 4, 3, 693--718.
• 9: Bramson, M. 1996. Convergence to equilibria for fluid models of FIFO queueing networks. Queue. Syst. 22, 5--45.
• 10: Anna Charny , Jean-Yves Le Boudec, Delay Bounds in a Network with Aggregate Scheduling, Proceedings of the First COST 263 International Workshop on Quality of Future Internet Services, p.1-13, September 25-26, 2000
• 11: David D. Clark , Scott Shenker , Lixia Zhang, Supporting real-time applications in an Integrated Services Packet Network: architecture and mechanism, Conference proceedings on Communications architectures & protocols, p.14-26, August 17-20, 1992, Baltimore, Maryland, United States
• 12: Cruz, R. L. 1991. A calculus for network delay, Part II: Network analysis. IEEE Trans. Inf. Theory 37, 132--141.
• 13: Josep Díaz , Dimitrios Koukopoulos , Sotiris Nikoletseas , Maria Serna , Paul Spirakis , Dimitrios M. Thilikos, Stability and non-stability of the FIFO protocol, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.48-52, July 2001, Crete Island, Greece [doi>10.1145/378580.378588]
• 14: Echague, J., Cholvi, V., and Fernandez, A. 2003. Universal stability results for low rate adversaries in packet switched networks. IEEE Commun. Lett. 7, 12.
• 15: Elwalid, A., and Mitra, D. 1999. Design of generalized processor sharing schedulers which statistically multiplex heterogeneous QoS classes. In Proceedings of IEEE INFOCOM, 1220--1230.
• 16: David Gamarnik, Stability of Adversarial Queues via Fluid Models, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.60, November 08-11, 1998
• 17: Georgiadis, L., Guérin, R., and Parekh, A. 1997. Optimal multiplexing on a single link: Delay and buffer requirements. IEEE Trans. Inf. Theory 43, 5, 1518--1535.
• 18: Georgiadis, L., Guérin, R., Peris, V., and Sivarajan, K. 1996. Efficient network QoS provisioning based on per node traffic shaping. In Proceedings of IEEE INFOCOM, 102--110.
• 19: Koupoulos, D., Nikoletseas, N., and Spirakis, P. 2001. The range of stability for heterogeneous and FIFO queueing networks. In Electronic Colloquium on Computational Complexity.
• 20: Jörg Liebeherr , Dallas E. Wrege , Domenico Ferrari, Exact admission control for networks with a bounded delay service, IEEE/ACM Transactions on Networking (TON), v.4 n.6, p.885-901, Dec. 1996 [doi>10.1109/90.556345]
• 21: Zvi Lotker , Boaz Patt-Shamir , Adi Rosén, New stability results for adversarial queuing, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564904]
• 22: Abhay K. Parekh , Robert G. Gallagher, A generalized processor sharing approach to flow control in integrated services networks: the multiple node case, IEEE/ACM Transactions on Networking (TON), v.2 n.2, p.137-150, April 1994 [doi>10.1109/90.298432]
• 23: Seidman, T. I. 1994. ‘First come, first served’ can be unstable! IEEE Trans. Autom. Control 39, 2166--2171.
• 24: Dimitrios Stiliadis, Traffic scheduling in packet-switched networks: analysis, design, and implementation, University of California, Santa Cruz, 1996
• 25: Dallas E. Wrege Jörg Liebeherr, A Near-Optimal Packet Scheduler for QoS Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.576, April 09-11, 1997
• 26: Zhang, H. 1995. Service disciplines for guaranteed performance service in packet-switching networks. Proc. IEEE.
• 27: Fundamental Trade-offs in Aggregate Packet Scheduling, Proceedings of the Ninth International Conference on Network Protocols, p.129, November 11-14, 2001

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Queueing theory

Additional Classification:
  F. Theory of Computation
  F.0 GENERAL

General Terms:
Algorithms, Performance, Theory

Keywords:
FIFO scheduling, network stability