A Memory-Based IPv6 Lookup Architecture Using Parallel Index Generation Units
A Memory-Based IPv6 Lookup Architecture Using Parallel Index Generation Units
复制标题
DOI：
10.1587/transinf.2014rcp0006
复制
发表时间：
2015-02
期刊：
影响因子：
--
通讯作者：
Hiroki Nakahara;Tsutomu Sasao;M. Matsuura;H. Iwamoto;Y. Terao
中科院分区：
文献类型：
--
作者：
Hiroki Nakahara;Tsutomu Sasao;M. Matsuura;H. Iwamoto;Y. Terao
在IPv6时代，由于IPv6地址数量迅速增加，所需的速度超过每秒千兆查找（GLPS），因此需要一种区域高效且高速的IP查找架构。本文展示了一种用于基于内存的 IPv6 查找架构的并行索引生成单元 (IGU)。为了减少 IGU 中的内存大小，我们使用线性变换和行移位分解。单内存实现需要 O(2l log k) 内存大小，其中 l 表示前缀长度，而使用 IGU 实现需要 O(kl) 内存大小，其中 k 表示前缀数量。在IPv6前缀查找中，由于l最多为64，k约为340K，因此IGU大大减少了内存大小。此外，为了降低成本，我们通过使用片内和片外存储器来实现并行IGU。我们展示了一种并行 IGU 的设计算法，用于存储给定的片外和片上存储器。并行IGU具有简单的架构，并通过使用在所有路径中插入流水线寄存器的完整流水线来执行查找。我们使用片外 DDRII+ 静态 RAM (SRAM) 在 Xilinx Virtex 6 FPGA 上加载了超过 340 K IPv6 伪前缀。其查找速度为每秒 1.100 千兆次查找 (GLPS)，足以满足下一代 400 Gbps 链路吞吐量所需的速度。至于归一化面积和查找速度，我们的实现优于现有 FPGA 实现。关键词: CAM, IP查找, 索引生成单元, FPGA
In the era of IPv6, since the number of IPv6 addresses rapidly increases and the required speed is more than Giga lookups per second (GLPS), an area-efficient and high-speed IP lookup architecture is desired. This paper shows a parallel index generation unit (IGU) for memorybased IPv6 lookup architecture. To reduce the size of memory in the IGU, we use a linear transformation and a row-shift decomposition. A singlememory realization requires O(2l log k) memory size, where l denotes the length of prefix, while the realization using IGU requires O(kl) memory size, where k denotes the number of prefixes. In IPv6 prefix lookup, since l is at most 64 and k is about 340 K, the IGU drastically reduces the memory size. Also, to reduce the cost, we realize the parallel IGU by using both onchip and off-chip memories. We show a design algorithm for the parallel IGU to store given off-chip and on-chip memories. The parallel IGU has a simple architecture and performs lookup by using complete pipelines those insert the pipeline registers in all the paths. We loaded more than 340 K IPv6 pseudo prefixes on the Xilinx Virtex 6 FPGA with off-chip DDRII+ Static RAMs (SRAMs). Its lookup speed is 1.100 giga lookups per second (GLPS) which is sufficient for the required speed for a next generation 400 Gbps link throughput. As for the normalized area and lookup speed, our implementation outperforms existing FPGA implementations. key words: CAM, IP lookup, index generation unit, FPGA