|
|
|
| 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.
|
|
Received: 21 March 2011
|
|
|
|
Corresponding Authors:
Zhou Ting
E-mail: zhout06@mails.tsinghua.edu.cn
|
|
|
|
|
|
|
2012, Vol. 34 
