Lookup engine

A look up engine according to claim 1, wherein the look up engine further comprises a tagging mechanism in which each key value has a tag associated therewith such that the output values can be ordered in accordance with the order of receipt of the input key value.

A method for looking up a value, the method comprising the steps of:

• (a) receiving a key value;
• (b) comparing the input key value with a plurality of stored key values;
• (c) outputting the value associated with the stored key value that matches the input key value, wherein steps (a), (b) and (c) are carried out concurrently.

A computer system comprising a plurality of processing means interconnected via a bus system, the computer system further comprising a look up engine, the look up engine comprising a storage means for storing a plurality of entries, each entry comprising a value and an associated key value, such that, in operation, a look up is carried out by outputting a value which is associated with the stored key value which matches an input key value, the look up engine comprising a plurality of look up state machines connected in parallel to enable multiple look ups to be carried out concurrently.

A look up engine comprising at least one storage means for storing a plurality of entries, each entry comprises a key value, an associated value and a skip value, such that, in operation a look up is carried out by outputting a value which is associated with the stored key value which matches an input key value, the input key comprising a plurality of bits, if the skipped bits of the input key value and the associated skip value mismatches, an error message is output to indicate lookup failure.

A method of constructing a trie in a storage means, the trie comprising a plurality of entries, the method comprising the steps of:

• identifying overlapping ranges between the plurality of entries;
• splitting the identified overlapping ranges;
• storing the plurality of entries within a trie structure.

A look up engine constructed and updated in accordance with a method of constructing a trie in a storage means, the trie comprising a plurality of entries, the method comprising the steps of:

• identifying overlapping ranges between the plurality of entries;
• splitting the identified overlapping ranges;
• storing the plurality of entries within a trie structure.