Paper Info
Title
Parallel Maximum Weight Bipartite Matching Algorithms for Scheduling in Input-Queued Switches
Abstract
An input-queued switch with virtual output queuing is able to provide a maximum throughput of 100% in the sup- porting more sophisticated scheduling strategies. Switch scheduling can be cast as a maximum flow problem. In this paper we propose a maximum weight bipartite matching (MWBM) scheduling algorithm for input-queued switches. Our goal is to provide 100% throughput while maintain- ing fairness and stability. Our algorithm provides sublinear parallel run time complexity using a polynomial number of processing elements. We are able to obtain the MWBM for a time slot in sublinear time by using the matching produced in the previous time slot based on the observa- tion that in input-queued cell-based switches, the weight of edges changes very little during successive time slots. To the best of our knowledge, our algorithm outperforms all pre- viously proposed MWBM scheduling algorithms proposed for input-queued switches. We also describe a linear time complexity MWBM algorithm for a general bipartite graph which outperforms the best known sublinear MWBM algo- rithm for any bipartite graph with less than 1015 number of nodes.
Year
DOI
Venue
2004
10.1109/IPDPS.2004.1302904
IPDPS
Keywords
Field
DocType
directed graphs,optical switches,parallel algorithms,scheduling algorithm,maximum flow,bipartite graph,linear time,throughput,stability,time complexity,polynomials,computational complexity,bipartite matching
Computer science,Scheduling (computing),Parallel algorithm,Parallel computing,Bipartite graph,Algorithm,Directed graph,Maximum flow problem,Throughput,Time complexity,Computational complexity theory,Distributed computing
Conference
Citations 
PageRank 
References 
6
0.49
15
Authors
3
Name
Order
Citations
PageRank
Morteza Fayyazi191.64
David Kaeli21535129.85
Waleed Meleis315718.29