电子学报 ›› 2001, Vol. 29 ›› Issue (4): 510-514.

• 论文 • 上一篇    下一篇

基于信源路由的时延受限点到点路由算法

张宝贤, 刘 越, 陈常嘉   

  1. 北方交通大学通信与信息工程系,北京 100044
  • 收稿日期:2000-01-03 修回日期:2000-06-08 出版日期:2001-04-25 发布日期:2001-04-25

Source-Based Delay-Constrained Unicast Routing Algorithms

ZHANG Bao-xian, LIU Yue, CHEN Chang-jia   

  1. Department of Communication and Information Engineering,Northern Jiaotong University,Beijing 100044,China
  • Received:2000-01-03 Revised:2000-06-08 Online:2001-04-25 Published:2001-04-25

摘要: 本文研究了网络路由中的一个NPC问题:时延受限最小代价路由问题.文中提出了一个理论框架,并给出了多个简单有效的启发式算法,在满足给定时延约束条件可行路径存在时,算法总能找到满足约束条件的代价优化路径.文中提出的启发式算法复杂性为O(|V|2)且在线复杂性为O(|V|).仿真显示算法取得了良好的平均代价性能.最后将模型扩展到多QoS限制条件下的路由问题.

关键词: 时延受限, 服务质量路由, 信源路由

Abstract: In this paper,we study the NP-hard delay-constrained least-cost routing problem.We propose a new framework to solve the problem and provide simple and efficient source routing heuristics from the model,through which one can always find a delay-constrained path if such a path exists.Computation complexity of our heuristics is O(|V|2) and on-line complexity is O(|V|).Simulation results show that our heuristics achieve good cost performance.Finally,we extend the model to routing problem under multiple QoS constraints.

Key words: delay-constrained, QoS-based routing, source routing

中图分类号: