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

Abstract : 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.
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger
Contributeur : Mohamed Lamine Lamali <>
Soumis le : dimanche 11 février 2018 - 15:35:04
Dernière modification le : mardi 8 janvier 2019 - 17:37:22
Document(s) archivé(s) le : lundi 7 mai 2018 - 23:54:49


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01706362, version 1


Mohamed Lamine Lamali, Nasreddine Fergani, Johanne Cohen. Algorithmic and complexity aspects of path computation in multi-layer networks. 2018. 〈hal-01706362v1〉



Consultations de la notice


Téléchargements de fichiers