RAPPORT FINAL

Responsable : Pierre Fraigniaud (CNRS, LRI, Univ. Paris-Sud)

Principaux partenaires :

• LIAFA (Paris VII)
• LIP (ENS Lyon)
• LRI (Paris Sud)
• Mascotte (I3S et INRIA Sophia-Antipolis)
• Ares (INSA Lyon et INRIA Rhône-Alpes)
• Heudiasyc (UTC, Compiègne)

• Petits-mondes et graphe du Web (Responsable : Matthieu Latapy, LIAFA, Paris VII)
• Réseaux ad hoc (Responsable : Isabelle Guerin-Lassous, Ares, CITI, INRIA Rhône-Alpes)
• Réseaux pair-à-pair (Responsable : Pierre Fraigniaud, LRI, Paris Sud)
• Graphe physique d'Internet (Responsable : Nicolas Schabanel, LIP, ENS Lyon)
• Graphes évolutifs (Responsable : Afonso Ferreira, Mascotte, I3S, INRIA Sophia)
• Algorithmes répartis adaptatifs(Responsable : Bertrand Ducourthial, Heudiasyc, UTC)

Objectifs de Dynamo
Liste des participants
Liste de publications
Texte complet de la proposition .pdf.ps
Programme réunion 14 novembre 2002

Objectifs :

De récentes évolutions technologiques ont bouleversé la nature et l'utilisation des réseaux informatiques et de télécommunication. En particulier, ceux-ci ont gagné en dynamicité. Ainsi, les noeuds et/ou les utilisateurs peuvent se connecter et se déconnecter à volonté du réseau, modifiant continuellement sa topologie. Cette caractéristique se vérifie pour des technologies très différentes et dans des cadres très variés. L'action spécifique Dynamo a pour objectif d'étudier l'impact de la dynamicité sur l'utilisation et les performances des réseaux.

(retour haut de page)

• Jean-Claude Bermond (DR CNRS, I3S, Mascotte, INRIA Sophia-Antipolis)
• Stéphane Boucheron (CR CNRS, LRI, Paris Sud)
• Johanne Cohen (CR CNRS, LORIA, Nancy)
• Bertrand Ducourthial (MdC, UTC, Compiègne)
• Afonso Ferreira (DR CNRS, I3S, Mascotte, INRIA Sophia-Antipolis)
• Eric Fleury (CR INRIA, Ares, INRIA Rhône-Alpes)
• Pierre Fraigniaud (DR CNRS, LRI, Paris Sud)
• Isabelle Guerin-Lassous (CR INRIA, Ares, INRIA Rhône-Alpes)
• Cyril Gavoille (Prof, LaBRI, Bordeaux)
• Michel Habib (Prof, LIRMM, Montpellier)
• Nicolas Hanusse (CR CNRS, LaBRI, Bordeaux)
• Frédéric Havet (CR CNRS, I3S, Mascotte, INRIA Sophia-Antipolis)
• Colette Johnen (MdC, LRI, Paris Sud)
• Ralf Klasing (CR CNRS, I3S, Mascotte, INRIA Sophia-Antipolis)
• Claire Kenyon (Prof, LIX, Polytechnique)
• Jean-Claude Konig (Prof, LIRMM, Montpellier)
• Daniel Krob (DR CNRS, LIAFA, Paris VII)
• Matthieu Latapy (CR CNRS, LIAFA, Paris VII)
• Christophe Paul (CR CNRS, LIRMM, Montpellier)
• Stéphane Perennes (CR CNRS, I3S, Mascotte, INRIA Sophia-Antipolis)
• André Raspaud (Prof, LaBRI, Bordeaux)
• Nicolas Schabanel (CR CNRS, LIP, ENS Lyon)
• Sébastien Tixeuil (MdC, LRI, Paris Sud)
• Stéphane Ubéda (Prof, CITI, INSA Lyon)
• Alessandro Vespignani (CR CNRS, Lab. Physique Theorique, Paris Sud)
• Laurent Viennot (CR INRIA, Hipercom, INRIA Rocquencourt)

