Minimum-Cost Multiple Paths Subject to Minimum Link and Node Sharing in a Network

In communication networks, multiple disjoint communication paths are desirable for many applications. Such paths, however, may not exist in a network. In such a situation, paths with minimum link and/or node sharing may be considered. This paper addresses the following two related fundamental questi...

Full description

Saved in:
Bibliographic Details
Published in:IEEE/ACM transactions on networking 2010-10, Vol.18 (5), p.1436-1449
Main Authors: Zheng, S Q, Jianping Wang, Bing Yang, Mei Yang
Format: Article
Language:English
Subjects:
Algorithm
Algorithms
Communication networks
complexity
Computer science
Costs
Criteria
disjoint paths
graph
Links
Load management
Mathematical models
multiple paths
network
network flow
network planning
Networks
Path planning
Polynomials
Protection
protocol
reliability
routing
Routing protocols
Studies
survivability
Telecommunication network reliability
Writing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In communication networks, multiple disjoint communication paths are desirable for many applications. Such paths, however, may not exist in a network. In such a situation, paths with minimum link and/or node sharing may be considered. This paper addresses the following two related fundamental questions. First, in case of no solution of disjoint multiple paths for a given application instance, what are the criteria for finding the best solution in which paths share nodes and/or links? Second, if we know the criteria, how do we find the best solution? We propose a general framework for the answers to these two questions. This framework can be configured in a way that is suitable for a given application instance. We introduce the notion of link shareability and node shareability and consider the problem of finding minimum-cost multiple paths subject to minimum shareabilities (MCMPMS problem). We identify 65 different link/node shareability constraints, each leading to a specific version of the MCMPMS problem. In a previously published technical report, we prove that all the 65 versions are mutually inequivalent. In this paper, we show that all these versions can be solved using a unified algorithmic approach that consists of two algorithm schemes, each of which can be used to generate polynomial-time algorithms for a set of versions of MCMPMS. We also discuss some extensions where our modeling framework and algorithm schemes are applicable.
ISSN:1063-6692
1558-2566
DOI:10.1109/TNET.2010.2044514