Optimal routing table design for IP address lookups under memory constraints

Author

Cheung, Gene ; McCanne, Steve

Author_Institution

Dept. of Electr. Eng. & Comput. Sci., California Univ., Berkeley, CA, USA

Volume

3

fYear

1999

fDate

21-25 Mar 1999

Firstpage

1437

Abstract

The design of lookup tables for fast IP address lookup algorithms using a general processor is formalized as an optimization problem. A cost model that models the access times and sizes of the hierarchical memory structure of the processor is formulated. Two algorithms, using dynamic programming and Lagrange multipliers, solve the optimization problem optimally and approximately respectively. Experimental results show our algorithms have visible improvements over existing ones in the literature

Keywords

approximation theory; dynamic programming; table lookup; telecommunication network routing; transport protocols; IP address lookups; Lagrange multipliers; access times; cost model; dynamic programming; experimental results; fast IP address lookup algorithms; general processor; hierarchical memory structure; memory constraints; memory size; optimal routing table design; optimization problem; Costs; Design optimization; Heuristic algorithms; IP networks; Internet; Memory management; Routing; Search engines; Spine; Table lookup;

fLanguage

English

Publisher

ieee

Conference_Titel

INFOCOM '99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE

Conference_Location

New York, NY

ISSN

0743-166X

Print_ISBN

0-7803-5417-6

Type

conf

DOI

10.1109/INFCOM.1999.752164

Filename

752164