Advanced

Flow Adjustment - a Flexible Routing Strategy for Demand Protection Against Multiple Partial Link Failures

Fouquet, Y.; Nace, D.; Pioro, Michal LU and Poss, M. (2014) The Fourth International Conference on Advanced Communications and Computation, INFOCOMP 2014
Abstract
In this paper, we study a flexible routing strategy for demand protection and a corresponding optimization problem for networks that permanently experience fluctuations of the capacity available on their links. This is an important and novel topic as limited link availability is a fundamental feature of wireless networks; yet majority of work in survivable network design is restricted to total failures of single links. Hence, protection against partial failures of multiple links is considered as congestion avoidance. We assume a given finite set of network states. Each state is characterized by a vector of link availability coefficients specifying, for each link, the fraction of its nominal (maximum) capacity available in this state, and... (More)
In this paper, we study a flexible routing strategy for demand protection and a corresponding optimization problem for networks that permanently experience fluctuations of the capacity available on their links. This is an important and novel topic as limited link availability is a fundamental feature of wireless networks; yet majority of work in survivable network design is restricted to total failures of single links. Hence, protection against partial failures of multiple links is considered as congestion avoidance. We assume a given finite set of network states. Each state is characterized by a vector of link availability coefficients specifying, for each link, the fraction of its nominal (maximum) capacity available in this state, and by a traffic coefficients vector specifying, for each demand, the proportion of its nominal traffic to be realized in the considered state. Our routing strategy allows for adjustment (thinning or thickening) of the reference path-flows. For a given nominal value x of a path-flow, its thickening is limited to Tx where T is a given constant greater than or equal to 1. Thus, in each state, the value of every path-flow can range from 0 to T times its reference value. It turns out that the corresponding link cost minimization problem (where link capacities and state-dependant path-flows are decision variables) is NP-hard. We present a non-compact linear programming formulation of the problem together with a solution algorithm based on path generation. We illustrate the effectiveness of the introduced routing strategy by presenting numerical results for a set of representative network examples. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to conference
publication status
published
subject
conference name
The Fourth International Conference on Advanced Communications and Computation, INFOCOMP 2014
language
English
LU publication?
yes
id
b6413588-c5d2-4dfc-a083-191909400984 (old id 5364846)
alternative location
https://hal.archives-ouvertes.fr/hal-01062979/document
date added to LUP
2015-05-04 11:25:00
date last changed
2016-04-16 11:11:56
@misc{b6413588-c5d2-4dfc-a083-191909400984,
  abstract     = {In this paper, we study a flexible routing strategy for demand protection and a corresponding optimization problem for networks that permanently experience fluctuations of the capacity available on their links. This is an important and novel topic as limited link availability is a fundamental feature of wireless networks; yet majority of work in survivable network design is restricted to total failures of single links. Hence, protection against partial failures of multiple links is considered as congestion avoidance. We assume a given finite set of network states. Each state is characterized by a vector of link availability coefficients specifying, for each link, the fraction of its nominal (maximum) capacity available in this state, and by a traffic coefficients vector specifying, for each demand, the proportion of its nominal traffic to be realized in the considered state. Our routing strategy allows for adjustment (thinning or thickening) of the reference path-flows. For a given nominal value x of a path-flow, its thickening is limited to Tx where T is a given constant greater than or equal to 1. Thus, in each state, the value of every path-flow can range from 0 to T times its reference value. It turns out that the corresponding link cost minimization problem (where link capacities and state-dependant path-flows are decision variables) is NP-hard. We present a non-compact linear programming formulation of the problem together with a solution algorithm based on path generation. We illustrate the effectiveness of the introduced routing strategy by presenting numerical results for a set of representative network examples.},
  author       = {Fouquet, Y. and Nace, D. and Pioro, Michal and Poss, M.},
  language     = {eng},
  title        = {Flow Adjustment - a Flexible Routing Strategy for Demand Protection Against Multiple Partial Link Failures},
  year         = {2014},
}