ILP formulation of the exact solution of multi-constrained minimum cost multicast - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Computer Networks Year : 2018

ILP formulation of the exact solution of multi-constrained minimum cost multicast

Abstract

Multimedia applications such as videoconferencing and collaborative applications require the satisfaction of several Quality of Service constraints (QoS). The routing with respect to QoS constraints was proposed in order to satisfy the user requirement and guarantee a certain level of performance to a data flow. As the communication architecture of these applications is often multicasting, the problem of finding a multicast route satisfying the QoS constraints proves to be challenging. In this paper we propose an Integer Linear Program (ILP) for finding the multicast route respecting a set of QoS constraints with minimum cost. Since the problem is NP-hard, we propose an efficient pretreatment algorithm (ArcReduce) to accelerate the resolution time. The pretreatment process can even answer in polynomial time, whether the problem has a solution or not, before starting the resolution process. The computation of the exact solution also allows for comparison of the heuristic solutions to the exact solution. We conduct an analysis of the ILP and the ArcReduce with various sizes of input data regarding the execution time, the success rate and the quality of the generated multicast route.
Fichier principal
Vignette du fichier
ComNetMM4janv_01818743.pdf (598.24 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-01818743 , version 1 (16-04-2021)

Identifiers

Cite

Walid Khallef, Sylvain Durand, Miklós Molnár. ILP formulation of the exact solution of multi-constrained minimum cost multicast. Computer Networks, 2018, 135, pp.160-170. ⟨10.1016/j.comnet.2018.02.016⟩. ⟨lirmm-01818743⟩
169 View
112 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More