Name
Abstract | ||
|---|---|---|
Packet classification is an important component of new Internet routers to support various services such as quality of service guarantee and virtual private network. Basically, packet classification can be considered as a process looking for the best matching filter in a filter set for several fields selected from packet header. Various data structures and search algorithms have been proposed for such multi-field packet classification. In particular, the nested binary tuple space search algorithm was designed for two-field conflict free filter sets. The time complexity of the nested binary search algorithm is ([log(W + 1)])2, where W is the length of the fields. To ensure that the filter set is conflict free, the authors assumed that conflicts are resolved by adding resolution filters. In this paper, we propose a novel search algorithm which can find the best matching filter in 2[log(W + 1)] probes. Although more resolution filters are added, empirical results for random filter sets show that our scheme requires less memory than the nested binary search algorithm because no primary markers (and the secondary markers of primary markers) are needed. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1109/GLOCOM.2002.1188550 | GLOBECOM |
Keywords | Field | DocType |
packet switching,packet classification algorithm,quality of service,virtual private networks,data structures,two-field conflict free filter sets,internet routers,multi-field classification,two-dimensional tuple-space,nested binary tuple space search algorithm,search algorithms,matching filter,internet,resolution filters,virtual private network,telecommunication network routing,tuple space,search algorithm,time complexity,binary search,data structure,matched filter | Tuple space,Data structure,Search algorithm,Computer science,Algorithm,Computer network,Theoretical computer science,Packet switching,Header,Binary search algorithm,Time complexity,Binary number | Conference |
Volume | ISSN | ISBN |
2 | 1930-529X | 0-7803-7632-3 |
Citations | PageRank | References |
1 | 0.36 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pau-chuan Ting | 1 | 1 | 1.37 |
| Yung-Sheng Hsu | 2 | 1 | 1.03 |
| Tsern-Huei Lee | 3 | 244 | 30.63 |