Optimal design of experiments with application to the inference of traffic matrices in large networks: second order cone programming and submodularity

Guillaume Sagnol 1, 2, 3
Abstract : 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.
Document type :
Theses
Complete list of metadatas

https://pastel.archives-ouvertes.fr/pastel-00561664
Contributor : Guillaume Sagnol <>
Submitted on : Tuesday, February 1, 2011 - 4:23:01 PM
Last modification on : Wednesday, March 27, 2019 - 4:08:31 PM
Long-term archiving on : Tuesday, November 6, 2012 - 1:05:51 PM

Identifiers

  • HAL Id : pastel-00561664, version 1

Citation

Guillaume Sagnol. Optimal design of experiments with application to the inference of traffic matrices in large networks: second order cone programming and submodularity. Optimization and Control [math.OC]. École Nationale Supérieure des Mines de Paris, 2010. English. ⟨NNT : 2010ENMP0054⟩. ⟨pastel-00561664⟩

Share

Metrics

Record views

909

Files downloads

1270