Start Over

Distributed Monitoring Problem

Authors :: 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)
Université libre de Bruxelles (ULB)
Source :: Electronic Notes in Discrete Mathematics, Electronic Notes in Discrete Mathematics, 2016, 52, pp.13--20. ⟨10.1016/j.endm.2016.03.003⟩, Electronic Notes in Discrete Mathematics, Elsevier, 2016, 52, pp.13--20. ⟨10.1016/j.endm.2016.03.003⟩
Publication Year :: 2016
Publisher :: Elsevier BV, 2016.
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.