计算机工程2017，Vol.43Issue(4)：84-89,6.DOI:10.3969/j.issn.1000-3428.2017.04.014
一种基于偏移编码特里树的高效IP寻址算法
An Efficient IP Addressing Algorithm Based on Offset Encoded Trie
摘要
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.关键词
路由器/IP寻址/最长前缀匹配/偏移编码特里树/软件定义网络/片上存储器Key words
router/IP addressing/longest prefix match/Offset Encoded Trie(OET)/software defined network/on-chip memory分类
信息技术与安全科学引用本文复制引用
李建辉,张永棠..一种基于偏移编码特里树的高效IP寻址算法[J].计算机工程,2017,43(4):84-89,6.基金项目
国家自然科学基金(31501227). （31501227）
