Achieving 100% Throughput in a Two-stage Multicast Switch
Zhou Ting① Zhao You-jian① Wang Rui-sheng②
①(Department of Computer Science & Technology, Tsinghua University, Beijing 100084, China) ②(Department of Electrical Engineering, University of Southern California, Los Angeles CA90089, USA)
Abstract:The Internet growth coupled with the variety of multicast services is creating an increasing need for multicast traffic support by routers and packet switches. However, the traditional crossbar-based multicast scheduling schemes are unable to meet the needs of high-speed switching for the low performance and high implementation complexity. In this paper, a Two-Stage Multicast Switch (TSMS) is proposed, which is a serial combination of a Multicast To Unicast (MTU) switch to copy input cells from various sources simultaneously and a Combined Input and Output Queueing (CIOQ) switch to deliver copies of multicast cells to their final destinations. Based on MTU switch, a novel Largest Fanout Cardinal Number First-Uniform Middle Buffer Allocation (LFCNF-UMBA) scheduling algorithm is designed to determine how to copy multicast cells into unicast cells. By coordinately using Maximal Matching scheduling algorithm in CIOQ switch, it is proved that speedup of 2−2/(N+1) is necessary and 2 is sufficient for a M×N TSMS to achieve 100% throughput under any admissible multicast traffic pattern, which is also verified by the simulation results.