## Survivable Mobile Phone Architectures: Models and Solution Methods

Please always quote using this URN: urn:nbn:de:0297-zib-2582

- In the highly competitive area of telecommunications, cost, quality, and network management are among the most important aspects to be considered when designing a network. We study the problem of dimensioning a telecommunication network that is still operating in case of a failure of a network component. Given a demand between each pair of nodes of a telecommunication network and a finite set of possible capacities for each edge of the network, we consider the problem of deciding what capacity to install on each edge of the network in order to minimize the building cost of the network and to satisfy the demand between each pair of nodes, even if a network component fails. The routing of the demands must satisfy the following additional restrictions: (a) there is a maximum number of nodes allowed in each path between any pair of nodes (path length restriction), and (b) there is a maximum percentage of the demand between each pair of nodes that can be routed through any network component (diversification restriction). Moreover, the chosen capacities must be such that, for every single node or single edge failure, a certain percentage of the demand between any pair of nodes is reroutable (i.e. it ``survives'' the particular failure). We formulate the problem as a mixed integer linear programming problem and present a cutting plane algorithm as well as several heuristics for its solution. Furthermore, we discuss several ways to implement survivability into a telecommunication network.

Author: | Dimitris Alevras, Martin Grötschel, Peter Jonas, Ulrich Paul, Roland Wessäly |
---|---|

Document Type: | ZIB-Report |

Date of first Publication: | 1996/12/02 |

Series (Serial Number): | ZIB-Report (SC-96-48) |

ZIB-Reportnumber: | SC-96-48 |

Published in: | Appeared in: IEEE Communications Magazine 36 (1998) 88-93 |