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

Abstract : In this paper, we study the cost optimal solution of the well-known multi-constrained multicast routing problem. This problem consists in finding a multicast structure that spans a source node and a set of destination nodes with respect to a set of constraints. This optimization problem is particularly interesting for the multicast network communications that require Quality of Service (QoS) guarantees. Moreover, finding the multicast structure with respect to the defined QoS requirements while minimizing a cost function is an NP-difficult optimization problem. According to the state-of-the-art, to solve the multi-constrained multicast routing problem, most of the proposed algorithms search for a multicast tree. In this paper, we demonstrate that the optimal connected partial spanning structure that solves the multi-constrained multicast routing problem can be different from a partial spanning tree. Indeed, we show that the minimum cost solution always corresponds to hierarchy, a recently proposed simple generalization of the tree concept. For that, we define and analyze the partial minimum spanning hierarchies as optimal solutions for the multi-constrained multicast routing problem. Moreover, we propose a branch and cut type exact algorithm that is based on some relevant properties of the hierarchical solutions.
Type de document :
Rapport
[Research Report] 11004, Rennes 1. 2010, pp.17
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00529121
Contributeur : Ist Rennes <>
Soumis le : lundi 25 octobre 2010 - 09:12:23
Dernière modification le : mardi 24 avril 2018 - 13:39:00
Document(s) archivé(s) le : mercredi 26 janvier 2011 - 02:47:59

Fichier

PI-1957.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00529121, version 1

Collections

Citation

Miklós Molnár, Alia Bellabas, Samer Lahoud. The Cost Optimal Solution of the Multi-Constrained Multicast Routing Problem. [Research Report] 11004, Rennes 1. 2010, pp.17. 〈inria-00529121〉

Partager

Métriques

Consultations de la notice

407

Téléchargements de fichiers

333