Clustered Linked List Forest for IPv6 Lookup
Authors:
- Oguzhan ErdemOEOguzhan Erdem
- Aydin CarusACAydin Carus
- 1 August 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 33-40
Abstract
Providing a high operating frequency and abundant parallelism, Field Programmable Gate Arrays (FPGAs) are the most promising base to realize SRAM-based pipelined architectures for high-speed Internet Protocol (IP) lookup. Owing to the restrictions of the state-of-the-art FPGAs on the number of I/O pins and on-chip memory, the existing approaches can hardly accommodate the large and sparsely-distributed IPv6routing tables. Therefore, memory efficient data structures are recently in high demand. In this paper, clustered linked list forest(CLLF) data structure is proposed for solving the longest prefix matching (LPM) problem in IP lookup. Our structure comprising clustered multiple parallel linked lists achieves significant memory compaction in comparison to the existing approaches. CLLF data structure is implemented on a high throughput SRAM-based parallel and pipelined architecture on FPGAs. Utilizing a state of-the-art FPGA device, CLLF architecture can accommodate up to 712K IPv6 prefixes while supporting fast incremental routingtable updates.Keywords
This publication has 21 references indexed in Scilit:
- FlashTrie: Beyond 100-Gb/s IP Route Lookup Using Hash-Based Prefix-Compressed TrieIEEE/ACM Transactions on Networking, 2012
- Scalable Tree-Based Architectures for IPv4/v6 Lookup Using Prefix PartitioningIEEE Transactions on Computers, 2011
- Memory-Efficient IPv4/v6 Lookup on FPGAs Using Distance-Bounded Path Compression2011
- Scalable High Throughput and Power Efficient IP-Lookup on FPGA2009
- A Memory-Balanced Linear Pipeline Architecture for Trie-based IP Lookup2007
- CAMP2006
- A TCAM-based distributed parallel IP lookup scheme and performance analysisIEEE/ACM Transactions on Networking, 2006
- Longest prefix matching using bloom filtersIEEE/ACM Transactions on Networking, 2006
- A Tree Based Router Search Engine Architecture with Single Port Memories2005
- Tree bitmapACM SIGCOMM Computer Communication Review, 2004