作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程

• 移动互联与通信技术 • 上一篇    下一篇

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

李建辉,张永棠   

  1. (广东东软学院 计算机科学与技术系,广东 佛山 528225)
  • 收稿日期:2016-02-24 出版日期:2017-04-15 发布日期:2017-04-14
  • 作者简介:李建辉(1974—),男,副教授、博士,主研方向为无线传感器网络、网络安全;张永棠,副教授、硕士。
  • 基金资助:
    国家自然科学基金(31501227)。

An Efficient IP Addressing Algorithm Based on Offset Encoded Trie

LI Jianhui,ZHANG Yongtang   

  1. (Department of Computer Science and Technology,Guangdong Neusoft Institute,Foshan,Guangdong 528225,China)
  • Received:2016-02-24 Online:2017-04-15 Published:2017-04-14

摘要: 提出一种新的偏移编码特里树(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

中图分类号: