A Memory-Based IPv6 Lookup Architecture Using Parallel Index Generation Units
-
- NAKAHARA Hiroki
- Department of Electrical and Electronic Engineering and Computer Science, Ehime University
-
- SASAO Tsutomu
- Department of Computer Science, Meiji University
-
- MATSUURA Munehiro
- Department of Computer Science and Electronics, Kyushu Institute of Technology
-
- IWAMOTO Hisashi
- REVSONIC Corp.
-
- TERAO Yasuhiro
- REVSONIC Corp.
Abstract
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.
Journal
-
- IEICE Transactions on Information and Systems
-
IEICE Transactions on Information and Systems E98.D (2), 262-271, 2015
The Institute of Electronics, Information and Communication Engineers
- Tweet
Keywords
Details 詳細情報について
-
- CRID
- 1390282679356610816
-
- NII Article ID
- 130004841817
-
- ISSN
- 17451361
- 09168532
-
- Text Lang
- en
-
- Data Source
-
- JaLC
- Crossref
- CiNii Articles
-
- Abstract License Flag
- Disallowed