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

来源期刊：中南大学学报(自然科学版)2001年第5期

论文作者：肖建华 王建新 陈松乔 陈建二

文章页码：528 - 531

关键词：QoS;时延;丢失率; NP完全问题

Key words：QoS; delay; loss rate; NP-completed problem

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

Abstract: One of critical functional components ofQoS deployment is the QoS-based routing. In essence, the QoS-basedis 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 undermulti additional-conditions, proposed a newheuristic algorithmforthismodel. The al gorithm 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(lgm+n×(1+d¹+d²+…+d^ρ₀))and it is better than the other algorithm for this problem.