FIFO is Unstable at Arbitrarily Low Rates
Dimitrios K. Koukopoulos, Marios Mavronicolas, Paul G. Spirakis · 2003
In this work, we study the stability of the FIFO (First-In-First-Out) protocol in the context of Adversarial Queueing Theory. As an important intermediate step, we consider dynamic capacities, where each network link capacity may arbitrarily take on values in the two-valued set of integers f1; Cg for C> 1 being the high capacity (a parameter). In this context: (1) We construct a FIFO network of only eight nodes which is already unstable at rate r = 0:41. This is the current record for instability of FIFO over networks of fixed-size (independent of r). (2) For every r> 0 we then construct a FIFO network (whose size increases with 1 r) which is unstable at rate r. Subsequently, we show how to simulate the particular FIFO network in (2) above with dynamic capacities 1, C, in order to produce a FIFO network with all link capacities being equal, while preserving instability thresholds. Hence, we eventually show our main result: FIFO can become unstable in the usual model of unit capacities links, for arbitrarily low packet injection rates. This closes a major open problem (the question of FIFO stability) in the field of Adversarial Queueing Theory posed in the pioneering work of Borodin et al. [5].