loading...
AM-Trie: An OC-192 Parallel Multidimensional Packet Classification Algorithm
Hangzhou, Zhejiang, China June 20-June 24
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/IMSCCS.2006.282006 First International Multi-Sympos ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Bo Zheng, Tsinghua University, China
Chuang Lin, Tsinghua University, China
Xuehai Peng, Tsinghua University, China
Nowadays, many high-speed Internet services and applications require high-speed multidimensional packet classification, but current high-speed classification often use expensive and power-slurping hardware (such as TCAM and FPGA). In this paper, we presented a novel algorithm, called AM-Trie (Asymmetrical Multi-bit Trie). Our algorithm creatively use redundant expression to reduce the height of Trie; use compression to reduce the storage cost and eliminate the trace back to enhance the search speed further. Moreover, AM-Trie is a parallel algorithm and very fit for the "multi-thread and multi-core" features of Network Processor; it has good scalability, the increase of policy number influences little to its performance. A heuristic field division algorithm is also presented, we proved in theoretical that there exists a minimum storage cost dividing solution when the height of the AM-Tire is given. Finally, a prototype is implemented based on Intel IXP2800 Network Processor. The performance testing result proves that AM-Trie is high-speed and scalable, the throughput of the TCP/IP 6-tuple classification achieves OC-192 (10 Gbps, 64 bytes per packet, i.e.20 Mpps) wire-speed in all situations.
Citation:
Bo Zheng, Chuang Lin, Xuehai Peng, "AM-Trie: An OC-192 Parallel Multidimensional Packet Classification Algorithm," imsccs, vol. 1, pp.377-384, 2006 First International Multi-Symposiums on Computer and Computational Sciences, 2006
Usage of this product signifies your acceptance of the Terms of Use.