Storage-Efficient Tree Structure with Level-Ordered Unary Degree Sequence for Packet Classification

Packet classification is an essential function in Internet routers that provides advanced network services such as virtual private networks (VPNs) and quality of service (QoS). Decision tree-based packet classification algorithms such as HiCuts and HyperCuts allow the tradeoff between storage and throughput in the experimental result with the real life rulesets. However, the memory consumption of these algorithms remains high when high throughput is required. In this paper, we propose the tree data structure whose storage is small maintaining high throughput. It is based on the two ideas: The first is to use Level Ordered Unary Degree Sequence (LOUDS) which is a succinct representation of a tree structure. A general tree of n nodes is usually represented in pointer form, requiring 64n bits in 64-bit architecture, whereas LOUDS requires 2n+o(n) bits. Because LOUDS can access any child node from its parent one in constant time, the tree traversal is fast. The second is reducing the information contained in the tree node. This also reduces storage requirements without affecting search speed. The proposed data structure requires up to approximately one ninth less memory than pointer-formed tree, and the time complexity of a packet classification is equivalent to the pointer-formed tree.