Fast IP table lookup and memory reduction

Author

Liu, Y.-C. ; Lea, C.-T.

Author_Institution

Dept. of Electr. & Electron. Eng., Hong Kong Univ. of Sci. & Technol., China

fYear

2001

fDate

2001

Firstpage

228

Lastpage

232

Abstract

One of the time-consuming tasks in IP4 packet processing is maximum sequence matching. Fast routing requires tens of millions of routing lookups to be performed in one second. This paper describes an implementation of IP table lookup. The implementation is intended as part of the cord of an OC-192 (10 Gbps) and OC-768 (40 Gbps) rate packet processor. One key element is a memory reduction technique that applies to all lookup algorithms. For algorithms with similar complexity as the one described in the paper, the improvement in terms of memory reduction is about 20%-30%

Keywords

SRAM chips; computational complexity; packet switching; pipeline processing; table lookup; telecommunication network routing; transport protocols; 10 Gbit/s; 40 Gbit/s; DRAM; IP4 packet processing; Internet router; OC-192 rate packet processor; OC-768 rate packet processor; SRAM; algorithm complexity; fast IP table lookup; fast routing; lookup algorithms; maximum sequence matching; memory reduction; pipeline technique; routing lookups; IP networks; Internet; Local area networks; Organizing; Random access memory; Routing; Software algorithms; Table lookup; Throughput; Tree data structures;

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.923637

Filename

923637