Detecting and handling elephant flows

• US 10,193,771 B2
• Filed: 03/31/2014
• Issued: 01/29/2019
• Est. Priority Date: 12/09/2013
• Status: Active Grant

• Current Assignee: Nicira Incorporated (Broadcom, Inc.)
• Original Assignee: Nicira Incorporated (Broadcom, Inc.)
• Inventors: Koponen, Teemu, Pettit, Justin, Casado, Martin, Davie, Bruce, Lambeth, W. Andrew
• Primary Examiner(s): Jaroenchonwanit, Bunjob
• Application Number:
  US14/231,647
• Publication Number:
  US 20150163144A1
• Time in Patent Office: 1,765 Days
• Field of Search: None
• CPC Class Codes: H04L 43/026 using flow identification
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 49/252 Store and forward routing
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/3018 Input queuing
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46

Abstract

Some embodiments provide a forwarding element that detects and handles elephant flows. In detecting, the forwarding element of some embodiments monitors statistics or measurements relating to a data flow. In handling, the forwarding element marks each packet associated with a detected elephant flow in some manner to differentiate it from a packet associated with a mouse flow. Alternatively, the forwarding element of break elephant flows into a number mouse flow by facilitating in sending packets associated with the detected elephant flow along different paths.

Claims

1. A non-transitory machine readable medium that stores a program which when executed by at least one processing unit implements a forwarding element, the program comprising sets of instructions for:

monitoring data flows associated with a network host to detect an elephant flow for which the forwarding element processes a plurality of packets, wherein the forwarding element encapsulates the packets of the elephant flow with an outer header; and

for at least two packets of the elephant flow, differentiating the two packets by (i) encapsulating a first packet of the elephant flow using a first header field value for a particular header field of the outer header and (ii) encapsulating a second packet of the elephant flow using a second header field value for the particular header field of the outer header,

wherein the different header field values for the particular header field break the elephant flow into at least two different mouse flows such that subsequent forwarding elements, to which the packets are sent from the forwarding element, send the packets of the detected elephant flow along different paths to reach a same destination.

2. The non-transitory machine readable medium of claim 1, wherein the program further comprises a set of instructions for forwarding the packets in the elephant flow to a multipathing hardware, wherein the header field is a source port field and the first and second header values are different first and second port numbers, wherein the first and second port numbers are translated by the multipathing hardware to send the packets along different paths.

3. The non-transitory machine readable medium of claim 1, wherein the different paths are equal-cost multi-path routing (ECMP) legs.

4. The non-transitory machine readable medium of claim 1, wherein the set of instructions for differentiating the two packets by encapsulating a first packet using a first header value and a second packet using a second header value comprises sets of instructions for:

performing a traceroute operation to identify a network map; and

identifying the first and second header values based on the network map, wherein the first and second header values are associated with different paths of the network map.

5. The non-transitory machine readable medium of claim 4, wherein the traceroute operation is a Paris traceroute operation.

6. The non-transitory machine readable medium of claim 1, wherein the program further comprises a set of instructions for marking each packet in the detected elephant flow with a sequence number to deliver the packet in the order that the packet was received.

7. The non-transitory machine readable medium of claim 6, wherein the program further comprises a set of instructions for marking each packet with an identifier to identify the detected elephant flow.

8. A host machine comprising:

a set of processing units; and

a set of non-transitory machine readable media that store, for execution by the set of processing units;

at least one virtual machine (VM); and

an edge forwarding element for monitoring data flows associated with the VM to detect elephant flows, wherein the monitoring comprises;

tracking a data flow by maintaining a statistic relating to the data flow;

determining whether the statistic is over a threshold value;

categorizing the data flow as an elephant flow when the statistic is over the threshold value

generating a first set of header values for a first encapsulation header to append to a first set of packets in the elephant flow; and

generating a second, different set of header values for a second encapsulation header to append to a second set of packets in the elephant flow, wherein the different header values of the encapsulation headers break the elephant flow into a first mouse flow and a second mouse flow such that subsequent forwarding elements send the first and second sets of packets along different paths.

9. The host machine of claim 8, wherein the edge forwarding element updates the statistic relating to the data flow by monitoring at least one of (i) a set of packets sent from the VM and (ii) a set of packets sent to the VM.

10. The host machine of claim 8, wherein a flow entry in a flow table is used to process the packets in the data flow and the statistic is a statistic of the flow entry, wherein the monitoring further comprises updating the statistic of the flow entry each time the flow entry is used to forward a packet.

11. The host machine of claim 8, wherein the statistic is a byte count, wherein the determining comprises comparing the byte count with the threshold value to determine whether the byte count is over the threshold value.

12. The host machine of claim 8, wherein the statistic is a data transfer rate, wherein the determining comprises comparing the data transfer rate with the threshold value to determine whether the data transfer rate is over the threshold value.

13. The host machine of claim 8, wherein the categorizing comprises identifying information to report to the network controller regarding the elephant flow.

14. The host machine of claim 13, wherein the information includes at least one of tunnel information, an ingress port, a source transport layer protocol port number, a destination transport layer port number, an Ethernet type, a source Ethernet address, a destination Ethernet address, a source IP address, and a destination IP address.

15. A method of handling an elephant flow, the method comprising:

detecting that a data flow associated with a network host is an elephant flow, wherein the packets of the elephant flow are encapsulated with an outer header;

for at least two packets of the elephant flow, differentiating the two packets by (i) encapsulating a first packet of the elephant flow using a first header field value for a particular header field of the outer header and (ii) encapsulating a second packet of the elephant flow using a second header field value for the particular header field of the outer header, wherein the different header field values for the particular header field break the elephant flow into at least two different mouse flows; and

forwarding the packets of the detected elephant flow to a forwarding element, wherein the forwarding element sends the packets along different paths, based on the first and second header values for the header field, to reach a same destination.

16. The method of claim 15 further comprising marking each packet of the mouse flows with an indicator that associates the packet with the elephant flow, wherein the indicator is a third header field value in a second header field of the outer header that indicates that the packet belongs to the elephant flow.

17. The method of claim 16, wherein the third header field value is a DSCP (Differentiated Service Code Point) value in the second header field of the outer header.

18. The method of claim 15, wherein the method is performed by an edge forwarding element, and the forwarding element to which each packet is sent is a non-edge forwarding element.

19. The method of claim 18, wherein the edge forwarding element is a software forwarding element that operates on a computing device, and the non-edge forwarding element is a hardware forwarding element that has hardware designed to support hardware forwarding.

20. The method of claim 15, wherein the different paths are equal-cost multi-path routing (ECMP) legs.