Description
Date depot: 1 janvier 1900
Titre: Inverse problems in networks
Directeur de thèse:
François BACCELLI (Inria-Paris (ED-386))
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
{{{Introduction au sujet de la thèse:}}}
La {tomographie par sondes actives} consiste à reconstruire l'état
internet d'un réseau (en général Internet) en le bombardant de sondes qui se mélange au trafic réel en différents points d'entrées, et en mesurant les pertes et réceptions de ces sondes ainsi que leur délais en divers points de sortie. Ces informations permettent ensuite de déduire de nombreux renseignements sur l'état global du réseau (connectivité, taux de pertes, délais moyens, localisation des ``problèmes'', bande passante des liens, etc.). Cette approche comporte de nombreux avantages:
-* Elle ne nécessite aucun accès interne au réseau: seules des mesures de bout en bout sont effectuées. Ce point est crucial car Internet est divisé en de nombreuses entités indépendantes (les systèmes autonomes, AS), généralement concurrentes et non-coopératives.
-* Elle tient naturellement compte de la nature dynamique du trafic et du réseau, grâce à l'interaction entre les paquets-sondes et les paquets normaux.
-* Comparées aux méthodes de mesure dites emph{passives}, elle ne nécessite et génère que peu de données, et ne pose pas les problèmes d'acheminement ou de stockage de ces données.
La thèse envisagée consistait à construire des fondements théoriques pour la tomographie par sondes actives, tant sur les plans mathématiques que statistiques et algorithmiques.
{{{Résultats obtenus:}}}
Mon travail lors de ces trois années s'est concentré sur 4 axes :
-# Un {travail de formulation des problèmes inverses} en théorie des files d'attente. Si les techniques ont déjà été utilisées en pratique, la formulation en tant que problème inverse pour un modèle de réseau est a priori nouvelle: nous avons formulé une définition générale de ces problèmes, répertorié les classes et caractéristiques principales des problèmes inverses, et indiqué leurs liens avec les mesures sur Internet ainsi que quelques exemples généraux.
-# Une {résolution détaillée de deux problèmes précis}: l'estimation paramétrique pour un réseau de Kelly en chaîne. Les réseaux de Kelly sont un premier choix naturel: il s'agit d'un modèle important en théorie des files d'attente, qui est à la fois réaliste et résolu par formes closes. Nous avons fourni un estimateur non-robuste au bruit à partir des moments des délais de bouts en bouts.
Pour le cas à 2 serveurs uniquement, nous avons étudié l'estimateur du maximum de vraisemblance, basé sur la distribution empirique des délais des sondes. Nous avons montré qu'il est asymptotiquement consistent, et qu'il vérifie une équation de point fixe qui n'admet en général qu'une seule solution.
Nous fournissons également une autre méthode de calcul basé sur l'algorithme Expectation-Maximization (EM), dont nous montrons dans ce cas particulier que ses paramètres convergent nécessairement vers une solution de l'équation de vraisemblance. Nous avons généralisé cette méthode à un nombre quelconque de noeuds. Des exemples numériques montrent que ces estimateurs sont performant à partir d'un nombre raisonnable de sondes.
Les méthodes ont été généralisées pour des arbres de diffusion en multicast}, gardant les hypothèses principales des réseaux de Kelly (à l'exception des sondes, qui sont multicast). À l'aide d'arguments de combinatoire sur des graphes, nous exprimons la densité jointe des délais des sondes (en fonction des capacités résiduelles des noeuds), et donnont alors une formule close pour l'itération de l'algorithme EM. L'algorithme EM étant extrêmement lent dans ce cas, nous avons développé des méthodes d'accéleration novatrices et efficaces, qui peuvent servir dans de nombreux cas d'algorithme itératifs où les deplacements sont ``proches de droites brisées''. Enfin, des études numériques montrent que l'algorithme EM convergent bien dans tous les cas génériques étudiés, et semblent indiquer (de manière préliminaire) que la méthode est relativement résilente à une imprécision de mesure des délais.
-# Une {validation empirique}, basée sur des traces de trafic collectée sur un serveur de coeur de réseau, pour le réseau de Kelly en chaine. À l'aide d'un simulateur, il s'agissait de valider les estimateurs proposés sur des traces réelles, et d'identifier les hypothèses cruciales, ainsi que celles qui sont vérifiées en pratique sur Internet. À partir d'enrichissement du modèle, nous avons proposé des facteur correctifs, simple à calculer en pratique.
-# Une étude des réseaux à partage de bande passante. Ces réseaux, qui admettent une forme produit, attribuent un débit à chaque flot de sorte à maximiser une fonction d'objectif. Il a été montré qu'avec de bons paramètres, les débits ainsi obtenus correspondent à ceux des protocoles TCP. Nous avons indiqué un certain nombres de problèmes inverses possibles, ainsi que leur signification précise, pour deux exemples de réseaux simples. Dans chaque cas, nous avons indiqué si le problème inverse était résoluble ou ambigü, ainsi qu'une méth
Doctorant.e: Kauffmann Bruno