US6862281B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
L4 lookup implementation using efficient CAM organization
Assignee: Cisco Technology Inc
•
Filing: 2001-05-10
•
Granted: 2005-03-01
•
Expires: 2021-05-10
Abstract
Abstract A method of segmenting Layer 4 packet routing lookups into multiple levels for sequential search in multiple tables provided in a specially organized memory device, such as a content addressable memory (CAM). Using a sequence of limited-width keys, a single CAM (or length-cascaded bank of CAMs) can be tuned to provided faster and more efficient use of limited CAM space. Lookups used to process continuous streams of packets (such as those in the Internet Protocol [IP] format) can be performed with the present invention in either one-packet-at-a-time sequential order or in a pipelined fashion. Packet streams arriving on multiple ports of the switch device can also take advantage of time division multiplexing to employ a single search engine embodying the present invention.
Inventors
- 👤 Varagur V. Chandrasekaran
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 04:00
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/74; H04L45/745; H04L45/7453; H04L69/00; H04L69/12; H04L69/22; H04L69/30; H04L69/32; H04L69/322; H04L69/326
Claims Analysis
Total Claims: 41
Claim 1
Independent Claim
114 words
A lookup method for use in a switch, comprising the steps of: parsing a packet header to obtain a plurality of data fields; selecting at least one of said plurality of data fields as a protocol identifier and using said protocol identifier to directly access a Server Flow Table start pointer (sFlowRTP); performing a first lookup using said sFlowRTP and using one or more of said data fields as a first key to determine a Client Flow Table start pointer (cFlowRTP); performing a second lookup using said cFlowRTP and using one or more of said data fields as a second key to obtain a flow entry; and switching said packet using said flow entry.
Claim 2
Dependent Claim
114 words
A lookup method for use in a switch, comprising the steps of: parsing a packet header to obtain a plurality of data fields; selecting at least one of said plurality of data fields as a protocol identifier and using said protocol identifier to directly access a Server Flow Table start pointer (sFlowRTP); performing a first lookup using said sFlowRTP and using one or more of said data fields as a first key to determine a Client Flow Table start pointer (cFlowRTP); performing a second lookup using said cFlowRTP and using one or more of said data fields as a second key to obtain a flow entry; and switching said packet using said flow entry.
Claim 3
Dependent Claim
20 words
The method of claim 1 , wherein said first lookup or said second lookup is performed in a Patricia tree.
Claim 4
Dependent Claim
19 words
The method of claim 1 , wherein said first lookup or said second lookup utilizes a content addressable memory.
Claim 5
Dependent Claim
17 words
The method of claim 3 , wherein said content addressable memory comprises a ternary content addressable memory.
Claim 6
Dependent Claim
19 words
The method of claim 1 , wherein said direct access, said first lookup, and said second lookup are pipelined.
Claim 7
Dependent Claim
34 words
The method of claim 1 , wherein for packets arriving at a plurality of ports, at least said selecting, said performing said first lookup, and said performing said second lookup are time division multiplexed.
Claim 8
Dependent Claim
36 words
The method of claim 1 , further comprising: validating said sFlowRTP prior to performing said first lookup; validating said cFlowRTP prior to performing said second lookup; and validating said flow entry prior to performing said switching.
Claim 9
Dependent Claim
110 words
A computer switching system, comprising computer instructions for: parsing a packet header to obtain a plurality of data fields; selecting at least one of said plurality of data fields as a protocol identifier and using said protocol identifier to directly access a Server Flow Table start pointer (sFlowRTP); performing a first lookup using said sFlowRTP and using one or more of said data fields as a first key to determine a Client Flow Table start pointer (cFlowRTP); performing a second lookup using said cFlowRTP and using one or more of said data fields as a second key to obtain a flow entry; and switching said packet using said flow entry.
Claim 10
Dependent Claim
110 words
A computer switching system, comprising computer instructions for: parsing a packet header to obtain a plurality of data fields; selecting at least one of said plurality of data fields as a protocol identifier and using said protocol identifier to directly access a Server Flow Table start pointer (sFlowRTP); performing a first lookup using said sFlowRTP and using one or more of said data fields as a first key to determine a Client Flow Table start pointer (cFlowRTP); performing a second lookup using said cFlowRTP and using one or more of said data fields as a second key to obtain a flow entry; and switching said packet using said flow entry.
Claim 11
Dependent Claim
21 words
The switching system of claim 8 , wherein said first lookup or said second lookup is performed in a Patricia tree.
Claim 12
Dependent Claim
20 words
The switching system of claim 8 , wherein said first lookup or said second lookup utilizes a content addressable memory.
Claim 13
Dependent Claim
18 words
The switching system of claim 10 , wherein said content addressable memory comprises a ternary content addressable memory.
Claim 14
Dependent Claim
20 words
The switching system of claim 8 , wherein said direct access, said first lookup, and said second lookup are pipelined.
Claim 15
Dependent Claim
35 words
The switching system of claim 8 , wherein for packets arriving at a plurality of ports, at least said selecting, said performing said first lookup, and said performing said second lookup are time division multiplexed.
Claim 16
Dependent Claim
37 words
The switching system of claim 8 , further comprising: validating said sFlowRTP prior to performing said first lookup; validating said cFlowRTP prior to performing said second lookup; and validating said flow entry prior to performing said switching.
Claim 17
Dependent Claim
120 words
A computer-readable medium storing a computer program executable by a computer, the computer program comprising computer instructions for: parsing a packet header to obtain a plurality of data fields; selecting at least one of said plurality of data fields as a protocol identifier and using said protocol identifier to directly access a Server Flow Table start pointer (sFlowRTP); performing a first lookup using said sFlowRTP and using one or more of said data fields as a first key to determine a Client Flow Table start pointer (cFlowRTP); performing a second lookup using said cFlowRTP and using one or more of said data fields as a second key to obtain a flow entry; and switching said packet using said flow entry.
Claim 18
Dependent Claim
120 words
A computer-readable medium storing a computer program executable by a computer, the computer program comprising computer instructions for: parsing a packet header to obtain a plurality of data fields; selecting at least one of said plurality of data fields as a protocol identifier and using said protocol identifier to directly access a Server Flow Table start pointer (sFlowRTP); performing a first lookup using said sFlowRTP and using one or more of said data fields as a first key to determine a Client Flow Table start pointer (cFlowRTP); performing a second lookup using said cFlowRTP and using one or more of said data fields as a second key to obtain a flow entry; and switching said packet using said flow entry.
Claim 19
Dependent Claim
21 words
The computer-readable medium of claim 15 , wherein said first lookup or said second lookup is performed in a Patricia tree.
Claim 20
Dependent Claim
20 words
The computer-readable medium of claim 15 , wherein said first lookup or said second lookup utilizes a content addressable memory.
Claim 21
Dependent Claim
18 words
The computer-readable medium of claim 10 , wherein said content addressable memory further-comprises a ternary content addressable memory.
Claim 22
Dependent Claim
20 words
The computer-readable medium of claim 15 , wherein said direct access, said first lookup, and said second lookup are pipelined.
Claim 23
Dependent Claim
35 words
The computer-readable medium of claim 15 , wherein for packets arriving at a plurality of ports, at least said selecting, said performing said first lookup, and said performing said second lookup are time division multiplexed.
Claim 24
Dependent Claim
37 words
The computer-readable medium of claim 15 , further comprising: validating said sFlowRTP prior to performing said first lookup; validating said cFlowRTP prior to performing said second lookup; and validating said flow entry prior to performing said switching.
Claim 25
Dependent Claim
115 words
A computer data signal embodied in a carrier wave, comprising computer instructions for: parsing a packet header to obtain a plurality of data fields; selecting at least one of said plurality of data fields as a protocol identifier and using said protocol identifier to directly access a Server Flow Table start pointer (sFlowRTP); performing a first lookup using said sFlowRTP and using one or more of said data fields as a first key to determine a Client Flow Table start pointer (cFlowRTP); performing a second lookup using said cFlowRTP and using one or more of said data fields as a second key to obtain a flow entry; and switching said packet using said flow entry.
Claim 26
Dependent Claim
115 words
A computer data signal embodied in a carrier wave, comprising computer instructions for: parsing a packet header to obtain a plurality of data fields; selecting at least one of said plurality of data fields as a protocol identifier and using said protocol identifier to directly access a Server Flow Table start pointer (sFlowRTP); performing a first lookup using said sFlowRTP and using one or more of said data fields as a first key to determine a Client Flow Table start pointer (cFlowRTP); performing a second lookup using said cFlowRTP and using one or more of said data fields as a second key to obtain a flow entry; and switching said packet using said flow entry.
Claim 27
Dependent Claim
22 words
The computer data signal of claim 22 , wherein said first lookup or said second lookup is performed in a Patricia tree.
Claim 28
Dependent Claim
21 words
The computer data signal of claim 22 , wherein said first lookup or said second lookup utilizes a content addressable memory.
Claim 29
Dependent Claim
20 words
The computer data signal of claim 24 , wherein said content addressable memory further comprises a ternary content addressable memory.
Claim 30
Dependent Claim
21 words
The computer data signal of claim 22 , wherein said direct access, said first lookup, and said second lookup are pipelined.
Claim 31
Dependent Claim
36 words
The computer data signal of claim 22 , wherein for packets arriving at a plurality of ports, at least said selecting, said performing said first lookup, and said performing said second lookup are time division multiplexed.
Claim 32
Dependent Claim
38 words
The computer data signal of claim 22 , further comprising: validating said sFlowRTP prior to performing said first lookup; validating said cFlowRTP prior to performing said second lookup; and validating said flow entry prior to performing said switching.
Claim 33
Dependent Claim
117 words
A computer switching system comprising: means for parsing a packet header to obtain a plurality of data fields; means for selecting at least one of said plurality of data fields as a protocol identifier and using said protocol identifier to directly accessing a Server Flow Table start pointer (sFlowRTP); means for performing a first lookup using said sFlowRTP and using one or more of said data fields as a first key to determine a Client Flow Table start pointer (cFlowRTP); means for performing a second lookup using said cFlowRTP and using one or more of said data fields as a second key to obtain a flow entry; and means for switching said packet using said flow entry.
Claim 34
Dependent Claim
117 words
A computer switching system comprising: means for parsing a packet header to obtain a plurality of data fields; means for selecting at least one of said plurality of data fields as a protocol identifier and using said protocol identifier to directly accessing a Server Flow Table start pointer (sFlowRTP); means for performing a first lookup using said sFlowRTP and using one or more of said data fields as a first key to determine a Client Flow Table start pointer (cFlowRTP); means for performing a second lookup using said cFlowRTP and using one or more of said data fields as a second key to obtain a flow entry; and means for switching said packet using said flow entry.
Claim 35
Dependent Claim
22 words
The method of claim 29 , wherein said means for performing said first lookup or said second lookup comprise a Patricia tree.
Claim 36
Dependent Claim
23 words
The method of claim 29 , wherein said means for performing said first lookup or said second lookup comprise a content addressable memory.
Claim 37
Dependent Claim
26 words
The method of claim 29 , wherein said means for directly accessing and said means for performing said first lookup and said second lookup are pipelined.
Claim 38
Dependent Claim
40 words
The method of claim 29 , wherein for packets arriving at a plurality of ports, at least said means for selecting, said means for performing said first lookup, and said means for performing said second lookup are time division multiplexed.
Claim 39
Dependent Claim
42 words
The method of claim 29 , further comprising: means for validating said sFlowRTP prior to performing said fist lookup; means for validating said cFlowRTP prior to performing said second lookup; and means for validating said flow entry prior to performing said switching.
Claim 40
Dependent Claim
96 words
A lookup method for use in a switch, comprising the steps of: parsing a packet header to obtain a plurality of data fields; selecting at least one of said plurality of data fields as a protocol identifier; performing a server flow lookup using said protocol identifier and one or more of said data fields to determine said Client Flow Table start pointer (cFlowRTP); performing a second lookup using said cFlowRTP and using one or more of said data fields as a second key to obtain a flow entry; and switching said packet using said flow entry.
Claim 41
Dependent Claim
96 words
A lookup method for use in a switch, comprising the steps of: parsing a packet header to obtain a plurality of data fields; selecting at least one of said plurality of data fields as a protocol identifier; performing a server flow lookup using said protocol identifier and one or more of said data fields to determine said Client Flow Table start pointer (cFlowRTP); performing a second lookup using said cFlowRTP and using one or more of said data fields as a second key to obtain a flow entry; and switching said packet using said flow entry.
References Cited (Backward Citations)
US3648254A
Cited
US4296475A
Cited
US4791606A
Cited
US5088032A
Cited
US4996666A
Cited
US5440715A
Cited
US5481540A
Cited
US5319763A
Cited
US5383146A
Cited
US5898689A
Cited
US6000008A
Cited
US5450351A
Cited
US6047369A
Cited
US5515370A
Cited
US6041389A
Cited
US6091725A
Cited
US5740171A
Cited
US6243667B1
Cited
US5978885A
Cited
US6069573A
Cited
US5842040A
Cited
US5841874A
Cited
US5930359A
Cited
US5956336A
Cited
US5920886A
Cited
US6307855B1
Cited
US6181698B1
Cited
US6097724A
Cited
US6295576B1
Cited
US6199140B1
Cited
US6061368A
Cited
US6236658B1
Cited
US6148364A
Cited
US6141738A
Cited
US6081440A
Cited
US6237061B1
Cited
US6480489B1
Cited
US6389468B1
Cited
US6453360B1
Cited
US6483804B1
Cited
US6650640B1
Cited
US6137707A
Cited
US6175513B1
Cited
US6154384A
Cited
US6134135A
Cited
US6240003B1
Cited
US6246601B1
Cited
US6781990B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2008-02-29 | 2008-08-30 | 2009-03-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2012-02-29 | 2012-08-30 | 2013-03-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2016-02-29 | 2016-08-30 | 2017-03-01 | $7700.00 | Window Closed / Lapsed |