QoS路由问题的反向优化算法

张品; 李乐民; 王晟

QoS路由问题的反向优化算法

张品^{①②;李乐民},
李乐民,
王晟

计量
- 文章访问数: 1972
- HTML全文浏览量: 64
- PDF下载量: 492
- 被引次数: 0
出版历程
- 收稿日期: 2004-01-09
- 修回日期: 2004-06-25
- 刊出日期: 2005-06-19

Reverse Optimization Algorithm for QoS Routing Problem

Zhang Pin^{①②;李乐民},
Li Le-min,
Wang Sheng

摘要

摘要: 寻找满足两个加性QoS约束条件的路径是网络QoS路由研究的核心问题,线性搜索算法是重要近似算法之一。本文提出一种结合了反向优化策略的线性搜索算法。当线性搜索过程所得到的路径不满足QoS需求时,对搜索到的路径选取合适的节点进行反向优化。算法的时间复杂度为O(K(m+nlog2(n)))。仿真显示本文的搜索策略扩大了搜索空间,提高了寻找可行路径的成功率。
- 两约束路由问题; 线性搜索算法; 反向优化
Abstract: Finding the path satisfying two additive QoS constraints is the key question of QoS research. The linear search algorithm is one of important approximation algorithms. This paper proposes a new linear search algorithm combined with the reverse optimization scheme. If the path found by the linear search procedure does not satisfy the QoS constraints, the proper nodes of the path are chosen to make the reverse optimization. The time complexity of proposed algorithm is 0(K(m+nlog2(n))). The simulation shows that the new approach extends the search fields and improves the succeeding ratio of finding the feasible paths.

HTML全文

参考文献(1)

Crawley E, Nair R, Rajagopalan B, Sandick H. A framework for QoS-based Routing in the intemet. Intemet Draft, RFC2386,1998.[2]Guerin R, kamat S, Orda A, Przygienda T, Williams D. QoS routing mechanisms and OSPF extensions. Intemet Draft,RFC2676, 1998.[3]Wang Z, Crowcroft J. QoS routing for supporting resource reservation. IEEE J. on SAC, 1996, 14(9): 1228- 1234.[4]Sobrinho J. Algebra and algorithms for path computation and hop-by-hop routing in the internet[J].IEEE/ACM Trans. on the Networking.2002, 10(4):541-[5]Garey M, Johnson D. Computers and Intractability: A Guide to the Theory ofNP Completeness.[M]. San. Francisco, New York:W. H. Freeman, 1979, chp. 4.[6]Chen S, Nahrstedt K. An overview of quality of service routing for next-generation high-speed networks: Problems and Solutions[J].IEEE Network.1998, 12(6):64-[7]Warburton A. Approximation of Pareto optima in multipleobjective, shortest path problems[J].Operations Research.1987,35(1):70-[8]Hassin R. Approximation schemes for the restricted shortest path problems. Mathematics Operations Research, 1992, 17(1):136- 142.[9]Yuan. X. Heuristic algorithms for multiconstrained quality-ofservice routing[J].IEEE/ACM Trans. on the Networking.2002,10(2):244-[10]Cheng S.[J].Nahrstedt K. On finding multi-constrained paths [A].IEEE ICC98[C], Atlanta, GA.1998,:-[11]Jaffe J. Algorithms for finding paths with multiple constraints.Networks, 1984, (14): 95 - 116.[12]Neve H, Mieghem P. A multiple quality of service routing algorithm for PNNI.[A] Proceedings IEEE ATM Workshop[C],May 26-29, Fairfax, VA, 1998:324 - 328.[13]Korkmaz T, Krunz M. An efficient algorithm for finding a path subject to two additive constraints [J].Computer Communications Journal.2002, 25(3):225-

施引文献

资源附件(0)

访问统计