Stability of Adaptive and Non-Adaptive Packet Routing Policies in Adversarial Queueing Networks

We investigate stability of adaptive and non-adaptive packet routing policies in adversarial queueing networks. A simple classification is provided of networks which are stable under any greedy scheduling policy - network is stable if and only the underlying undirected graph contains only two edges. This complements a recent result by Goel, which provides classification of stable networks, in which the underlying graph is directed. We also propose a simple and distributed policy which is stable in an arbitrary adversarial queueing network even for the critical value of the arrival rate r=1. Finally, a simple and checkable network flow type load condition is formulated for adaptive adversarial queueing networks and a policy is proposed which achieves stability under this new load condition. This load condition is a relaxation of the condition previously proposed by Aiello et. al.