使用Ford-Fulkerson算法研究输入排队调度

摘要：

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

关键词：Ford-Fulkerson、算法、匹配、调度

所属期刊栏目：41

分类号：TP391.9(计算技术、计算机技术)

在线出版日期：2005-04-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：79-81,110