Controlling flow rates of traffic among endpoints in a network

• US 10,348,600 B2
• Filed: 02/08/2017
• Issued: 07/09/2019
• Est. Priority Date: 02/09/2016
• Status: Expired due to Fees

• Current Assignee: Splunk Inc.
• Original Assignee: Flowtune, Inc.
• Inventors: Perry, Jonathan
• Primary Examiner(s): Moore, Ian N
• Assistant Examiner(s): Van Roie, Justin T
• Application Number:
  US15/427,393
• Publication Number:
  US 20170230298A1
• Time in Patent Office: 881 Days
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 43/0876 Network utilisation, e.g. volume of load or congestion level
• CPC Class Codes: H04L 43/0888 Throughput
• CPC Class Codes: H04L 43/12 Network monitoring probes
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 47/522 Dynamic queue service slot or variable bandwidth allocation
• CPC Class Codes: H04L 47/629 Ensuring fair share of resources, e.g. weighted fair queuing [WFQ]
• CPC Class Codes: H04L 47/78 Architectures of resource allocation

Abstract

Among other things, flow rates of traffic among endpoints in a network are controlled. Notifications are received about flowlets originating or received at the endpoints. Each of the flowlets includes one or more packets that are in a queue associated with a corresponding flowlet. In response to the received notifications, updated flow rates are computed for the flowlets. The updated flow rates are sent to devices for use in controlling flow rates for the flowlets in accordance with the computed updated flow rates.

Claims

1. A method for controlling flow rates of traffic among endpoints in a network, the method comprising:

receiving notifications about flowlets originating or received at the endpoints, each of the flowlets comprising one or more packets that are in a queue associated with the flowlet,

in response to the received notifications, computing updated flow rates for the flowlets, in which the computing of the updated flow rates for the flowlets comprises applying an explicit optimization process, in which the optimization process comprises a modified Newton-like method, in which the modified Newton-like method comprises an optimization process that finds prices for links of the network, the prices comprising penalties for exceeding capacities of links of the network, and sending the updated flow rates to devices for use in controlling the flow rates for the flowlets in accordance with the computed updated flow rates.

2. The method of claim 1 in which the notifications are received from the devices or other devices in the network including switches or other devices at which flow is monitored.

3. The method of claim 1 in which the devices include switches or other implementation devices.

4. The method of claim 1 in which the network comprises links and each of two or more processing cores receives the notifications only with respect to a particular subset of the links and sends the updated flow rates only for flowlets associated with the particular subset of the links.

5. The method of claim 4 in which the respective particular subsets of links to be received by respective processing cores are based on the number of processing cores that will process flows carried on the links.

6. The method of claim 5 in which each of the links comprises a half-duplex or other single-directional link.

7. The method of claim 1 in which the modified Newton-like method comprises applying LaGrange multipliers.

8. The method of claim 1 in which the computing of the updated flow rates for the flowlets comprises estimating effects on flows that will occur as a result of one or more of the updates.

9. The method of claim 1 in which the updated flow rates are computed to reach a global network resource allocation objective.

10. The method of claim 1 in which the updated flow rates are computed to reduce over-allocation of flows on links of the network.

11. The method of claim 1 in which the updated flow rates are computed to reduce delays in the queues.

12. The method of claim 1 in which the notifications are received from the devices and the updated flow rates are sent to the devices through a kernel bypass.

13. The method of claim 1 comprising applying a rate normalizer to the updated flow rates.

14. The method of claim 13 in which the rate normalizer normalizes rates to link capacities.

15. The method of claim 1 in which the computing of updated flow rates comprises organizing the computation based on flow blocks and link blocks.

16. The method of claim 1 in which the updated flow rates are computed based on information about applications that are associated with the flowlets.

17. The method of claim 16 in which the information about the application includes at least one of the identity of the application that started a flow, the identity of a user who started the application, a CPU load generated by the application, what files are open for the application, the read and write throughputs in aggregate or to each individual file, or the amount of memory used by the application.

18. The method of claim 1 in which sending the updated flow rates to devices for use in controlling flow rates comprises sending the updated flow rates only when the updated flow rates change by a factor larger than a threshold.

19. The method of claim 1 in which sending the updated flow rates to devices for use in controlling flow rates comprises sending the updated flow rates from intermediary servers that are associated with respective subsets of the endpoints.

20. The method of claim 1 comprising tracing the paths of flows in the network.

21. The method of claim 20 in which the paths of flows are determined based on at least one of ECMP hashes of the flow, or a software defined networking controller, tunneling configuration, or MPLS configuration associated with the flow.

22. A method for controlling flow rates of traffic among endpoints in a network, the method comprising:

receiving notifications about flowlets originating or received at the endpoints, each of the flowlets comprising one or more packets that are in a queue associated with the flowlet,

in response to the received notifications, computing updated flow rates for the flowlets,

sending the updated flow rates to devices for use in controlling the flow rates for the flowlets in accordance with the computed updated flow rates, and

tracing the paths of flows in the network,

in which the tracing comprises mutilating a TCP checksum to cause an endpoint to drop a probe packet without terminating a connection or notifying an application.

23. The method of claim 22 in which the computing of the updated flow rates for the flowlets comprises applying an explicit optimization process.

24. The method of claim 23 in which the optimization process comprises a modified Newton-like method.

25. The method of claim 24 in which the modified Newton-like method comprises an optimization process that finds prices for links of the network.

26. The method of claim 23 in which the optimization process uses a network utility maximization framework.

27. The method of claim 23 in which the optimization process uses a weighted proportional fairness objective.

28. The method of claim 23 in which the computing of the updated flow rates for the flowlets comprises reusing computations performed when computing previous updated flow rates.

29. The method of claim 22 in which the tracing comprises opening a raw socket.

30. The method of claim 22 in which the tracing comprises sending multiple probes in parallel distinguished by sequence number.