多约束分离路径算法DisjointMultiple-ConstrainedPaths-NAS.PDFVIP

多约束分离路径算法 多约束分离路径算法 *† ** ** 郭宇春 , Fernando Kuipers , Piet Van Mighem * 北京交通大学电子信息工程学院 ** 荷兰代尔夫特大学电子工程数学与计算机科学学院 摘要：多媒体流和视讯会议等新应用的出现要求网络提供可靠的服务质量（QoS）保证。为网络中的每对节点建立两条多约束 链路/节点分离路由是提供可靠QoS的一条重要途径。如何建立两条链路/节点分离多约束路径是一个关键问题，这一问题与经 典的一维测度下的分离路径问题有着很多概念上的不同。本文分析了这一问题的困难性，并提出一组解决此问题的启发式算法。 关键词：可靠QoS路由、分离路径、多约束路径 Disjoint Multiple-Constrained Paths Algorithms *† ** ** Yuchun Guo , Fernando Kuipers , Piet Van Mighem * School of Electronic and Information Engineering, Beijing Jiaotong University, 100044 Beijing, P.R. China ** Faculty o f Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, P.O. Box 5031, 2600 GA Delft, The Netherlands Abstract: Networks are expected to provide reliable quality of service (QoS) imposed by new applications such as multimedia streaming and video conferencing. Using two link/node-disjoint paths between a pair of nodes in a network is a common approach to provide reliable QoS. The problem of finding link/node disjoint paths satisfying multiple constraints is a major issue in this context . This problem faces many different concepts compared with the classical one-dimension disjoint paths problem. This paper addresses these conceptual problems and presents some heuristics for solving this problem. Key Words: reliable QoS routing, disjoint paths, multiple-constrained paths 1. 引言 随着多媒体流和视讯会议等新应用的出现要求网络提供可靠的服务质量 （QoS ）保证，不仅要满足应用 的QoS 要求，还要在网络故障时