• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Thèses
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Thèses
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

Survavibility in Multilayer Networks : models and Polyhedra

Sécurisation de réseaux multicouches : modèles et polyèdres

Taktak, Raouia (2013), Survavibility in Multilayer Networks : models and Polyhedra, doctoral thesis prepared under the supervision of Mahjoub, Ali Ridha, Université Paris Dauphine, 231 p.

View/Open
2013PA090076.pdf (1.663Mb)
Type
Thèse
Date
2013-07
Pages
231
Metadata
Show full item record
Author(s)
Taktak, Raouia
Under the direction of
Mahjoub, Ali Ridha
Abstract (FR)
Dans cette thèse, nous nous intéressons à un problème de fiabilité dans les réseaux multicouches IP-sur-WDM. Etant donné un ensemble de demandes pour lesquelles on connaît une topologie fiable dans la couche IP, le problème consiste à sécuriser la couche optique WDM en y cherchant une topologie fiable. Nous montrons que le problème est NP-complet même dans le cas d'une seule demande. Ensuite, nous proposons quatre formulations en termes de programmes linéaires en nombres entiers pour le problème. La première est basée sur les contraintes de coupes. Nous considérons le polyèdre associé. Nous identifions de nouvelles familles de contraintes valides et étudions leur aspect facial. Nous proposons également des algorithmes de séparation pour ces contraintes. En utilisant ces résultats, nous développons un algorithme de coupes et branchements pour le problème et présentons une étude expérimentale. La deuxième formulation utilise comme variables des chemins entre des terminaux dans le graphe sous-jacent. Un algorithme de branchements et génération de colonnes est proposé pour cette formulation. Par la suite, nous discutons d'une formulation dite naturelle utilisant uniquement les variables de design. Enfin, nous présentons une formulation étendue compacte qui, en plus des variables naturelles, utilise des variables de routage. Nous montrons que cette formulation fournit une meilleure borne inférieure.
Abstract (EN)
This thesis deals with a problem related to survivability issues in multilayer IP-over-WDM networks. Given a set of traffic demands for which we know a survivable logical routing in the IP layer, the aim is determine the corresponding survivable topology in the WDM layer. We show that the problem is NP-hard even for a single demand. Moreover, we propose four integer linear programming formulations for the problem. The first one is based on the so-called cut inequalities. We consider the polyhedron associated with the formulation. We identify several families of valid inequalities and discuss their facial aspect. We also develop separation routines. Using this, we devise a Branch-and-Cut algorithm and present experimental results. The second formulation uses paths between terminals of the underlying graph as variables. We devise a Branch-and-Price algorithm based on that formulation. In addition, we investigate a natural formulation for the problem which uses only the design variables.  Finally, we propose an extended compact formulation which, in addition to the design variables, uses routing variables. We show that this formulation provides a tighter bound for the problem.
Subjects / Keywords
Réseaux IP-Sur-WDM; Sécurisation; Complexité; Polytope; Facette; Algorithme de coupes et branchements; Algorithme de branchements et génération de colonnes; Formulation étendue; IP-Over-WDM networks; Survivability; Complexity; Facet; Branch-And-Cut algorithm; Branch-And-Price algorithm; Extended formulation
JEL
C44 - Operations Research; Statistical Decision Theory
C6 - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling

Related items

Showing items related by title and author.

  • Thumbnail
    Le problème de sécurisation multicouche du réseau optique 
    Gabrel, Virginie; Mahjoub, Ali Ridha; Taktak, Raouia (2010) Communication / Conférence
  • Thumbnail
    Design of Multilayer Survivable Optical Networks 
    Borne, Sylvie; Gabrel, Virginie; Mahjoub, Ali Ridha; Taktak, Raouia (2010) Communication / Conférence
  • Thumbnail
    Design of Multilayer Survivable Optical Networks 
    Gabrel, Virginie; Mahjoub, Ali Ridha; Taktak, Raouia (2010) Communication / Conférence
  • Thumbnail
    Multilayer Survivable Optical Network Design 
    Taktak, Raouia; Mahjoub, Ali Ridha; Gabrel, Virginie; Borne, Sylvie (2011) Communication / Conférence
  • Thumbnail
    Gestion de la sécurité dans les systèmes de télécommunications : modèles, polyèdre et algorithmes 
    Naghmouchi, Mohamed yassine (2019-06-17) Thèse
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo