On the complexity of resilient network design
Author
Summary, in English
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.
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.
Department/s
Publishing year
2010
Language
English
Pages
108-118
Publication/Series
Networks
Volume
55
Issue
2
Document type
Journal article
Publisher
John Wiley & Sons Inc.
Topic
- Electrical Engineering, Electronic Engineering, Information Engineering
Status
Published
Research group
- Networking
ISBN/ISSN/Other
- ISSN: 1097-0037