Scheduling algorithms for Virtual Output Queuing switches

• Autorzy: Baranowska A. , Kabaciński W.
• Języki publikacji: EN

Abstrakty

EN

In this article we have given an overview of different scheduling algorithms for virtual output queuing switches. We have also proposed three new scheduling algorithms for VOQ switches called Hierarchical Round-Robin Matching (HRRM), Matching Matching with Random Selection (MMRS) and Maximal Matching with Round-Robin Selection (MMRRS). Evaluation of the proposed algorithms was performed under Bernoulli and bursty packet arrivals with uniform and non-uniform distributions to output ports. Performance evaluation of the proposed algorithm under different traffic models is given and compared with other well-known algorithms. The simulation results show that MMRRS and HRRM achieves 100% throughput and low MTD for high loads.

Słowa kluczowe

EN

packet scheduling algorithms; virtual output queuing switches; packet switching

PL

algorytmy szeregujące; komutacja pakietów

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: Electronics and Telecommunications Quarterly
• Rocznik: 2007
• Tom: Vol. 53, No 3
• Strony: 252--272
• Opis fizyczny: Bibliogr. 19 poz., rys., tab., wykr.

Twórcy

autor

Baranowska A.

autor

Kabaciński W.

• Katedra Sieci Telekomunikacyjnych i Komputerowych, Politechnika Poznańska, ul. Polanka 3, 60-965 Poznań,

Bibliografia

• 1. Y. Tamir, G. Frazier: High performance multiqueue buffers for VLSI communication switches. Proc. 15th Annu. Symp. Comput. Arch., June 1988, pp. 343-354.
• 2. A. Baranowska, W. Kabaciński: MMRS and MMRRS Packet Scheduling Algorithms for VOQ Switches. Third Polish-German Teletraffic Symposium, September 2004, pp. 359-368.
• 3. A. Baranowska, W. Kabaciński: The New Packet Scheduling Algorithms for VOQ Switches, Lecture Notes in Computer Science, 2004, 3124, pp. 711-716.
• 4. T. Anderson, S. Owicki, J. Saxe: High Speed Switch Scheduling for Local Area Networks, ACM Trans. Comput. Syst., 1993, vol. 11, no 4, pp. 319-352.
• 5. N. McKeown, P. Varaiya, J. Warland: Scheduling cells in an Input-Queued Switch, IEEE Electron. Lett., 1993, pp. 2174-2175.
• 6. N. McKeown: The iSLIP scheduling algorithm for input-queued switches, IEEE Transactions on Networking, April 1999, vol. 7, no 2, pp. 188-201.
• 7. K. Yoshigoe, K. Christensen: An evolution to crossbar switches with virtual output queuing and buffered cross points, IEEE Network, Vol.17, no 5, 2003, pp. 48-56.
• 8. D. Serpanos, P. Antoniadis: FIRM: A Class of Distributed Scheduling Algorithms for Highspeed ATM Switches with Multiple Input Queues, IEEE INFOCOM 2000 - The Conference on Computer Communications, 2000, pp. 548-555.
• 9. Y. Jiang, M. Hamdi: A Fully Desynchronized Round-Robin Matching Scheduler for a VOQ Packet Switch Architecture, IEEE HPSR'2001, 2001, pp. 407-411.
• 10. H. J. Chao, C. H. Lam, E. Oki: Broadband Packet Switching Technologies: A Practical Guide to ATM Switches in IP Routers, New York: Willey, 2001.
• 11. N. McKeown: Scheduling Algorithms for Input-Queued Switches, Ph.D. thesis, University of California at Berkeley, 1995.
• 12. J. Chao: Saturn: A Terabit Packet Switch Using Dual Round-Robin, Global Telecommunications Conference, GLOBECOM'00, 2000, vol. 1, pp. 487-495.
• 13. Y. Li, S. S. Panwar, H. J. Chao: On the Performance of a Dual Round-Robin Switch, Proceedings of IEEE INFOCOM 2001, April 2001, pp. 22-26.
• 14. J. Liu, H. C. Kit, M. Hamdi, Chi Ying Tsui: Stable Round-Robin Scheduling Algorithms for High-Performance Input Queued Switches, in Proceedings of the 10th Symposium on Hotl'02, 2002, pp. 43, IEEE Computer Society.
• 15. A. Baranowska, W. Kabaciński: MMRS and MMRRS Packet Scheduling Algorithms for VOQ Switches, Proc. MMB PGTS 2004, 2004, pp. 359-368.
• 16. A. Baranowska, W. Kabaciński: Evaluation of MMRS and MMRRS Packet Scheduling Algorithms for VOQ Switches under Bursty Packet Arrivals, 2005, Hong Kong.
• 17. A. Baranowska, W. Kabaciński: Hierarchical Round-Robin Matching for Virtual Output Queuing Switches, A-ICT 2005, Portugalia, 2005, pp. 196-201.
• 18. P. Giaccone, B. Prabhakar, D. Shah: Randomized Scheduling Algorithms for High-Aggregate Bandwidth Switches. IEEE J. Select. Areas Commun., May 2003, 21(4), pp. 546-559.
• 19. D. Shah, P. Giaccone, B. Prabhakar: Efficent Randomized Algorithms for Input-Queued Switch Scheduling, Hot-Interconnects IX, 2002, 22(1), pp. 10-18.