System and method for flow management in software-defined networks

• US 10,164,883 B2
• Filed: 09/01/2016
• Issued: 12/25/2018
• Est. Priority Date: 11/10/2011
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Inventors: Tavarekere Ananthapadmanabha, Kashyap, Agarwal, Vivek, Chinthalapati, Eswara S. P.
• Primary Examiner(s): Dalencourt, Yves
• Application Number:
  US15/254,879
• Publication Number:
  US 20170134281A1
• Time in Patent Office: 845 Days
• 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:

one or more ports capable of processing data flows based on a flow rule;

flow circuitry configured to allocate a flow identifier to a generic flow definition, which indicates a flow that is not specific to any input port of the switch;

lookup circuitry configured to;

store, in a first data structure, one or more port-specific flow rules generated based on the generic flow definition, wherein each port-specific flow rule corresponds to a port of the one or more ports; and

store the flow identifier in a respective entry of a second data structure, wherein each entry of the second data structure corresponds to a port of the one or more ports; and

forwarding circuitry configured to determine an egress port for a packet based on one of the one or more port-specific flow rules.

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

3. The switch of claim 1, wherein the lookup circuitry is further configured to store, in a third data structure, the generic flow definition with 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-capable switch.

5. The switch of claim 1, wherein the second data structure is a per-port linked list, wherein a respective entry of the second data structure is associated with a corresponding port of the one or more ports;

wherein a respective element in the entry indicates a flow identifier for a flow definition applicable to the corresponding port; and

wherein the elements in the entry are sorted in the order of priority of the corresponding flow definitions.

6. The switch of claim 1, wherein the lookup circuitry is further configured to store, in a fourth data structure, one or more flow definitions with corresponding flow identifier(s).

7. The switch of claim 6, wherein a respective entry in the fourth data structure stores a flow definition;

wherein the switch further comprises a hash circuitry configured to compute a hash value based on the flow identifier for the flow definition; and

wherein the hash value is used as an index to the entry of the fourth data structure.

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

and

wherein while updating the flow definition, the updating circuitry 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 for 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 first data structure, thereby preserving the priority order of the flow rules for the port after the update.

9. A method, comprising:

allocating a flow identifier to a generic flow definition, which indicates a flow that is not specific to any input port of a switch, wherein the switch comprises one or more ports capable of processing data flows based on a flow rule;

storing, in a first data structure one or more port-specific flow rules generated based on the generic flow definition, wherein each port-specific flow rule corresponds to a port of the one or more ports;

storing the flow identifier in a respective entry of a second data structure, wherein each entry of the second data structure corresponds to a port of the one or more ports; and

determining an egress port for a packet based on one of the one or more port-specific flow rules.

10. The method of claim 9, wherein the first data structure is stored in a CAM.

11. The method of claim 9, further comprising storing, in a third data structure, the generic flow definition with 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-capable switch.

13. The method of claim 9, wherein the second data structure is a per-port linked list, wherein a respective entry of the second data structure is associated with a corresponding port of the one or more ports;

wherein a respective element in the entry indicates a flow identifier for a flow definition applicable to the corresponding port; and

wherein the elements in the entry are sorted in the order of priority of the corresponding flow definitions.

14. The method of claim 9, further comprising storing, in a fourth data structure, one or more flow definitions with corresponding flow identifier(s).

15. The method of claim 14, wherein a respective entry in the fourth data structure stores a flow definition;

wherein the method further comprises computing a hash value based on the flow identifier for the flow definition; and

wherein the hash value is used as an index to the entry of the fourth data structure.

16. The method of claim 14, 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 for 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 first data structure, thereby preserving the priority order of the flow rules for the port after the update.

17. A computing system, comprising:

one or more ports capable of processing data flows based on a flow rule;

a processor; and

a non-transitory computer-readable storage medium storing instructions which when executed by the processor cause the processor to perform a method, the method comprising;

allocating a flow identifier to a generic flow definition, which indicates a flow that is not specific to any input port of the switch;

storing, in a first data structure, one or more port-specific flow rules generated based on the generic flow definition, wherein each port-specific flow rule corresponds to a port of the one or more ports;

storing the flow identifier in a respective entry of a second data structure, wherein each entry of the second data structure corresponds to a port of the one or more ports; and

determining an egress port for a packet based on one of the one or more port-specific flow rules.

18. The computer system of claim 17, wherein the method further comprises storing, in a third data structure, the generic flow definition with a flag indicating that the generic flow definition is not specific to any input port.

19. The computer system of claim 17, wherein the second data structure is a per-port linked list, wherein a respective entry of the second data structure is associated with a corresponding port of the one or more ports;

wherein a respective element in the entry indicates a flow identifier for a flow definition applicable to the corresponding port; and

wherein the elements in the entry are sorted in the order of priority of the corresponding flow definitions.

20. The computer system of claim 19, wherein the method further comprises:

traversing a per-port linked list for a port associated with the flow definition to be updated to locate a flow identifier for 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 first data structure, thereby preserving the priority order of the flow rules for the port after the update.