Skip to Main content Skip to Navigation
Journal articles

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.
Complete list of metadatas

Cited literature [26 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01405702
Contributor : Miklos Molnar <>
Submitted on : Wednesday, November 30, 2016 - 12:06:34 PM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM
Long-term archiving on: : Monday, March 27, 2017 - 9:18:54 AM

File

JCC_2016111515091113.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

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. ⟨10.4236/jcc.2016.414005⟩. ⟨lirmm-01405702⟩

Share

Metrics

Record views

333

Files downloads

398