2020 · 13 citations · 47 references
ComputingComputer SystemsComputer NetworksDistributed SystemsNetwork SecurityCongestion ControlFlow ControlNetwork Flow AlgorithmsNetwork FlowsNetwork Traffic AnalysisTraffic Flow AnalysisCongestion AnalysisCountersFlow-based AnalysisNetwork Flow AnalysisNetwork MonitoringNetwork Monitoring ArchitectureNetwork Traffic EngineeringTraffic Monitoring
Network-wide per-flow measurements are instrumental in diverse applications such as identifying attacks, detecting load imbalance, and performing traffic engineering. These measurements utilize scarcely available flow counters that monitor a single flow, but there are often more flows than counters in a single device. Therefore, existing flow-level techniques suggest pooling together the resources of all the network devices. Still, these either make strong assumptions on the traffic or require an excessive number of counters to track all the network flows. In this work, we present novel, readily deployable, distributed algorithms that do not require device coordination or assumptions about the traffic. Through an extensive evaluation on real network topologies and network traces, we show that our algorithms attain near-optimal flow coverage in diverse conditions. Specifically, our algorithms reduce the space required to monitor all the flows by up to 4x compared to the best alternative.
47
Space/time trade-offs in hash coding with allowable errors
Burton H. Bloom · Communications of the ACM · 1970 · 7.5K citations · Full text
Network traffic characteristics of data centers in the wild
Theophilus Benson, Aditya Akella, David A. Maltz · 2010 · 2.2K citations
Finding frequent items in data streams
Moses Charikar, Kevin Chen, Martı́n Farach-Colton · Theoretical Computer Science · 2003 · 1.3K citations
Biswanath Mukherjee, L.T. Heberlein, Karl Levitt · IEEE Network · 1994 · 1K citations