The Research Of High-performance Multi-dimensional Packet Classification Algorithm

With the rapid development of network technology and the emerging network applications, internet users have made deeper demands on the network service reliability, security and diversity. The routers need to provide diverse services such as firewalls, traffic billing, traffic control, differentiated services and QoS to satisfy different users. In order to support these new network services, the traditional one-dimensional packet classification algorithm which matching the packets by destination address can not meet the new various demands and the routers need to process multi-dimensional packet classification by the multi-field information from the header of data, such as the data packets of five-tuple (source IP, destination IP, source port, destination port, protocol). Today, research has shown that the rapid progress of Internet is continuously posing great demands and challenges on the multi-dimensional packet classification algorithm performance. It requires not only high matching speed, low memory occupation, but also the dynamic update and scalability performance for algorithms. Therefore, the research on the high-performance multi-dimensional packet classification algorithm is the necessary requirement of the large-scale and high-speed network. In this paper, we proposed two high-performance multi-dimensional packet classification algorithms, one belongs to software algorithm, and another belongs to hardware algorithm. As follows:Aspects of the software algorithm, we proposed a high-performance two-dimensional packet classification algorithm called TB (Joint Tuple Space and Bitmap). From dimensions decomposition idea, TB combined tuple space and bitmap technology to design and implement. TB first processed one-dimension matching for SIP and DIP respectively, then used cross-combination method to form tuple space access route, and also reduced the number of tuple space to access further by bitmap filtering technique. Compared to traditional tuple space algorithm, the structure of TB is clear, concise and easy to implement, has better time and space performance, easier to update, and also has a better scalability. The experimental results show that TB saves 35.1% of the space requirement than RSFR and the number of average memory accesses lower than RSFR 26.6%.Aspects of the hardware algorithm, we proposed an efficient multi-dimensional packet classification algorithm called CBHT(Counting Bloom filter and Hash Table). Considering the aggregation property of the rules which a packet matched, CBHT combined counting bloom filter and hash table to design and implement. Based on the aggregation property, for five-dimensional packet classification, we first got the small-scale rule set which matching the IP address using counting bloom filter. In this limited rule set we processed search on the other three dimensions. CBHT improves traditional structure of the hardware algorithm by considering the aggregation property, also improved the speed of packet matching effectively and supports rule set's dynamic update. We use Stanford University's PALAC platform to assess the performance of CBHT algorithm, the experimental results show that CBHT has better time performance, save hardware resources, and support rule set's dynamic update effectively.