文章基本信息

标题：Multi-constrained Shortest Disjoint Paths for Reliable QoS Routing
本地全文：下载
作者：Xiong, Ke ; Qiu, Zheng-Ding ; Guo, Yuchun 等
期刊名称：ETRI Journal
印刷版ISSN：1225-6463
电子版ISSN：2233-7326
出版年度：2009
卷号：31
期号：5
页码：534-544
DOI：10.4218/etrij.09.0108.0531
语种：English
出版社：Electronics and Telecommunications Research Institute
摘要：Finding link-disjoint or node-disjoint paths under multiple constraints is an effective way to improve network QoS ability, reliability, and so on. However, existing algorithms for such scheme cannot ensure a feasible solution for arbitrary networks. We propose design principles of an algorithm to fill this gap, which we arrive at by analyzing the properties of optimal solutions for the multi-constrained link-disjoint path pair problem. Based on this, we propose the link-disjoint optimal multi-constrained paths algorithm (LIDOMPA), to find the shortest link-disjoint path pair for any network. Three concepts, namely, the candidate optimal solution, the contractive constraint vector, and structure-aware non-dominance, are introduced to reduce its search space without loss of exactness. Extensive simulations show that LIDOMPA outperforms existing schemes and achieves acceptable complexity. Moreover, LIDOMPA is extended to the node-disjoint optimal multi-constrained paths algorithm (NODOMPA) for the multi-constrained node-disjoint path pair problem.
关键词：QoS routing;network reliability;disjoint paths;multi-constrained;optimal solution;nondominance