Distributed Network Monitoring with Bounded Link Utilization in IP Networks

Designing optimal measurement infrastructure is a key step for network management. In this work we address the problem of optimizing a scalable distributed polling system. The goal of the optimization is to reduce the cost of deployment of the measurement infrastructure by identifying a minimum poller set subject to bandwidth constraints on the individual links. 

We show that this problem is NP-hard and propose three different heuristics to obtain a solution. We evaluate our heuristics on both hierarchical and flat topologies with different network sizes under different polling bandwidth constraints. We found that the heuristic of choosing the poller that can poll the maximum number of un-polled nodes was the best approach. 

Our simulation studies show that the results obtained by our best heuristic is close to the lower bound obtained using LP relaxation (in the worst case, by a factor of 4 in terms of the number of pollers and by a 35% increase in terms of the bandwidth consumed).