DocumentCode
1676733
Title
Packet classification using independent sets
Author
Sun, Xuehong ; Zhao, Yiqiang Q.
Author_Institution
Sch. of Math. & Stat., Carleton Univ., Canada
fYear
2003
Firstpage
83
Abstract
This paper describes a new algorithm for packet classification using the concept of independent sets. The algorithm has very small memory requirements. The search speed is neither sensitive to the rule table nor to the percentage of wildcards in the fields. It also scales well from two dimensional classifiers to high dimensional ones. In particular, the algorithm is inherently parallel. Hardware tailored to this algorithm can achieve very fast search speed.
Keywords
Internet; data structures; packet switching; parallel processing; pattern classification; set theory; telecommunication network routing; Internet; data structure; heuristic algorithm; independent sets; memory access time; memory factor; memory requirements; memory storage; packet classification; parallel mechanism; search speed; update algorithm; wildcards; Classification algorithms; Electronic mail; Hardware; Mathematics; Parallel algorithms; Random access memory; Statistics; Sun; Web and internet services; Wire;
fLanguage
English
Publisher
ieee
Conference_Titel
Computers and Communication, 2003. (ISCC 2003). Proceedings. Eighth IEEE International Symposium on
ISSN
1530-1346
Print_ISBN
0-7695-1961-X
Type
conf
DOI
10.1109/ISCC.2003.1214105
Filename
1214105
Link To Document