计算机科学
利用
可扩展性
前缀
IPv6
算法
并行计算
计算机网络
互联网
计算机安全
操作系统
语言学
哲学
作者
Thibaut Stimpfling,N. Belanger,J. M. Pierre Langlois,Yvon Savaria
出处
期刊:IEEE ACM Transactions on Networking
[Institute of Electrical and Electronics Engineers]
日期:2019-08-01
卷期号:27 (4): 1529-1542
被引量:7
标识
DOI:10.1109/tnet.2019.2926230
摘要
Due to the emergence of new network applications, current IP lookup engines must support high bandwidth, low lookup latency, and the ongoing growth of IPv6 networks. However, the existing solutions are not designed to address jointly these three requirements. This paper introduces SHIP, an IPv6 lookup algorithm that exploits prefix characteristics to build a data structure designed to meet future application requirements. Based on the prefix length distribution and prefix density, prefixes are first clustered into groups sharing similar characteristics and then encoded in hybrid trie-trees. The resulting memory-efficient and scalable data structure can be stored in low-latency memories and allows the traversal process to be parallelized and pipelined in order to support high packet bandwidth in hardware. In addition, SHIP supports incremental updates. Evaluated on real and synthetic IPv6 prefix tables, SHIP has a logarithmic scaling factor in terms of the number of memory accesses and a linear memory consumption scaling. Compared with other well-known approaches, SHIP reduces the required amount of memory per prefix by 87%. When implemented on a state-of-the-art field-programmable gate array (FPGA), the proposed architecture can support processing 588 million packets per second.
科研通智能强力驱动
Strongly Powered by AbleSci AI