CardSketch: Shift Attention for Network-wide Cardinality Telemetry

Network telemetry is an essential part of network management and infrastructure. Among them, cardinality telemetry provides statistics on network connectivity and distribution. Network-wide cardinality telemetry refers to the deployment of multiple telemetry nodes in network for cardinality estimate. This requires the deployed data structure to be mergeable, enabling the consolidation of data from different nodes. Unfortunately, existing mergeable data structures can’t simultaneously address two important criterions of cardinality telemetry: measurement accuracy and estimation interval. We propose CardSketch, aiming to adjust attention to cardinality telemetry based on changes of the network state. CardSketch incorporates a shift attention mechanism that leverages the randomness of hash functions to achieve unbiased transformations between data structures. This mechanism enables real-time selection of cardinality estimation methods based on the network’s state while preserving the original telemetry information as much as possible during the attention shift. We have implemented prototypes of CardSketch in software and hardware. Through extensive experimentation, the results demonstrate that CardSketch achieves excellent cardinality telemetry with minimal memory overhead. Even with a mere 50KB of memory space, it achieves a measurement precision of 87.75% and a measurement recall of 91.49%. Additionally, CardSketch supports multi-point aggregation and arbitrary partial key queries.