A Report on NSDI'13: Software Defined Traffic Measurement with OpenSketch

Updated on 2013-04-10. This is a report of the presentation done by Lavanya Jose on 2013-04-03. Paper co-authors are Minlan Yu, University of Southern California; Lavanya Jose, Princeton University; Rui Miao, University of Southern California.

Lavanya Jose started her presentation enumerating some questions existing measurement technologies are either unable to answer, or would require a prohibitive amount of resources to do so. Who is sending a lot of packets to a specific subnet, how are flow size distributions, is there anyone doing a port scan, etc. are some of the questions. NetFlow cannot answer many of the questions posed. For example, NetFlow typically does not sample light flows, such as port-scanning flows. Increasing sampling rate is an option, but then it becomes resource-consuming. Streaming algorithms could be used as well, though each algorithm answers one question only.

Given the above, the question now is: what measurement architecture can answer all the questions? The answer is: OpenSketch! OpenSketch is a software defined traffic measurement architecture which separates the measurement control and data-plane functions, and uses sketches (Count Min Sketch) as building blocks to provide a generic and efficient measurement API. Lavanya discussed about the basics of sketches, highlighting the trade-off between memory consumption and accuracy of the resulting measures. The error can be estimated, which thus can indicate the degree of confidence one can have on the accuracy of the obtained measures.

There is an issue with sketches, however: each one can estimate only one function. To solve this, Lavanya indicated a solution based on a three stage pipeline that can support many sketches. The first stage in this pipeline is to hash the packet (based on the header), then classify it (based on the packet header and hash values), and finally update a set of counters based on the results of the previous stages. This pipeline can be configured in the controller plane in order to obtain the required measures and implement the measurement tasks to solve the questions initially posed. Lavanya continued the presentation discussing possible strategies for implementing sketches with the pipeline, how one can provision the pipeline so that one can implement multiple, different sketches, and discussed evaluation results. The main take-away? OpenSketch truly adheres to the SDN philosophy: separate the measurement control and data-plane functions, and make measurement in switches efficient and easy.

After the presentation, the session chair (Dejan Kostić, Institute IMDEA Networks) asked about the possibility of achieving throughput of 10 Gbps. Lavanya said it is possible, but sequentially updating the SRAM might become a bottleneck for tasks which update many counters per-packet. The session chair continued by asking about the limitations of OpenSketch. Lavanya replied that the data plane is somewhat limited so that OpenSketch can be made simple enough to implement with commodity hardware and operate at line rate. For example, some sketches can not be implemented as they use more complex data structures (such as binary trees or heaps) not provided by the data plane.