Reformulating the Monitor Placement Problem: Optimal Network-wide Sampling

Confronted with the generalization of monitoring in operational networks, researchers have proposed static placement algorithms that can help ISPs deploy a network-wide monitoring infrastructure in a cost effective way. However, a static placement of monitors cannot be optimal given the short-term and long-term variations in traffic due to re-routing events, anomalies and the normal network evolution.

In addition, most ISPs already deploy router embedded monitoring functionalities. Despite some limitations (inherent to being part of a router), these monitoring tools give greater visibility on the network traffic but raise the question on how to configure a network-wide monitoring infrastructure that may contain hundreds of monitoring points.

Taking this new network monitoring tools into account, we reformulate the placement problem as follows: given a network where all links can be monitored, which monitors should be activated and which sampling rate should be set on them in order to achieve a given measurement task with high accuracy and low resource consumption? We provide a formulation of the problem, an optimal algorithm to solve it, and we study its performance on a real backbone network.

This is joint work with Gion Reto Cantieni (EPFL), Chadi Barakat (INRIA), Christophe Diot (Thomson) and Patrick Thiran (EPFL).