A Stability Analysis of Randomized Scheduling Algorithm for Input-Queued Switches
Mao Sheng Sun, Jun Wu · Applied Mechanics and Materials · 2010
Input-Queued switching fabrics are widely used in high speed network switches for their scalability. However, a scheduling algorithm must be elaborative designed for input-queued switches to get high throughput. The randomized algorithms are attractive in kinds of scheduling algorithms for their low complexity and well performance. In this paper, a fluid model is introduced to analyze the rate stability of switching systems with randomized schedulers. By this method, we proved that the randomized scheduling algorithm can achieve 100% throughput under any admissible traffics which satisfy the strong law of large numbers (SLLN).