Method and apparatus for longest prefix matching

1. A lookup table including stored data, the lookup table comprising:

data including prefixes organized in a tree structure;

at least one Random Access Memory (RAM) for storing the data;

wherein said RAM includes a plurality of windows searchable in one cycle, a number of real prefixes in each window being less than a fixed number of entries that can be stored in said window; and

a single Ternary Content Addressable Memory (TCAM) for storing aggregation prefixes in a non-ascending order of their prefix lengths and an index of each said aggregation prefix, each index pointing to one of said RAM windows.

2. The lookup table according to claim 1 , wherein each window has said fixed number of entries and can be read and dynamically mapped in one cycle.

3. The lookup table according to claim 2 , wherein each window contains a plurality of entries, each entry containing at least a prefix field and a tag field.

4. The lookup table according to claim 3 , wherein said prefix field and tag field have sizes that vary in different windows.

5. The lookup table according to claim 1 , wherein the lookup table entries are protected by a protection scheme.

6. The lookup table according to claim 1 , wherein said RAM is implemented by multiple embedded RAM blocks, wherein each RAM block contains a part of the window information.

7. The lookup table according to claim 1 wherein said RAM is implemented as on-chip RAM memories.

8. The lookup table according to claim 1 , wherein said RAM is arranged for random access per window for reading to comparators, and for content access inside each said window for writing.

9. A method for performing a Longest Prefix Match (LPM) comprising:

organizing data in a lookup table including

storing the data in a Random Access Memory (RAM);

said RAM comprising a plurality of windows, each said window capable of storing a fixed number of entries; and

inserting aggregation prefixes having indices in a Ternary Content Addressable Memory (TCAM) in a non-ascending order of their prefix lengths, each index pointing to one of said windows;

where said step of organizing data comprises:

organizing lookup table prefixes in a binary tree structure

splitting the Prefix tree into a number of Prefix sub-trees where each sub-tree consists of a number of real prefixes less than said fixed number of entries in a corresponding window, said real prefixes having a common aggregation prefix; searching for a matching prefix according to a lookup key in said TCAM;

receiving a match signal from said TCAM including an index pointing to one of said RAM windows; and

searching according to said lookup key in said pointed to window in one cycle.

10. The method according to claim 9 , wherein said steps of searching in the said TCAM of a present lookup key and searching the RAM for a previous lookup key are performed simultaneously in one cycle.

11. The method according to claim 9 , wherein said prefix tree is split into prefix sub-trees by

traversing said tree from a root node;

selecting, at each node, a child node having a largest weight, wherein a weight is the number of nodes on a tree having that root, and splitting the tree to form a sub-tree at a first node having a weight less than a window size of said RAM;

writing the sub-tree real prefixes into one of said RAM windows in which all entries have a prefix field with an identical number of most significant bits

writing an entry with zero prefix into one of said RAM windows, if a sub tree node (or aggregating prefix) is not a real prefix, pointing to the same lookup result as the closest parent that represents a real prefix called herein backtracking pointer

writing the aggregation prefixes into a TCAM, each entry pointing to the corresponding RAM window having prefixes with the same aggregation prefix.

12. The method according to claim 9 , wherein said RAM is arranged for random parallel access per window for reading to comparators, and for content access inside each said window for writing.

13. A method for performing a Longest Prefix Match (LPM) comprising:

organizing data in a lookup table including

a Random Access Memory (RAM) for storing the data;

said RAM comprising a plurality of windows; and

a Ternary Content Addressable Memory (TCAM) for storing aggregating prefixes and associated indices, each index pointing to one of said windows;

searching according to a lookup key in said TCAM;

receiving a match signal from said TCAM including an index pointing to one of said windows; and

searching according to said lookup key in said pointed to window;

wherein said step of organizing includes organizing said data in said windows into entries, each entry containing at least a prefix and a tag;

further comprising

reading all entries of one of said windows in parallel;

generating a masked lookup key for each entry by masking each of the lookup key's least significant bits according to the entry's tag value;

comparing each entry's prefix to said masked key to identify a match;

selecting an entry with a largest tag value, when more than one entry provides a positive result; and

providing an index of the selected matching entry in case of a match.

14. The method according to claim 13 , wherein said step of organizing data in a lookup table comprises:

organizing the prefixes in a tree structure;

splitting the Prefix tree into a number of Prefix sub-trees where each sub-tree consists of a number of real prefixes less than a number of entries in a corresponding window.

15. The method according to claim 14 , wherein said Prefix tree is split into prefix sub-trees by

traversing said tree from a root node;

selecting, at each node, a child node having a largest weight, wherein a weight is the number of nodes representing lookup table entries (real prefixes) on a tree having that child node as root, and splitting the tree to form a sub-tree at a first node having a weight less than a window size of said RAM;

writing the sub-tree real prefixes into one of said RAM windows in which all entries have a prefix field with an identical number of most significant bits

writing an entry with zero prefix into one of said RAM windows, if a sub tree node is not a real prefix, pointing to the same lookup result as the closest parent that represents a real prefix called herein backtracking pointer

writing the aggregation prefixes is into said TCAK each entry pointing to the corresponding RAM window having prefixes with the same aggregation prefix.

16. A method according to claim 15 , wherein said step of writing aggregation prefixes includes inserting the aggregation prefixes into said TCAM in a non-ascending order of their prefix lengths.