Utilizing 2-D leaf-pushing for packet classification

Packet classification is one of the most challenging functionalities performed by routers at wire-speed for every incoming packet. For search spaces composed of multiple rules represented geometrically, various space decomposition algorithms have been studied to provide effective search methods. While an area-based quad-trie (AQT) provides a simple and intuitive way of mapping the geometrical search space into a two-dimensional (2-D) trie structure, it does not provide high-speed classification performance because the mapping is incomplete. This paper proposes the application of leaf-pushing into the 2-D trie to improve the classification performance of the AQT. The leaf-pushing AQT provides a more effective method of searching rules covering each input packet in the decomposed space. We also discuss an efficient implementation technique for our algorithm using a Bloom filter and a hash table. Simulation results show that our proposed leaf-pushing AQT improves the packet classification performance up to 37 times for sets with up to 100,000 rules compared with the AQT. To be compared with other space decomposition algorithms, a refined structure of the leaf-pushing AQT is also proposed. Simulation results show that the proposed refined structure provides an effective space decomposition method as well as the balance between memory requirements and classification speed, while most of other space decomposition algorithms show a trade-off between them.