Optimal design of experiments with application to the inference of traffic matrices in large networks: second order cone programming and submodularity
Plans d'expériences optimaux et application à l'estimation des matrices de trafic dans les grands réseaux : programmation conique du second ordre et sous-modularité
Résumé
We approach the problem of optimizing the measurements in large IP networks, by using the theory of optimal experimental designs. This method gives raise to large scale optimization problems, for which we develop a resolution technique relying on Second Order Cone Programming (SOCP). The heart of our method is a rank reduction theorem in semidefinite programming. Some combinatorial problems --which arise when the goal is to find an optimal subset of the available experiments-- are also studied. The application to the inference of the traffic matrix in telecommunication networks is the object of the second part of this manuscript. We develop a method in which we optimize the estimation of several (randomly drawn) linear combinations of the traffic demands. This approach is compared to previous ones, and is fully evaluated by mean of simulations relying on real data. In particular, we handle some instances that were previously intractable.
Nous abordons le problème de l'optimisation des mesures dans les grands réseaux Internet par la théorie des plans d'expériences optimaux. Cette approche donne lieu d'étudier des problèmes de grande taille en conception optimale d'expériences, pour lesquels nous développons une méthode de résolution fondée sur l' Optimisation Conique du Second Ordre. Le cœur de notre méthode est un théorème de réduction du rang en optimisation semi-définie. Certains aspects combinatoires sont également étudiés. L'application à l'inférence des matrices de trafic dans les réseaux IP fait l'objet de la seconde partie de ce manuscrit. Nous développons une méthode où l'on optimise l'estimation de plusieurs combinaisons linéaires (tirées de façon aléatoire) des demandes de trafic. Nous comparons notre approche aux précédentes au travers de simulations sur des données réelles. En particulier, nous traitons des instances pour lesquelles les approches précédentes étaient incapables de fournir une solution.