A processor based high-speed longest prefix match search engine

Author

Kobayashi, Masayoshi ; Murase, Tutomu

Author_Institution

Networking Res. Labs, NEC Corp., Japan

fYear

2001

fDate

2001

Firstpage

233

Lastpage

239

Abstract

This paper describes a new IP forwarding table search method that can be implemented on a general-purpose processor with a high-speed cache memory. It uses an efficient small data structure to store an IP forwarding table in the cache memory by exploiting a characteristic of the IP address prefixes of forwarding tables in the Internet backbone. At the particular level of the prefix-tree, the number of the prefixes below most of the nodes is very small. The method enables a general-purpose 500-MHz processor equipped with a 512-KB internal cache to perform searches at the wire-speed of a 2.4-Gb/sec link

Keywords

Internet; cache storage; general purpose computers; microprocessor chips; search engines; transport protocols; tree data structures; 2.4 Gbit/s; 500 MHz; 512 kByte; IP address; IP forwarding table search method; IP forwarding table storage; Internet backbone; data structure; efficient small data structure; general-purpose processor; high-speed cache memory; internal cache; longest prefix match search engine; prefix-tree; processor based high-speed search engine; routers; wire-speed; Cache memory; Cams; Frequency; Internet; Laboratories; SONET; Search engines; Search methods; Spine; Throughput;

fLanguage

English

Publisher

ieee

Conference_Titel

High Performance Switching and Routing, 2001 IEEE Workshop on

Conference_Location

Dallas, TX

Print_ISBN

0-7803-6711-1

Type

conf

DOI

10.1109/HPSR.2001.923638

Filename

923638