L4 lookup implementation using efficient CAM organization

• US 6,862,281 B1
• Filed: 05/10/2001
• Issued: 03/01/2005
• Est. Priority Date: 05/10/2001
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Chandrasekaran, Varagur V.
• Primary Examiner(s): VINCENT, DAVID ROBERT
• Application Number:
  US09/854,013
• Time in Patent Office: 1,391 Days
• Field of Search: 370351- 4, 370/389, 370392- 3, 370400-403, 370/404, 370/469, 370/471, 370/474, 370/475, 711/216, 711/108
• US Class Current: 370/392
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 69/12 Protocol engines
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers
• CPC Class Codes: H04L 69/326 in the transport layer [OSI layer 4] H04L69/16 takes precedence

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.

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.

2. The method of claim 1, wherein said first lookup or said second lookup is performed in a Patricia tree.

3. The method of claim 1, wherein said first lookup or said second lookup utilizes a content addressable memory.

4. The method of claim 3, wherein said content addressable memory comprises a ternary content addressable memory.

5. The method of claim 1, wherein said direct access, said first lookup, and said second lookup are pipelined.

6. 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.

7. 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.

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.

9. The switching system of claim 8, wherein said first lookup or said second lookup is performed in a Patricia tree.

10. The switching system of claim 8, wherein said first lookup or said second lookup utilizes a content addressable memory.

11. The switching system of claim 10, wherein said content addressable memory comprises a ternary content addressable memory.

12. The switching system of claim 8, wherein said direct access, said first lookup, and said second lookup are pipelined.

13. 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.

14. 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.

18. The computer-readable medium of claim 10, wherein said content addressable memory further-comprises a ternary content addressable memory.

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.

16. The computer-readable medium of claim 15, wherein said first lookup or said second lookup is performed in a Patricia tree.

17. The computer-readable medium of claim 15, wherein said first lookup or said second lookup utilizes a content addressable memory.

19. The computer-readable medium of claim 15, wherein said direct access, said first lookup, and said second lookup are pipelined.

20. 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.

21. 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.

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.

23. The computer data signal of claim 22, wherein said first lookup or said second lookup is performed in a Patricia tree.

24. The computer data signal of claim 22, wherein said first lookup or said second lookup utilizes a content addressable memory.

25. The computer data signal of claim 24, wherein said content addressable memory further comprises a ternary content addressable memory.

26. The computer data signal of claim 22, wherein said direct access, said first lookup, and said second lookup are pipelined.

27. 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.

28. 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.

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.

30. The method of claim 29, wherein said means for performing said first lookup or said second lookup comprise a Patricia tree.

31. The method of claim 29, wherein said means for performing said first lookup or said second lookup comprise a content addressable memory.

32. 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.

33. 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.

34. 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.

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.