期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

两约束路由问题的近似解法 被引量：1

Approximate algorithms for the bi-constraint path problem
在线阅读 下载PDF
导出
摘要 首先回顾了一些重要的QoS路由算法,然后对关于两约束路由问题(BCP,bi-constraintpath problem)的线性搜索算法进行了数学分析,确定了搜索因子的范围和最佳搜索因子的值。基于以上分析,我们给出了BCP和单约束最短路径问题(RSP,restricted shortest path problem)的近似算法,并对算法性能进行了分析;最后,本文研究了采用非线性链路代价函数求解BCP。测试结果表明本文提出的算法是求解BCP和RSP的有效算法。 We overview some important QoS routing algorithms. Then, we make mathematical analysis on the linear search algorithm for the BCP(bi-constraint path problem). We determine the bound of the search factor and the value of the best search factor. Based on this analysis, we propose approximate algorithms on BCP and RSP(restricted shortest path problem) and make performance analysis on them. At last we study using a non-linear function as the link function to solve BCP. The tests show that these algorithms are efficient.
作者 张品 李乐民 王晟
机构地区 电子科技大学宽带光纤传输与通信系统技术重点实验室
出处 《通信学报》 EI CSCD 北大核心 2003年第12期32-41,共10页 Journal on Communications
基金 国家自然科学基金(60002004)
关键词 两约束路由问题 线性搜索算法 QOS路由 搜索因子 非线性链路代价函数 bi-constraint path problem linear search algorithm QoS routing search factor
分类号 TN915.01 [电子电信—通信与信息系统]
  • 相关文献

参考文献10

  • 1[1]WANG Z, CROWCROFT J. QoS routing for supporting resource reservation[J] IEEE JSAC, 1996, 14(9): 1228-1234.
  • 2[2]GAREY M, JOHNSON D. Computers and Intractability: A Guide to the Theory of NP Completeness[M]. W H Freeman, San Francisco, 1979.
  • 3[3]CHENG S, NAHRSTEDT K. On finding multi-constrained paths[A]. IEEE ICC'98[C]. 1998. 874-879.
  • 4[4]KORKMAZ T, KRUNZ M. Multi-constrained optimal path selection[A]. IEEE INFOCOM 2001[C]. 2001. 824-833.
  • 5[5]NEVE H, MIEGHEM P. A multiple quality of service routing algorithm for PNNI[A]. Proceedings IEEE ATM Workshop[C]. Fairfax, VA, USA, 1998. 324-338.
  • 6[6]CHONG E, MADDILA S. On finding single source single destination k-shortest paths[A]. Proceedings 7th Int Conf Computing and Information[C]. 1995. 40-47.
  • 7[7]JAFFE J. Algorithms for finding paths with multiple constraints[J]. Networks, 1984, 14: 95-116.
  • 8[8]KORKMAZ T, KRUNZ M. An efficient algorithm for finding a path subject to two additive constraints[J]. Computer Comm- unications, 2002, 25(3):225-238.
  • 9[9]HASSIN R. Approximation schemes for the restricted shortest path problems[J]. Mathematics Operations Research, 1992, 17(12): 136-142.
  • 10[10]EPPSTEIN D. Finding the k-shortest paths[A]. Proceeding 35th. Symp Foundations of Computer Science[C]. 1994. 154-165.

同被引文献11

  • 1SUURBALLE J W.Disjoint paths in a network[J].Networks,1974,4(2):125-145.
  • 2SUURBALLE J W,TAR JAN R E.A quick method for finding shortest pairs of disjoint paths[J].Networks,1984,14(2):325-336.
  • 3BHANDARI R.Optimal diverse routing in telecommunication fiber networks[A].Proc IEEE NFOCOM 94[C].Toronto,Ontario,Canada,1994.1498-1508.
  • 4CASTANON D A.Efficient algorithms for finding the K best paths through a trellis[J].IEEE Trans on Aerospace and Electronic Systems,1990,26(2):405-410.
  • 5ALEXANDER S.Finding k disjoint paths in a directed planar graph[J].SIAM Journal on Computing,1994,23(4):780-788.
  • 6LEE S W,WU C S.A k-best paths algorithm for highly reliable communication network[J].IEICE Trans on Communication,1999,E82-B(4):586-590.
  • 7ITALIANO G,RASTOGI R,YENER B.Restoration algorithms for virtual private networks in the hose model[A].Proceedings of IEEE INFOCOM'02[C].New York,2002.131-139.
  • 8KAR K,KODIALAM M,LAKSHMAN T V.Routing restorable bandwidth guaranteed connections using maximum 2-route flows[J].IEEE/ACM Transactions on Networking,2003,11(5):772-781.
  • 9KODIALAM M,LAKSHMAN T V.Restorable dynamic quality of service routing[J].IEEE Communications Magazine,2002,40(6):72-81.
  • 10YUCHUN GUO,KUIPERS F,MIEGHEM P V.A link-disjoint paths algorithm for reliable QoS routing[J].International Journal of Communication Systems,2003,16(9):779-798.

引证文献1

二级引证文献11

通信学报
2003年 第12期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部