The Cost Optimal Solution of the Multi-Constrained Multicast Routing Problem

Miklós Molnár 1, * Alia Bellabas 2 Samer Lahoud 2
* Auteur correspondant
1 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 ATNET - Advanced Technolgy in Networking
IRISA-D2 - RÉSEAUX, TÉLÉCOMMUNICATION ET SERVICES
Abstract : In this paper, we define the cost optimal solution of the multi-constrained multicast routing problem. This problem consists in finding a multicast structure that spans a source node and a set of destinations with respect to a set of constraints, while minimizing a cost function. This optimization is particularly interesting for multicast network communications that require Quality of Service (QoS) guarantees. Finding such a structure that satisfies the set of constraints is an NP-hard problem. To solve the addressed routing problem, most of the proposed algorithms focus on multicast trees. In some cases, the optimal spanning structure (i.e. the optimal multicast route) is neither a tree nor a set of trees nor a set of optimal QoS paths. The main result of our study is the exact identification of this optimal solution. We demonstrate that the optimal connected partial spanning structure that solves the multi-constrained multicast routing problem always corresponds to a hierarchy, a recently proposed generalization of the tree concept. We define the directed partial minimum spanning hierarchies as optimal solutions for the multi-constrained multicast routing problem and analyze their relevant properties. To our knowledge, our paper is the first study that exactly describes the cost optimal solution of this NP-hard problem.
Type de document :
Article dans une revue
Computer Networks, Elsevier, 2012, 56 (13), pp.3136-3149. 〈10.1016/j.comnet.2012.04.020〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00738062
Contributeur : <>
Soumis le : mercredi 3 octobre 2012 - 12:19:23
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Lien texte intégral

Identifiants

Citation

Miklós Molnár, Alia Bellabas, Samer Lahoud. The Cost Optimal Solution of the Multi-Constrained Multicast Routing Problem. Computer Networks, Elsevier, 2012, 56 (13), pp.3136-3149. 〈10.1016/j.comnet.2012.04.020〉. 〈lirmm-00738062〉

Partager

Métriques

Consultations de la notice

421