Network routing table using content addressable memory

• US 6,307,855 B1
• Filed: 07/07/2000
• Issued: 10/23/2001
• Est. Priority Date: 07/09/1997
• Status: Expired due to Term

• Current Assignee: Yoichi Hariguchi
• Original Assignee: Yoichi Hariguchi
• Inventors: Hariguchi, Yoichi
• Primary Examiner(s): Olms, Douglas
• Assistant Examiner(s): Pizarro, Ricardo M.
• Application Number:
  US09/611,881
• Time in Patent Office: 473 Days
• Field of Search: 370/351, 370/389, 370/392, 370/422, 370/398, 370/391, 370/390, 370/395, 370/396, 370/256, 370/406, 370/471, 713/160, 711/108, 711/212, 711/164, 707/3, 707/6, 707/7, 709/220, 709/226
• US Class Current: 370/392
• CPC Class Codes: G11C 15/04 using semiconductor elements
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/7453 using hashing

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.

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.

2. The CAM of claim 1, further comprising a prioritizer connected to the entry mask value lines of the plurality of CAM entries, wherein the prioritizer produces output signals as follows:

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.

8. The CAM of claim 7, further comprising a mask bit storing circuit that stores a mask bit for the CAM cell.

9. The CAM of claim 7, further comprising an entry mask register for storing an entry mask index value for a CAM entry.

10. The CAM of claim 9, further comprising a decoder, wherein the decoder produces from the entry mask index value a plurality of mask bits.

11. A network routing table comprising the CAM of claim 7, wherein the search key is an input destination address and the stored data bits in each CAM entry specify a stored destination address.

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.

13. The CAM of claim 12, wherein the means for masking an activation of the means for indicating a match comprises means for storing the entry mask bits.

14. The CAM of claim 12, wherein the means for masking an activation of the entry hit line means comprises:

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.

17. The method of claim 16, further comprising storing the entry mask bits for each entry.

18. The method of claim 16, further comprising:

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.