| 基于Edmonds-Karp算法的输入排队调度 |
| |
| 引用本文： | 法拉.基于Edmonds-Karp算法的输入排队调度[J].计算机工程,2005,31(18):13-15. |
| |
| 作者姓名： | 法拉 |
| |
| 作者单位： | 北京航空航天大学计算机科学与技术学院,软件开发环境国家重点实验室,北京,100083 |
| |
| 摘 要： | 输入排队Crossbar调度算法是以获得交换机的输入端口和输出端口最大匹配,从而得到高吞吐量为目的.因而在调度算法理论研究中把应用了二部图最大匹配的Maximum Size Matching和 Maximum Weight Matching算法作为目前各种调度算法性能评价标准.Edmonds-Karp算法是图论中求解网络最大流的经典算法之一.该文介绍了如何使用Edmonds-Karp算法求解二部图的最大匹配问题,并且应用算法于输入排队调度算法仿真中,得出经典MSM和MWM算法的性能仿真曲线,为进一步研究调度算法打下了理论基础.
|
| 关 键 词： | 匹配 调度 Edmonds-Karp算法 |
| 文章编号： | 1000-3428（2005）18-0013-03 |
| 收稿时间： | 06 10 2004 12:00AM |
| 修稿时间： | 2004-06-10 |
Input-queued Crossbar Scheduling Based on Edmonds-Karp Algorithm |
| |
| Falah Mousa Falah AlALI.Input-queued Crossbar Scheduling Based on Edmonds-Karp Algorithm[J].Computer Engineering,2005,31(18):13-15. |
| |
| Authors: | Falah Mousa Falah AlALI |
| |
| 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. |
| |
| Keywords: | Matching Scheduling Edmonds-Karp algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
