Exact Algorithm to Solve the Minimum Cost Multi-Constrained Multicast Routing Problem - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Journal of Computer and Communications Year : 2016

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

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.
Fichier principal
Vignette du fichier
JCC_2016111515091113.pdf (1.57 Mo) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

lirmm-01405702 , version 1 (30-11-2016)

Licence

Attribution

Identifiers

Cite

Miklós Molnár. Exact Algorithm to Solve the Minimum Cost Multi-Constrained Multicast Routing Problem. Journal of Computer and Communications, 2016, Special Issue on Routing Research, 4 (14), pp.57-79. ⟨10.4236/jcc.2016.414005⟩. ⟨lirmm-01405702⟩
169 View
222 Download

Altmetric

Share

Gmail Facebook X LinkedIn More