| 摘 要: 最坏情况的吞吐率是衡量路由算法性能的重要因素之一。负载最重的地方是最坏情况吞吐率的体现，因 此最坏情况的吞吐率在路由算法中很关键。在此基础上本文提出了通过利用匈牙利算法来评估网络负载的方法并且通过 实验仿真进行比较。将匈牙利算法和穷举法运用到Oblivious路由中的O1TURN、VAL等算法中进行比较。实验结果表 明运用该方法与利用传统的穷举法相比，可以大大减少计算量、降低时间复杂度，实验结果证明了方法的可行性和有 效性。 |
| 关键词: 匈牙利算法；最坏情况吞吐率；Oblivious路由；穷举法 |
|
中图分类号: TP393
文献标识码: A
|
| 基金项目: 国家自然科学基金项目“容错处理器网格的高效重构技术”(No60970016). |
|
| Methodology for Evaluating Network Load in Routing Algorithm Based on Hungarian Algorithm |
|
ZHANG Fangshuang,DUAN Xinming
|
( School of Computer Science and Software, Tianjin University of Technology, Tianjin 300387, China)
|
| Abstract: The worst-case throughput traffic is one of the important factors that evaluate the performance of the routing algorithm.The heaviest load is the demonstration of the worst-case throughput traffic,so the worst-case throughput traffic is critical in the routing algorithm.Based on this,this paper proposes a method to evaluate network load by using Hungarian algorithm and compares them through simulation experiments.Hungarian algorithm and exhaustive method are applied to O1TURN,VAL and other algorithms in Oblivious routing for comparison.The experimental results show that compared with the traditional exhaustive method,the proposed method can greatly reduce the computational complexity and the time complexity.It also proves the feasibility and effectiveness of the method. |
| Keywords: Hungarian algorithm;worst-case throughput;oblivious routing;exhaustive method |
