文献类型：期刊文献

中文题名：最宽不相交多路径均衡路由算法的改进及其分析

英文题名：Improvement and Analysis of Widest Disjoint Paths Algorithm for Proportional Routing

作者：朱尚明[1];高大启[1]

机构：[1]华东理工大学计算机科学与工程系,上海200237

年份：2007

卷号：33

期号：3

起止页码：389

中文期刊名：华东理工大学学报（自然科学版）

外文期刊名：Journal of East China University of Science and Technology

收录：CSTPCD;;EI(收录号：20072910703238);Scopus;北大核心:【北大核心2004】；CSCD:【CSCD2011_2012】；

基金：国家自然科学基金资助项目(60373073);60675027;国家863计划(2006AA10Z315)

语种：中文

中文关键词：最宽不相交路径;候选路径;剩余带宽;阻塞概率

外文关键词：widest disjoint paths; candidate paths; residual bandwidth; blocking probability

摘要：针对最宽不相交路径(WDP)算法计算每个可行路径工作量大而且非常耗时——计算n条路径需要耗费O(n3)次迭代的问题,为了减少算法的复杂度和缩短计算候选路径的时间,提出了一种通过减少可行路径集的数量和限制计算迭代次数的改进算法,该算法使用具有可用带宽的可行路径集的子集代替所有可行路径来计算候选路径。性能分析表明:改进后的算法和最初的WDP算法相比具有较快的收敛速度和较低的计算复杂度,对于给定的通信流量能够提升网络性能。
It is a heavy computation to perform widest disjoint paths （WDP） algorithm on every path, and the algorithm is very time-consuming--computing a set of n paths will take O（n^3） cycles. To decrease the complexity of this algorithm and shorten the time of computing candidate paths, a modified WDP algorithm by reducing the number of available paths and limiting the number of iterations is proposed in this paper. Our proposed approach only uses a subset of available paths rather than all available paths to compute the candidate paths. Performance analysis shows that the proposed scheme provides much faster convergence and has less computation complexity in comparison with the original WDP algorithm, and it can yields potential better performance of an offered traffic flows.