Skip to Main content Skip to Navigation
Journal articles

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 metadata
Contributor : Miklos Molnar <>
Submitted on : Friday, April 16, 2021 - 2:43:16 PM
Last modification on : Friday, April 16, 2021 - 3:36:08 PM
Long-term archiving on: : Saturday, July 17, 2021 - 6:46:46 PM


Files produced by the author(s)




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⟩



Record views


Files downloads