Some challenging problems in resilient network design

Session : SS1-2 / SS1 : Challenging Mixed-Integer Problems in Network Optimization
Jeudi 11 février 15:00 - 16:40 Salle : CI2-06
Yoann Fouquet, Dritan Nace, Michal Pioro et Michael Poss

In the presented study, we investigate network optimization problems related to the design and configuration of networks which can suffer from total or partial link failures. We are concerned with a general class of problems expressed in terms of minimum cost multi-commodity flow (MCMCF) problems, which are largely used for optimal design and dimensioning of telecommunication networks. These problems basically consist in transporting different commodities (traffic demands) from their respective sources to destinations, competing for network resources such as link capacities. Obviously, there should be enough capacity in the network to simultaneously carry all traffic required by the demands. In telecommunication networks, the idea of failure is largely limited to scenarios in which links fail totally but only one at a time (a failure state consists of total failure of one link, i.e., the temporary loss of that link). This assumption may be considered valid for large-scale wired networks using for instance optical fibers. However, there are several cases when the capacities of links are only partially reduced (i.e., links fail partially), and, moreover, several links can fail simultaneously. Examples of networks with such multiple partial link failures are as follows: - Wireless networks. A typical (link availability) state is characterized by a subset of those links that loose a fraction of their maximum capacity because of unfavorable weather (fog, rain, ...) that directly affects the channel transmission condition. - Upper layers of wired communication networks, such as MPLS layer. In such network layers a typical link failure state is composed of several links that lose a fraction of their capacity because of the effect of upwards propagation of the total failure of a single link in the transport (e.g., optical) network layer. Despite a large amount of strategies available to recover from total failures (global rerouting, N:M protection, path diversity, etc..), only a few of them seem to be able to manage partial failures.

Mots clés : resilent network, path generation, partial failure