Abstract
In data-communication networks, network reliability is of great concern to both network operators and customers. On the one hand, the customers care about receiving reliable services and, on the other hand, for the network operators it is vital to determine the most vulnerable parts of their network. In this article, we first study the problem of establishing a connection over at most k (partially) link-disjoint paths and for which the total availability is no less than δ (0 < δ ≤ 1). We analyze the complexity of this problem in generic networks, shared-risk link group networks and multilayer networks. We subsequently propose a polynomial-time heuristic algorithm and an exact integer nonlinear program for availability-based path selection. The proposed algorithms are evaluated in terms of acceptance ratio and running time. Subsequently, in the three aforementioned types of networks, we study the problem of finding a (set of) network cut(s) for which the failure probability of its links is largest.
Original language | English |
---|---|
Pages (from-to) | 306-319 |
Number of pages | 14 |
Journal | Networks |
Volume | 66 |
Issue number | 4 |
DOIs | |
Publication status | Published - 1 Dec 2015 |
Externally published | Yes |
Keywords
- availability
- heuristic
- integer nonlinear program
- multilayer networks min-cut link-disjoint paths
- reliability
- routing
- shared-risk link group networks
- survivability