US5938736A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Search engine architecture for a high performance multi-layer switch element
Assignee: Oracle America Inc
•
Filing: 1997-06-30
•
Granted: 1999-08-17
•
Expires: 2017-06-30
Abstract
Abstract A multi-layer switch search engine architecture is provided. According to one aspect of the present invention, a switch fabric includes a search engine, and a packet header processing unit. The search engine may be coupled to a forwarding database memory and one or more input ports. The search engine is configured to schedule and perform accesses to the forwarding database memory and to transfer forwarding decisions to the one or more input ports. The header processing unit is coupled to the search engine and includes an arbitrated interface for coupling to the one or more input ports. The header processing unit is configured to receive a packet header from one or more of the input ports and is further configured to construct a search key for accessing the forwarding database memory based upon a predetermined portion of the packet header. The predetermined portion of the packet header is selected based upon a packet class with which the packet header is associated.
Inventors
- 👤 Shimon Muller
- 👤 Ariel Hendel
- 👤 Louise Yeung
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 11:45
CPC Classifications
H; H04; H04L; H04L49/00; H04L49/60; H04L49/602; H04L45/00; H04L45/74; H04L45/745; H04L45/7453; H04L9/00; H04L9/40; H04L49/20; H04L49/201; H04L49/205; H04L49/30; H04L49/3009; H04L49/35; H04L49/351; H04L69/00; H04L69/22
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
135 words
A switch fabric comprising: a search engine for coupling to a forwarding database memory and a plurality of input ports, the search engine configured to schedule and perform accesses to the forwarding database memory and to transfer forwarding decisions to the plurality of input ports; and a header processing unit coupled to the search engine and having an arbitrated interface for coupling to the plurality of input ports, the header processing unit configured to receive a packet header from an input port of the plurality of input ports and to construct a first search key for accessing the forwarding database memory based upon a predetermined portion of the packet header, the predetermined portion of the packet header being selected based upon a class of a plurality of classes with which the packet header is associated.
Claim 2
Dependent Claim
135 words
A switch fabric comprising: a search engine for coupling to a forwarding database memory and a plurality of input ports, the search engine configured to schedule and perform accesses to the forwarding database memory and to transfer forwarding decisions to the plurality of input ports; and a header processing unit coupled to the search engine and having an arbitrated interface for coupling to the plurality of input ports, the header processing unit configured to receive a packet header from an input port of the plurality of input ports and to construct a first search key for accessing the forwarding database memory based upon a predetermined portion of the packet header, the predetermined portion of the packet header being selected based upon a class of a plurality of classes with which the packet header is associated.
Claim 3
Dependent Claim
112 words
The switch fabric of claim 1, wherein the header processing unit further comprises the following pipeline stages: an address accumulation unit, coupled to the plurality of input ports and the arbitrated interface, for accessing address information from the packet header; an encapsulation processing unit, coupled to the plurality of input ports and the arbitrated interface, for selecting a predetermined set of fields from the packet header to determine a type of encapsulation; a header class matching unit coupled to the plurality of input ports and the arbitrated interface, the header class matching including comparison logic to determine a header class based upon the type of encapsulation and a predetermined set of fields.
Claim 4
Dependent Claim
19 words
The switch fabric of claim 1, where in the first search key is a Layer 3 (L3) search key.
Claim 5
Dependent Claim
28 words
The switch fabric of claim 3, where the header processing unit is further configured to construct a Layer 2 (L2) search key for accessing the forwarding database memory.
Claim 6
Dependent Claim
19 words
The switch fabric of claim 1, where in the first search key is a Layer 2 (L2) search key.
Claim 7
Dependent Claim
23 words
The switch fabric of claim 1, wherein the plurality of input ports may each request for a forwarding decision independently of the others.
Claim 8
Dependent Claim
26 words
The switch fabric of claim 1, wherein the forwarding database memory comprises one or more content addressable memories (CAMs) coupled to a random access memory (RAM).
Claim 9
Dependent Claim
35 words
The switch fabric of claim 1, further including a command execution unit configured to interface with a processor, the command execution unit further configured to access the forwarding database memory on behalf of the processor.
Claim 10
Dependent Claim
37 words
The network device of claim 1, wherein the forwarding database memory comprises a first memory and a second memory and wherein the search engine is configured to pipeline accesses to the first memory and the second memory.
Claim 11
Dependent Claim
35 words
The switch fabric of claim 3, wherein the L2 search key is of a first size and the L3 search key is of a second size, the second size being greater than the first size.
Claim 12
Dependent Claim
146 words
A switch fabric comprising: a search engine for coupling to a forwarding database memory and a plurality of input ports, the search engine configured to schedule and perform accesses to the forwarding database memory and to transfer forwarding decisions to the plurality of input ports; and a header processing unit coupled to the search engine and having an arbitrated interface for coupling to the plurality of input ports, the header processing unit configured to receive a packet header from an input port of the plurality of input ports and to construct a first key and a second key for accessing a forwarding database memory, the first key comprising one or more fields from a first portion of the packet header and having a first length, the second key comprising one or more fields from a second portion of the packet header and having a second length.
Claim 13
Dependent Claim
146 words
A switch fabric comprising: a search engine for coupling to a forwarding database memory and a plurality of input ports, the search engine configured to schedule and perform accesses to the forwarding database memory and to transfer forwarding decisions to the plurality of input ports; and a header processing unit coupled to the search engine and having an arbitrated interface for coupling to the plurality of input ports, the header processing unit configured to receive a packet header from an input port of the plurality of input ports and to construct a first key and a second key for accessing a forwarding database memory, the first key comprising one or more fields from a first portion of the packet header and having a first length, the second key comprising one or more fields from a second portion of the packet header and having a second length.
Claim 14
Dependent Claim
45 words
The switch fabric of claim 11, wherein the first key is a Layer 2 (L2) key for retrieving an L2 entry from the forwarding database memory, the second key is a Layer 3 (L3) key for retrieving an L3 entry from the forwarding database memory.
Claim 15
Dependent Claim
16 words
The switch fabric of claim 12, wherein the first length is smaller than the second length.
Claim 16
Dependent Claim
36 words
The switch fabric of claim 12, wherein the first portion of the packet header comprises a media access control (MAC) header, and wherein the second portion of the packet header comprises an Internet Protocol (IP) header.
Claim 17
Dependent Claim
26 words
The switch fabric of claim 11, wherein the forwarding database memory comprises one or more content addressable memories (CAMs) coupled to a random access memory (RAM).
Claim 18
Dependent Claim
34 words
The switch fabric of claim 15, wherein an address for accessing the RAM includes an index produced by the one or more CAMs, and wherein the RAM contains both L2 and L3 forwarding information.
Claim 19
Dependent Claim
142 words
The switch fabric of claim 11, wherein the packet header includes an L2 header and an L3 header, and wherein the header processing unit comprises pipelined logic to allow processing of more than one packet header simultaneously, the pipeline logic including: an encapsulation block configured to determine the type of header encapsulation that has been employed in a first packet header and to determine an indication of the start of the L3 header based upon the type of header encapsulation; and an L3 header class matching block coupled to the encapsulation block for receiving the indication of the start of the L3 header, the L3 header class matching block configured to determine a class of a plurality of L3 classes with which a second packet header is associated based upon one or more fields in the L2 header and the L3 header.
Claim 20
Dependent Claim
122 words
A network device comprising: a plurality of ports including a first port for receiving a packet from a network; a forwarding memory including a first memory and a second memory, the first memory having stored therein an associative data entry corresponding to an the packet, the second memory coupled to the first memory and having stored therein an associated data entry corresponding to the associative data entry, the associative data entry including an indication of a set of ports to which the packet should be forwarded; and a search engine coupled to the plurality of ports and the forwarding memory, the search engine configured to schedule and perform accesses to the forwarding memory and to transfer the indication to the first port.
Claim 21
Dependent Claim
122 words
A network device comprising: a plurality of ports including a first port for receiving a packet from a network; a forwarding memory including a first memory and a second memory, the first memory having stored therein an associative data entry corresponding to an the packet, the second memory coupled to the first memory and having stored therein an associated data entry corresponding to the associative data entry, the associative data entry including an indication of a set of ports to which the packet should be forwarded; and a search engine coupled to the plurality of ports and the forwarding memory, the search engine configured to schedule and perform accesses to the forwarding memory and to transfer the indication to the first port.
Claim 22
Dependent Claim
28 words
The network device of claim 18, wherein the search engine is configured to eliminate Layer 2 (L2) destination address (DA) matching whenever an L2 learning cycle is needed.
Claim 23
Dependent Claim
29 words
The network device of claim 19, wherein the first memory comprises one or more content addressable memories (CAMs), and wherein the second memory comprises a random access memory (RAM).
Claim 24
Dependent Claim
19 words
The network device of claim 18, wherein the first memory and the second memory may be accessed in parallel.
Claim 25
Dependent Claim
23 words
The network device of claim 21, wherein the search engine is configured to pipeline accesses to the first memory and the second memory.
Claim 26
Dependent Claim
29 words
The network device of claim 22, wherein the first memory comprises one or more content addressable memories (CAMs), and wherein the second memory comprises a random access memory (RAM).
References Cited (Backward Citations)
US4652874A
Cited
US4935869A
Cited
US4850042A
Cited
US4807111A
Cited
US4811337A
Cited
US4899333A
Cited
US4922503A
Cited
US4933938A
Cited
US5220562A
Cited
US5278830A
Cited
US5210746A
Cited
US5301333A
Cited
US5309437A
Cited
US5231633A
Cited
US5150358A
Cited
US5481540A
Cited
US5251205A
Cited
US5353412A
Cited
US5293379A
Cited
US5500860A
Cited
US5392432A
Cited
US5461624A
Cited
US5343471A
Cited
US5742760A
Cited
US5432907A
Cited
US5720032A
Cited
US5457681A
Cited
US5425028A
Cited
US5291482A
Cited
US5490252A
Cited
US5410540A
Cited
US5649109A
Cited
US5410722A
Cited
US5459714A
Cited
US5485578A
Cited
US5386413A
Cited
US5477537A
Cited
US5455820A
Cited
US5426736A
Cited
US5394402A
Cited
US5450399A
Cited
US5555405A
Cited
US5515376A
Cited
US5610905A
Cited
US5473607A
Cited
US5422838A
Cited
US5485455A
Cited
US5790546A
Cited
US5570365A
Cited
US5535202A
Cited
US5761435A
Cited
US5509123A
Cited
US5459717A
Cited
US5602841A
Cited
US5572522A
Cited
US5606669A
Cited
US5461611A
Cited
US5617421A
Cited
US5583981A
Cited
US5600641A
Cited
US5751967A
Cited
US5640605A
Cited
US5619500A
Cited
US5594727A
Cited
US5490139A
Cited
US5675741A
Cited
US5784573A
Cited
US5726977A
Cited
US5745048A
Cited
US5706472A
Cited
US5561666A
Cited
US5633865A
Cited
US5561791A
Cited
US5619661A
Cited
US5636371A
Cited
US5734865A
Cited
US5790808A
Cited
US5651002A
Cited
US5754540A
Cited
US5691984A
Cited
US5740175A
Cited
US5757771A
Cited
US5684800A
Cited
US5754801A
Cited
US5740375A
Cited
US5781549A
Cited
US5724358A
Cited
US5764634A
Cited
US5740171A
Cited
US5764636A
Cited
US5742604A
Cited
US5757795A
Cited
US5802052A
Cited
US5748905A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-08-16 | 2003-02-15 | 2003-08-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-08-16 | 2007-02-15 | 2007-08-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-08-16 | 2011-02-15 | 2011-08-17 | $7700.00 | Window Closed / Lapsed |