3532 articles – 5253 Notices  [english version]

hal-00097726, version 1

Multicast tree allocation algorithms for distributed interactive simulation

Johanne Cohen () 1, Dominique Barth () 2, Corentin Durbach ()

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 :  Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA)
  • INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
  • 2 :  Parallélisme, Réseaux, Systèmes d'information, Modélisation (PRISM)
  • 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
  • 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