1. Space optimal packet classification for 2D conflict-free filters
- Author
-
Chung Keung Poon and Andy Kwok
- Subjects
Set (abstract data type) ,Router ,Theoretical computer science ,Computer science ,Linear space ,Matched filter ,Binary number ,Routing (electronic design automation) ,Data structure ,Communication complexity ,Algorithm - Abstract
In this paper, we study the 2D packet classification problem for a set of conflict-free filters in an IP network. We design a linear space data structure with O(min{logiu loglogn, /spl radic/lognloglogn}) query time where n is the number of filters in the router and w is the number of bits in an IP address. This is the first optimal space data structure with poly-logarithmic query time for this problem. Our technique can also be extended to solve the binary dispatching problem in object-oriented programming.
- Published
- 2004