標題: Fast Packet Classification Using Multi-Dimensional Encoding
作者: Huang, Chi Jia
Chen, Chien
資訊工程學系
Department of Computer Science
關鍵字: router;packet classification;multi-dimensional encoding;bitmap intersection;network processor
公開日期: 1-Jun-2009
摘要: Internet routers need to classify incoming packets quickly into flows in order to support features such as Internet security, virtual private networks and Quality of Service (QoS). Packet classification uses information contained in the packet header, and a predefined rule table in the routers. Packet classification of multiple fields is generally a difficult problem. Hence, researchers have proposed various algorithms. This study proposes a multi-dimensional encoding method in which parameters such as the source IP address, destination IP address, source port, destination port and protocol type are placed in a multi-dimensional space. Similar to the previously best known algorithm, i.e., bitmap intersection, multidimensional encoding is based on the multi-dimensional range lookup approach, in which rules are divided into several multi-dimensional collision-free rule sets. These sets are then used to form the new coding vector to replace the bit vector of the bitmap intersection algorithm. The average memory storage of this encoding is Theta (L . N . log N) for each dimension, where L denotes the number of collision-free rule sets, and N represents the number of rules. The multi-dimensional encoding practically requires much less memory than bitmap intersection algorithm, Additionally, the computation needed for this encoding is as simple as bitmap intersection algorithm. The low memory requirement of the proposed scheme means that it not only decreases the cost of packet classification engine, but also increases the classification performance, since memory represents the performance bottleneck in the packet classification engine implementation using a network processor.
URI: http://dx.doi.org/10.1587/transcom.E92.B.2044
http://hdl.handle.net/11536/7192
ISSN: 0916-8516
DOI: 10.1587/transcom.E92.B.2044
期刊: IEICE TRANSACTIONS ON COMMUNICATIONS
Volume: E92B
Issue: 6
起始頁: 2044
結束頁: 2053
Appears in Collections:Articles


Files in This Item:

  1. 000267638400017.pdf