Methods and apparatus for defining flow types and instances thereof such as for identifying packets corresponding to instances of the flow types

• US 7,496,035 B1
• Filed: 01/31/2003
• Issued: 02/24/2009
• Est. Priority Date: 01/31/2003
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Sadasivan, Ganesh, Marimuthu, Peram, Srinivas, Rengabashyam, Eatherton, William N., Ma, Xiaoxue
• Primary Examiner(s): Pham; Chi H.
• Assistant Examiner(s): MEW, KEVIN D
• Application Number:
  US10/355,831
• Time in Patent Office: 2,216 Days
• Field of Search: 370/230, 370/230.1, 370/231, 370/232, 370/233, 370/234, 370/235, 707/6, 707/102, 709/238
• US Class Current: 370/235
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers

Abstract

Methods and apparatus are disclosed for defining flow types and instances thereof such as for identifying packets corresponding to instances of the flow types. A flow type is defined and includes a set of properties including at least one of the possible properties selectable when defining a flow type. An instance of the flow type is defined and a set of corresponding associative memory entries is generated. A lookup word generator of a packet processing engine is typically notified of the use of the flow type, and one or more lookup words are generated typically by extracting fields from a received packet and/or from other sources. Based on a result of lookup operations on the set of associative memories entries using the generated one or more lookup words, the received packet can be identified as whether it matches or does not match the instance of the flow type.

Claims

1. A tangible computer-readable medium embodying computer-executable instructions for performing steps, when executed by one or more processors, for defining and using flow types and instances thereof, said steps comprising:

defining a first flow type including a first set of properties, the first set of properties including at least one property of a plurality of possible properties selectable when defining a flow type, said defining the first flow type including generating an entry in a flow type data structure maintained in a computer storage device for the first flow type, said entry identifiable based on an identifier of the first flow type and said entry including an identification of each property in the first set of properties, with each said property defining a field for containing a corresponding type of value to be matched in an instance of the first flow type;

defining a first instance of the first flow type based on the entry in the flow type data structure corresponding to the first flow type, said defining the first instance including retrieving the first flow type from the computer storage device in order to identify the first set of properties, and associating an attribute in the first instance with each property in the first set of properties;

generating one or more first associative memory entries, based on said defined first instance of the first flow type, including a value for each said attribute in the first instance; and

programming one or more associative memories with said generated first associative memory entries;

wherein the computer storage device is distinct from said one or more associative memories.

2. The computer-readable medium of claim 1, wherein said defining the first instance includes identifying attributes for each of the properties of the first set of properties.

3. The computer-readable medium of claim 1, wherein said steps comprise indicating the first flow type to a lookup word generator;

wherein the lookup word generator is configured to generate one or more lookup words according to the first flow type in response to said indication of the first flow type.

4. The computer-readable medium of claim 1, wherein said defining the first flow type includes receiving configuration information identifying said at least one property of the plurality of possible properties.

5. The computer-readable medium of claim 1, wherein the configuration information is input via a command line interface.

6. The computer-readable medium of claim 1, wherein said steps further comprise:

defining a second instance of the first flow type based on the entry in the flow type data structure corresponding to the first flow type, said defining the first instance including retrieving the first flow type from the computer storage device in order to identify the first set of properties, and associating an attribute in the first instance with each property in the first set of properties;

generating one or more second associative memory entries, based on said defined second instance of the first flow type, including a value for each said attribute in the first instance; and

programming said one or more associative memories with said generated second associative memory entries.

7. The computer-readable medium of claim 6, wherein the first instance is associated with a first application and the second instance is associated with a second application.

8. The computer-readable medium of claim 1, wherein the first instance is associated with two or more different applications.

9. The computer-readable medium of claim 1, wherein said defining the first instance includes identifying a data structure specification of the first flow type.

10. The computer-readable medium of claim 1, wherein said steps comprise:

defining a second flow type including a second set of properties, the second set of properties including at least one selected property of the plurality of possible properties selectable when defining a flow type, said defining the second flow type including generating an entry in the flow type data structure for the second flow type, said entry identifiable based on an identifier of the second flow type and said entry including an identification of each property in the second set of properties;

defining a second instance of the second flow type based on the entry in the flow type data structure corresponding to the second flow type, said defining the second instance including retrieving the second flow type from the computer storage device;

generating one or more second associative memory entries based on said defined second instance of the second flow type; and

programming said one or more associative memories with said generated second associative memory entries;

wherein said second instance includes an instantiated matching value for each of the second set of properties.

11. The computer-readable medium of claim 1, wherein the first set of properties consists of less than all of the plurality of possible properties selectable when defining the flow type.

12. An apparatus for defining and using flow types and instances thereof, the apparatus comprising:

means for defining a first flow type including a first set of properties, the first set of properties including at least one property of a plurality of possible properties selectable when defining a flow type, said defining the first flow type including generating an entry in a flow type data structure maintained in a computer storage device for the first flow type, said entry identifiable based on an identifier of the first flow type and said entry including an identification of each property in the first set of properties, with each said property defining a field for containing a corresponding type of value to be matched in an instance of the first flow type;

means for defining a first instance of the first flow type based on the entry in the flow type data structure corresponding to the first flow type, said defining the first instance including retrieving the first flow type from the computer storage device in order to identify the first set of properties, and associating an attribute in the first instance with each property in the first set of properties;

means for generating one or more first associative memory entries, based on said defined first instance of the first flow type, including a value for each said attribute in the first instance; and

means for programming one or more associative memories with said generated first associative memory entries;

