Browse Prior Art Database

Efficient BaRT-based Routing table searches using both on-chip and off-chip memory

IP.com Disclosure Number: IPCOM000018576D
Original Publication Date: 2003-Jul-24
Included in the Prior Art Database: 2003-Jul-24
Document File: 2 page(s) / 35K

Publishing Venue

IBM

Abstract

Different ways of implementing enhanced searches in routing tables are introduced with regard to the use of on-chip and off-chip memory.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 2

Efficient BaRT-based Routing table searches using both on -chip and off-chip memory

The BaRT (Balanced Routing Table) algorithm for efficient routing table searches is described in [1] and
[2].

In the following, focus is on implementation of this type of search engine in environments involving both on-chip and off-chip memory.

On-chip memory typically can be accessed at a larger access granularity (e.g., 256 bits) due to the feasibility of wider on-chip data buses. For this type of memory, the wide-memory version of the BaRT algorithm as described in [2] can be used. Off-chip memory is usually accessed at smaller granularities
(e.g., 32 bits) due to the I/O (pin) limitations. For this type of memory, the `narrow-memory' version of the BaRT algorithm as described in [1] can be used.

Routing tables typically involve a small number (e.g., 5 %) of so called nested prefixes, which are routing table entries that are a prefix of other routing table entries. These nested prefixes can be handled efficiently using the wide-memory version of BaRT, but less efficiently with the `narrow-memory' version of BaRT: In the latter case nested prefixes result either in extra memory accesses or in extra storage requirements.

A first aspect of the proposal involves storing the BaRT-compressed tables, that are located at the first (upper) levels of the data structure, in on-chip memory and storing the BaRT-compressed tables at the remaining (lower) levels of the data structure in off-chip memory. The tables stored in the wider on-chip memory are compressed according to the wide-memory version of BaRT as explained in [2], the tables stored in off-chip memory are compressed according to th...