北京航空航天大学学报 ›› 2006, Vol. 32 ›› Issue (02): 209-213.

• 论文 • 上一篇    下一篇

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

张涛, 柳重堪, 张军   

  1. 北京航空航天大学 电子信息工程学院, 北京 100083
  • 收稿日期:2005-01-20 出版日期:2006-02-28 发布日期:2010-09-20
  • 作者简介:张 涛(1973-),男,山东威海人,博士生,zhtao73@163.com.
  • 基金资助:

    国家863资助项目(2003AA712022);国家自然科学基金资助项目(10377005)

Algorithm for delay constraints optimal path calculation

Zhang Tao, Liu Zhongkan, Zhang Jun   

  1. School of Electronics and Information Engineering, Beijing University of Aeronautics and Astronautics, Beijing 100083, China
  • Received:2005-01-20 Online:2006-02-28 Published:2010-09-20

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

Abstract: 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 toimprove 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.

中图分类号: 


版权所有 © 《北京航空航天大学学报》编辑部
通讯地址:北京市海淀区学院路37号 北京航空航天大学学报编辑部 邮编:100191 E-mail:jbuaa@buaa.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发