Network routing table using content addressable memory

• US 6,181,698 B1
• Filed: 07/09/1997
• Issued: 01/30/2001
• Est. Priority Date: 07/09/1997
• Status: Expired due to Fees

• Current Assignee: Yoichi Hariguchi
• Original Assignee: Yoichi Hariguchi
• Inventors: Hariguchi, Yoichi
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Pizarro, Ricardo M.
• Application Number:
  US08/890,350
• Time in Patent Office: 1,301 Days
• Field of Search: 370/389, 370/390, 370/391, 370/392, 370/395, 370/396, 370/422, 710/108
• 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 routing table circuit for determining from a destination address an associated table entry, the circuit comprising:

a plurality of routing table entries for determining in parallel a set of routing table entry hit addresses from the destination address,

a prioritizer for selecting a single routing entry address from the set of routing table entry hit addresses, and

a memory for producing the associated table entry from the single routing entry address,

wherein each entry in the routing table comprises;

a collection of CAM cells for storing stored address bits;

a masking circuit for masking a portion of the stored address bits in accordance with an address prefix associated with the stored address bits; and

a mask output circuit for providing the address prefix to the prioritizer.

2. A method for routing a data packet having a packet destination address, the method comprising:

determining from the packet destination address an associated table entry; and

routing the packet in accordance with the associated table entry;

wherein the step of determining the associated table entry from the packet destination address comprises;

determining a set of table entry hit addresses by applying the packet destination address to a collection of CAM cells that store a stored address and store an address prefix of the stored address;

selecting a single entry address from the set of table entry hit addresses, and

producing the associated table entry from the single entry address.

3. An apparatus for routing a data packet having a packet destination address, the apparatus comprising:

a routing table circuit for determining from the packet destination address a next device identifier; and

a switching fabric for routing the packet in accordance with the next device identifier;

wherein the routing table circuit comprises;

a plurality of routing table entries for determining in parallel a set of table entry hit addresses from the destination address,

a prioritizer for selecting a single entry address from the set of table entry hit addresses, and

a memory for producing the next device identifier from the single entry address, wherein each entry in the routing table comprises;

a collection of CAM cells for storing stored address bits; and

a masking circuit for masking a portion of the stored address bits in accordance with an address prefix for the destination address.