TY - GEN
T1 - Update-aware controlled prefix expansion for fast IP lookups
AU - Chang, Yeim Kuan
AU - Lin, Yung Chieh
AU - Ho, Kuan Ying
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=74949092402&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=74949092402&partnerID=8YFLogxK
U2 - 10.1109/HPSR.2009.5307416
DO - 10.1109/HPSR.2009.5307416
M3 - Conference contribution
AN - SCOPUS:74949092402
SN - 9781424451746
T3 - 2009 International Conference on High Performance Switching and Routing, HPSR 2009
BT - 2009 International Conference on High Performance Switching and Routing, HPSR 2009
T2 - 2009 International Conference on High Performance Switching and Routing, HPSR 2009
Y2 - 22 June 2009 through 24 June 2009
ER -