Update-aware controlled prefix expansion for fast IP lookups

Yeim Kuan Chang, Yung Chieh Lin, Kuan Ying Ho

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publication2009 International Conference on High Performance Switching and Routing, HPSR 2009
DOIs
Publication statusPublished - 2009 Dec 1
Event2009 International Conference on High Performance Switching and Routing, HPSR 2009 - Paris, France
Duration: 2009 Jun 222009 Jun 24

Publication series

Name2009 International Conference on High Performance Switching and Routing, HPSR 2009

Other

Other2009 International Conference on High Performance Switching and Routing, HPSR 2009
CountryFrance
CityParis
Period09-06-2209-06-24

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Hardware and Architecture
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Update-aware controlled prefix expansion for fast IP lookups'. Together they form a unique fingerprint.

Cite this