Back to Search
Start Over
Space optimal packet classification for 2D conflict-free filters
- Source :
- ISPAN, Scopus-Elsevier
- Publication Year :
- 2004
- Publisher :
- IEEE, 2004.
-
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.
Details
- Database :
- OpenAIRE
- Journal :
- 7th International Symposium on Parallel Architectures, Algorithms and Networks, 2004. Proceedings.
- Accession number :
- edsair.doi.dedup.....32b1614c0bb203a8733a4eaf8e304305