On The Overlay Network Design Problem For The Soft-Label Switched Paths In Ip Networks

Abstract

In this paper, we tackle the design problem of the network overlay used by the soft-label switched paths (soft-LSPs) in Internet protocol (IP) networks. The design problem consists in finding the capacity on each link and the routing metrics that ensure the successful rerouting of the soft-LSPs for all failure scenarios of interest to the network planner. The objective is to minimize the cost of the network overlay. A mixed non-linear mathematical programming model is proposed for the problem. In order to obtain “good” solutions for real-size instances of the problem, we propose a tabu search algorithm. Finally, numerical result arc presented and analyzed.

Résumé

Dans cet article, nous traitons du problème de la conception du réseau logique utilisé par les LSPs (Label Switched Paths) souples dans les réseaux IP (Internet Protocol). Le problème consiste a trouver la capacité qui devra être réservée sur chaque lien ainsi que les métriques des liens qui assurent le réacheminement des LSPs souples pour tous les scénarios de pannes d’intérêts pour le planificateur du réseau. L’objectif est de minimiser le coût du réseau logique. Un modèle de programmation mathématique non linéaire à variables mixtes est proposé. Dans le but d’obtenir de bonnes solutions pour des exemplaires de taille réelle, un algorithme de recherche avec tabous est proposé. Des résultats numériques sont présentés et analysés.

Key words::

• network overlay design
• soli-label switched paths
• mathematical model
• tabu search

Mots-clés::

• conception d’un réseau logique
• label switched paths
• modèle mathématique
• recherche avec tabous

Additional information

Notes on contributors

Steven Chamberland

Steven Chamberland received the Electrical Engineering degree from the École Polytechnique de Montréal in 1994 and the Ph.D. degree in Operations Research in 1998 also from the École Polytechnique. From 1998 to 1999, he was with the network architecture group of Bell Canada and from 1999 to 2001, he was a professor at the École de technologie supérieure. Since 2001, he has been an assistant professor of Computer Engineering at lhe École Polytechnique. His research interests include telecommunication network planning and design and network architecture. Dr. Chamberland is a member of IEEE and ACM.