ILP formulation of the exact solution of multi-constrained minimum cost multicast - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Computer Networks Année : 2018

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

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Identifiants

Citer

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⟩
168 Consultations
110 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More