Data Structure Engineering for High Performance Software Packet Processing

演讲人: Dong Zhou Carnegie Mellon University
时间: 2019-04-11 10:00-2019-04-11 11:00
地点:FIT 1-222

Compared with using specialized hardware, software packet processing on general-purpose hardware provides extensibility and programmability. From software routers to virtual switches to Network Function Virtualization (NFV), we are seeing increasing applications of software-based packet processing. However, software-based solutions often face performance challenges, primarily because general-purpose CPUs are not optimized for processing network packets. In this talk, I will present how to tackle the performance of software packet processing by optimizing the main data structures of the application. To demonstrate the effectiveness of our approach, we examined three applications: Ethernet forwarding, LTE-to-Internet gateway and virtual switches. For each application, we propose algorithmic refinements and engineering principles to improve its main data structures, including:

1. A concurrent, read-optimized hash table for x86 architecture;

2. An extremely compact data structure for set separation;

3. A new cache design optimized for network appliances that balances between hit rate and lookup latency.

In all three applications, we are able to achieve higher performance than existing solutions.


Dong Zhou is a final-year Ph.D. student in Computer Science Department at Carnegie Mellon University, advised by Prof. David G. Andersen. He received his M.S. degree from CMU and received B.E. degree in Computer Science Engineering from Institute for Interdisciplinary Information Sciences, Tsinghua University. From 2015-2018, he worked as a core developer at Hudson River Trading, a world-leading quantitative high-frequency trading firm. His research interests are in building resource-efficient, high-performance software systems and network appliances.