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

QoS约束下的链路分离路径问题研究 被引量：11

Researches on the problem of link disjoint paths pair with QoS constraints
下载PDF
导出
摘要 研究了QoS约束下的链路分离路径问题,建立了2种QoS约束下的链路分离优化路径问题的模型。首先证明无向图的不具备端到端QoS约束的链路分离路径问题可以转化为其链路分裂图的对应问题,而具备端到端QoS约束的相应问题则无法进行类似转换。同时证明2种QoS约束下的链路分离优化路径问题都属于NP完全问题,最后对其近似算法进行研究并对算法进行比较测试。 The problem of link disjoint paths pair with QoS constraints was discussed. Two routing models about link disjoint optimal paths pair with QoS constraints were constructed. First it proved that the problem of link disjoint paths pair in the undirected graph without end to end QoS constraints counld be converted to the correspond problem in its link split graph, while the problem with end to end QoS constraints counld not be converted. Then it＇s proved that both of these questions are NP complete. Finally the approximation algorithms is given and simulation on them is made.
作者 张品 章坚武 李乐民 王晟
机构地区 杭州电子科技大学通信学院 电子科技大学光纤通信重点实验室
出处 《通信学报》 EI CSCD 北大核心 2006年第6期36-42,共7页 Journal on Communications
基金 国家自然科学基金资助项目(60472008) 浙江省自然科学基金资助项目(R105473)~~
关键词 链路分离路径 QOS约束 链路分裂图 link disjoint paths QoS constraints link split graph
分类号 TN915.01 [电子电信—通信与信息系统]
  • 相关文献

参考文献12

  • 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.

二级参考文献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.

同被引文献85

  • 1倪明放,王曦,武欣嵘,陈建文,于战科.多约束最优路由选择和不相交路由选择问题[J].军事通信技术,2010,31(4):71-76. 被引量：2
  • 2郭宇春,Fernando Kuipers,PietVan Mighem,陈常嘉.多约束分离路径算法[J].铁道学报,2005,27(2):49-57. 被引量：3
  • 3[1]CHEN S G,NAHRAEDT K.An overview of quality-of-service routing for the next generation high-speed networks:problems and solutions[J],IEEE Network,Special Issue on Transmision and Distribution of Digital Viedeo,1998,(11):64 -79.
  • 4[2]SUURBALLE J W.Disjoint paths in a network[J].Networks,1974,(4):125-145.
  • 5[3]BHANDARI R.Optimal diverse routing in telecommunication fiber networks[J].Proc.IEEEINFOCOM.94,Toronto,Ontario,Canada,1994,3(6):1498-1508.
  • 6[4]GUO Y C,KUIPERS F,MIEHGEM P V.A link-disjoint paths algorithm for reliable QoS routing[J].International Journal of Communication Systems,2003,16 (9):779-798.
  • 7DAS A,MARTEL C,MUKHERJEE B,et al.A better approach to reliable multi-path provisioning[A].IEEE Global Communications Conferences(GLOBECOM)[C].2007.2724-2728.
  • 8SAWADA N,KANEKO K.Pairwise disjoint paths in pancake graphs[A].Eighth International Conference on Parallel and Distributed Computing,Applications and Technologies,DPCAT 07[C].2007.376-382.
  • 9CHEN S,NAHRSTEDT K.On finding multi-constrained paths[A].IEEE International Conference on Communications ICC'98[C].1998.874-879.
  • 10TAFT-PLOTKIN N,BELLUR B,OGIER R.Quality-of-service routing using maximally disjoint paths[A].The 7th International Workshop on Quality-of-Service[C].1999.119-128.

引证文献11

二级引证文献31

通信学报
2006年 第6期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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