Skip to Main content Skip to Navigation
New interface
Journal articles

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 - Methods, Algorithms for Operations REsearch
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 ATNET - Advanced Technolgy in Networking
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 metadata
Contributor : Miklos Molnar Connect in order to contact the contributor
Submitted on : Wednesday, October 3, 2012 - 12:19:23 PM
Last modification on : Tuesday, September 6, 2022 - 5:00:28 PM

Links full text



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



Record views