Network routing table using content addressable memory
OwnerYoichi Hariguchiinventor
Life of this patent
Estimating the term…
Abstract
A routing table comprises routing table entries [230], a word line driver [92], prioritizer [100], and memory [106]. Each routing table entry [230] comprises content addressable memory (CAM) cells [220] and an entry masking circuit. The routing table looks up in parallel an entry matching an input network address, and outputs the search result in deterministic time. Only the bits specified by the masking circuit in each entry are compared when searching. If multiple entries match the input, the prioritizer [100] uses mask information from the masking circuits of the matching entries to select the best entry, e.g. the entry having the most matching bits.
Claims19
A content addressable memory (CAM) comprising a plurality of CAM entries,
- wherein each CAM entry comprises:
- a plurality of CAM cells, wherein each CAM cell stores a data bit for the CAM entry and compares the stored data bit with a bit of a search key;
- an entry hit line, wherein the entry hit line indicates a match between said bit the search key and the stored data bits of the CAM cells in the CAM entry;
- an entry masking circuit, wherein the entry masking circuit masks an activation of the entry hit line in accordance with entry mask bits, and
- entry mask value lines connected to the entry masking circuit, wherein the entry mask value lines output the entry mask bits from the CAM entry.
A content addressable memory (CAM) comprising a plurality of CAM entries, each of which comprises a plurality of CAM cells, wherein each CAM cell comprises:
- a data bit storing circuit that stores a data bit for the CAM cell;
- a comparator that compares the stored data bit with a bit of a search key;
- a hit line, wherein the hit line indicates a match between the bit of the search key and the stored data bit;
- a masking circuit, wherein the masking circuit masks an activation of the hit line in accordance with a mask bit;
- and
- a mask value line connected to the masking circuit, wherein the mask value line outputs the mask bit from the CAM cell.
A content addressable memory (CAM) comprising a plurality of CAM entries,
- wherein each CAM entry comprises:
- means for storing data bits for the CAM entry and for comparing the stored data bits with a search key;
- means for indicating a match between the search key and the stored data bits of the means for storing data bits for the CAM entry;
- means for masking an activation of the means for indicating a match, in accordance with entry mask bits, and
- means for outputing the entry mask bits from the CAM entry.
A method for storing and comparing data bits with a search key, the method comprising:
- providing a content addressable memory (CAM) comprising a plurality of CAM entries;
- storing data bits in the CAM entries;
- comparing the search key with the stored data bits in each of the CAM entries;
- indicating a match between the search key and the stored data bits of each CAM entry;
- masking, for each CAM entry in accordance with mask bits for the entry, an activation of the indicated match for the entry;
- and
- outputing the mask bits from each entry of the CAM.
Dependencies are inferred from the claim text.