摘要
随着互联网的广泛应用,网络服务质量(QoS)保证技术显得越来越重要,为了保证网络服务质量,希望根据多个QoS约束参数来选择可行路由。一般说来,多受限路径优化问题是一个NP完全问题,因此在多项式时间复杂度里不能解决该问题,针对这个问题,在启发式算法的基础上,提出一种改进扩展Bellman-Ford最短路径算法(MEBF),将NP完全问题简化为在多项式时间复杂度里能解决的问题。模拟的结果表明,该算法有良好的运行效率和QoS路由成功率。
With the wider application based on the web technology, the guarantee technology of QoS gets more and more important. In order to realize the QoS, the alternate routing is applicable according to several QoS parameters with constraints. In general, the optimal routing problem with multiple constraints is a non-polynomial complete (NP-C) problem. Therefore, the problem can not be solved in the polynomial time based on the degree of complexity. Pointing to the problem an improving algorithm with modified extending Bellman-Ford was provided on the base of heuristic algorithm. Furthermore, the NP-C problem would be simplified and might be solved in polynomial time. The simulation results show that the algorithm is well efficient and rather potent.
出处
《计算机工程与设计》
CSCD
2004年第4期569-571,578,共4页
Computer Engineering and Design
