Lookup engine
A look up engine 200 comprising a storage means 212 a , 212 b 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 outputing a value which is associated with the stored key value which matches an input key value. The look up engine 200 comprises a plurality of look up state machines 206 a, 206 b, 206 c, 206 d connected in parallel to enable multiple look ups to be carried out concurrently. Each entry comprises an associated skip value, if the skipped bits of the input key value and the associated skip value mismatches, an error message is output to indicate lookup failure. The entries may be stored in a trie format which is constructed by identifying overlapping ranges between the plurality of entries; splitting the identified overlapping ranges; storing the plurality of entries within a trie structure.
1 - 31 . (canceled)
32 . 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.
33 . A method according to claim 32 , wherein the depth of the trie is programmable.
34 . A method according to claim 33 , wherein the entries are arranged in a PATRICIA trie.
35 . A method according to any one of claim 32 , wherein, the method further comprises the step of:
providing each entry with a skip value such that, during the look up operation, the skip value associated with the value corresponding to the input key value is compared with the skipped bits of the input key value;
outputting the value associated with the stored key value that matches the input key value if the skip value matches the skipped bits of the input key value, and outputting an error message to indicate look up failure if the skip value does not match the skipped bits of the input key.
36 . 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.