Network Resource Allocation

• US 20170230298A1
• Filed: 02/08/2017
• Published: 08/10/2017
• Est. Priority Date: 02/09/2016
• Status: Active Grant

• Current Assignee: Splunk Inc.
• Original Assignee: Flowtune, Inc.
• Inventors: Perry, Jonathan
• Granted Patent: US 10,348,600 B2
• Time in Patent Office: 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. Also, rates of flow at endpoints of a network are controlled. A device in the network sends notification of a start or end of a flowlet at an endpoint of the network. The notification is sent to an allocator to which other devices send notifications with respect to other flowlets. At the device, a communication rate is received from the allocator. The rate is one of a set of communication rates for flowlets starting and ending at endpoints of the network. The device controls a rate of communication on a link of the network based on the received communication rate. Also, network resources are allocated to devices at endpoints of a network. A modified Newton like process is applied to optimize current flow rates at respective devices based on information about flowlets starting or ending at the devices, the capacities of links of the network, and information about the paths of the flowlets through the network.

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, and

sending the updated flow rates to devices for use in controlling 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 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 computing of the updated flow rates for the flowlets comprises applying an explicit optimization process.

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

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

10. The method of claim 9 in which the prices comprise penalties for exceeding capacities of links of the network.

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

12. 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.

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

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

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

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

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

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

19. 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.

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

21. The method of claim 20 in which the rate normalizer normalizes rates to link capacities.

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

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

24. The method of claim 23 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.

25. 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.

26. 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.

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

28. The method of claim 27 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.

29. The method of claim 27 in which the tracing comprises tracing the paths of only large flows.

30. The method of claim 27 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.

31. The method of claim 27 in which the tracing comprises opening a raw socket.

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

33. A method for controlling rates of flow at endpoints of a network, comprising

a device in the network sending notification of a start or end of a flowlet at an endpoint of the network, the notification being sent to an allocator to which other devices send notifications with respect to other flowlets,

at the device receiving a communication rate from the allocator, the rate being one of a set of communication rates for flowlets starting and ending at endpoints of the network, and

the device controlling a rate of communication on a link of the network based on the received communication rate.

34. The method of claim 33 comprising the device sending the notification when a queue in the network is not empty.

35. The method of claim 33 comprising the device determining a path of the flowlet through the network and reporting the path to the allocator.

36. A method for allocating network resources to devices at endpoints of a network, the method comprising

applying a modified Newton like process to optimize current flow rates at respective devices based on information about flowlets starting or ending at the devices, the capacities of links of the network, and information about the paths of the flowlets through the network.