A fast and updatable IP address lookup scheme

Author

Chung, Sang-Hun ; Sungkee, J. ; Yoon, Hyunsoo ; Cho, Jung-Wan

Author_Institution

Dept. of Electr. Eng. & Comput. Sci., Korea Adv. Inst. of Sci. & Technol., Seoul, South Korea

fYear

2001

fDate

2001

Firstpage

419

Lastpage

424

Abstract

The Internet is growing very rapidly in both the size and the amount of traffic. This growth has placed excessive strain on the Internet infrastructure, especially on routers. The IP address lookup is the operation that searches the longest matching prefix for the destination address of an incoming packet in order to determine the next hop of the packet. This operation is complex and is a major bottleneck in high-performance routers. In this paper, we propose a fast and updatable lookup scheme that can be easily implemented in hardware. We also present the memory allocation policy that supports for the incremental update of the forwarding table. Since our lookup scheme can be implemented with the small-bit logic and SRAM, the average delay per one lookup is about 18 ns. That is, our scheme can achieve 55.56 × 10⁶ routing lookups/s in average

Keywords

Internet; performance evaluation; storage management; table lookup; telecommunication network routing; transport protocols; IP address lookup; Internet; Internet performance; Internet traffic; bottleneck; forwarding table; hardware architecture; incremental update; lookup scheme; memory allocation; Bandwidth; Capacitive sensors; Computer science; Delay; Hardware; Internet; Logic; Random access memory; Routing; Web sites;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer Networks and Mobile Computing, 2001. Proceedings. 2001 International Conference on

Conference_Location

Los Alamitos, CA

Print_ISBN

0-7695-1381-6

Type

conf

DOI

10.1109/ICCNMC.2001.962627

Filename

962627