Granted Patent B2

US 7,446,681 · App. 11/424,064 · Granted Nov 4, 2008

Abstract

Claims (56)

1. A method of constructing, from a first array of entries, a second array having a reduced number of entries compared with the first array, the method comprising:

partitioning the first array into one or more groups of entries, wherein the first array includes N entries and is partitioned into N groups, each group containing N/M entries;

categorizing each group with a category categorizing relationships between entries of a respective group, or entries of a respective group and at least one entry of another group;

forming a compression code containing a sequence of coded identifiers, each identifier identifying the category of a respective group; and

constructing the second array to include selected entries from the first array, the selected entries depending on the category of each group and arranged so as to be indexable by processing a first index into the first array, and the compression code to derive a second index for retrieving an entry from the second array that is equivalent to the indexed entry of the first array, without decompressing the second array.

2. A method according to claim 1 wherein the category is a category selected from one or more of:

(a) a category categorizing that the entries in a group are identical;

(b) a category categorizing that the entries in a group are different;

(c) a category categorizing that at least some of consecutive entries of a group are identical; and

(d) a category categorizing that at least some of the entries in a group are identical with at least one entry of another group.

3. A method according to claim 1 , wherein the construction of the second array by selecting entries from the first array depending on the category of a group G includes entering into the second array:

(a) zero entries of the first array for each group categorized as having entries that are identical to the last entry in the preceding group, (G−1);

(b) one entry of the first array for each group categorized as having entries that are identical to each other, but different from the last entry in the preceding group, (G−1);

(c) (N/2*M) entries of the first array for each group categorized as having its first (N/2*M) entries identical to each other and also identical to the last entry in the preceding group, (G−1); and

(d) 2* (N/2*M) entries for each other group.

4. A method according to claim 3 wherein the category of each group is identified by a 2-bit binary identifier.

5. A method according to claim 4 wherein each set bit in a 2-bit binary coded identifier is indicative of a respective known number of equivalent entries in the second array that have been selected from the respective group of the first array.

6. A method according to claim 5 wherein:

(a) each group of the first array having zero entries entered into the second array is identified by the 2-bit identifier “00”;

(b) each group of the first array having one entry in the second array is identified by the 2-bit identifier “01”;

(c) each group of the first array having (N/2*M) entries in the second array is identified by the 2-bit identifier “10”; and

(d) each group of the first array having 2* (N/2*M) entries in the second array is identified by the 2-bit identifier “11”.

7. A method according to claim 1 , wherein the first array of entries includes a first sub-table of a longest prefix match table.

8. A method according to claim 1 , wherein the second array is a compressed sub-table containing selected entries from the first sub-table and wherein selecting entries from the first sub-table depending on the category of a group includes entering into the compressed sub-table:

(a) zero entries of the first sub-table for each group categorized as having entries that are identical to the last entry in the preceding group, (G−1);

(b) one entry of the first sub-table for each group categorized as having entries that are identical to each other, but different to the last entry in the preceding group, (G−1);

(c) (N/2*M) entries of the first sub-table for each group categorized as having its first (N/2*M) entries identical to each other and also identical to the last entry in the preceding group, (G−1); and

(d) 2* (N/2*M) entries of the first sub-table for each other group;

and wherein each category is identified using a dibit identifier.

9. A method of retrieving, from a second array, an entry that is equivalent to an entry of a first array indexed by a first index, the second array having a reduced number of entries compared to the first array, the method comprising:

processing the first index to identify a group of entries in the first array containing the entry indexed by the first index;

obtaining a compression code containing, for each group, a coded identifier categorizing a relationship between entries of a respective group, or entries of the respective group and at least one entry of another group;

indexing into the compression code to locate the coded identifier associated with the indexed group of the first array;

deriving, front the coded identifier for the indexed group of the first array and the identifiers for the groups preceding the indexed group, a second index for indexing into the second array to retrieve an entry that is equivalent to the indexed entry of the first array; and

retrieving the entry of the second array indexed by the second index.

10. A method according to claim 9 wherein the deriving of the second index comprises:

processing identifiers for groups preceding the group containing the indexed entry to obtain an index value indicative of the total number of equivalent entries in the second array for the preceding groups; and

modifying the index value according to the category of the indexed group to derive the second index.

11. A method according to claim 10 wherein the derivation of the second index is performed by a table lookup hardware circuit.

12. A method according to claim 11 wherein the table hardware look up circuit includes a pair of population counters, one each for counting the number of least significant bits and the most significant bits set in the 2-bit coded identifiers for the groups preceding the group containing the indexed entry.

13. A method according to claim 9 wherein each coded identifier includes a 2-bit binary coded identifier, and wherein each set bit in a 2-bit coded identifier is indicative of a respective known number of equivalent entries in the second array that have been selected from the respective group of the first array.

14. A method according to claim 10 wherein the index value is obtained by counting the set bits in the 2-bit coded identifiers for groups preceding the indexed group.

15. A method according to claim 9 , wherein the first array of entries includes a first sub-table of a longest prefix match table.

16. A method according to claim 15 , wherein the second array is a compressed sub-table containing selected entries from the first sub-table and wherein the first index includes a portion of a binary search key, so that the method comprises:

processing the portion of the binary search key to identify a group of entries in the first sub-table containing the entry indexed by the portion of the binary search key;

obtaining a compression code containing, for each group, a 2-bit coded identifier categorizing a relationship between entries of a respective group, or entries of the respective group and at least one entry of another group;

indexing into the compression code to locate the 2-bit coded identifier associated with the group of the first sub-table containing the indexed entry;

deriving, from the 2-bit coded identifier for the indexed group of the first sub-table and the 2-bit identifiers for the groups preceding the indexed group, a second index for indexing into the compressed sub-table to retrieve an entry that is equivalent to the indexed entry of the first sub-table; and

retrieving the entry of the compressed sub-table indexed by the second index.

17. A method of deriving, from a first index into a first array containing plural groups of entries and a compression code containing for each group of the first array a coded identifier categorizing a relationship between entries of a respective group, or entries of the respective group and at least one entry of another group, a second index into a second array, the method comprising:

processing the first index to identify the group of the first array containing the entry indexed by the first index;

indexing into the compression code to retrieve the identifier associated with the indexed group of the first array;

processing the identifiers for groups preceding the indexed group to obtain an index value indicative of the total number of equivalent entries in the second array for the preceding groups; and

modifying the index value according to the category of the indexed group to derive the second index.

18. A method according to claim 17 wherein each coded identifier includes a 2-bit binary coded identifier and wherein each set bit in a 2-bit coded identifier is indicative of a respective known number of equivalent entries in the second array that have been selected from the respective group of the first array.

19. A method according to claim 18 , wherein the first array of entries includes a sub-table of a longest prefix match table.

Assignments (17)