loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
2004 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN'04)
Space Optimal Packet Classification for 2-d Conflict-free Filters
Hong Kong, SAR, China
May 10-May 12
ISBN: 0-7695-2135-5
ASCII Text
x 
 
Chung Keung Poon, Andy Kwok, "Space Optimal Packet Classification for 2-d Conflict-free Filters," Parallel Architectures, Algorithms, and Networks, International Symposium on, pp. 260, 2004 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN'04), 2004.
 
 
BibTex
x
 
@article{ 10.1109/ISPAN.2004.1300490,
author = {Chung Keung Poon and Andy Kwok},
title = {Space Optimal Packet Classification for 2-d Conflict-free Filters},
journal ={Parallel Architectures, Algorithms, and Networks, International Symposium on},
volume = {0},
year = {2004},
issn = {1087-4089},
pages = {260},
doi = {http://doi.ieeecomputersociety.org/10.1109/ISPAN.2004.1300490},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Parallel Architectures, Algorithms, and Networks, International Symposium on
TI - Space Optimal Packet Classification for 2-d Conflict-free Filters
SN - 1087-4089
SP
EP
A1 - Chung Keung Poon,
A1 - Andy Kwok,
PY - 2004
KW - null
VL - 0
JA - Parallel Architectures, Algorithms, and Networks, International Symposium on
ER -
 
Chung Keung Poon, City University of Hong Kong
Andy Kwok, City University of Hong Kong
In this paper, we study the 2-dimensional packet classification problem for a set of conflict-free filters in an IP network. We design a linear space data structure with O(min{logwloglogn, \sqrt {\log n\log \log n}}) 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 arose in object-oriented programming.
Citation:
Chung Keung Poon, Andy Kwok, "Space Optimal Packet Classification for 2-d Conflict-free Filters," ispan, pp.260, 2004 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN'04), 2004
Usage of this product signifies your acceptance of the Terms of Use.