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

Walid Khallef 1 Sylvain Durand 1 Miklós Molnár 1
1 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01818743
Contributor : Miklos Molnar <>
Submitted on : Tuesday, June 19, 2018 - 3:04:53 PM
Last modification on : Monday, December 10, 2018 - 7:02:02 PM

Identifiers

Collections

Citation

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

Share

Metrics

Record views

217