Packet classification algorithm based on self-adaptive cache

An applicable and easy-to-implement packet classification algorithm CSAC (classification on self-adaptive cache) with high performance is presented. It caches the searching path of the packet set within a field subspace, reuses the searching result for the classification of the subsequent packets in the same field subspace, and reduces the cache hit-miss penalty. According to state changes of the cache by the fluctuation of network traffic, the algorithm introduces a self-adaptive cache scheme to guarantee effectively the cache hit ratio, which adjusts dynamically the granularity and structure of the cache, and locations of cache items in hash buckets. Furthermore, CSAC does not need the preprocessing phase required by most of heuristic algorithms, and it supports multi-field complex rules (such as layer 4-7 fields, logic match operation, etc.) and increment update of rule set. It is suitable for applications with various packet classification requirements, such as network edge security, traffic audit and load balancing, etc. Some firewall and IDS appliances using CSAC have favorable performance in actual network environment.EI02196-2034