Computer Engineering and Applications ›› 2022, Vol. 58 ›› Issue (11): 107-116.DOI: 10.3778/j.issn.1002-8331.2012-0529

• Network, Communication and Security • Previous Articles     Next Articles

IPv6 Addressing Algorithm Using Prefix Feature

HUANG Ping, LIU Xinlin, SUN Fengjie   

  1. 1.Information Center, Shenzhen Power Supply Bureau Co., Ltd., Shenzhen, Guangdong 518000, China
    2.School of Electrical and Electronic Engineering, North China Electric Power University, Beijing 102206, China
  • Online:2022-06-01 Published:2022-06-01

使用前缀特性的IPv6寻址算法

黄萍,刘昕林,孙凤杰   

  1. 1.深圳供电局有限公司 信息中心,广东 深圳 518000
    2.华北电力大学 电气与电子工程学院,北京 102206

Abstract: With the development of the Internet and the expansion of the application of IPv6, the IP addressing engine must meet the three characteristics of high bandwidth, low search latency, and large capacity. However, the existing methods cannot simultaneously meet the above requirements. Therefore, a new IPv6 addressing algorithm is proposed here, which uses the prefix feature to construct a data structure to meet future application requirements. According to the prefix length distribution and density, it clusters them into clusters with similar characteristics, and then encodes them in a hybrid dictionary tree. The resulting data structure with memory efficiency and scalability can be stored in a low-latency memory, and allows parallelization and pipelining of the traversal process in order to support high bandwidth on the hardware. Experimental results show that the proposed algorithm reduces the amount of memory required for each prefix by 87%. In addition, when implemented on the most advanced field programmable gate array, the architecture can support processing 588 million packets per second.

Key words: network, IPv6, forwarding, lookup, forwarding information base

摘要: 随着互联网的发展以及IPv6的应用范围的扩大,IP寻址引擎必须要满足高带宽、低查找延迟以及大容量这三个特点。然而,现有的方法不能同时满足以上需求。因此提出了一种新的IPv6寻址算法,该算法利用前缀特性来构建一个数据结构,以满足未来的应用需求。根据前缀长度分布和密度,将其聚类成具有相似特征的簇,然后在混合字典树中进行编码。由此产生的具有内存效率和可扩展性的数据结构可以存储在低延迟存储器中,并且允许遍历过程并行化和流水线化,以便在硬件上支持高带宽。实验结果表明,提出的算法将每个前缀所需的内存量减少了87%。此外,在最先进的现场可编程门阵列上实现时,该架构可支持每秒处理5.88亿个数据包。

关键词: 网络, IPv6, 转发, 寻址, 转发信息库