Partitioning search key thereby distributing table across...

Details Partitioning search key thereby distributing table across... Partitioning search key thereby distributing table across...

2001-08-10

2004-04-20

Mizrahl, Diane D. (Department: 2175)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000

Reexamination Certificate

active

06725216

ABSTRACT:

TECHNICAL FIELD
The present invention relates to the field of a packet switching network, and more particularly to partitioning a search key thereby distributing a table, e.g., direct table, across multiple non-contiguous segments within a memory bank, multiple banks of memory or memory modules.
BACKGROUND INFORMATION
A packet switching network has switching points or nodes for transmissions of data among senders and receivers connected to the network. The switching performed by these switching points is in fact the action of passing on packets of data received by a switching point or node to a further node in the network. Such switching actions are the means by which communication data is moved through the packet switching network.
Each node may comprise a packet processor configured to process packets of data. When a packet processor receives a particular packet of data, the packet processor may produce what is commonly referred to as a key. The key may be hashed into a smaller size key commonly referred to as a search key. That is, the search key may be two or more bits of the key where the one or more bits may be non-contiguous bits of the key. It is noted that the non-contiguous bits of the key may be selected using various logical operations such as AND, OR and NOT. The search key may be used to determine what actions to perform on the packet as described in further detail below. Typically, a key may be generated by the packet processor by extracting particular information in the packet header, e.g., source and destination address, source and destination port. Once the key is generated, a selected two or more bits of the key may be hashed into a search key used to access an entry into a table commonly referred to as a direct table. The direct table may comprise entries storing pointers that point to particular entries in a data structure memory. The data structure memory may comprise a plurality of entries storing data structures. A data structure may comprise data as to what actions, e.g., modify packet, port to forward packet, the packet processor should perform on the packet.
A search key may be used to access an entry in the direct table by performing what is commonly referred to as a “full match” search. In a full match search, if the search key indexes to an empty entry in the direct table, then a default action, e.g., transmitting packet to a higher layer classification, may be taken. If the search key indexes to an entry in the direct table with exactly one stored pattern, then the full key of the identity of the new packet is masked and compared with the stored item. If there is a match, then the action associated with the stored item may be taken. If there is not a match, a default action may be taken. If the search key indexes to an entry in the direct table corresponding to more than one stored pattern, then additional bits of the key are tested until all but at most one match is eliminated from further consideration. That is, the other bits of the key that were not hashed into the search key may be tested until all but at most one match is eliminated from further consideration. Then the full key of the identity of the new packet is masked and compared with the remaining stored item. If there is a match, then the action associated with the stored item may be taken. If there is not a match, a default action may be taken.
Since a search key may be many bits long, e.g., sixteen, the packet processor may use only certain bits to determine which entry to access in the direct table. Consequently, one or more entries may be accessed in the direct table by the same search key thereby causing a collision. The larger the size of the direct table, i.e., the more entries in the direct table, the less probability of a collision occurring. Hence, it may be desirable to build a single table with a size correlated to the length of the search key, i.e., the number of entries in the single table is equivalent to 2
n
where n is the number of bits in the search key. However, a direct table that size may not be feasible to build.
It would therefore be desirable to partition a search key into multiple segments thereby distributing a table, e.g., direct table, across multiple non-contiguous segments within a memory bank, multiple banks of memory or memory modules. By distributing a table, e.g., direct table, across multiple non-contiguous segments within a memory bank, multiple banks of memory or memory modules, tables that may not have been feasible to build may be built. Furthermore, by distributing a table, e.g., direct table, across multiple non-contiguous segments within a memory bank, multiple banks of memory or memory modules, search keys may be able to access the distributed table at a faster rate than the table constructed as a single table. The search keys may be able to access the distributed table at a faster rate than the table constructed as a single table since each layer of the distributed table is smaller in size than the table constructed as a single table thereby being able to be stored in faster memory. Furthermore, a table distributed across multiple non-contiguous segments within a memory bank, multiple banks of memory or memory modules, may have the same probability of collisions as the distributed table constructed on a single table of the same size.
SUMMARY
The problems outlined above may at least in part be solved in some embodiments by partitioning a search key into a plurality of segments where each segment length corresponds to a size of a particular level of a table. By partitioning a search key into a plurality of segments, a table may be distributed by storing levels of the table across multiple non-contiguous segments within a memory bank, across multiple banks in a memory or across memory modules.
In one embodiment of the present invention, a method for retrieving information in a distributed table by partitioning a search key may comprise the step of an internal processor within the packet processor receiving a packet of data. The internal processor may extract one or more fields in the packet header of the received packet to generate a key. The internal processor may then hash two or more bits of the key to generate a search key. The search key may then be partitioned into a plurality of segments where the length of each segment corresponds to a size of a particular layer of a table. For example, suppose the internal processor generates a key with a length of thirty-two bits, e.g., 111001101111001101111001101111001101. As stated above, a portion of the key may be hashed into a search key used to index into a particular entry in a table, e.g., direct table. For example, the first nine bits, e.g., 111001101, of the key may be used to index into a particular entry in the table as a search key. The internal processor may then partition the search key into two segments where the first segment has a length of four bits (W
0
=4), e.g., 1110, and the second segment has a length of five bits (W
1
=5), e.g., 01101. As stated above, the size of each layer of the table may be correlated to the length of each segment of the search key. For example, the size of the first layer (2
4
) may be correlated to the length of the first segment (W
0
=4) and the size of the second layer (2
5
) may be correlated to the length of the second search key (W
1
=5). The internal processor may be configured to read a particular entry in a layer, e.g., first layer, of the table using the value of the segment associated with the layer, e.g., first segment with a value of 1110.
A determination may be made by the internal processor to determine if the particular entry read was empty. If the particular entry read was empty then the internal processor may execute a default action. If the particular entry read was not empty then a determination may be made by the internal processor to determine if the particular entry read by the internal processor stores a pointer that points to the next level of the table. If the particular entry points to the next leve

Affiliated with

Also associated with

Rating

Partitioning search key thereby distributing table across... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Partitioning search key thereby distributing table across..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Partitioning search key thereby distributing table across... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3214577