System and method for flow management in software-defined networks

• US 9,450,870 B2
• Filed: 11/05/2012
• Issued: 09/20/2016
• Est. Priority Date: 11/10/2011
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Brocade Communications Systems, Inc. (Broadcom, Inc.)
• Inventors: Ananthapadmanabha, Kashyap Tavarekere, Agarwal, Vivek, Chinthalapati, Eswara S. P.
• Primary Examiner(s): Dalencourt, Yves
• Application Number:
  US13/669,313
• Publication Number:
  US 20130124707A1
• Time in Patent Office: 1,415 Days
• Field of Search: 709/223
• US Class Current: 1/1
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/2483 involving identification of individual flows
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 61/103 across network layers, e.g. resolution of network layer into physical layer addresses or address resolution protocol [ARP]

Abstract

A system facilitates flow definition management in a switch. During operation, the system identifies a generic flow definition which specifies a flow that is not specific to any input port of a switch. The system further stores in a flow lookup data structure one or more port-specific flow rules based on the generic flow definition, wherein each port-specific flow rule corresponds to a respective port capable of processing data flows.

Claims

1. A switch, comprising:

processing circuitry;

one or more switch ports;

a flow definition management apparatus configured to;

identify a generic flow definition which specifies a flow that is not specific to any input switch port of the switch; and

convert the generic flow definition to one or more input-port-specific flow rules, wherein an input-port-specific flow rule corresponds to one of the switch ports of the switch; and

a flow lookup data structure configured to store the one or more input-port-specific flow rules in association with the corresponding switch port, wherein the corresponding switch port supports processing a dataflow based on a flow rule.

2. The switch of claim 1, further comprising a content addressable memory (CAM), wherein the flow lookup data structure is stored in the CAM.

3. The switch of claim 1, wherein the generic flow definition comprises a flag indicating that the generic flow definition is not specific to any input port.

4. The switch of claim 1, wherein the switch is an OpenFlow supported switch.

5. The switch of claim 1, further comprising a per-port linked list for a respective port with support for processing a data flow based on a flow rule;

wherein a node in the linked list indicates a flow identifier for a flow definition applicable to the port; and

wherein the nodes in the linked list are sorted in the order of priority of the corresponding flow definitions.

6. The switch of claim 1, further comprising a flow table configured to store in an entry a flow definition in association with a flow identifier of the flow definition.

7. The switch of claim 6,

wherein the switch further comprises a hash computation apparatus configured to compute a hash value based on the flow identifier of the flow definition;

and

wherein the hash value is used as an index to the entry.

8. The switch of claim 1, further comprising a flow definition updating apparatus configured to update a flow definition;

and

wherein while updating the flow definition, the flow definition updating apparatus is configured to;

traverse a per-port linked list for a port associated with the flow definition to be updated to locate a flow identifier of the flow definition to be updated;

determine one or more flow identifiers whose priority is lower than the located flow identifier; and

rewrite the flow rules associated with the determined flow identifiers in the flow lookup data structure, thereby preserving the priority order of the flow rules for the port after the update.

9. A method, comprising:

identifying, by a switch, a generic flow definition which specifies a flow that is not specific to any input switch port of the switch, wherein the switch comprises processing circuitry and one or more switch ports; and

converting the generic flow definition to one or more input-port-specific flow rules, wherein an input-port-specific flow rule corresponds to one of the switch ports of the switch; and

storing in a flow lookup data structure the one or more input-port-specific flow rules in association with the corresponding switch port, wherein the corresponding switch port supports processing a data flow based on a flow rule.

10. The method of claim 9, wherein the flow lookup data structure is stored in a content addressable memory (CAM).

11. The method of claim 9, wherein the generic flow definition comprises a flag indicating that the generic flow definition is not specific to any input port.

12. The method of claim 9, wherein the switch is an OpenFlow supported switch.

13. The method of claim 9, further comprising maintaining a per-port linked list for a respective port with support for processing a dataflow based on a flow rule;

wherein a node in the linked list indicates a flow identifier for a flow definition applicable to the port; and

wherein the nodes in the linked list are sorted in the order of priority of the corresponding flow definitions.

14. The method of claim 9, further comprising store in an entry in a flow table a flow definition in association with a flow identifier of the flow definition.

15. The method of claim 14,

further comprising computing a hash value based on the flow identifier of the flow definition;

and

wherein the hash value is used as an index to the entry.

16. The method of claim 9, further comprising updating a flow definition by:

traversing a per-port linked list for a port associated with the flow definition to be updated to locate a flow identifier of the flow definition to be updated;

determining one or more flow identifiers whose priority is lower than the located flow identifier; and

rewriting the flow rules associated with the determined flow identifiers in the flow lookup data structure, thereby preserving the priority order of the flow rules for the port after the update.

17. A switch means, comprising:

processing circuitry means;

one or more switch port means;

a flow definition management means for;

identifying a generic flow definition which specifies a flow that is not specific to any input port of the switch means; and

converting the generic flow definition to one or more input-port-specific flow rules, wherein an input-port-specific flow rule corresponds to one of the switch port means of the switch means; and

a flow lookup means for storing the one or more input-port-specific flow rules in association with the corresponding port, wherein the corresponding switch port means supports processing a data flow based on a flow rule.

18. The switch means of claim 17, further comprising:

a per-port linked list means for storing flow identifiers of a respective port with support for processing data flows.

19. The switch means of claim 17, wherein the generic flow definition comprises a flag indicating that the generic flow definition is not specific to any input port.

20. The switch means of claim 17, further comprising a flow definition updating means for updating a flow definition.