Title :
Packet classification using two-dimensional multibit tries
Author :
Lu, Wencheng ; Sahni, Sartaj
Author_Institution :
Dept. of Comput. & Inf. Sci. & Eng., Florida Univ., Gainesville, FL, USA
Abstract :
We develop fast algorithms to construct space-optimal constrained two-dimensional multibit tries for Internet packet classifier applications. Experimental evidence suggests that using the same memory budget, space-optimal two-dimensional multibit tries require 1/4 to 1/3 the memory accesses required by two-dimensional one-bit tries for table lookup.
Keywords :
Internet; dynamic programming; pattern classification; table lookup; tree data structures; Internet packet classifier applications; dynamic programming algorithms; memory accesses; packet classification; space-optimal two-dimensional multibit tries; table lookup; Application software; Dynamic programming; Information filtering; Information filters; Information science; Internet; Matched filters; Protocols; Switches; Table lookup; Packet classification; dynamic programming; multibit tries; prefix expansion; two-dimensional tries;
Conference_Titel :
Computers and Communications, 2005. ISCC 2005. Proceedings. 10th IEEE Symposium on
Print_ISBN :
0-7695-2373-0
DOI :
10.1109/ISCC.2005.118