1. E. Altman, A. Ferreira, and J. Galtier. Les réseaux satellitaires de télécommunication. Dunod, 1999.
2. E. Bampis, R.Giroudeau and J-C. Konig. Using duplication for the multiprocessor scheduling problem with hierarchical communications. Parallel Processing Letter 10(1), pp133-140, 2000.
3. D. Barraez, S. Boucheron and W. Fernandez de la Vega. About the fluctuations of the giant component. Combinatorics, Probability and Computing 9, 287-304. 2000.
4. L. Barrière, P. Fraigniaud, L. Narayanan, and J. Opatrny. Dynamic construction of Bluetooth scatternets of fixed degree and low diameter. In 14th ACM-SIAM Symp. on Discrete Algorithms (SODA), 2003.
5. L. Barrière, P. Fraigniaud, L. Narayanan, and J. Opatrny. Robust position-based routing in wireless ad hoc networks with unstable transmission ranges. In 5th ACM International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM), 2001. (To appear in Wiley's Wireless Communications and Mobile Computing journal).
6. L. Barrière, P. Fraigniaud, E. Kranakiss, and D. Krizanc. Efficient routing in networks with long range contacts. In 15th International Symposium on Distributed Computing (DISC), 2001.
7. K. Bertet, C. Chaudet, I. Guerin Lassous and L. Viennot. Impact of Interferences on Bandwidth Reservation for Ad Hoc Networks: a First Theoretical Study. In IEEE Symposium on Ad Hoc Wireless Networks (SAWN), 2001.
8. C. Chaudet and I. Guerin Lassous. BRuIT: Bandwidth Reservation under InTerferences influence. In European Wireless (EW), pp466-472, 2002.
9. G. Chelius, E. Fleury, and S. Ubéda. Merging ad hoc environment with wireless access: an overview. In Mediterranean Ad Hoc Networking Workshop (Med-hoc-Net), 2002.
10. G. Chelius and E. Fleury. Ananas : A Local Area Ad hoc Network Architectural Scheme. In Mobile and Wireless Communications Networks (MWCN), IEEE, Sept. 2002.
11. T. Chich, J. Cohen and P. Fraigniaud. Unslotted deflection routing: a practical and efficient protocol for multi-hop optical networks. IEEE/ACM Transaction on Networking 9(1), pp47-59, 2001.
12. J. Cohen, E Fleury, and J. Gustedt. JUMBO : protocole de routage unicast dans les réseaux ad-hoc. 2èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), pp31-34, INRIA, 2000.
13. D. Coudert and H. Rivano. Lightpath assignment for multifibers wdm optical networks with wavelength translators. IEEE Globecom, 2002.
14. G. Damiand, M.Habib and C. Paul. A simple paradigm for graph recognition : application to cographs and distance hereditary graphs. Theoretical Computer Science 263, pp99-111, 2001.
15. . Ducourthial and S. Tixeuil. Self-stabilization with r-operators. Distributed Computing 14(3), pp147-162, 2001.
16. B. Ducourthial and S. Tixeuil. Self-stabilization with Path Algebra. Theoretical Computer Science (to appear).
17. B. Ducourthial and S. Tixeuil. Multidistribution multi-sources adaptative. In 3èmes rencontres francophones sur les Aspects Algorithmiques des Telecommunications (AlgoTel '01), pp135-142, INRIA, 2001.
18. A. Ferreira. On models and algorithms for dynamic communication networks: The case for evolving graphs. In 4èmes rencontres francophones sur les Aspects Algorithmiques des Telecommunications (AlgoTel '02), INRIA, 2002.
19. A. Ferreira and D. Krob. Editors of Mobile Networks Applications (MONET) -- Special Issue on Discrete Algorithms and Methods for Mobile Computing and Communications. ACM/Baltzer 6(6), 2001.
20. E Fleury and M Marathe. Editors of International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM). ACM Press, 2002.
21. E. Fleury and H. Koubaa. Service Location Protocol Overhead in the Random Graph Model for Ad Hoc Networks. In Symposium on Computers and Communications (ISCC), IEEE, 2002.
22. P. Gauron. Topologies dynamiques pour les systèmes pair-à-pair. Rapport de stage, DEA I.D., Ecole Doctorale Informatique, Paris Sud, 2002.
23. C. Gavoille. Routing in Distributed Networks: Overview and Open Problems. ACM SIGACT News 32(1), pp36-52, 2001.
24. C. Gavoille, M. Katz, N. Katz, C.Paul et D.Peleg Approximate distance labeling schemes. In European Symp. on Algorithms (ESA), LNCS 2161, pp476-487, 2001.
25. C. Gavoille and A. Zemmari. The Compactness of Adaptive Routing Tables. Journal of Discrete Algorithms 2(2), pp243-260, 2002.
26. J.-L. Guillaume, M. Latapy and L. Viennot. Efficient and Simple Encodings for the Web Graph. In 11-th Int. conference World Wide Web (WWW), 2002.
27. J.-L. Guillaume and M. Latapy The Web graph: an overview. In 4èmes rencontres francophones sur les Aspects Algorithmiques des Telecommunications (AlgoTel), INRIA, 2002.
28. N. Hanusse, E. Kranakis and D. Krizanc. Searching with Mobile Agents in Networks with Liars. Discrete Applied Mathematics (to appear).
29. N. Hanusse, D. Kavvadias, E. Kranakis and D. Krizanc. Memoryless Search Algorithms in Network with Faulty Advice. In IFIP International Conference on Theoretical Computer Science, pp206-217, 2002.
30. F. Havet and M. Wennink. The Push Tree Problem. In 13th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp318-319, 2001.
31. A.Irlande, J-C Konig, and C. Laforest. Construction of low-cost and low diameter steiner trees for multipoint groups. In SIROCCO, pp197-210 (2000)
32. A. Karlin, C. Kenyon and D. Randall. Dynamic TCP acknowledgement and other stories about e/(e-1). In 33rd Annual ACM Symposium on Theory of Computing (STOC), 2001.
33. C. Kenyon and N. Schabanel. The data broadcast problem with non-uniform transmission times. In 10th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp547-556, 1999. (Accepted for publication in Algorithmica).
34. C. Kenyon, N. Schabanel, and N. Young. Polynomial-Time Approximation Scheme for Data Broadcast. In 32nd ACM Symposium on Theory of Computing (STOC), pp659-666, 2000.
35. R. Pastor-Satorras, A. Vazquez, and A. Vespignani. Dynamical and correlation properties of the Internet. Physical Review Letters 87, 258701 (2001).
36. N. Schabanel. The databroadcast problem with preemption. In 17th Int. Symposium on Theoritical Aspects of Computer Science (STACS), LNCS 1770, pp181-192, 2000.
37. A. Vazquez, R. Pastor-Satorras, and A. Vespignani. Large scale topological and dynamical properties of the Internet. Physical Review E 65, 258701 (2002).
38. A. Vazquez, R. Pastor-Satorras, and A. Vespignani. Internet topology at the router and autonomous system level. Submitted to IEEE Journal on Selected Areas in Communications (2002).

  10h15-10h30 : Brève présentation de Dynamo (Pierre Fraigniaud)
  10h30-11h15 : Petits-mondes et graphe du Web (Matthieu Latapy)
  11h15-12h00 : Graphe physique d'Internet (J. Ignacio Alvarez-Hamelin et Nicolas Schabanel) Bibliographie: .bib

  12h00-13h30 : Déjeuner

  13h30-14h15 : Réseaux ad hoc (Isabelle Guerin-Lassous) Bibliographie: .txt
  14h15-15h00 : Réseaux pair-à-pair (Pierre Fraigniaud)

  15h00-15h30 : Pause café

  15h30-16h15 : Graphes évolutifs (Afonso Ferreira)
  16h15-17h00 : Algorithmes répartis adaptatifs (Bertrand Ducourthial)

  17h00-18h00 : Discussion

  18h00 Fin de la réunion

(retour haut de page)