$O(\log W)$ Multidimensional Packet Classification
Haibin Lu, Sartaj K. Sahni · IEEE/ACM Transactions on Networking · 2007
We use a collection of hash tables to represent a multidimensional packet classification table. These hash tables are derived from a trie-representation of the multidimensional classifier. The height of this trie is O(W), where W is the sum of the maximum possible length, in bits, of each of the fields of a filter. The leaves at level i of the trie together with markers for some of the leaves at levels j such that j>i are stored in a hash table Hi. The placement of markers is such that a binary search of the Hi's successfully locates the highest-priority filter that matches any given packet. The number of hash tables equals the trie height, O(W). Hence, a packet may be classified by performing O(logW) hash-table lookups. So the expected lookup-complexity of our data structure for multidimensional packet classification is O(logW). Our proposed scheme affords a memory advantage over the O(logW) 1-D scheme of Waldvogel For multidimensional packet classification, our proposed scheme provides both a time and memory advantage over the extended grid-of-tries scheme of Baboescu et al