BitCuts: Towards Fast Packet Classification for Order-Independent Rules

摘要

Packet classification is required to achieve high throughput while fitting into a commodity memory hierarchy. Therefore, fewer memory accesses and a reasonable memory footprint are the main concerns when designing a packet classification algorithm. Recent work proposed a hybrid packet classification solution incorporating both software and TCAM-based approaches. Specifically, SAX-PAC observed that real-life packet classification rules can be represented by a few groups of order-independent rules. In each group, any two rules do not intersect and can possibly be separated on a fraction of fields, reducing the complexity of the classifier. Consequently, it has been suggested that the order-independent groups be handled by existing software algorithms, and the rest of the rules (the order-dependent part) be handled by TCAM. However, SAX-PAC did not design specific software algorithms for order-independent rules. For these rules, existing algorithms are still inefficient in terms of classification speed. Decision-tree algorithms, the state-of-the-art software approach, always traverse tens of tree nodes in order to identify the matching rule. Speed is further decreased when packets need to match multiple order-independent groups. This paper proposes BitCuts, a bit-level decision-tree algorithm targeting a promising classification speed on order-independent rules. Our evaluation shows that BitCuts only requires 30%~40% of the number of memory accesses of existing algorithms and still achieves small a memory footprint on large rulesets.