Fast matching algorithms for repetitive optimization: An application to switch scheduling

Scheduling in an input buffered switch can be viewed as repeated matching (corresponding to once every time slot) in a bipartite graph. It has been shown that scheduling algorithms based on maximum weight matching (MWM) with queue-lengths as the weights, leads to excellent performance in terms of throughput and delay. However, computing MWM using a strongly polynomial time algorithm requires O(n(3)) operations in an n x n switch. The main motivation for this paper comes from the following two observations: (1) The weights of edges (packets in buffer) change only a little between successive time slots, thus changing the weight of the MWM only by a small amount; (2) Under MWM algorithm, the average queue-sizes are small. The main difficulty in utilizing these properties comes from the fact that small changes in weights can change the matching arbitrarily, thus making it hard for current popular algorithms to compute an MWM quickly using the information from past (or memory). In this paper, we develop an algorithm based on the algorithm of Cunningham and Marsh [1] that uses the above two properties in order to to find the new MWM quickly. Specifically, for an n port input-queued switch, i.e. a switch with n inputs and n outputs, our algorithm finds MWM in O(n(2)) operations using past information. We believe that the incremental nature of our algorithm may be useful in the context of other applications.