1. Distributed Monitoring Problem
- Author
-
Dimitri Papadimitriou, Bernard Fortz, Alcatel-Lucent Bell - Belgique, Alacatel Lucent, Integrated Optimization with Complex Structure (INOCS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université libre de Bruxelles (ULB)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Graphes et Optimisation Mathématique [Bruxelles] (GOM), and Université libre de Bruxelles (ULB)
- Subjects
Mathematical optimization ,021103 operations research ,Computer science ,Applied Mathematics ,05 social sciences ,Real-time computing ,0211 other engineering and technologies ,Passive monitoring ,050801 communication & media studies ,[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] ,02 engineering and technology ,Network monitoring ,Multi-commodity flow problem ,Task (project management) ,Network planning and design ,0508 media and communications ,Path (graph theory) ,Discrete Mathematics and Combinatorics ,Routing (electronic design automation) ,Integer programming ,ComputingMilieux_MISCELLANEOUS - Abstract
The distributed monitoring problem refers to the placement and configuration of passive monitoring points to jointly realize a task of monitoring traffic flows. Given a monitoring task, the objective consists in minimizing the total monitoring cost to realize this task. We formulate this problem as a mixed-integer program. This formulation can also be dualized to determine the gain obtained when varying the number of monitoring points (i.e., the installation cost) and the fraction of monitored traffic (i.e., the configuration cost). As traffic flows can follow different paths depending on the routing strategy, we compare the resulting cost and gain when they are routed along the min-cost path, the paths obtained by solving the min-cost multicommodity flow and the multicommodity capacity network design problem.
- Published
- 2016
- Full Text
- View/download PDF