hal-00097726, version 1
Multicast tree allocation algorithms for distributed interactive simulation
International Journal of High Performance Computing and Networking 4 (2006) 137--151
Résumé : We deal with a way of realizing real-time communications required by a distributed interactive simulation (DIS), using multipoint communication technics. These technics would be the basic principles of the data distributed management (DDM) of the simulation tool. 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 (i.e., if the associated cells overlap) are represented by a graph called {\em neighborhood graph}. The problem we deal with consists in covering efficiently the neighborhood graphs by groups of nodes (such that each edge is covered by at least one group), and in allocating in the target network a subtree with a given bandwidth to each group. After giving the formal definition of the considered problem, we show that it is NP-complete. Then, we give some lower bounds technics. Finally, we give two heuristics to solve this problem and we analyse them.
- 1 :
- INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
- 2 :
- CNRS : UMR8144 – Université de Versailles Saint-Quentin-en-Yvelines
- Domaine : Informatique/Réseaux et télécommunications
Informatique/Algorithme et structure de données
Informatique/Modélisation et simulation
- hal-00097726, version 1
- http://hal.archives-ouvertes.fr/hal-00097726
- oai:hal.archives-ouvertes.fr:hal-00097726
- Contributeur :
- Soumis le : Vendredi 22 Septembre 2006, 11:09:18
- Dernière modification le : Vendredi 16 Novembre 2007, 14:20:53


Exporter