一种基于自适应缓存机制的报文分类算法  

A Packet Classification Algorithm Based on Self-Adaptive Cache

作　　者：张建宇[1] 韦韬[1] 邹维[1] 

机构地区：[1]北京大学计算机科学技术研究所,北京100871

出　　处：《计算机研究与发展》2006年第2期196-203,共8页Journal of Computer Research and Development

基　　金：国家"十五"科技攻关计划基金项目(2001BA802B07)~~

摘　　要：提出了一种高效、适用性好、易于实现的报文分类算法CSAC（classification on self-adaptive cache）．该算法通过缓存属性子空间内报文集合的分类查询路径，将查询结果复用于同一子空间后续报文的分类．而缓存命中失效时也不必从头开始查询，减少了失效的时间开销．根据通信流量上下文变化对缓存运行状态造成的影响，算法采用自适应缓存机制，通过动态调整缓存的粒度、结构和缓存项在散列桶中的位置，有效地保证了缓存命中率．此外，算法不需要预处理过程，支持多维复杂规则（如4～7层属性、逻辑匹配操作等）和规则增量更新，比较适合于网络边界安全、用户流量审计和负载均衡等报文分类比较复杂的应用．采用CSAC算法开发的高端防火墙和入侵检测设备在实际网络环境中的性能良好．An applicable and easy-to-implement packet classification algorithm CSAC （classification on selfadaptive 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 preproeessing 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.

关 键 词：报文分类 自适应缓存 缓存粒度 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]