Title: Multicast tree allocation algorithms for Distributed Interactive Simulation

Authors: Dominique Barth, Johanne Cohen, Corentin Durbach

Addresses: PRiSM-CNRS, Universite de Versailles-St Quentin en Yvelines, 45 avenue des Etats-Unis 78035 Versailles Cedex, France. ' LORIA-CNRS, 615 Rue du Jardin Botanique, 54602 Villers les Nancy, France. ' PRiSM-CNRS, Universite de Versailles-St Quentin en Yvelines, 45 avenue des Etats-Unis 78035 Versailles Cedex, France

Abstract: We consider real-time communications required by a Distributed Interactive Simulation (DIS), using multipoint communication technics. We focus here on a classical interactive game between participants distributed on a geographic map, where each participant is associated to a square cell on it. The needs of communication between participants are represented by a graph. The problem we consider consists in covering efficiently this graph by groups of nodes, and in allocating in the target network a subtree with a given bandwidth to each group. The problem is proved NP-complete. Lower bounds, and two heuristics with their analysis are provided.

Keywords: networks; distributed simulation; multicast; multipoint communication; intersection graphs; NP-completeness; heuristics; simulation; group communication.

DOI: 10.1504/IJHPCN.2006.010636

International Journal of High Performance Computing and Networking, 2006 Vol.4 No.3/4, pp.137 - 151

Published online: 10 Aug 2006 *

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