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

doi:10.3778/j.issn.1002-8331.2012-0529

摘要/Abstract

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

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

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寻址算法[J]. 计算机工程与应用, 2022, 58(11): 107-116.

HUANG Ping, LIU Xinlin, SUN Fengjie. IPv6 Addressing Algorithm Using Prefix Feature[J]. Computer Engineering and Applications, 2022, 58(11): 107-116.

参考文献

[1] 杨欣颜.基于改进ESN的网络流量预测方法研究[D].南京：南京邮电大学，2019.
YANG X Y.The research of network traffic prediction method based on improved echo state network[D].Nanjing：Nanjing University of Posts and Telecommunications，2019.
[2] 张千里，姜彩萍，王继龙，等.IPv6地址结构标准化研究综述[J].计算机学报，2019，42（6）：1384-1405.
ZHANG Q L，JIANG C P，WANG J L，et al.A survey on IPv6 addres structure standardization researches[J].Chinese Journal of Computers，2019，42（6）：1384-1405.
[3] CHAO H，LIU B.High performance switches and routers[M].Hoboken，NJ，USA：Wiley，2007.
[4] LE H，PRASANNA V.Scalable tree-based architectures for IPv4/v6 lookup using prefix partitioning[J].IEEE Transactions on Computers，2012，61（7）：1026-1039.
[5] TONG D，YANG Y，PRASANNA V.A memory efficient IPv6 lookup engine on FPGA[C]//International Conference on Reconfigurable Computing & FPGAs，2013：1-6.
[6] 李卓群.IPv4向IPv6的过渡技术研究[J].有线电视技术，2019（3）：63-64.
LI Z Q.Research on transition technology from IPv4 to IPv6[J].Cable TV Technology，2019（3）：63-64.
[7] 赵肃波.中国IPv6发展与网络安全挑战[J].信息安全研究，2019，5（3）：261-272.
ZHAO S B.The challenges of IPv6 development and network security in China[J].Journal of Information Security Research，2019，5（3）：261-272.
[8] 王子文.新一代互联网中IPv6地址变化特性的研究[D].北京：北京邮电大学，2017.
WANG Z W.Research on the change characteristics of IPv6 address in the new generation internet[D].Beijing：Beijing University of Posts and Telecommunications，2017.
[9] IPv6 Global Unicast Address Assignments[EB\OL].[2020-10-20].http：//www.iana.org/assignments/ipv6-unicast-address-assignments/ipv6-unicast-address-assignments.xhtml.
[10] ASAI H，OHARA Y.Poptrie：a compressed trie with population count for fast and scalable software IP routing table lookup[J].ACM SIGCOMM Computer Communication Review，2015，45（4）：57-70.
[11] PONTARELLI S，REVIRIEGO P，MITZENMACHER M.EMOMA：exact match in one memory access[J].IEEE Transactions on Knowledge and Data Engineering，2018，30（11）：2120-2133.
[12] YASUKATA K，HONDA M，SANTRY D，et al.StackMap：low-latency networking with the OS stack and dedicated NICs[C]//Usenix Technical Conference，2016：43-56.
[13] HUO S，ZHANG D，LI Y.Multi-stride indexing：improve NFA for fast and scalable DPI[J].Chinese Journal of Electronics，2018，27（1）：86-92.
[14] RIPE NCC Network Coordination.RIS raw data set[EB/OL].[2020-10-20].https：//www.ripe.net/analyse/internet-measurements/routing-information-service-ris/ris-raw-data.
[15] YANG T，XIE G，LIU A，et al.Guarantee IP lookup performance with FIB explosion[J].ACM SIGCOMM Computer Communication Review，2014，44（4）：39-50.
[16] BASU A，NARLIKAR G.Fast incremental updates for pipelined forwarding engines[J].IEEE/ACM Transactions on Networking，2005，13（3）：690-703.
[17] ZHOU S，PRASANNA V.Scalable GPU-accelerated IPv6 lookup using hierarchical perfect hashing[C]//2015 IEEE Global Communications Conference（GLOBECOM），San Diego，CA，2015：1-6.