Tuesday, August 23, 2016

One Sketch to Rule Them All: Rethinking Network Flow Monitoring with UnivMon

Zaoxing Liu (Johns Hopkins University)
Antonis Manousis (Carnegie Mellon University)
Gregory Vorsanger (Johns Hopkins University)
Vyas Sekar (Carnegie Mellon University)
Vladimir Braverman (Johns Hopkins University)

Ability to accurately estimate network metrics like flow size distribution, heavy hitters, super spreaders, entropy measures, traffic pattern changes, is useful for network management tasks like traffic engineering, accounting, worm detection and anomaly detection. The paper presents “UnivMon” framework that achieves high fidelity across a range of monitoring tasks while maintaining generality late binding and avoiding application-level specific customized algorithms. UnivMon is also aimed at providing "one-big-switch" abstraction for monitoring various dimensions through network-wide coordination schemes.

UnivMon's data plane uses primitives based on universal sketching, which requires no prior knowledge of the metrics, thereby providing the required late-binding through the usage of a general sketch. For any incoming stream of packets, UnivMon generates log(n) sub-streams by running the original stream through log(n) independent hash functions. Those sub-streams are then processed in parallel, to identify the L2 heavy-hitters and compute counters. These counters are then processed in an offline stage where the application metrics are estimated. To provide support for network-level monitoring, UnivMon control plane assigns the individual switches with sketching manifests, which are created with the goal of correctness and load balancing through solving a constrained optimization problem. The counters from individual switch sketches are then aggregated to provide network-wide monitoring.

UnivMon's data plane is implemented in P4 in four stages: sampling, sketching, heavy hitters computation, metric estimation. The first two stages are implemented in the data plane; the heavy hitters computation stage is partially handled by the data plane (heavy hitter identification) and the control plane (heavy hitters frequency computation). UnivMon is evaluated using CAIDA backbone traces. They compare the performance of UnivMon against OpenSketch for the following application metrics: heavy hitters, change detection and entropy estimation. They found UnivMon to be competitive with the custom per-application algorithms with a very low maximum error gap. UnivMon's memory requirements were also found to grow logarithmically. For the network-wide monitoring, even distribution of resources were provided by UnivMon.


Q: Can your universal monitor be used for reversible caches?
Yes, we can achieve the same result by sampling based techniques instead of using reversible keys. This will be similar to the approach on heavy hitters.

Q: IPv4 addresses which have 32-bits will lead to smaller tables, what happens with IPv6?

Memory usage increases only logarithmically, so this won’t be a problem.