Report Number: CS-TN-99-90
Institution: Stanford University, Department of Computer Science
Title: Simulation of Iterative Matching for Combined Input and Output Queueing
Author: Pichai, Srinivasan
Author: Mudulodu, Sriram
Date: August 1999
Abstract: Since its introduction the Stable Marriage problem has been a subject of interest in mathematics and computer science. Recently this algorithm has found application in the area of switch scheduling algorithms for high performance switches. Inputs and Output ports of the switch compute their preference lists based on expected departure times for an ideal output queued switch. The stable matching as computed by the Galey-Shapley for this set of preferences determines the configuration of the interconnection fabric. The nature of the stable matching enables the emulation of an output-queued switch with combined input and output queueing using a speedup factor of 2. However it is important to compute the stable match efficiently for high performance. Hence parallel iterative versions of the algorithm have been proposed. In this report we investigate the convergence time of the parallel stable matching algorithm. The definition of the preference lists imposes special constraints on the problem and this reduces the worst case complexity of the algorithm. Simulations have shown that convergence time for the average case is also considerably lower than the general version of the algorithm.
http://i.stanford.edu/pub/cstr/reports/cs/tn/99/90/CS-TN-99-90.pdf