Flow monitoring is increasingly used for a wide range of network security and anomaly detection applications. These applications require that flow monitoring infrastructures provide high flow coverage and be able to support fine-grained network-wide objectives. Coordinated Sampling (cSamp) is a recent proposal for improving the flow monitoring capabilities of ISPs to address these demands. In this paper, we address a key deployment impediment for cSamp-like solutions – the requirement that each router must determine the Origin-Destination (OD) pair of each packet it observes. We cast cSamp in a new framework called cSamp-T that enables us to apply powerful results from the theory of maximizing submodular set functions to build effective flow monitoring solutions in which each router works with only local information. We show that cSamp-T provides near-ideal performance in maximizing the total flow coverage in the network. Further, with a small amount of additional targeted provisioning or upgrading a small number of ingress routers to add OD-pair identifiers, cSamp-T obtains near-optimal maximization of the minimum fractional coverage across all OD-pairs. We demonstrate these results on a range of real topologies. From a practical perspective, these results are promising since they expand the applicability of cSamp-like solutions to ISPs where OD-pair identification is challenging and also provides an incremental deployment path for ISPs. Additionally, we believe that many of the techniques we develop here are more broadly applicable to other aspects of network management and measurement.

32 pages

*Carnegie Mellon University and University of North Carolina-Chapel Hill

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by [email protected]