B.-C. Choi, H.-S. Lee, B.-T. Kim, and J.-T. Lee (Korea)
Packet Classification, Tree Bitmap, Rule, Multi-field
Packet classification is an important factor to provide various services such as QoS(Quality of Service) guarantee and VPN(Virtual Private Network) in Internet. Packet classification is a process to search the best matching rule on rule tables by employing multi-field such as source address, protocol, and port number as well as destination address in IP header. In this paper, we propose a hardware-based packet classification algorithm by employing tree bitmap of multi-bit trie. We divide the searching fields and rule prefixes into multi-bit stride, and search a rule with each stride hierarchically. The proposed scheme can reduce the access times of rule search by using the fixed size of upper bits of rule prefix as the index key. We also employ a marker prefix in order to remove backtracking during searching a rule. In this paper, we generate two-dimensional random rule set of source address and destination address from routing tables provided by IPMA(Internet Performance Measurement and Analysis) Project, and compare memory usages and performance with the existing schemes. We found that the rule search scheme using multi-bit tree bitmap is better than existing schemes in both aspects of memory usage and access times.
Important Links:
Go Back
