DocumentCode
3013435
Title
Space optimal packet classification for 2D conflict-free filters
Author
Poon, Chung Keung ; Kwok, Andy
Author_Institution
Dept. of Comput. Sci., City Univ. of Hong Kong, China
fYear
2004
fDate
10-12 May 2004
Firstpage
260
Lastpage
265
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, √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.
Keywords
IP networks; communication complexity; object-oriented programming; telecommunication network routing; 2D conflict-free filters; IP address; IP network; binary dispatching problem; linear space data structure; object-oriented programming; poly-logarithmic query time; space optimal packet classification; Computer science; Councils; Cryptography; Data structures; Dispatching; IP networks; Matched filters; Nonlinear filters; Object oriented programming; Routing;
fLanguage
English
Publisher
ieee
Conference_Titel
Parallel Architectures, Algorithms and Networks, 2004. Proceedings. 7th International Symposium on
ISSN
1087-4089
Print_ISBN
0-7695-2135-5
Type
conf
DOI
10.1109/ISPAN.2004.1300490
Filename
1300490
Link To Document