一种基于时延约束的最优路径求解算法

作为QoS路由和流量工程的关键技术之一,基于时延约束的最优路径问题一直没有得到有效的解决.针对现有的算法很难得到最优解和计算复杂度过大等问题,提出了一种基于时延约束的最优路径求解(DCOP)算法,该算法通过减少算法的搜索空间来有效地降低算法的计算复杂度,可得到最优的无环解.算法采用自适应参数设计,提高了对网络规模和复杂业务变化的适应性.仿真表明该算法比同类算法计算复杂性降低了近一个数量级,且算法具有自适应能力,设计简单,易于工程实现. 

Algorithm for delay constraints optimal path calculation

As one of the most challenging problems in the QoS Routing and traffic engineering,the problem of delay constraints optimal path calculation has the non-polynomial(NP) complete complexity.The algorithm which is proposed in literature has some problem,such as not getting optimal path and being very hard complexity etc.So a delay constraints optimal path(DCOP) algorithm which can solve this problem well was proposed.By reduced the search region of the algorithm,the efficiency of algorithm can be improved effectively and an optimal loop-less path can be gotten.The self-adapting parameter design is adopted in this algorithm to improve the adaptability on the network scale and the changing of complicated service.Using extensive simulations on random graphs and random assigned link weights,the huge improvement in complexity of the new algorithm is tested.The test also indicate that the algorithm has more adaptability and more practicability.