多约束分离路径算法

Disjoint Multiple-constrained Paths Algorithms

多媒体流和视讯会议等新应用的出现要求网络提供可靠的服务质量(QoS)保证。为网络中的每对节点建立两条多约束链路/节点分离路由是提供可靠QoS的一条重要途径。如何建立两条链路/节点分离多约束路径是一个关键问题,这一问题与经典的一维测度下的分离路径问题有着很多概念上的不同。本文分析了这一问题的困难性,并提出一组解决此问题的启发式算法。

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.