On Constructing Efficient Shared Decision Trees for Multiple Packet Filters
Source: Rice University
Multiple packet filters serving different purposes (e.g., firewalling, QoS) and different virtual routers are often deployed on a single physical router. The HyperCuts decision tree is one efficient data structure for performing packet filter matching in software. Constructing a separate HyperCuts decision tree for each packet filter is not memory efficient. A natural alternative is to construct shared HyperCuts decision trees to more efficiently support multiple packet filters. However, the authors experimentally show that naively classifying packet filters into shared HyperCuts decision trees may significantly increase the memory consumption and the height of the trees.