L4 lookup implementation using efficient CAM organization
First Claim
1. 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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
35 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. 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. - View Dependent Claims (9, 10, 11, 12, 13, 14, 18)
-
-
15. 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. - View Dependent Claims (16, 17, 19, 20, 21)
-
-
22. 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. - View Dependent Claims (23, 24, 25, 26, 27, 28)
-
-
29. 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. - View Dependent Claims (30, 31, 32, 33, 34)
-
-
35. 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.
-
Specification