保证100%吞吐率的两级组播交换结构

 在路由器或交换机的交换结构中实现组播是提高组播应用速度的重要途径之一。传统的交叉开关结构(crossbar)组播调度方案有两种缺陷，一种是性能较低，另一种是实现的复杂度太高，无法满足高速交换的需要。该文提出了一个新的基于交叉开关的两级组播交换结构(TSMS)，第1级是组播到单播的交换结构，第2级是联合输入和输出排队(CIOQ)交换，并为该结构设计了合适的最大扇出排队(FCN)优先-均匀分配中间缓存调度算法(LFCNF-UMBA)。理论分析和仿真实验都显示在该结构中，加速比低于2−2/(N+1)倍时吞吐率不可能实现100%；而采用LFCNF-UMBA调度算法，2倍加速比就可保证在任意允许(admissible)组播的吞吐率达到100%。

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 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.