17
Modélisation mathématique d’Internet Julien Reynier Publications disponibles sur http:// www.eleves.ens.fr /home/ jreynier /

Modélisation mathématique d’Internet

  • Upload
    tien

  • View
    35

  • Download
    0

Embed Size (px)

DESCRIPTION

Modélisation mathématique d’Internet. Julien Reynier. Publications disponibles sur http://www.eleves.ens.fr/home/jreynier/. Plan. Partie Pratique Une brève histoire d’Internet La congestion dans Internet Pourquoi modéliser ? Partie Théorique Équations fluides La méthode de champ moyen - PowerPoint PPT Presentation

Citation preview

Page 1: Modélisation mathématique d’Internet

Modélisation mathématique d’Internet

Julien Reynier

Publications disponibles sur http://www.eleves.ens.fr/home/jreynier/

Page 2: Modélisation mathématique d’Internet

Plan

• Partie Pratique– Une brève histoire d’Internet– La congestion dans Internet– Pourquoi modéliser ?

• Partie Théorique– Équations fluides– La méthode de champ moyen– Expérimentations

Page 3: Modélisation mathématique d’Internet

Les pionniers d’Internet

Tim Berners-Lee

Créateur du Web (1990-1992)

Vint Cerf

Créateur de TCP (1973-1980)

Jon Postel

Éditeur des RFC (1969-

1998)

Page 4: Modélisation mathématique d’Internet

Les briques techniques d’Internet

• Commutation de paquets (1960)

• Décentralisation complète (1965)

• TCP/IP : un protocole qui abstrait la couche matérielle (1973-1980)

• Des applications : mail (1972), forums et news (Usenet, 1979), le DNS (1987), WWW (1991), moteurs de recherche (1993)…

Page 5: Modélisation mathématique d’Internet

De l’idée à la réalité

• Un mécène : le DoD via ARPA

• Un déploiement universitaire massif (à partir de 1980)

• TCP/IP laissé dans le domaine public par ARPA (1986)

• Premiers ISP et fin progressive de l’AUP (1988-1992)

Page 6: Modélisation mathématique d’Internet

Plan

• Partie Pratique– Une brève histoire d’Internet– La congestion dans Internet– Pourquoi modéliser ?

• Partie Théorique– Équations fluides– La méthode de champ moyen– Expérimentations

Page 7: Modélisation mathématique d’Internet

Causes et solutions historiques

• 1975 : des collisions de paquets nombreuses aux concentrateurs (routeurs - switchs) -> Apposition de files d’attentes

• 1989 : capacité du réseau dépassée -> TCP implémente le contrôle de congestion décentralisé.

• 1993 : Tentative de contrôle au routeur• Aujourd’hui : le problème n’est toujours

pas définitivement résolu

Page 8: Modélisation mathématique d’Internet

Plan

• Partie Pratique– Une brève histoire d’Internet– La congestion dans Internet– Pourquoi modéliser ?

• Partie Théorique– Équations fluides– La méthode de champ moyen– Expérimentations

Page 9: Modélisation mathématique d’Internet

La modélisation pour les nuls

• Le problème de la congestion est trop difficile pour être résolu en temps raisonnable par l’ingénierie classique.

• L’interaction d’un grand nombre d’utilisateurs rend :– les simulations longues et inefficaces– les mesures difficiles à interpréter

• Les méthodes doivent « passer à l’échelle » pour résister à l’augmentation de l’usage. Ceci est irréalisable sans les mathématiques.

Page 10: Modélisation mathématique d’Internet

Plan

• Partie Pratique– Une brève histoire d’Internet– La congestion dans Internet– Pourquoi modéliser ?

• Partie Théorique– Équations fluides– La méthode de champ moyen– Expérimentations

Page 11: Modélisation mathématique d’Internet

L’approche classique

• Écrire ad nihilo les équations d’évolution du système considéré.

Page 12: Modélisation mathématique d’Internet

Pros et cons

• La formule marche bien en particulier pour des études de stabilité, elle modélise bien la réalité

• Elle n’a aucune justification, expérimentale ou mathématique

• Elle n’est pas adaptable pour étudier des variations dans le protocole

Page 13: Modélisation mathématique d’Internet

Plan

• Partie Pratique– Une brève histoire d’Internet– La congestion dans Internet– Pourquoi modéliser ?

• Partie Théorique– Équations fluides– La méthode de champ moyen– Expérimentations

Page 14: Modélisation mathématique d’Internet

L’approche de la physique statistique sur une version

améliorée de la physique quantique

• On modélise le comportement individuel des utilisateurs (avec mémoire)

• On étudie les lois de leur interaction lorsque leur nombre devient grand

• On en déduit la loi d’évolution exacte et prouvée. On connaît toutes les approximations qui ont été faites.

Page 15: Modélisation mathématique d’Internet

L’urne de Polya : le niveau 0 du champ moyen

• Une urne contient N boules, 55% de rouges et le reste de bleues

• On étudie la proportion de rouge sur le tirage de boules SANS remise.

• Quand N devient grand, cette proportion devient à coup sur exactement 55% sur tout tirage donné.

Application : Il est inutile de dépouiller tous les votes pour des élections

Page 16: Modélisation mathématique d’Internet

Plan

• Partie Pratique– Une brève histoire d’Internet– La congestion dans Internet– Pourquoi modéliser ?

• Partie Théorique– Équations fluides– La méthode de champ moyen– Expérimentations

Page 17: Modélisation mathématique d’Internet

0

200

400

600

800

1000

1200

1400

1600

1800

2000

0 2 4 6 8 10 12 14

400

0

1000

2000

3000

4000

0 2 4 6 8 10 12 14

800

0

200

400

600

800

1000

0 2 4 6 8 10 12 14

200

Limit : Matlab2 4 6 8 10 12 14 160

.1

.2

.3

.4

.5

.6.7.8.91

La convergence vers les équations du champ moyen