Reduce network monitoring memory footprint by exploiting sparsity

What is it about?

In high-speed networks, traffic monitoring employs specific data structures, called sketches, to estimate metrics of interest at a low memory cost. Sketches are arrays of shared counters. Traditionally, each sketch is allocated a fixed memory budget in advance. However, because they need to prepare for worst-case scenarios, sketches are over-provisioned in practice, leaving most counters at zero. This sparsity leads to a significant waste of precious memory resources in network devices. In this paper, we propose a novel representation of these data structures to exploit their sparsity. Our proposal consists of allocating new sketch counters only when needed. It requires additional mechanisms to be implemented inside network device monitoring systems. This method reaches 2x to 11x memory reduction while maintaining the same estimation accuracy.

Featured Image

Photo by Brian Wangenheim on Unsplash

Photo by Brian Wangenheim on Unsplash

Why is it important?

While memory is scarce in network devices (in the dozens of MB), more and more functionalities are competing for it. Thus, it is crucial to favor frugality by avoiding to over-size the data structures used. In this paper, we tackle this problem in the context of network traffic monitoring.