Method and apparatus for high speed table search

Details Method and apparatus for high speed table search Method and apparatus for high speed table search

2001-03-08

2004-01-13

Jung, David (Department: 2134)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000

Reexamination Certificate

active

06678678

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to a method and apparatus for searching an electronically stored table of information including a plurality of table entries, and more specifically to a method and apparatus for facilitating high speed linear searching of a table by a plurality of agents that are each required to search many entries of the table using different search keys.
2. Description of the Related Art
In the fields of electronic data communications and data processing, electronically stored tables of information are used in vast variety of applications to provide a mapping between two or more information spaces. The tables of information, which include a plurality of entries, may be searched in accordance with many different methods.
Generally, a searching agent searches a table using a search key, and may read one or more tables entries to determine an exact match or a best match depending on the particular application requirements. It is a common design requirement that each of a plurality of searching agents having different search keys is required to search a single table of information. For applications in which it is generally not feasible to employ a multiplicity of memory devices storing the same table of information, an arbitration scheme is typically employed to resolve requests from each of the searching agents for access to the single table.
Many algorithms and devices have been developed to efficiently search tables of information. A basic brute force method is linear searching wherein a device searches a table linearly one entry at a time. Linear searching is the simplest search method, and it is ideal for searching small tables in applications having slow search requirements. However, linear searching becomes impractical as the table sizes increase because the maximum search time is proportional to the table size.
In order to shorten the table search time, binary searching methods may be used wherein all entries of the table are sorted in a particular order, and the search times are equal to log
2
(table size). Binary searching methods are particularly desirable for searching large tables using software, but sorting the table entries in a particular order is not a simple task. Due to this high maintenance requirement, binary searching is often not feasible to implement in hardware.
One of the quickest methods of table searching uses content addressable memory (CAM) searching wherein all table entries are compared against a search key at the same time, and the search result is delivered to an output instantly. However, CAM searching provides high search performance at the expense of implementing greater logic using a greater amount of silicon real estate. Moreover, there is typically a limit to the size of comparison fields (i.e. data width) and the size of payload fields which may be used in CAM searching.
Some of the most common methods of table search employ hashing algorithms in which table entries are grouped into different buckets in accordance with the particular type of hashing algorithm (i.e. crc32). Searching systems employing hashing algorithms are capable of narrowing the searching area to a specific location (a bucket), and this limits the maximum searching time. The maximum table searching time is based on the size of the bucket, and the table search time remains constant as the number of buckets increases. As the number of the table entries increase, the possibility that two or more entries are hashed to a same bucket also increases. If the maximum table entry (the size of table) is considerably larger than the typical number of entries used at the same time and the hash algorithm spreads the entries evenly, there is a good chance that only one or two entries are in a bucket. In this case, the average search time will be rather short (one or two clock cycles per search). A good hash algorithm scatters table entries evenly over the search table, but there is a possibility that many table entries may hashed into the same bucket. Thus, using 100 percent of a table is not practical, and the size of the table often needs to be much larger than the typical number of table entries.
In the field of data communications, there are many applications wherein each of a plurality of searching agents is required to search a single table of information. In routing and switching devices, a table of information is often used to provide a mapping mechanism for forwarding data, typically in the form of a packet (e.g., an Ethernet Packet), from one location to another location.
As packets arrive at each of a plurality of associated ports of a switch or router device, a plurality of port searching agents, each associated with one of the ports, must search information stored in the table to determine an appropriate action. For example, if the table includes an entry providing a direction for the arrived packet, the device forwards the packet in the direction indicated. If the table does not include an entry providing a direction for the arrived packet, the device may handle the packet based on a default setting. Examples of default settings include sending the packet to all available ports (broadcasting), sending the packet to a central processing unit (CPU) for analysis in accordance with a predefined set of rules, or dropping the packet. For Ethernet routing applications, a table of information is typically organized based on particular fields (e.g., a medium access control (MAC) Address, an IP Address, a Virtual LAN ID, etc.) of a packet. When particular fields of the packet match particular fields of the table, the device utilizes the corresponding information in the table to forward the packet.
In conventional table searching systems wherein each of a plurality searching agents is required to search a single table of information, a “pull” searching method is typically employed wherein each of the searching agents is required to initiate table searching. An arbitration scheme is usually employed to resolve requests initiated by each of a plurality of searching agents for access to the single table.
FIG. 1
shows a generalized block diagram of a conventional table information searching system at
10
, the system operating in accordance with conventional pull search techniques. The system
10
includes a plurality of N+1 searching agents
12
designated AGENT_
0
, AGENT_
1
, . . . AGENT_N. As an example, each of the searching agents
12
may be a port agent communicatively coupled with a receiving port of a switching device. Each of the searching agents
12
includes: a receiver port
14
for receiving a search key (e.g., a destination address of a data jacket); an arbitration request signal output port
16
for providing one of a plurality of N+1 request signals designated REQ_
0
, REQ_
1
. . . REQ_N; an arbitration grant signal input port
18
for receiving an associated one of a plurality of N+1 grant signals designated GNT_
0
, GNT_
1
. . . GNT_N; a table data input port
20
for receiving table information via a table data bus
21
as further explained below; and a memory address output port
22
for providing address values to a search address bus
23
as further explained below.
The system
10
further includes; an arbitration logic unit
26
having a plurality of request signal input ports
28
for receiving associated ones of the arbitration request signals, and a plurality of N+1 arbitration grant signal output ports
30
each providing an associated one of the arbitration grant signals to port
18
of an associated one of the agents
12
; and a table information memory unit
36
for storing a table of information, and having a table data output port
38
for providing table data to the table data input port
20
of selected ones of the searching agents
12
via the bus
21
, and a search address input port
40
for receiving the memory address values from the ports
22
of selected ones of the agents
12
.
The table information memory unit
36
is typically implemented

Affiliated with

Also associated with

Rating

Method and apparatus for high speed table search does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and apparatus for high speed table search, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for high speed table search will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3236533