期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2003
卷号：2003
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：In this work, we study the stability of the {\sf FIFO} ({\sf First-In-First-Out}) protocol in the context of Adversarial Queueing Theory. As an important intermediate step, we consider {\em dynamic capacities}, where each network link capacity may arbitrarily take on values in the two-valued set of integers 1 C for 1"> C 1 being the {\em high capacity} (a parameter). In this context: \begin{itemize} \item[(1)] We construct a {\sf FIFO} network of only eight nodes which is already unstable at rate r = 0 41 . This is the current record for instability of {\sf FIFO} over networks of fixed-size (independent of r ). \item[(2)] For every 0"> r 0 we then construct a {\sf FIFO} network (whose size increases with r 1 ) which is unstable at rate r . \end{itemize} Subsequently, we show how to simulate the particular {\sf FIFO} network in (2) above with dynamic capacities 1 , C , in order to produce a {\sf FIFO} network with all link capacities being equal, while preserving instability thresholds. Hence, we eventually show our main result: {\sf FIFO} can become unstable in the usual model of {\em unit capacities} links, for arbitrarily low packet injection rates. This closes a major open problem (the question of {\sf FIFO} stability) in the field of Adversarial Queueing Theory posed in the pioneering work of Borodin {\em et al.}~\cite{BKRSW01}.
关键词：adversarial queueing theory , FIFO , routing , stability
1 
