Optimal routing table design for IP address lookups under memory constraints

Absrract-The design of lookup tables for fast IP address lookup algo-rithms using a general processor is formalized as an optimization prob-lem. 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. I