Clos交换网络中随机化的加权匹配调度算法

Randomized Weight Matching Dispatching Scheme for Clos-Network Switches

为达到100%的吞吐率,传统MSM型Clos网络调度算法通常是以高算法复杂度为代价,为避免这一现象,提出了一种低复杂度的分布式调度算法,即随机加权匹配调度,可利用缓存的信息和到达过程的随机性来寻找匹配.该算法中,输入级模块将请求信息均匀分布到中间级模块,由各中间级模块独立分布式地执行匹配算法.由于不需要迭代,且级间传递信息少,算法降低了调度过程中的通信开销.仿真结果表明,新算法在多种业务下都能达到100%吞吐率.

The current dispatching schemes for memory-space-memory （MSM） Clos-network switches provide 100% throughput under admissible traffics but with higher algorithm complexity. A low-complexi- ty and distributed scheduling algorithm, called randomized weight matching dispatching scheme （RWMD） , is proposed. Under this approach, each input module balances requests among central mod- ules, and each central module can carry out scheduling algorithm concurrently and independently, where the memory and the randomness of the arrival process are used for matching. With single iteration and less information exchange between stages, RWMD reduces the communication overhead greatly. Simula- tion shows that RWMD can achieve 100% throughput under uniform and non-uniform traffics.