Update-Aware Controlled Prefix Expansion for Fast IP Lookups
Source: National Cheng Kung University
In high performance routers design, fast IP address lookup is always a challenge. In order to obtain fast lookup speed, multi-bit tries are often used to represent the routing tables. The drawbacks of multi-bit tries are the large memory usage and extensive update cost. To reduce the memory usage of multi-bit tries, Srinivasan and Varghese proposed a scheme called Controlled Prefix Expansion (CPE) that uses the dynamic programming technique to obtain the optimal multi-bit tries in terms of memory usage. Furthermore, current backbone routers usually run the Border Gateway Protocol (BGP). BGP may cause a few hundred of updates per second.