Routing on Shortest Pair of Disjoint Paths with Bandwidth Guaranteed

被引：3
|
作者：
Leng, Hongze [1 ]
Song, Junqiang [1 ]
Xie, Zheng [2 ]
Liang, Meilian [3 ]
Zhang, Jun [4 ]
机构：
[1] Natl Univ Def Technol, Comp Sch, Changsha 410073, Hunan, Peoples R China
[2] Natl Univ Def Technol, Sch Sci, Changsha 410073, Peoples R China
[3] Guangxi Univ, Sch Math & Informat Sci, Nanning 530004, Peoples R China
[4] Beijing Univ Aeronaut & Astronaut, Sch Elect & Informat Engn, Beijing 100083, Peoples R China
来源：
EIGHTH IEEE INTERNATIONAL CONFERENCE ON DEPENDABLE, AUTONOMIC AND SECURE COMPUTING, PROCEEDINGS | 2009年
关键词：
QoS; multipath; shortest pair; disjoint; bandwidth; guaranteed; ALGORITHM; SELECTION;
D O I：
10.1109/DASC.2009.81
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
QoS routing and multipath routing have been receiving much attention respectively in network communication. However, the research combining those two kinds of routing is rare. This paper integrated the ideas of QoS and multipath, and presented the problem of Shortest Pair of Disjoint Paths with Bandwidth Guaranteed. We proved it to be NP-Complete, and then proposed a heuristic algorithm. The analysis indicates that our algorithm shows good performance and it can produce optimal solutions in most cases.
引用
收藏
页码：557 / +
页数：3
相关论文
共 50 条
  • [1] Routing on the Shortest Pairs of Disjoint Paths
    Babarczi, Peter
    Retvari, Gabor
    Ronyai, Lajos
    Tapolcai, Janos
    2022 IFIP NETWORKING CONFERENCE (IFIP NETWORKING), 2022,
  • [2] On Disjoint Shortest Paths Routing on the Hypercubea
    Cheng, Eddie
    Gao, Shuhong
    Qiu, Ke
    Shen, Zhizhang
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS, PROCEEDINGS, 2009, 5573 : 375 - +
  • [3] An Efficient Disjoint Shortest Paths Routing Algorithm for the Hypercube
    Qiu, Ke
    PROCEEDINGS OF THE 2008 14TH IEEE INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED SYSTEMS, 2008, : 43 - 47
  • [4] Bandwidth Guaranteed Shortest Path Routing in Wireless Mesh Networks
    Zeng, Yuanyuan
    Xi, Bo
    Zeng, Ziming
    Wang, Hao
    2006 FIRST INTERNATIONAL CONFERENCE ON COMMUNICATIONS AND NETWORKING IN CHINA, 2006,
  • [5] Multi-constrained Shortest Disjoint Paths for Reliable QoS Routing
    Xiong, Ke
    Qiu, Zheng-ding
    Guo, Yuchun
    Zhang, Hongke
    ETRI JOURNAL, 2009, 31 (05) : 534 - 544
  • [6] The disjoint shortest paths problem
    Eilam-Tzoreff, T
    DISCRETE APPLIED MATHEMATICS, 1998, 85 (02) : 113 - 138
  • [7] Shortest Disjoint Paths on a Grid
    Mari, Mathieu
    Mukherjee, Anish
    Pilipczuk, Micha L.
    Sankowski, Piotr
    PROCEEDINGS OF THE 2024 ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA, 2024,
  • [8] DISJOINT SHORTEST PATHS IN GRAPHS
    ENOMOTO, H
    SAITO, A
    COMBINATORICA, 1984, 4 (04) : 275 - 279
  • [9] Disjoint shortest paths problem
    Discrete Appl Math, 2 (113-138):
  • [10] Bandwidth Guaranteed Scheduling and Shortest Path Routing in Wireless Mesh Networks
    Zeng Ziming
    Zhang Liyi
    2007 INTERNATIONAL CONFERENCE ON WIRELESS COMMUNICATIONS, NETWORKING AND MOBILE COMPUTING, VOLS 1-15, 2007, : 1705 - 1708
12345