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 the permanent sessions model at arbitrarily small network loads, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.219-228, January 07-09, 2007, New Orleans, Louisiana
• 3: 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]
• 4: 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]
• 5: M. Andrews , A. Fernandez , M. Harchol-Balter , T. Leighton , L. Zhang, General dynamic routing with per-packet delay guarantees of O(distance+1/session rate), Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.294, October 19-22, 1997