Streaming Algorithms in Network Measurement
摘要
The efficient measurement of network traffic is crucial given its immense volume and rapid speed, presenting significant challenges. To address these challenges, emerging methods utilize sketches, which are a collection of streaming algorithms characterized by their compact data structures and minimal memory footprint. Sketches excel in processing packet streams with low resource overhead and at line speed, owing to their reliance on simple computations like hashing and addition. Moreover, their compatibility with network programmable hardware makes them particularly advantageous for traffic analysis. This chapter introduces classical sketches and their variants tailored for traffic measurement, while also exploring their deployment across various network environments such as software-defined networking, network function virtualization, and programmable data plane.