摘要： 输入排队Crossbar调度算法是以获得交换机的输入端口和输出端口最大匹配,从而得到高吞吐量为目的。因而在调度算法理论研究中把应用了二部图最大匹配的MaximumSizeMatching和MaximumWeightMatching算法作为目前各种调度算法性能评价标准。Edmonds-Karp算法是图论中求解网络最大流的经典算法之一。该文介绍了如何使用Edmonds-Karp算法求解二部图的最大匹配问题,并且应用算法于输入排队调度算法仿真中,得出经典MSM和MWM算法的性能仿真曲线,为进一步研究调度算法打下了理论基础。

关键词: 匹配, 调度, Edmonds-Karp算法

Abstract: Input-queued crossbar scheduling algorithms are employed to match input ports to output ports of a switch as many as possible.So,maximum size matching (MSM) and maximum weight matching (MWM),based on the bipartite graph matching,become the theoretical criteria of various scheduling algorithms.While Edmonds-Karp algorithm is a popular-used one to find the maximum flow in transport networks.This paper explains how to employ Edmonds-Karp algorithm in solving the bipartite graph matching,and have successfully applied this algorithm to the simulation of scheduling algorithms and got accurate simulation results.It can be a theoretical foundation to do further researches on scheduling algorithms.

中图分类号: 

• TP393.02