IP address lookup using bit-shuffled trie

详细信息    查看全文

• 作者：Derek Pao ; ^{d.pao@cityu.edu.hk" class="auth_mail} ; Ziyan Lu ^{ziyanlu2-c@my.cityu.edu.hk" class="auth_mail} ; Yat Hang Poon ^{garypoon014@gmail.com" class="auth_mail}
• 关键词：IPv4 and IPv6 address lookup ; Packet forwarding ; Pipelined architecture
• 刊名：Computer Communications
• 出版年：1 July 2014
• 年：2014
• 卷：47
• 期：Complete
• 页码：51-64
• 全文大小：1800 K

文摘

An algorithmic RAM-based IP address lookup method called bit-shuffled trie is presented. By rearranging the bits of the prefixes, memory efficient index tables can be constructed to support IP address lookup. The address lookup engine can be implemented using pipelined architecture with simple processing logic. The proposed method has superior memory efficiency. The memory cost for a 474 K prefixes IPv4 routing table is only 1.1 MB, and the memory cost for a 215 K 64-bit prefixes IPv6 routing table is about 1.7 MB. The exceptional memory efficiency of the proposed method allows us to implement the IP address lookup engine for both IPv4 and IPv6 on a single FPGA device. Incremental updates to the routing table can be handled efficiently. On average, about 8 memory-write operations to the data structures are required to process an insertion or deletion.