44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.
Download PDF

Abstract

We study the stability of the commonly used packet forwarding protocol, FIFO (First In First Out), in the adversarial queueing model. We prove that FIFO can become unstable, i.e., lead to unbounded buffer-occupancies and queueing delays, at arbitrarily low injection rates. In order to demonstrate instability at rate &Ugr we use a network of size polynomial in 1/&Ugr.
Like what you’re reading?
Already a member?
Get this article FREE with a new membership!

Related Articles