Report Number: CS-TN-99-90
Institution: Stanford University, Department of Computer Science
Title: Simulation of Iterative Matching for Combined Input and
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.