Logical operation unit for packet processing

• US 6,658,002 B1
• Filed: 06/17/1999
• Issued: 12/02/2003
• Est. Priority Date: 06/30/1998
• Status: Expired due to Term

• Current Assignee: Cisco Systems, Inc.
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Bechtolsheim, Andreas V., Chen, Sun-Den, Ross, Mark A.
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): HOANG, THAI D
• Application Number:
  US09/335,800
• Time in Patent Office: 1,629 Days
• Field of Search: 370/232, 370/466, 370/392-395, 370/389, 370/401-402, 370/403, 709/5, 709/11, 709/224, 709/220, 709/245, 709/246-248
• US Class Current: 370/392
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/31 by tagging of packets, e.g. using discard eligibility [DE] bits
• CPC Class Codes: H04L 63/101 Access control lists [ACL]

Abstract

An apparatus and method for performing logical operations on information in the communications protocol stack, such as the transport layer (L4) port numbers, characterizing a received packet or frame of data in a data communications device such as a router or switch. The results of the logical operations, along with other packet/frame-identifying data, are used to generate a more efficient lookup key. A content addressable memory (CAM) lookup is used to determine the action indicated by the rules defined by a rule-based routing or switching scheme, such as an access control list (ACL). The results of these logical operations extend the key space and thus provide a finer-grained match between the original, unextended input key and a rule action, thereby pointing to a rule action precisely tailored to packet processing. The rule can thus be applied with fewer CAM entries, providing the versatility improvement and CAM cost reduction necessary to keep up with the ever-increasing rule complexity requirements of advanced data communication and internetworking systems. An embodiment utilizing asymmetrical processing of packets, depending on whether the packet is inbound to the data communications device or outbound from it, is also disclosed. Furthermore, a ternary content-addressable memory (TCAM) implementation is disclosed. Use of a TCAM for ACL or other rule lookups further enhances the efficiency of rule processing by providing a masking capability for each TCAM entry which can be used to provide an additional level of flexibility for rule element checking.

Claims

1. An apparatus for expediting processing in a data communications device comprising:

an input interface circuit that reads a data packet comprising one or more readable fields;

a logic circuit connected to said input interface circuit that performs at least one logical function of at least one of said readable fields to create a result vector; and

a lookup interface circuit connected to said input interface circuit and said logic circuit that extracts from said result vector an auxiliary field and combines said auxiliary field with said readable fields into a lookup key;

wherein said lookup key is used to perform a content addressable memory lookup.

2. The apparatus according to claim 1 wherein said logical function comprises an input, a plurality of first values, a plurality of second values, a plurality of operators, and a result vector, wherein:

each of said first values has a corresponding operator and an optional corresponding second value stored as a set in said logic circuit;

said input is provided by said logic circuit and comprises at least one of said readable fields; and

said operator in said set is selected from the group consisting of greater than, less than, not equal to, and range;

said operator “

greater than”

having a positive result when said input is greater than said first value;

said operator “

less than”

having a positive result when said input is less than said first value;

said operator “

not equal to”

having a positive result when said input is not equal to said first value; and

said operator “

range”

having a positive result when said input is between said first value and said second value;

wherein a comparison is made substantially simultaneously of said input to said first value and optionally to said second value in each said set according to said corresponding operator; and

wherein the results of each said comparison together form a result vector.

3. The apparatus according to claim 1 wherein:

said logic circuit creates said result vector based at least in part on pre-defined logical functions.

4. The apparatus according to claim 1 wherein said content addressable memory lookup is performed using a ternary content addressable memory.

5. The apparatus according to claim 1 wherein said readable fields comprise a source port number and a destination port number.

6. The apparatus according to claim 1 wherein said data communications device further comprises:

a mapping circuit connected to said input interface circuit that reads an interface designation from said packet and maps said interface designation to a label;

wherein said lookup interface circuit extracts said auxiliary field using said label.

7. The apparatus according to claim 6 wherein:

said mapping circuit comprises a control signal output derived from said interface designation and connected to said logic circuit; and

said logic circuit creates said result vector based at least in part on said control signal.

8. The apparatus according to claim 6 wherein said processing of inbound packets differs from said processing of outbound packets.

9. The apparatus according to claim 8 further comprising:

an input interface circuit that reads one or more readable fields and an interface designator from an inbound data packet.

10. The apparatus according to claim 8 further comprising:

a lookup interface circuit that receives an interface designator from a requesting unit; and

retrieves one or more readable fields from a memory.

11. A method of expediting processing comprising the steps of:

reading one or more readable fields from a data packet;

performing at least one logical function of at least one of said readable fields to create a result vector;

extracting from said result vector an auxiliary field;

combining said auxiliary field with said readable fields to create a lookup key; and

accessing a content-addressable memory with said lookup key.

12. The method of claim 11 wherein said logical function comprises an input, a plurality of first values, a plurality of second values, a plurality of operators, and a result vector, wherein:

each of said first values has a corresponding operator and an optional corresponding second value stored as a set in a logic circuit;

said input is provided by said logic circuit and comprises at least one of said readable fields; and

said operator in said set is selected from the group consisting of greater than, less than, not equal to, and range;

said operator “

greater than”

having a positive result when said input is greater than said first value;

said operator “

less than”

having a positive result when said input is less than said first value;

said operator “

not equal to”

having a positive result when said input is not equal to said first value; and

said operator “

range”

