The complexity of deciding stability under FFS in the Adversarial Queueing model

We address the problem of deciding whether a given network is stable in the Adversarial Queueing Model when considering farthest-from-source (FFS) as the queueing policy to schedule the packets through its links. We show a characterisation of the networks which are stable under FFS in terms of a family of forbidden subgraphs. We show that the set of networks stable under FFS coincide with the set of universally stable networks. Since universal stability of networks can be checked in polynomial time, we obtain that stability under FFS can also be decided in polynomial time. (C) 2004 Elsevier B.V. All rights reserved.