Bit-shuffled trie: A new approach for IP address lookup

Author

Pao, Derek ; Lu, Ziyan

Author_Institution

Electron. Eng. Dept., City Univ. of Hong Kong, Hong Kong, China

fYear

2010

fDate

25-26 Oct. 2010

Firstpage

1

Lastpage

3

Abstract

IP address lookup is a fundamental operation in packet forwarding. Using multi-level index tables to find out the next-hop value is an attractive approach due to its simplicity. However, memory efficiency is relatively low because prefixes are sparsely distributed in the address space. In this poster, we shall outline a new approach to construct memory efficient index tables based on a technique called bit-shuffling. The proposed method is evaluated using a real-life IPv4 routing table with 321K prefixes. The lookup tables occupy 0.8MB memory.

Keywords

IP networks; memory architecture; table lookup; telecommunication network routing; tree data structures; IP address lookup; address space; bit-shuffled trie; memory efficient index tables; multilevel index tables; next hop value; packet forwarding; real-life IPv4 routing table; Engines; Hardware; IP networks; Indexes; Memory management; Routing; Table lookup; IP address lookup; packet forwarding; pipelined architecture;

fLanguage

English

Publisher

ieee

Conference_Titel

Architectures for Networking and Communications Systems (ANCS), 2010 ACM/IEEE Symposium on

Conference_Location

La Jolla, CA

Print_ISBN

978-1-4244-9127-8

Electronic_ISBN

978-1-4503-0379-8

Type

conf

Filename

5623841