DocumentCode :
380641
Title :
Efficient hardware architecture for fast IP address lookup
Author :
Pao, Derek ; Liu, Cutson ; Wu, Angus ; Yeung, Lawrence ; Chan, K.S.
Author_Institution :
Dept. of Comput. Eng. & Inf. Technol., City Univ. of Hong Kong, Kowloon, China
Volume :
2
fYear :
2002
fDate :
2002
Firstpage :
555
Abstract :
A multigigabit IP router may receive several million packets per second from each input link. For each packet, the router needs to find the longest matching prefix in the forwarding table in order to determine the packet´s next-hop. In this paper, we present an efficient hardware solution for the IP address lookup problem. We model the address lookup problem as a searching problem on a binary-trie. The binary-trie is partitioned into four levels of fixed size 255-node subtrees. We employ a hierarchical indexing structure to facilitate direct access to subtrees in a given level. It is estimated that a forwarding table with 40 K prefixes will consume 2.5 Mbytes of memory. The searching is implemented using a hardware pipeline with a minimum cycle of 12.5 ns if the memory modules are implemented using SRAM. A distinguishing feature of our design is that forwarding table entries are not replicated in the data structure. Hence, table updates can be done in constant time with only a few memory accesses.
Keywords :
Internet; indexing; protocols; string matching; table lookup; telecommunication network routing; tree data structures; tree searching; SRAM; binary trie searching; data structure; fast IP address lookup; forwarding table; hardware architecture; hardware pipeline; hierarchical indexing structure; longest matching prefix; memory accesses; multigigabit IP router; table updates; Computer architecture; Data structures; Explosions; Hardware; Indexing; Information technology; Pipelines; Random access memory; Routing; Table lookup;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
INFOCOM 2002. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE
ISSN :
0743-166X
Print_ISBN :
0-7803-7476-2
Type :
conf
DOI :
10.1109/INFCOM.2002.1019300
Filename :
1019300
Link To Document :
بازگشت