Sketches are compact data structures maintained in network switches that store the summary of network data flows and permit answering queries with estimated results. This project aims to develop new virtual sketching methods that reduce big network data to measurement summaries orders-of-magnitude smaller than what the traditional sketches can do. The new methods hold the promise of allowing routers to perform measurement on large network traffic at line speed, allowing enterprise systems to keep their network data records for much longer time, and allowing users with ordinary computing resources to work on big network data.
A major research thrust in sketches is to reduce their memory footprint. Virtual sketches permit different flows to share a common pool of memory. Space sharing can drastically reduce the memory requirement, but this sharing introduces noise. Fortunately, we find that for randomized sharing schemes, the noise can be statistically measured and removed. This project will investigate (1) a theoretical study on new methods of space sharing, (2) common procedures for highly efficient online operations on virtual sketches with low overhead, (3) spatial virtual sketches for joint measurement of network data at different routers, (4) temporal virtual sketches for joint measurement of network data across different time periods, and (5) virtual composite sketches for sophisticated network data measurement.