having a positive result when said input is between said first value and said second value;

wherein a comparison is made substantially simultaneously of said input to said first value and optionally to said second value in each said set according to said corresponding operator; and

wherein the results of each said comparison together form a result vector.

13. The method of claim 11 wherein:

said logic circuit creates said result vector based at least in part on pre-defined logical functions.

14. The method of claim 11 wherein said content addressable memory is a ternary content addressable memory.

15. The method of claim 11 wherein said readable fields comprise a source port number and a destination port number.

16. The method of claim 11 further comprising:

reading an interface designation from said packet;

mapping said interface designation to a label; and

extracting said auxiliary field using said label.

17. The method of claim 16 wherein said mapping comprises deriving a control signal output from said interface designation and wherein said result vector is based at least in part on said control signal.

18. The method of claim 16 wherein said processing of inbound packets differs from said processing of outbound packets.

19. The method of claim 18 further comprising the steps of:

if processing an inbound packet,

reading one or more readable fields and an interface designator from said inbound data packet;

but if processing an outbound packet,

receiving an interface designator from a requesting unit; and

retrieving one or more readable fields from a memory.

20. A computer system for expediting processing comprising computer instructions for:

reading one or more readable fields from a data packet;

performing at least one logical function of at least one of said readable fields to create a result vector;

extracting from said result vector an auxiliary field;

combining said auxiliary field with said readable fields to create a lookup key; and

accessing a content-addressable memory with said lookup key.

21. The computer system of claim 20 wherein said logical function comprises an input, a plurality of first values, a plurality of second values, a plurality of operators, and a result vector, wherein:

each of said first values has a corresponding operator and an optional corresponding second value stored as a set in a logic circuit;

said input is provided by said logic circuit and comprises at least one of said readable fields; and

said operator in said set is selected from the group consisting of greater than, less than, not equal to, and range;

said operator “

greater than”

having a positive result when said input is greater than said first value;

said operator “

less than”

having a positive result when said input is less than said first value;

said operator “

not equal to”

having a positive result when said input is not equal to said first value; and

said operator “

range”

having a positive result when said input is between said first value and said second value;

wherein a comparison is made substantially simultaneously of said input to said first value and optionally to said second value in each said set according to said corresponding operator; and

wherein the results of each said comparison together form a result vector.

22. The computer system of claim 20 wherein:

said logic circuit creates said result vector based at least in part on pre-defined logical functions.

23. The computer system of claim 20 wherein said content addressable memory is a ternary content addressable memory.

24. The computer system of claim 20 wherein said readable fields comprise a source port number and a destination port number.

25. The method of claim 20 further comprising:

reading an interface designation from said packet;

mapping said interface designation to a label; and

extracting said auxiliary field using said label.

26. The method of claim 25 wherein said mapping comprises deriving a control signal output from said interface designation and wherein said result vector is based at least in part on said control signal.

27. The computer system of claim 25 wherein said processing of inbound packets differs from said processing of outbound packets.

28. The computer system of claim 27 further comprising the steps of:

if processing an inbound packet,

reading one or more readable fields and an interface designator from said inbound data packet;

but if processing an outbound packet,

receiving an interface designator from a requesting unit; and

retrieving one or more readable fields from a memory.

29. A computer-readable storage medium comprising computer instructions for:

reading one or more readable fields from a data packet;

performing at least one logical function of at least one of said readable fields to create a result vector;

extracting from said result vector an auxiliary field;

combining said auxiliary field with said readable fields to create a lookup key; and

accessing a content-addressable memory with said lookup key.

30. The computer-readable storage medium of claim 29 wherein said logical function comprises an input, a plurality of first values, a plurality of second values, a plurality of operators, and a result vector, wherein:

each of said first values has a corresponding operator and an optional corresponding second value stored as a set in a logic circuit;

said input is provided by said logic circuit and comprises at least one of said readable fields; and

said operator in said set is selected from the group consisting of greater than, less than, not equal to, and range;

said operator “

greater than”

having a positive result when said input is greater than said first value;

said operator “

less than”

having a positive result when said input is less than said first value;

said operator “

not equal to”

having a positive result when said input is not equal to said first value; and

said operator “

range”

having a positive result when said input is between said first value and said second value;

wherein a comparison is made substantially simultaneously of said input to said first value and optionally to said second value in each said set according to said corresponding operator; and

wherein the results of each said comparison together form a result vector.

31. The computer-readable storage medium of claim 29 wherein:

said logic circuit creates said result vector based at least in part on pre-defined logical functions.

32. The computer-readable storage medium of claim 29 wherein said content addressable memory is a ternary content addressable memory.

33. The computer-readable storage medium of claim 29 wherein said readable fields comprise a source port number and a destination port number.

34. The method of claim 29 further comprising:

reading an interface designation from said packet;

mapping said interface designation to a label; and

extracting said auxiliary field using said label.

35. The method of claim 34 wherein said mapping comprises deriving a control signal output from said interface designation and wherein said result vector is based at least in part on said control signal.

36. The computer-readable storage medium of claim 34 wherein said processing of inbound packets differs from said processing of outbound packets.

37. The computer-readable storage medium of claim 36 further comprising the steps of:

if processing an inbound packet,

reading one or more readable fields and an interface designator from said inbound data packet;

but if processing an outbound packet,

receiving an interface designator from a requesting unit; and

retrieving one or more readable fields from a memory.