A Stability Analysis of Randomized Scheduling Algorithm for Input-Queued Switches
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).
M. S. Sun and J. Wu, "A Stability Analysis of Randomized Scheduling Algorithm for Input-Queued Switches", Applied Mechanics and Materials, Vols. 20-23, pp. 1439-1445, 2010