Browse Prior Art Database

Apparatus for Efficient Multi-Bit-Width Table Look-Up

IP.com Disclosure Number: IPCOM000030804D
Original Publication Date: 2004-Sep-25
Included in the Prior Art Database: 2004-Sep-25
Document File: 6 page(s) / 93K

Publishing Venue

Siemens

Related People

Juergen Carstens: CONTACT

Abstract

Usually, table look-up is considered for a uni-bit-width (unique-bit-width) of the keys as well as the table entries. There are a lot of methods for looking up a uni-bit-width table, each with its own advantages and disadvantages. The most representative ones are the linear search, the binary-tree search, the binary-range search, and the content addressable memory (CAM). These are schematically depicted in Figure 1. The look-up key and all of the table entries have the same bit-width, W. The processing unit (PU) is in charge of finding all matching entries in the table for the given look-up key. The output is a vector of indexes of the matching entries. Normally, the index vector is stored in a buffer in the memory and the PU gives the pointer (or address) of the buffer as the output. The index vector can also be given in a bit vector, where the location of a set bit represents the index of a matching entry. However, there are applications where it is required that the look-up works with different bit-widths. The most prominent example is the longest-matching-prefix look-up for IP routing. In this application, the look-up key is the destination address of a received IP packet, which is always of the full bit-width (e.g. 32 bits for IPv4). The table entries, on the other hand, mostly consist of fewer prefix-bits. The task is then to find the longest entry matching the key. Another example is the so-called "table look-up in a compressed domain", where the table entries are of different bit-widths, too. Furthermore, here the look-up key itself may have varying bit-widths. The most straightforward approach to do the multi-bit-width look-up is storing the table with the maximum bit-width, say W. Entries of a smaller bit-width are extended with zeros. The look-up key is also extended if its bit-width is smaller than W. Then the uni-bit-width machine can still be used, as shown in Figure 2. Clearly, this solution wastes both memory size and processing resources.

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 33% of the total text.

Page 1 of 6

S

Apparatus for Efficient Multi-Bit-Width Table Look-Up

Idea: Dr. Jinan Lin, DE-Munich; Dr. Sankamarayan Jagannathan, IN-Bangalore; Dr. Xiaoning Nie,

DE-Munich

Usually, table look-up is considered for a uni-bit-width (unique-bit-width) of the keys as well as the table entries. There are a lot of methods for looking up a uni-bit-width table, each with its own advantages and disadvantages. The most representative ones are the linear search, the binary-tree search, the binary-range search, and the content addressable memory (CAM). These are schematically depicted in Figure 1. The look-up key and all of the table entries have the same bit- width, W. The processing unit (PU) is in charge of finding all matching entries in the table for the given look-up key. The output is a vector of indexes of the matching entries. Normally, the index vector is stored in a buffer in the memory and the PU gives the pointer (or address) of the buffer as the output. The index vector can also be given in a bit vector, where the location of a set bit represents the index of a matching entry.

However, there are applications where it is required that the look-up works with different bit-widths. The most prominent example is the longest-matching-prefix look-up for IP routing. In this application, the look-up key is the destination address of a received IP packet, which is always of the full bit-width (e.g. 32 bits for IPv4). The table entries, on the other hand, mostly consist of fewer prefix-bits. The task is then to find the longest entry matching the key. Another example is the so-called "table look-up in a compressed domain", where the table entries are of different bit-widths, too. Furthermore, here the look-up key itself may have varying bit-widths. The most straightforward approach to do the multi-bit- width look-up is storing the table with the maximum bit-width, say W. Entries of a smaller bit-width are extended with zeros. The look-up key is also extended if its bit-width is smaller than W. Then the uni- bit-width machine can still be used, as shown in Figure 2. Clearly, this solution wastes both memory size and processing resources.

Alternatively, the table can be partitioned into several sub-tables according to the bit-width of the entries. Each sub-table has a constant bit-width for all of its entries. A look-up machine of uni-bit-width can hence be deployed for each sub-table. The look-up key is directed according to its bit-width, Wi, to the relevant machines, as shown in Figure 3. The main drawback of this solution is the inefficient utilization of the processing resources because for each look-up key only the relevant processing units are active while the others remain idle. A more efficient method, where only a single PU is deployed, has been proposed for looking up in compressed domains. However, the method is only suitable for the linear look-up or CAM. This publication proposes a new solution to the problem of multi-bit-width table look-u...