Network routing table using content addressable memory
DCFirst Claim
1. 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.
0 Assignments
Litigations
0 Petitions
Accused Products
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.
-
Citations
19 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5, 6)
if the entry hit line in each of the CAM entries is not activated, a “
no hit”
signal;
if the entry hit line in only one of the CAM entries is activated, a “
hit”
signal and a hit entry address; and
if the entry hit line in each of more than one of the CAM entries is activated, a “
hit”
signal and a hit entry address selected in dependence upon mask bits of entries corresponding to activated hit lines.
-
-
3. The CAM of claim 1, wherein the entry masking circuit comprises an entry mask register, wherein the entry mask register stores the entry mask bits.
-
4. The CAM of claim 1, wherein the entry masking circuit comprises:
-
a mask index register, wherein the mask index register stores an entry mask index value for the entry, and a decoder, wherein the decoder produces from the entry mask index value the entry mask bits.
-
-
5. The CAM of claim 1, wherein the entry masking circuit comprises a mask memory cell associated with each of the CAM cells.
-
6. A network routing table comprising the CAM of claim 1, wherein the search key is an input destination address and the stored data bits in each CAM entry specify a stored destination address.
-
7. 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. - View Dependent Claims (8, 9, 10, 11)
-
-
12. 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. - View Dependent Claims (13, 14, 15)
means for storing an entry mask index value for the entry, and means for producing from the entry mask index value the entry mask bits.
-
-
15. The CAM of claim 12, wherein the means for masking an activation of the means for indicating a match comprises means for storing a mask bit associated with each data bit of the means for storing data bits.
-
16. 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. - View Dependent Claims (17, 18, 19)
storing an entry mask index value for each entry; and
producing from the entry mask index value the entry mask bits.
-
-
19. The method of claim 16, further comprising storing a mask bit for each stored bit in each CAM entry.
Specification