Analysis of Maximum-Size Matching Scheduling Algorithms in Input Queue Switches Under Uniform

EE384Y Project: Final Proposal Spring 2004

Analysis of Maximum-Size Matching Scheduling Algorithms in input queue switches under uniform traffic

Team Members:

Mohsen Bayati, Neda Beheshti

INTRODUCTION

In the design of input queue switches, good scheduling algorithms play very important role. It has been shown that the Maximum Wait Matching Algorithm (MWM) is stable, however it’s difficult to implement. Another scheduling algorithm is the Maximum Size Matching Algorithm. It is known to be unstable under non-uniform traffic pattern [3]. On the other hand there have been results about stability of some specific MSM for scheduling traffic. But the question of how it performs under uniform traffic remains open. Simulations suggest the stability of MSM algorithms under uniform traffic but there have been no analytical results proving the same. We plan to work on this problem and hope to study the structure of MSM scheduling algorithms so as to figure out the inherent hardness in this problem.

IDEAS

Weller and Hejk [5] introduced a new model of packet arrival traffic and analyzed the throughput of simple packet switching systems under this model. Their model constrained the number of packets to any input or for any output port over time periods of specified length.

Iyer and McKeown [4] extended their arguments for stochastic (Bernoulli) arrivals and showed the stability of a class of MSM algorithms (called critical MSM) under batch scheduling. One of our ideas is studying their results mainly to understand the problem better in other situations and get some ideas for our work.

With a different approach, Dai and Prabhakar [1] used the fluid model to prove stability of MWM and also stability of maximal matching algorithm under speedup 2, which concludes the stability of MSM under speedup 2. We want to understand this method better and try to get a fluid model argument for the MSM without any speedup. This might also lead us to prove the stability by making a suitable Lyapunov function.

Another way of looking at the problem is trying randomized algorithms, as Giaccone, Prabhakar and Shah [2] did for MWM.

SUMMARY OF ACTION

1. Reading related background and literature

2. Using simulations

3. Studying different examples (e.g. small number of inputs/outputs)

4. Trying to find a suitable Lyapunov functions for showing stability

5. Using results from parts 2 and 3 and trying to build special examples and make guesses about the problem.

6. Trying to extend previous works [2,4,5].

TENTATIVE SCHEDULE

04/12-04/16 Number 1. 04/19-04/23 Number 2

04/19-04/23 Number 3 04/26-04/30 Number 4

05/03-05/07 Number 5 05/10-05/14 Number 6

04/17-05/21 Collecting the results and making the presentation and final report

TEAM MEMBERS ROLES

It’s going to be a complete joint work

References

[1] The throughput of data switches with and without speedup, J.G. Dai and B. Prabhakar, Proceedings of the IEEE INFOCOM, 2:556-564, Tel Aviv, Israel, March 2000

[2] Randomized Scheduling Algorithms for High Aggregate Bandwidth Swithces, P. Giaccone, B. Prabhakar and D. Shah

[3] Achieving 100% Throughput in an Input-Queued Switch, N. McKeown, A. Mekkittikul, V. Anantharam and J. Walrand, IEEE Transactions on Communications, Vol. 47, No. 8, August 1999.

[4] Maximum Size Matching and Input Queued Switches, S. Iyer and N. McKeown, Proceedings of the 40th Annual Allerton Conference on Communication, Control and Computing, 2002

[5] Scheduling non-uniform traffic in a packet-switching system with small propagation delay, T. Weller and B Hajek, IEEE/ACM Transactions on Networking, 5(6) : 813-823, 1997.