Distributed Monitoring Problem

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.