BROWSE
Detail
Conference Paper
A High-speed Packet Classification using Multi-bit Tree Bitmap
Cited - time in 
Share 
Share
- Authors
- Byeong-cheol Choi, Heyung-sub Lee, Bong-tae Kim, Jeong-tae Lee
- Issue Date
- 2004-08
- Citation
- International Conference on Internet and Multimedia Systems and Applications (IMSA) 2004, pp.184-189
- Publisher
- IASTED
- Language
- English
- Type
- Conference Paper
- Abstract
- 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.
- KSP Keywords
- Best matching rule, Existing schemes, High Speed, IP header, Internet performance measurement, Measurement and analysis, Packet classification algorithm, Random rule, Rule Set, Source address, Tree bitmap(TBM)