Title :
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
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;
Conference_Titel :
High Performance Switching and Routing, 2001 IEEE Workshop on
Conference_Location :
Dallas, TX
Print_ISBN :
0-7803-6711-1
DOI :
10.1109/HPSR.2001.923637
