Update-aware Controlled Prefix Expansion for fast IP lookups

摘要

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 [1,2,3,6]. 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) [2] 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. To make multi-bit tries adequate to these updates, a series of multi-bit tries nodes need to be modified. Since these updates can seriously affect the lookup speed, we need to minimize these update cost. However, CPE does not concern this issue. In this paper, we explore the optimization issue in terms of the update cost. We want to find an update-optimal multi-bit tries that still have the efficiency of lookup speed and memory usage. Contrast to CPE, our solutions achieve a 26% reduction of the update overhead and improve 38% of the search speed. Besides, we also examine our schemes in IPv6 routing tables. The experimental results show that our scheme can also scale well in IPv6.