A distributed switch scheduling algorithm

The maximum weight matching algorithm is a high-performance scheduling algorithm for cross-bar switches. It is known that it performs optimally under heavy loads. However, its centralized nature and high computational complexity limit the algorithm’s applicability. This paper presents a randomized algorithm for distributed switch scheduling that is capable of delivering high throughput.