New Stability Results for Adversarial Queuing

Authors:
  • ZLZvi Lotker
    Zvi Lotker
  • BPBoaz Patt-Shamir
    Boaz Patt-Shamir
  • ARAdi Rosén
    Adi Rosén

Abstract
We consider the model of "adversarial queuing theory" for packet networks introduced by Borodin et al. [J. ACM, 48 (2001), pp. 13--38].We show that the scheduling protocol first-in-first-out (FIFO) can be unstable at any injection rate larger than 1/2 and that it is always stable if the injection rate is less than 1/d, where d is the length of the longest route used by any packet. We further show that every work-conserving (i.e., greedy) scheduling policy is stable if the injection rate is less than 1/(d+1).