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

Improvement and Analysis of Widest Disjoint Paths Algorithm for Proportional Routing

针对最宽不相交路径(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.