Availability-based path selection and network vulnerability assessment

Song Yang, Stojan Trajanovski, Fernando A. Kuipers*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

24 Citations (Scopus)

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 languageEnglish
Pages (from-to)306-319
Number of pages14
JournalNetworks
Volume66
Issue number4
DOIs
Publication statusPublished - 1 Dec 2015
Externally publishedYes

Keywords

  • availability
  • heuristic
  • integer nonlinear program
  • multilayer networks min-cut link-disjoint paths
  • reliability
  • routing
  • shared-risk link group networks
  • survivability

Fingerprint

Dive into the research topics of 'Availability-based path selection and network vulnerability assessment'. Together they form a unique fingerprint.

Cite this