Instability of FIFO at Arbitrarily Low Rates in the Adversarial Queueing Model

F
FOCS
2003
44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03)
Abstract - Instability of FIFO at Arbitrarily Low Rates in the Adversarial Queueing Model

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Rajat Bhattacharjee Articles by Ashish Goel

44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03)

Cambridge, Massachusettes

October 11-October 14

ISBN: 0-7695-2040-5

	ASCII Text	x
	Rajat Bhattacharjee, Ashish Goel, "Instability of FIFO at Arbitrarily Low Rates in the Adversarial Queueing Model," Foundations of Computer Science, IEEE Annual Symposium on, pp. 160, 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03), 2003.

	BibTex	x
	@article{ 10.1109/SFCS.2003.1238190, author = {Rajat Bhattacharjee and Ashish Goel}, title = {Instability of FIFO at Arbitrarily Low Rates in the Adversarial Queueing Model}, journal ={Foundations of Computer Science, IEEE Annual Symposium on}, volume = {0}, year = {2003}, issn = {0272-5428}, pages = {160}, doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2003.1238190}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Foundations of Computer Science, IEEE Annual Symposium on TI - Instability of FIFO at Arbitrarily Low Rates in the Adversarial Queueing Model SN - 0272-5428 SP EP A1 - Rajat Bhattacharjee, A1 - Ashish Goel, PY - 2003 KW - null VL - 0 JA - Foundations of Computer Science, IEEE Annual Symposium on ER -

Rajat Bhattacharjee, University of Southern California

Ashish Goel, Stanford University

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2003.1238190

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;.

Citation:

Rajat Bhattacharjee, Ashish Goel, "Instability of FIFO at Arbitrarily Low Rates in the Adversarial Queueing Model," focs, pp.160, 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03), 2003

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.