Efficient multipath flow monitoring

Network administrators and traffic management tools need up-to-date traffic metrics to monitor and balance traffic load. Recording and reporting flow information is costly in terms of control plane traffic and router memory. Prior work mitigates these costs by limiting the number of monitoring devices, sampling, or only reporting constraint violations. However, these techniques are limited to single-path routing, do not address multiple network flows, and do not guarantee network coverage. We propose strategies to minimize the cost of placing a sufficient number of logical monitors on edges (called turnstiles) so as to monitor all (possibly multipath) flows. Our main result is an (ln m+1)(ln k+1)-approximation algorithm for the general Turnstile Placement problem, for a network with m edges and k flows (commodities). We also show achieving an o(ln k) approximation ratio is NP-hard. We examine a simple heuristic algorithm for the problem as well as a method to adapt existing single path solutions. Simulations show that our approximation algorithm achieves near optimal performance and outperforms existing approaches. The proposed methods reduce monitoring costs in multipath networks, enabling more agile and more accurate load balancing of network flows.