DETECTING AND HANDLING ELEPHANT FLOWS

• US 20150163144A1
• Filed: 03/31/2014
• Published: 06/11/2015
• 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
• Granted Patent: US 10,193,771 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 storing a program that 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; and

when an elephant flow is detected, generating different header values for packets in the detected elephant flow,

wherein the different header values are used to break the elephant flow into several different mouse flows and send each of several of the packets along different paths.

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 each different header value is a port number in an outer header of the packet, wherein the different 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 program further comprises a set of instructions for performing a traceroute operation to identify a network map, and choosing the different paths based on 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 a identifier to identify the detected elephant flow.

8. A host machine comprising:

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 statics is over a threshold value, and

categorizing the data flow as an elephant flow if the statistics is over the threshold value.

9. The host machine of claim 8, wherein the edge forwarding elements updates the statistic associated with the data flow by monitoring a set of packets sent from the VM or 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, wherein monitoring comprises comprising updating the statistic of the flow entry each time the flow entry is used to forward a particular packet.

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

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

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

14. The method of claim 8, wherein the information includes at least one of tunnel information, ingress port, source transport layer protocol port number, destination transport layer port number, Ethernet type, source Ethernet address, destination Ethernet address, source IP address, and 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;

identifying a set of packets in the elephant data flow;

marking each packet with a marking to differentiate the packet from each other packet in another different data flow; and

forwarding the packet to a forwarding element,

wherein the forwarding element process each marked packet different from each other packet that is not marked with the marking in order to reduce any delays caused by the elephant data flow in processing each other packet in the other data flow.

16. The method of claim 15, wherein marking each packet comprises setting at least header value in the packet'"'"'s header to indicate that the packet belongs to the elephant flow.

17. The method of claim 16, wherein the value is a (Differentiated Services Code Point) DSCP value in the packet'"'"'s header.

18. The method of claim 15, wherein the method is performed by an edge forwarding element, and the forwarding element that receives each marked packet 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 in hardware forwarding.