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

【Abstract】 Ford-Fulkerson algorithm is a typical one to find the maximum flow in transport networks.While input-queued crossbar scheduling algorithms are making their efforts to match input ports and output ports of the switch as many as possible.So,Maximum Size Matching(MSM)and Maximum Weight Matching(MWM),which are based on the bipartite graph matching,become the theoretical criteria of various scheduling algorithms.In this paper,we explained how to employ Ford-Fulkerson algorithm in solving the bipartite graph matching.We have successfully applied this algorithm to the simulation of crossbar scheduling algorithms and obtained accurate simulation results.It can be a theoretical foundation to do further researches on scheduling algorithms.更多还原