Algorithmic and complexity aspects of path computation in multi-layer networks - CentraleSupélec Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2018

Algorithmic and complexity aspects of path computation in multi-layer networks

Résumé

Carrier-grade networks comprise several layers where different protocols coexist. Nowadays, most of these networks have different control planes to manage routing on different layers, leading to a suboptimal use of the network resources and to additional operational costs. However, some routers are able to encapsulate, decapsulate, and convert protocols, and act as a liaison between these layers. A unified control plane would be useful to optimize the use of the network resources and to automate the routing configurations. Software-Defined Networking based architectures, offer an opportunity to design such a control plane. One of the most important problems to deal with in this design is the path computation process. Classical path computation algorithms cannot resolve the problem as they do not take into account encapsulations and conversions of protocols. In this paper, we propose algorithms to solve this problem, and we study several cases. If there is no bandwidth constraint, we propose a polynomial algorithm that compute the optimal path. We also give lower and upper bounds on the optimal path length. On the other hand, we show that the problem is NP-hard if there is a bandwidth constraint (or other Quality of Service parameters), even if there is only two protocols and in a symmetric graph. We study the complexity and the scalability of our algorithms and evaluate their performances on real and random topologies. The results show that they are faster than the previous ones proposed in the literature. These algorithms can also have important applications in automatic tunneling.
Fichier principal
Vignette du fichier
TON_hal.pdf (1.32 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01706362 , version 1 (11-02-2018)
hal-01706362 , version 2 (01-11-2018)

Identifiants

  • HAL Id : hal-01706362 , version 1

Citer

Mohamed Lamine Lamali, Nasreddine Fergani, Johanne Cohen. Algorithmic and complexity aspects of path computation in multi-layer networks. 2018. ⟨hal-01706362v1⟩
745 Consultations
411 Téléchargements

Partager

Gmail Facebook X LinkedIn More