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

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/inria-00529121
Contributor : Ist Rennes <>
Submitted on : Monday, October 25, 2010 - 9:12:23 AM
Last modification on : Thursday, November 15, 2018 - 11:57:44 AM
Long-term archiving on: Wednesday, January 26, 2011 - 2:47:59 AM

File

PI-1957.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00529121, version 1

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⟩

Share

Metrics

Record views

480

Files downloads

467