针对高速交换结构的广义极大匹配调度算法

Extended Maximal Matching Algorithm in High-Speed Switches

调度算法是决定交换结构性能和实现复杂度的重要因素,极大匹配算法在这两方面存在不足.本文提出一类广义极大匹配(EMM)算法,使用不同权值参数能够派生出不同子类的算法.对广义极大匹配算法的研究从两方面展开,首先在2倍数据加速比下证明任何EMM(2)算法都能取得100%的吞吐量,并通过仿真表明能够取得与理想输出排队相近的延时性能;其次在没有加速比的条件下通过仿真表明具有2个以上权值参数的广义极大匹配算法能够大大提高极大匹配算法的吞吐量性能.

Scheduling algorithms make a great impact on the performance and implementation complexity of switch architecture. Traditional maximal matching （MM） algorithm cannot get a proper balance between these two factors,so in this paper we propose a new kind of Extended Maximal Matching （EMM） algorithm.By using different weight parameters,EMM algorithm can derive different kinds of algorithms. We prove that any EMM（2） algorithm with data speedup of 2 can deliver 100% throughput, and show it can also achieve almost the same delay performance as ideal Output Queueing （OQ）.Furthermore,under the situation of non-speedup, through simulation we show EMM algorithms, with more than two weight parameters, can greatly increase the throughput performance of MM algorithm.