wherein the computer storage device is distinct from said one or more associative memories.

13. The apparatus of claim 12, wherein said means for defining the first instance includes means for identifying attributes for each of the properties of the first set of properties.

14. The apparatus of claim 12, comprising means for generating lookup words corresponding to the first flow type.

15. The apparatus of claim 12, wherein said means for defining the first flow type includes means for receiving configuration information identifying said at least one property of the plurality of possible properties.

16. The apparatus of claim 15, wherein the configuration information is input via a command line interface.

17. The apparatus of claim 12, wherein the first instance is associated with two or more different applications.

18. The apparatus of claim 12, wherein the first set of properties consists of less than all of the plurality of possible properties selectable when defining the flow type.

19. A computer-implemented method for performing steps for defining and using flow types and instances thereof, the method comprising:

receiving configuration information identifying at least one property of a plurality of possible properties selectable when defining a flow type;

defining a first flow type including a first set of properties, the first set of properties including said at least one property, said defining the first flow type including generating an entry in a flow type data structure maintained in a computer storage device for the first flow type, said entry identifiable based on an identifier of the first flow type and said entry including an identification of each property in the first set of properties, with each said property defining a field for containing a corresponding type of value to be matched in an instance of the first flow type;

defining a first instance of the first flow type based on the entry in the flow type data structure corresponding to the first flow type, said defining the first instance including retrieving the first flow type from the computer storage device in order to identify the first set of properties, and associating an attribute in the first instance with each property in the first set of properties;

generating one or more first associative memory entries, based on said defined first instance of the first flow type, including a value for each said attribute in the first instance; and

programming one or more associative memories with said generated first associative memory entries;

wherein the computer storage device is distinct from said one or more associative memories.

20. The method of claim 19, wherein said defining the first instance includes identifying attributes for each of the properties of the first set of properties.

21. The method of claim 19, further comprising indicating the first flow type to a lookup word generator.

22. The method of claim 19, further comprising:

generating one or more lookup words corresponding to the first flow type; and

communicating said one or more lookup words to said one or more associative memories.

23. The method of claim 19, further comprising:

defining a second instance of the first flow type based on the entry in the flow type data structure corresponding to the first flow type, said defining the first instance including retrieving the first flow type from the computer storage device in order to identify the first set of properties, and associating an attribute in the first instance with each property in the first set of properties;

generating one or more second associative memory entries, based on said defined second instance of the first flow type, including a value for each said attribute in the first instance; and

programming said one or more associative memories with said generated second associative memory entries.

24. The method of claim 23, wherein the first instance is associated with a first application and the second instance is associated with a second application.

25. The method of claim 19, wherein the first instance is associated with two or more different applications.

26. The method of claim 19, further comprising:

defining a second flow type including a second set of properties, the second set of properties including at least one selected property of the plurality of possible properties selectable when defining a flow type, said defining the second flow type including generating an entry in the flow type data structure for the second flow type, said entry identifiable based on an identifier of the second flow type and said entry including an identification of each property in the second set of properties;

defining a second instance of the second flow type based on the entry in the flow type data structure corresponding to the second flow type, said defining the second instance including retrieving the second flow type from the computer storage device;

generating one or more second associative memory entries based on said defined second instance of the second flow type; and

programming said one or more associative memories with said generated second associative memory entries;

wherein said second instance includes an instantiated matching value for each of the second set of properties.

27. The method of claim 19, wherein the first set of properties consists of less than all of the plurality of possible properties selectable when defining the flow type.

28. An apparatus comprising one or more processors and memory, wherein the memory stores one or more instructions that, when executed by said one or more processors, perform operations for defining and using flow types and instances thereof, said operations comprising:

defining a first flow type including a first set of properties, the first set of properties including at least one property of a plurality of possible properties selectable when defining a flow type, said defining the first flow type including generating an entry in a flow type data structure maintained in a computer storage device for the first flow type, said entry identifiable based on an identifier of the first flow type and said entry including an identification of each property in the first set of properties, with each said property defining a field for containing a corresponding type of value to be matched in an instance of the first flow type;

defining a first instance of the first flow type based on the entry in the flow type data structure corresponding to the first flow type, said defining the first instance including retrieving the first flow type from the computer storage device in order to identify the first set of properties, and associating an attribute in the first instance with each property in the first set of properties;

generating one or more first associative memory entries, based on said defined first instance of the first flow type, including a value for each said attribute in the first instance; and

programming one or more associative memories with said generated first associative memory entries;

wherein the computer storage device is distinct from said one or more associative memories.

29. The apparatus of claim 28, wherein said operations comprise indicating the first flow type to a lookup word generator;

wherein the lookup word generator is configured to generate one or more lookup words according to the first flow type in response to said indication of the first flow type.

30. The apparatus of claim 28, wherein said operations comprise:

defining a second flow type including a second set of properties, the second set of properties including at least one selected property of the plurality of possible properties selectable when defining a flow type, said defining the second flow type including generating an entry in the flow type data structure for the second flow type, said entry identifiable based on an identifier of the second flow type and said entry including an identification of each property in the second set of properties;

defining a second instance of the second flow type based on the entry in the flow type data structure corresponding to the second flow type, said defining the second instance including retrieving the second flow type from the computer storage device;

generating one or more second associative memory entries based on said defined second instance of the second flow type; and

programming said one or more associative memories with said generated second associative memory entries;

wherein said second instance includes an instantiated matching value for each of the second set of properties.

31. The apparatus of claim 28, comprising a packet processing engine configured to processes packets based on lookup operations performed on said programmed one or more associative memories.