Extended Maximal Matching Algorithm in High-Speed Switches
Bin Liu · Dianzi xuebao · 2007
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.