Title: An algorithm based on Voronoi diagrams for the multi-stream multi-source multicast routing problem

Authors: Romerito Campos De Andrade; Marco César Goldbarg; Elizabeth Ferreira Gouvêa Goldbarg

Addresses: Postgraduate Program in Systems and Computation, Federal University of Rio Grande do Norte, Campus Universitário, Lagoa Nova, Natal, RN, Brazil ' Department of Informatics and Applied Mathematics, Federal University of Rio Grande do Norte, Campus Universitário, Lagoa Nova, Natal, RN, Brazil ' Department of Informatics and Applied Mathematics, Federal University of Rio Grande do Norte, Campus Universitário, Lagoa Nova, Natal, RN, Brazil

Abstract: In this study, we present a new heuristic for the multi-stream multi-source multicast routing problem. The core of the heuristic proposed in this study is based on a generalisation of Voronoi diagrams in graphs. It allows building the trees needed to serve the demands of multiple sessions efficiently. Also, the proposed algorithm supports multiple sources. We performed an extensive experimental analysis of different network and problem configurations such as the number of sessions, nodes, sources and participants per session. We compare the proposed algorithm to heuristics proposed previously. The results of the experiments showed that the heuristic proposed in this study finds high-quality solutions efficiently.

Keywords: multicast routing; multi-source; multi-session; Voronoi diagram.

DOI: 10.1504/IJICA.2018.095789

International Journal of Innovative Computing and Applications, 2018 Vol.9 No.4, pp.216 - 229

Received: 08 Jun 2017
Accepted: 30 Jan 2018
Published online: 22 Oct 2018 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article