两级交换机中分组有序到达算法研究

Novel algorithm of maintaining packet order in two-stage switch

为了提高高性能分组交换机的扩展性,张尚正等人提出了一种称为负载平衡交换机(load-balancedswitch)的交换结构,该交换机分为两级交换结构,每一级都采用一种时序固定的连接方式,具有良好的扩展性;同时可以提供100%吞吐量保证。但是,负载平衡交换机的基本结构会出现分组乱序的情况。本文提出了一种在两级负载平衡交换机中保证分组顺序到达的满帧填充算法,该算法具有良好的交换特性(平均时延及吞吐量),同时也是一种分布式算法,各个端口可以独立地进行操作。

To enhance the scalability of high performance packet switches, recently a two-stage load-balanced switch was introduced by Zhang, in which each stage used a deterministic sequence of configurations. The switch was simple to be scalable and had been proved to provide 100% throughput. However, in its basic fabric, the load-balanced switch may mis-sequence the packets. A new algorithm called FFS （full frame stuff） was proposed in this paper, which maintains packet order in the two-stage load-balanced switch and has excellent switching performance （in terms of mean delay and throughput）.This algorithm is distributed and each port operates independently.