HEXA: Compact Data Structures for Faster Packet Processing
Data structures representing directed graphs with edges labeled by symbols from a finite alphabet are used to implement packet processing algorithms used in a variety of network applications. In this paper we present a novel approach to represent such data structures, which significantly reduces the amount of memory required. This approach called History-based Encoding, eXecution and Addressing (HEXA) challenges, the conventional assumption that graph data structures must store pointers of log2n bits to identify successor nodes. We show how the data structures can be organized so that implicit information can be used to locate successors, significantly reducing the amount of information that must be stored explicitly. We demonstrate that the binary tries used for IP route lookup can be implemented using just two bytes per stored prefix (roughly half the space required by Eathertons tree bitmap data structure) and that string matching can be implemented using 20-30％ of the space required by conventional data representations. Compact representations are useful, because they allow the performance-critical part of packet processing algorithms to be implemented using fast, on-chip memory, eliminating the need to retrieve information from much slower off-chip memory. This can yield both substantially higher performance and lower power utilization. While enabling a compact representation, HEXA does not add significant complexity to the graph traversal and update, thus maintaining a high performance.
Sailesh Kumar Jonathan Turner Patrieck Crowley Michael Mitzenmacher
Washington University Computer Science and Engineering Harvard University Electrical Engineering and Computer Science
国际会议
The 15th IEEE International Conference on Network Protocols(ICNP 2007)(第15届IEEE国际网络协议大会)
北京
英文
246-255
2007-10-16（万方平台首次上网日期，不代表论文的发表时间）