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

Miklós Molnár 1, * Alia Bellabas 2 Samer Lahoud 2
* Corresponding author
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.
Document type :
Journal articles
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00738062
Contributor : <>
Submitted on : Wednesday, October 3, 2012 - 12:19:23 PM
Last modification on : Thursday, November 15, 2018 - 11:57:46 AM

Links full text

Identifiers

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⟩

Share

Metrics

Record views

505