AN INNOVATIVE PARALLELED PACKET ALGORITHM WITH PLUS BITS
Packet classification (PC) is one of the core technologies for next generation network service. The goal is to classify packet into different “flow and classification result can be applied in Differentiated Service. Though many multi-dimensional classifications have been put forward, few of them could accomplish fast search speed, low storage requirements and fast updates at the same time, especially when these algorithms are revised from IPv4 to IPv6. In this paper, we present an innovative packet classification algorithm, called Partial Paralleled algorithm based on Plus Bits (P3). P3 algorithm begins by two paralleled single-field engines and followed by hash table of the remained 3 fields. A novel structure, Plus Bits, is introduced to reduce hash memory accesses. For a 4k filterset, P3 algorithm can achieve about 9 memory accesses on average, taking 326 KB of memory for its data structure and supporting incremental update. We show that our P3 algorithm can meet the demand of current PC requirements.
Partial Parallelism Plus Bits Hash
Yun Liu Wenjie Li Ran Cai Qiong Sun Xiaohua Huang Yan Ma
Research Institute of Networking Technology, Beijing University of Posts and Telecommunications, Bei Research Institute of Networking Technology, Beijing University of Posts and Telecommunications, Bei
国际会议
北京
英文
247-251
2009-11-06（万方平台首次上网日期，不代表论文的发表时间）