The recent introduction of SDN allows deploying new centralized network algorithms that dramatically improve network operations. In such algorithms, the centralized controller obtains a network-wide view by merging measurement data from Network Measurement Points (NMPs). A fundamental challenge is that several NMPs may count the same packet, reducing the accuracy of the measurement. Existing solutions circumvent this problem by assuming that each packet traverses a single NMP or that the routing is fixed and known. This work suggests novel algorithms for three fundamental network-wide measurement problems without making any assumptions on the topology and routing and without modifying the underlying traffic. Specifically, this work introduces two algorithms for estimating the number of (distinct) packets or byte volume in the measurement, estimating per-flow packet and byte counts, and finding the heavy hitter flows. Our work includes formal accuracy guarantees and an extensive evaluation consisting of the realistic fat-tree topology and three real network traces. Our evaluation shows that our algorithms outperform existing works and provide accurate measurements within reasonable space parameters.

The q-MAX problem, which seeks to find the q largest elements in a data stream, has numerous networking applications including sketches, network-wide heavy hitters, and others. In this poster, we propose an improvement to the q-MAX algorithm [5] that leverages sampling to accelerate the computation. Despite being randomized, our algorithm never fails (i.e., it is a Las Vegas algorithm) and runs up to 62% faster when evaluated on real packet traces and tasks. Moreover, on a real networking application and workload, our algorithm provides an 11-53% higher throughput.

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.