A Memory-Based IPv6 Lookup Architecture Using Parallel Index Generation Units

Hiroki NAKAHARA  Tsutomu SASAO  Munehiro MATSUURA  Hisashi IWAMOTO  Yasuhiro TERAO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E98-D   No.2   pp.262-271
Publication Date: 2015/02/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2014RCP0006
Type of Manuscript: Special Section PAPER (Special Section on Reconfigurable Systems)
Category: Architecture
Keyword: 
CAM,  IP lookup,  index generation unit,  FPGA,  

Full Text: PDF(1MB)>>
Buy this Article




Summary: 
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 memory-based IPv6 lookup architecture. To reduce the size of memory in the IGU, we use a linear transformation and a row-shift decomposition. A single-memory 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 on-chip 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.