摘要
设计并实现了一种基于索引指针的可扩展IP包分类算法.该算法通过分析源/目的端口号和协议类型字段在实际应用中的分布特性,将这3个字段映射到一个8比特元组上,压缩了分类维数;算法依据压缩后的8比特元组将分类规则集划分为256个子集,并为每个子集建立一个索引指针,指向该子集的存贮起始地址;算法通过计算IP包中"源/目的IP地址联合字段"中各个比特的信息熵值,找出最优的比特序列作为根和子节点,为每个规则子集建立一棵Tries查找树,既保证了存贮空间和查找时间最小,而且不存在回溯问题.实验结果证明,该算法分类效率高.
In this paper,a scalable IP packet classification algorithm using indexed pointers has been proposed.According to the distribution of source port,destination port and protocol type fields in the real applications,the algorithm maps the three fields to an eight-bit value and divides the whole rule set into 256 subsets.It assigns each subset an indexed pointer that points to the starting address of its storage space.The algorithm finds the best bit sequence and uses them as root and child nodes by calculating each bit＇s information entropy value of the combined field of source IP address and destination IP address,then it establishes a Tries lookup tree for each rule subset.By doing so,it requires the least storage space and lookup time without retrospect.The experimental results indicate that the new algorithm is highly efficient.
出处
《微电子学与计算机》
CSCD
北大核心
2012年第4期32-35,40,共5页
Microelectronics & Computer
基金
中央高校基本科研业务费专项资金资助项目(K50511030003)
关键词
包分类
索引指针
信息熵
Tries查找树
packet classification
indexed pointer
entropy of information
Tries lookup tree
