Achieving Stability in Networks of Input-Queued Switches

Recent research has generated many interesting results on scheduling input-queued switches. However, most of this work focuses on a single switch in isolation. In this paper we study the problem of scheduling a network of input-queued switches. We consider the longest-Queue-First and Longest-Port-First protocols that are stable for a single switch and show that they can be unstable even for a fixed traffic pattern in a simple network of eight input- queued switches. Moreover, this result holds regardless of how the traffic sharing the same port-pair is scheduled at each switch. On the positive side we present a protocol, Longest-in-Network, that is stable in networks of input-queued switches. This result holds even if the traffic pattern is allowed to change over time.