BitMatrix: A Multipurpose Sketch for Monitoring of Multi-tenant Networks

Sketches are probabilistic data structures capable of summarizing and storing network data (packets, bytes, and flows), with a certain degree of accuracy, that have become widely popular for network measurement and monitoring. In this paper, we propose a new multi-purpose sketch, called BitMatrix, which is capable of working in multi-tenant networks. Owing to its multi-dimensional architecture, BitMatrix can differentiate between bit markings and byte/packet counting from different sources in a network. As a multi-purpose sketch, BitMatrix and its algorithms contribute to the literature by providing information regarding the paths traversed by each packet and are designed for use in multi-tenant networks. We also designed a statistical model to adjust the measurements owing to the probabilistic behavior of the sketches. Such a model is able to infer the standard error rate and approximate the BitMatrix counters to the real value. The adjusted BitMatrix measurement has a Mean Absolute Percentage Error of ± 6.14%. The BitMatrix sketch was implemented using P4 language and a simulator was also developed, that allowed its scaling using real traces from CAIDA in an NSF network topology.