Value-Coded Trie Structure for High-Performance IPv6 Lookup
Küçük Resim Yok
Tarih
2015
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Oxford Univ Press
Erişim Hakkı
info:eu-repo/semantics/closedAccess
Özet
Dynamically updateable and memory-efficient search structures for Internet protocol (IP) lookup have lately attracted a great deal of attention from the researchers. In this paper, we focus on the next-generation IPv6 routing protocol comprising large and sparsely distributed routing tables. The existing data structures either suffer from inefficient resource and memory usage (trie-based algorithms), or require complicated construction processes such as converting routing prefixes into their longer representatives and sorting (tree-based algorithms), or both. We propose a novel data structure denoted value-coded trie (VC-trie) for IP lookup. VC-trie provides significant memory saving in comparison with that of the existing solutions in both IPv4 and IPv6 domains. Thereby, our structure can support longer prefix lengths and larger routing tables. We also design an static random access memory (SRAM)-based pipelined architecture to assist the VC-trie structure to improve the throughput. The architecture is implemented utilizing a state-of-the-art field programmable gate array (FPGA) device and sustainable throughput of 448 million lookups per second (with a routing table consisting of 324K prefixes) is achieved. Furthermore, the architecture can be enhanced with external SRAMs to relax the limitations of the existing FPGA device in on-chip memory.
Açıklama
Anahtar Kelimeler
Trie, Longest Prefix Match, Pipeline, IP Lookup, Packet Forwarding, Ipv4/V6 Lookup
Kaynak
Computer Journal
WoS Q Değeri
Q2
Scopus Q Değeri
Q2
Cilt
58
Sayı
2
