Achieving 100% Throughput in a Two-stage Multicast Switch

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 of22/(N+1) is necessary and 2 is sufficient for aMN TSMS to achieve 100% throughput under any admissible multicast traffic pattern, which is also verified by the simulation results.