Efficient BaRT-based Routing table searches using both on-chip and off-chip memory
Original Publication Date: 2003-Jul-24
Included in the Prior Art Database: 2003-Jul-24
Different ways of implementing enhanced searches in routing tables are introduced with regard to the use of on-chip and off-chip memory.
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  and
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  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  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 , the tables stored in off-chip memory are compressed according to th...