Exact Algorithm to Solve the Minimum Cost Multi-Constrained Multicast Routing Problem

Miklós Molnár 1
1 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : The optimal solution of the multi-constrained QoS multicast routing problem is a tree-like hierarchical structure in the topology graph. This multicast route contains a feasible path from the source node to each of the destinations with respect to a set of QoS constraints while minimizing a cost function. Often, it is a tree. In other cases, the hierarchies can return several times to nodes and links of the topology graph. Similarly to Steiner problem, finding such a structure is an NP-hard problem. The usual tree and topology enumeration algorithms applied for the Steiner problem cannot be used to solve the addressed problem. In this paper, we propose an exact algorithm based on the Branch and Bound principle and improved by the Lookahead technique. We show relevant properties of the optimum hierarchy permitting efficient pruning of the search space. To our knowledge, our paper is the first to propose an exact algorithm for this non-trivial multi-constrained optimal multicast route computation. Simulations illustrate the efficiency of the proposed pruning operations. The analysis of the execution time shows that in simple topologies and with tight QoS constraints the exact algorithm requires relatively little execution time. With loose constraints the computation time cannot be tolerated even for off-line route computation. In these cases, the solution is close to a Steiner tree and heuristics can be applied. These results can serve as basis for the design of efficient, polynomial-time routing algorithms.
Type de document :
Article dans une revue
Journal of Computer and Communications, SCIRP, 2016, Special Issue on Routing Research, 4 (14), pp.57-79. 〈http://www.scirp.org/Journal/PaperInformation.aspx?PaperID=72009〉. 〈10.4236/jcc.2016.414005〉
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01405702
Contributeur : Miklos Molnar <>
Soumis le : mercredi 30 novembre 2016 - 12:06:34
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : lundi 27 mars 2017 - 09:18:54

Fichier

JCC_2016111515091113.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Collections

Citation

Miklós Molnár. Exact Algorithm to Solve the Minimum Cost Multi-Constrained Multicast Routing Problem. Journal of Computer and Communications, SCIRP, 2016, Special Issue on Routing Research, 4 (14), pp.57-79. 〈http://www.scirp.org/Journal/PaperInformation.aspx?PaperID=72009〉. 〈10.4236/jcc.2016.414005〉. 〈lirmm-01405702〉

Partager

Métriques

Consultations de la notice

153

Téléchargements de fichiers

129