一种基于偏移编码特里树的高效IP寻址算法  

An Efficient IP Addressing Algorithm Based on Offset Encoded Trie

作　　者：李建辉 张永棠 

机构地区：[1]广东东软学院计算机科学与技术系,广东佛山528225

出　　处：《计算机工程》2017年第4期84-89,共6页Computer Engineering

基　　金：国家自然科学基金(31501227)

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

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]