摘要： 提出一种新的偏移编码特里树(OET)的IP寻址算法,即采用OET表示一组IP前缀规则,以减少其存储空间需求。OET的每个节点仅维护1个下一跳步位图和1个偏移值,不需要孩子指针和下一跳步指针,从而提高了IP寻址性能。采用实际IP前缀规则集进行实验评估,与树位图特里树相比,对于实际IPv4和IPv6前缀规则集,OET在存储空间开销上分别减少60%~76%和55%~63%,是一种存储高效的数据结构,整个OET可存储在片上存储器中,能实现高速的IP地址查找,满足虚拟路由器和软件路由器的可扩展性要求。

关键词: 路由器, IP寻址, 最长前缀匹配, 偏移编码特里树, 软件定义网络, 片上存储器

Abstract: A novel Offset Encoded Trie(OET) IP addressing algorithm is proposed.It uses OET to represent a set of IP prefix rules,significantly reducing the storage space requirements.Each OET node maintains only one next hop step and a bitmap offset value,without the need of child pointers and pointer to the next hop step,thereby improving the IP addressing performance.The actual IP prefix rule sets are used for experimental evaluation.Compared with bitmap trie,OET reduces the storage space overhead on actual IPv4 and IPv6 prefix rule sets by 60%~76% and 55%~63%.Therefore,OET is an efficient data storage structure.The entire OET may be stored in on-chip memory to achieve high-speed IP address lookup,meeting scalability requirements of the virtual routers and software routers.

Key words: router, IP addressing, longest prefix match, Offset Encoded Trie(OET), software defined network, on-chip memory

中图分类号: 

• TP301.6