Title :
Packet classification using independent sets
Author :
Sun, Xuehong ; Zhao, Yiqiang Q.
Author_Institution :
Sch. of Math. & Stat., Carleton Univ., Canada
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;
Conference_Titel :
Computers and Communication, 2003. (ISCC 2003). Proceedings. Eighth IEEE International Symposium on
Print_ISBN :
0-7695-1961-X
DOI :
10.1109/ISCC.2003.1214105
