Browse Prior Art Database

New Caching Scheme for Routing Table Lookups

IP.com Disclosure Number: IPCOM000015158D
Original Publication Date: 2001-Aug-19
Included in the Prior Art Database: 2003-Jun-20
Document File: 3 page(s) / 53K

Publishing Venue

IBM

Abstract

Introduction IP Forwarding is the process in which an Internet router uses the IP destination address of an incoming packet to search a routing table according to a longest-matching prefix search in order to determine the next router (i.e., next hop) to which the packet has to be forwarded to. The high search rates required by the increasing link speeds (OC-192, OC-768, etc.) force the IP forwarding function to use fast but expensive memory such as embedded DRAM and SRAM, having only limited storage capacity. In addition, routing tables are growing at exponential rates. These two trends have driven several research efforts towards lookup schemes using memory hierarchies similar as in general-purpose computers (e.g., L1/L2 caches, main memory). Some earlier schemes were based on conventional processor caches, which were indexed by the full 32-bit IPv4 destination address. With these schemes, the cache is searched using an exact-match operation. A longest-matching prefix search is only performed on the complete data structure in the main memory upon a cache-miss. More recent projects focus on caches that are searched using prefix-match rather than exact-match as this appears to be much more efficient. These projects store variable-length prefixes in the cache instead of 32-bit IPv4 addresses, and perform cache control at the corresponding granularity (e.g., maintaining information to determine the least-recently-used prefix for a replacement operation).

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 51% of the total text.

Page 1 of 3

New Caching Scheme for Routing Table Lookups

Introduction

IP Forwarding is the process in which an Internet router uses the
IP destination address of an incoming packet to search a routing
table according to a longest-matching prefix search in order to
determine the next router (i.e., next hop) to which the packet
has to be forwarded to.

The high search rates required by the increasing link speeds
(OC-192, OC-768, etc.) force the IP forwarding function to use
fast but expensive memory such as embedded DRAM and SRAM, having
only limited storage capacity. In addition, routing tables are
growing at exponential rates. These two trends have driven
several research efforts towards lookup schemes using memory
hierarchies similar as in general-purpose computers (e.g., L1/L2
caches, main memory). Some earlier schemes were based on
conventional processor caches, which were indexed by the full
32-bit IPv4 destination address. With these schemes, the cache is
searched using an exact-match operation. A longest-matching
prefix search is only performed on the complete data structure in
the main memory upon a cache-miss.

More recent projects focus on caches that are searched using
prefix-match rather than exact-match as this appears to be much
more efficient. These projects store variable-length prefixes in
the cache instead of 32-bit IPv4 addresses, and perform cache
control at the corresponding granularity (e.g., maintaining
information to determine the least-recently-used prefix for a
replacement operation).

Description

The presented caching scheme focuses on search structures similar
to the one described in [1], which will be used as reference
structure in the following description. For a description of the
search operation, the update process, the entry formats and other
details of the data structure is referred to in [1].

The presented caching scheme is based on caching entire subtrees
of the data structure instead of individual prefixes. The concept
is shown in Figure 1. In this figure the initial level of the
data structure is stored...