Supervision : Clémence MAGNIEN

Analyse empirique et modélisation de la dynamique de la topologie de l’Internet

L'Internet est une structure complexe qui connecte environ trois milliards de personnes. Aucune carte officielle n'étant disponible, les chercheurs doivent mener des campagnes de mesure coûteuses, et gérer le fait que les données obtenues peuvent être biaisées. De nombreux travaux ont étudié la topologie de l’Internet, mais peu d’entre eux se sont intéressés à comment elle évolue. Nous considérons la dynamique de la topologie de routage au niveau IP et proposons un modèle simple qui simule la dynamique d’une topologie de réseau réel. En étudiant les résultats de la simulation, nous montrons que ce modèle captures les invariantes observés. De plus, l’analyse des résultats de simulations de différents types de réseaux nous permet de trouver des caractéristiques structurelles qui ont le plus grand impact sur ​la dynamique de la topologie. Nous trouvons, notamment, que le nombre de routes entre deux ordinateurs, qui correspond au plus courts chemins dans le modèle, joue un rôle important dans la dynamique. Nous étudions donc la taille du sous-graphe des plus courts chemins entre deux nœuds. Nous sommes aussi intéressés par les processus sous-jacents qui causent les dynamiques observées. Nous introduisons une méthode non-classique de l'estimation des paramètres de un processus stochastique et nous appliquons cette méthode pour les mesures modélisées et réelles afin de caractériser le taux de l'évolution de la topologie. Nous montrons aussi que la dynamique de réseau est une dynamique non-uniforme: les parties différentes du réseau peuvent avoir différentes vitesses d'évolution.

2011-2024 Publications

• 2024
  • J.‑L. Baril, M. Bousquet‑Mélou, S. Kirgizov, M. Naima : “The ascent lattice on Dyck paths”, (2024)
• 2023
  • J.‑L. Baril, S. Kirgizov, M. Naima : “A lattice on Dyck paths close to the Tamari Lattice”, Computational Logic and Applications, Kraków, Poland (2023)
  • J.‑L. Baril, S. Kirgizov, M. Naima : “A lattice on Dyck paths close to the Tamari lattice”, (2023)
• 2022
  • A. Baudin, M. Danisch, S. Kirgizov, C. Magnien, M. Ghanem : “Clique percolation method: memory efficient almost exact communities”, The 17^th International Conference on Advanced Data Mining and Applications (ADMA), Syndey, Australia (2022)
• 2015
  • F. Queyroi, S. Kirgizov : “Suppression Distance Computation for Hierarchical Clusterings”, Information Processing Letters, vol. 15 (9), pp. 689–693, (Elsevier) (2015)
• 2014
  • S. Kirgizov : “Analyse empirique et modélisation de la dynamique de la topologie de l’Internet”, thesis, phd defence 12/12/2014, supervision Magnien, Clémence (2014)
  • J. Bensmail, R. Duvignau, S. Kirgizov : “On the complexity of turning a graph into the analogue of a clique”, 9^th International colloquium on graph theory and combinatorics (ICGT 2014), Grenoble, France (2014)
• 2013
  • C. Magnien, A. Medem Kuatse, S. Kirgizov, F. Tarissan : “Towards realistic modeling of IP-level routing topology dynamics”, Networking science, vol. 3 (1-4), pp. 24-33 (2013)
  • S. Kirgizov : “Distribution multimodale de la taille du sous-graphe des plus courts chemins dans un graphe aléatoire”, Journées Graphes et Algorithmes (JGA), Orsay, France (2013)
  • S. Kirgizov, C. Magnien, F. Tarissan, A. Liu : “Studying the impact of measurement frequency on the IP-level routing topology dynamics”, Actes du Colloque sur le Traitement du Signal et des Images (GRETSI'13), Brest, France, pp. 1-4 (2013)
• 2011
  • X. Dutreilh, S. Kirgizov, O. Melekhova, J. Malenfant, N. Rivierre, I. Truck : “Using Reinforcement Learning for Autonomic Resource Allocation in Clouds: towards a fully automated workflow”, 7^th International Conference on Autonomic and Autonomous Systems (ICAS’2011), Venice, Italy, pp. 67-74 (2011)