Paper Info
Title
Memory-Efficient IPv4/v6 Lookup on FPGAs Using Distance-Bounded Path Compression
Abstract
Memory efficiency with compact data structures for Internet Protocol (IP) lookup has recently regained much interest in the research community. In this paper, we revisit the classic trie-based approach for solving the longest prefix matching (LPM) problem used in IP lookup. In particular, we target our solutions for a class of large and sparsely-distributed routing tables, such as those potentially arising in the next generation IPv6 routing protocol. Due to longer prefix and much larger address space, straight-forward implementation of trie based LPM can significantly increase the number of nodes and/or memory required for IP lookup. Additionally, due to the available on-chip memory and the number of I/O pins of in the state-of-the art Field Programmable Gate Arrays (FPGAs), existing designs cannot support large IPv6 routing tables consisting of over 300K prefixes. We propose two algorithms to compress the uni-bit-trie representation of a given routing table: (1) single-prefix distance bounded path compression and (2) multiple-prefix distance bounded path compression. These algorithms determine the optimal maximum slap distance at each node of the trie to minimize the total memory requirement. Our algorithms demonstrate substantial reduction in the memory footprint compared with the uni-bit-trie algorithm (1.86× for IPv4 and 6.16× for IPv6), and with the original path compression algorithm (1.77× for IPv4 and 1.53× for IPv6). Furthermore, implementation on a state of-the-art FPGA shows that our algorithms achieve 466 million lookups per second and are well suited for 100Gbps lookup. The implementation also scales to support larger routing tables and longer prefix length when we go from IPv4 to IPv6.
Year
DOI
Venue
2011
10.1109/FCCM.2011.40
FCCM
Keywords
Field
DocType
memory-efficient ipv4,path compression,ip networks,ipv6 routing protocol,distance-bounded path compression,optimal maximum slap distance,prefix length,ipv6,lpm problem,trie,pipeline,trie-based approach,single-prefix distance bounded path compression,ip lookup,v6 lookup,i/o pins,memory efficiency,routing table,memory-efficient ipv4/v6 lookup,field programmable gate array,multiple-prefix distance bounded path compression,transport protocols,routing table lookup,routing protocols,memory footprint,ipv4,fpga,total memory requirement,uni-bit-trie algorithm,field programmable gate arrays,ipv6 routing table,available on-chip memory,larger routing table,table lookup,compact data structure,internet protocol,on-chip memory,sparsely-distributed routing table,longest prefix matching,algorithm design,routing protocol,memory management,compression algorithm,algorithm design and analysis,hardware,routing,data structure,chip,throughput
Internet Protocol,Computer science,Parallel computing,Memory management,Longest prefix match,Routing table,Memory footprint,Data compression,Trie,Routing protocol
Conference
ISBN
Citations 
PageRank 
978-0-7695-4301-7
9
0.51
References 
Authors
18
3
Name
Order
Citations
PageRank
Hoang Le119617.35
Weirong Jiang252132.11
Viktor K. Prasanna37211762.74