Custom circuitry for adaptive hardware routing engine

Claim 2

Custom circuitry for reducing an L-bit data unit into an N-bit data unit selectable to include any combination of bits from the L-bit data unit, where L is an integer greater than two, N is an integer greater than one and L is greater than N, comprising: N successive multiplexors, each multiplexor receiving as inputs bits from M bit positions within the L-bit data unit including all but the first bit received as an input by the immediately preceding multiplexor, if any, and all but the last bit received as an input by the immediately succeeding multiplexor, if any, and wherein M is an integer sufficiently great such that each bit within the L-bit data unit is received as an input by at least one of the N successive multiplexors; and means for instructing each multiplexor to select for transmission as an output a single bit, if any, from the bits received as inputs by the multiplexor.

Claim 3

The custom circuitry according to claim 1, wherein the instructing means includes means for transmitting to each multiplexor a command identifying a single bit position, if any, from which the multiplexor is to select a bit for transmission as an output.

Claim 4

The custom circuitry according to claim 1, wherein the instructing means includes means for transmitting to the N successive multiplexors commands which in the aggregate identify the up to N bit positions within the L-bit data unit, which are the most distinctive according to the most recent calculation made by a hashing algorithm, from which the multiplexors are to select bits for transmission as outputs.

Claim 5

The custom circuitry according to claim 2, wherein the command is stored in and retrieved from a memory element.

Claim 6

The custom circuitry according to claim 3, wherein the commands are stored in and retrieved from one or more memory elements.

Claim 7

In a hardware routing engine, custom circuitry for implementing a dynamic data hashing algorithm, comprising: means for selecting an identifier from an identifier set; means for reducing the identifier to a value, the value including bits from the bit positions within the identifier which are the most distinctive according to the most recent calculation made by a hashing algorithm; means for adding an offset, if required, to the value to create an initial pointer to the first RAM entry in a linked list of one or more RAM entries; and means for using the initial pointer, and any subsequent pointer retrieved from any accessed RAM entry in the linked list, to access the first and any subsequent RAM entry, respectively, and retrieve match information for comparison with a match identifier associated with the identifier set, until either a match is found or all RAM entries in the linked list have been accessed.

Claim 8

In a hardware routing engine, custom circuitry for implementing a dynamic data hashing algorithm, comprising: means for selecting an identifier from an identifier set; means for reducing the identifier to a value, the value including bits from the bit positions within the identifier which are the most distinctive according to the most recent calculation made by a hashing algorithm; means for adding an offset, if required, to the value to create an initial pointer to the first RAM entry in a linked list of one or more RAM entries; and means for using the initial pointer, and any subsequent pointer retrieved from any accessed RAM entry in the linked list, to access the first and any subsequent RAM entry, respectively, and retrieve match information for comparison with a match identifier associated with the identifier set, until either a match is found or all RAM entries in the linked list have been accessed.

Claim 9

The custom circuitry according to claim 6, further comprising: means for tracking the number of comparisons for which a match is not found; and means for instructing the hashing algorithm to recalculate the most distinctive bit positions if the number of comparisons for which a match is not found has exceeded a configurable number.

Claim 10

The custom circuitry according to claim 6, further comprising: means for tracking the number of comparisons for which a match is not found; means for tracking the number of linked lists for which a configurable number of comparisons for which a match is not found has exceeded a configurable number; and means for instructing the hashing algorithm to recalculate the most distinctive bit positions if the number of linked lists has exceeded a configurable number.

Claim 11

In a hardware routing engine, custom circuitry for implementing a dynamic data hashing algorithm, comprising: means for selecting a look-up mode based on the most recent look-up mode information; means for selecting an identifier from an identifier set based on the selected look-up mode; means for reducing the identifier to value, the value including bits from the bit positions within the identifier which are the most distinctive according to the most recent calculation made by a hashing algorithm; means for adding an offset, if any, to the value to generate an initial pointer to the first RAM entry in a linked list of one or more RAM entries; means for using the initial pointer, and any subsequent pointer retrieved from any accessed RAM entry in the linked list, to access the first and any subsequent RAM entry, respectively, and retrieve match information for comparison with a match identifier associated with the identifier set, until either a match is found or all RAM entries in the linked list have been accessed; means for retrieving any subsequent look-up mode information from the RAM entry for which a match is found; and means for transmitting any subsequent look-up mode information to the look-up mode selecting means.

Claim 12

In a hardware routing engine, custom circuitry for implementing a dynamic data hashing algorithm, comprising: means for selecting a look-up mode based on the most recent look-up mode information; means for selecting an identifier from an identifier set based on the selected look-up mode; means for reducing the identifier to value, the value including bits from the bit positions within the identifier which are the most distinctive according to the most recent calculation made by a hashing algorithm; means for adding an offset, if any, to the value to generate an initial pointer to the first RAM entry in a linked list of one or more RAM entries; means for using the initial pointer, and any subsequent pointer retrieved from any accessed RAM entry in the linked list, to access the first and any subsequent RAM entry, respectively, and retrieve match information for comparison with a match identifier associated with the identifier set, until either a match is found or all RAM entries in the linked list have been accessed; means for retrieving any subsequent look-up mode information from the RAM entry for which a match is found; and means for transmitting any subsequent look-up mode information to the look-up mode selecting means.

Claim 13

The custom circuitry according to claim 9, further comprising: means for determining the number of RAM entries accessed in the linked list; and means for instructing the hashing algorithm to recalculate the most distinctive bit positions if the accessed number of RAM entries has exceeded a configurable number.