Optimal routing table design for IP address lookups under memory constraints
Gene Cheung, Steven McCanne · 1999
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.