Simulation codes (full version), C++ version of our old simulation codes in C and adding more benchmark algorithms and more "features" (e.g., P95 delay), for our switching paper:
Long Gong, Paul Tune, Liang Liu, Sen Yang, and Jun (Jim) Xu. 2017. Queue-Proportional Sampling: A Better Approach to Crossbar Scheduling for Input-Queued Switches. Proc. ACM Meas. Anal. Comput. Syst. 1, 1, Article 3 (June 2017), 33 pages. DOI:https://doi.org/10.1145/3084440
.
├── common Source codes shared by different algorithms
├── FQPP_QPA_iSLIP Source codes for variants of QPS-iSLIP (with PA)
├── FQPP_QPA_Serena Source codes for variants of QPS-SERENA (with PA)
├── FQPS_iSLIP Source codes for variants of QPS-iSLIP
├── FQPS_Serena Source codes for variants of QPS-SERENA
├── iLQF Source codes for iLQF
├── iLQF_ShakeUp Source codes for iLQF-ShakeUp
├── iSLIP Source codes for iSLIP
├── iSLIP_ShakeUp Source codes for iSLIP-ShakeUp
├── MWM Source codes for Maximum Weighted Maximum (MWM)
├── O1 Source codes for the O(1) algorithm
├── py Some useful python script
├── QPP_QPA Source codes for QPS (with PA)
├── QPP_QPA_iSLIP Source codes for QPS-iSLIP (with PA)
├── QPP_QPA_Serena Source codes for QPS-SERENA (with PA)
├── QPS Source codes for QPS
├── QPS_iSLIP Source codes for QPS-iSLIP
├── QPS_Serena Source codes for QPS-SERENA
├── results Directory for storing simulation results
└── Serena Source codes for SERENA
Algorithms from literature:
- iSLIP [1]: the standard iSLIP algorithm,
- PIM [2]: parallel iterative matching,
- MWM [4]: maximum weighted matching,
- SERENA [5]: previous matching + arrival graph,
- iLQF [3]: iterative longest queue first, and
- ShakeUp (including iSLIP-ShakeUP and iLQF-ShakeUp) [7]: another "add-on" approach
- O(1) [8]: a O(1) crossbar scheduling algorithm based on Glauber dynamics
Final proposals (USED IN OUR PAPER):
- QPS-iSLIP [6]: Queue Proportional Sampling (QPS) augmented iSLIP
- QPS-SERENA [6]: Queue Proportional Sampling (QPS) augmented SERENA
Other proposals (COMPARED IN OUR PAPER)
- FQPS-iSLIP [6]: Variants of Queue Proportional Sampling (QPS) augmented iSLIP
- FQPS-SERENA [6]: Variants of Queue Proportional Sampling (QPS) augmented SERENA
- QPS-iSLIP (with PA): Queue Proportional Sampling (QPS), with Proportional Accepting (PA), augmented iSLIP
- QPS-SERENA (with PA): Queue Proportional Sampling (QPS), with Proportional Accepting (PA), augmented SERENA
- Install dependencies:
./install_dependencies.sh
- compile:
mkdir build cd build cmake .. make
- uniform,
- diagonal,
- log diagonal, and
- quasi diagonal.
- Bernoulli,
- Pareto bursts
This project was modified from Dr. Bill Lin's original source codes.
- Long Gong long.github@gmail.com
[1] McKeown, N., 1999. The iSLIP scheduling algorithm for input-queued switches. IEEE/ACM transactions on networking, 7(2), pp.188-201.
[2] Anderson, T.E., Owicki, S.S., Saxe, J.B. and Thacker, C.P., 1993. High-speed switch scheduling for local-area networks. ACM Transactions on Computer Systems (TOCS), 11(4), pp.319-352.
[3] McKeown, N.W., 1995. Scheduling algorithms for input-queued cell switches (Doctoral dissertation, University of California, Berkeley).
[4] McKeown, N., Mekkittikul, A., Anantharam, V. and Walrand, J., 1999. Achieving 100% throughput in an input-queued switch. IEEE Transactions on Communications, 47(8), pp.1260-1267.
[5] Giaccone, P., Prabhakar, B. and Shah, D., 2003. Randomized scheduling algorithms for high-aggregate bandwidth switches. IEEE Journal on Selected Areas in Communications, 21(4), pp.546-559.
[6] Gong, L., Tune, P., Liu, L., Yang, S. and Xu, J., 2017. Queue-Proportional Sampling: A Better Approach to Crossbar Scheduling for Input-Queued Switches. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1(1), pp.1-33.
[7] Goudreau, M.W., Kolliopoulos, S.G. and Rao, S.B., 2000, March. Scheduling algorithms for input-queued switches: randomized techniques and experimental evaluation. In Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Cat. No. 00CH37064) (Vol. 3, pp. 1634-1643). IEEE.
[8] Ye, S., Shen, Y. and Panwar, S., 2010, September. An O (1) scheduling algorithm for variable-size packet switching systems. In 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton) (pp. 1683-1690). IEEE.