Advanced

On the complexity of resilient network design

Tomaszewski, A; Pioro, Michal LU and Zotkiewicz, M (2010) In Networks 55(2). p.108-118
Abstract
In this article we prove NP-hardness of two well-known

optimization problems related to the design of multicommodity

flow networks with two different methods

for providing network resiliency against failures: path

diversity and flow restoration. Path diversity is a static

mechanism that consists of using, for each demand, a

number of paths and oversizing the flows assigned to

these paths so that for any failure the total surviving flow

is not less than the volume of the demand. By contrast,

flow restoration is a dynamic mechanism that consists

of reassigning the failed flows to backup paths when a

failure occurs. Both mechanisms are of... (More)
In this article we prove NP-hardness of two well-known

optimization problems related to the design of multicommodity

flow networks with two different methods

for providing network resiliency against failures: path

diversity and flow restoration. Path diversity is a static

mechanism that consists of using, for each demand, a

number of paths and oversizing the flows assigned to

these paths so that for any failure the total surviving flow

is not less than the volume of the demand. By contrast,

flow restoration is a dynamic mechanism that consists

of reassigning the failed flows to backup paths when a

failure occurs. Both mechanisms are of practical interest

because although flow restoration is in general superior

to path diversity in terms of the required amount of

resource capacity, it might be too complicated to implement.

By providing an appropriate reduction from the

fractional graph coloring problem, we show that both

problems are NP-hard in the general case of failure

scenarios that admit simultaneous failures of multiple

links. Finally, we discuss how to efficiently solve the two

problems using path generation techniques. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
Networks
volume
55
issue
2
pages
108 - 118
publisher
John Wiley & Sons
external identifiers
  • wos:000274946600005
  • scopus:77049101234
ISSN
1097-0037
DOI
10.1002/net.20321
language
English
LU publication?
yes
id
c735dcf2-ed1a-4054-afb8-7e20ca8795a0 (old id 1363112)
date added to LUP
2009-03-19 15:52:52
date last changed
2017-01-01 07:52:48
@article{c735dcf2-ed1a-4054-afb8-7e20ca8795a0,
  abstract     = {In this article we prove NP-hardness of two well-known<br/><br>
optimization problems related to the design of multicommodity<br/><br>
flow networks with two different methods<br/><br>
for providing network resiliency against failures: path<br/><br>
diversity and flow restoration. Path diversity is a static<br/><br>
mechanism that consists of using, for each demand, a<br/><br>
number of paths and oversizing the flows assigned to<br/><br>
these paths so that for any failure the total surviving flow<br/><br>
is not less than the volume of the demand. By contrast,<br/><br>
flow restoration is a dynamic mechanism that consists<br/><br>
of reassigning the failed flows to backup paths when a<br/><br>
failure occurs. Both mechanisms are of practical interest<br/><br>
because although flow restoration is in general superior<br/><br>
to path diversity in terms of the required amount of<br/><br>
resource capacity, it might be too complicated to implement.<br/><br>
By providing an appropriate reduction from the<br/><br>
fractional graph coloring problem, we show that both<br/><br>
problems are NP-hard in the general case of failure<br/><br>
scenarios that admit simultaneous failures of multiple<br/><br>
links. Finally, we discuss how to efficiently solve the two<br/><br>
problems using path generation techniques.},
  author       = {Tomaszewski, A and Pioro, Michal and Zotkiewicz, M},
  issn         = {1097-0037},
  language     = {eng},
  number       = {2},
  pages        = {108--118},
  publisher    = {John Wiley & Sons},
  series       = {Networks},
  title        = {On the complexity of resilient network design},
  url          = {http://dx.doi.org/10.1002/net.20321},
  volume       = {55},
  year         = {2010},
}