多可加性条件下的端点到端点QoS路由算法

The end-to-end QoS routing algorithm under multi additional-conditions

基于QoS的路由是QoS中最关键的功能组件之一 .从本质上看 ,QoS路由就是端点到端点的带结点条件和边条件限制的最短路径问题 ,这种问题是NP完全的 .作者研究了可加性条件限制的QoS路由模型和路由算法 ,分析了可加性条件的性质并得到了其对路由长度限制的定理 ,为多个可加性条件的QoS路由问题建立了一个一般性的数学模型 ;最后根据此模型 ,提出了一种新的启发式求解算法 .在算法中 ,采用限制条件的可加性进行搜索剪枝 ,从而使新算法在实际应用中更有效 ;该算法的时间复杂度为o(lgm +n× (1+d1 +d2 +… +dρ0 ) ) .应用结果表明 ,由于采用搜索剪枝 ,该算法在实际应用中具有时间复杂度减小、运行速度加快等特点 .

One of critical functional components of QoS deployment is the QoS based routing. In essence, the QoS based is an end to end path finding problem with some constraints in nodes and in edges. This problem is NP completed problem. In this paper, the authors addressed the properties of additional conditions in QoS model, built a generalization mathematical model for QoS under multi additional conditions, proposed a new heuristic algorithm for this model. The algorithm is called the M WFS, which is the cutting branch WFS by using the result of theorem 1. The new algorithm′s time complexity is o(n lg m+n×(1+d 1+d 2+...+d ρ 0 )) and it is better than the other algorithm for this problem.