SpreadSketch: Toward Invertible and Network-Wide Detection of Superspreaders

Superspreaders (i.e., hosts with numerous distinct connections) remain severe threats to production networks. How to accurately detect superspreaders in real-time at scale remains a non-trivial yet challenging issue. We present SpreadSketch, an invertible sketch data structure for network-wide superspreader detection with the theoretical guarantees on memory space, performance, and accuracy. SpreadSketch tracks candidate superspreaders and embeds estimated fan-outs in binary hash strings inside small and static memory space, such that multiple SpreadSketch instances can be merged to provide a networkwide measurement view for recovering superspreaders and their estimated fan-outs. We present formal theoretical analysis on SpreadSketch in terms of space and time complexities as well as error bounds. Trace-driven evaluation shows that SpreadSketch achieves higher accuracy and performance over state-of-the-art sketches. Furthermore, we prototype SpreadSketch in P4 and show its feasible deployment in commodity hardware switches.

• We design SpreadSketch, a new invertible sketch data structure for network-wide superspreader detection with memory space, performance, and accuracy guarantees.

• We present formal theoretical analysis on SpreadSketch, including its space complexity, update and detection time complexities, as well as error bounds on superspreader detection and fan-out estimation. buckets rows Bucket (, ) A table of buckets *,+ : total fan-out in (, ) *,+ : candidate superspreader *,+ : maximum level observed *,+ *,+ *,+