Method and system for optimizing network traffic in a distributed system with a point of convergence

1. A computer-implemented method for managing network bandwidth in a distributed system having multiple endpoints that upload data to a central server or server cluster, the method comprising:

collecting network measurements from traffic flows in a network over which the endpoints upload the data to the central server or server cluster;

determining a logical topology of the network based on the network measurements, wherein determining the logical topology includes determining bandwidth bottlenecks in the network that are represented as links having corresponding capacities in the logical topology;

solving an optimization problem to determine a bandwidth allocation scheme for the endpoints uploading data, wherein the corresponding capacities of the links representing the determined bandwidth bottlenecks in the logical topology are constraints in the optimization problem; and

controlling bandwidth consumption by the endpoints based on the determined bandwidth allocation scheme.

2. The method of claim 1 , wherein determining the bandwidth bottlenecks includes comparing network measurements of each pair of the endpoints to identify whether the pair of the endpoints shares a bottleneck.

3. The method of claim 1 , wherein the optimization problem is a convex optimization problem that is solved to maximize or minimize a utility function.

4. The method of claim 1 , wherein solving the optimization problem includes traversing a tree representing the logical topology with a reverse breadth-first search and allocating bandwidth during the traversing of the tree.

5. The method of claim 1 , wherein the network measurements are collected by a plurality of servers and aggregated at a single server or cluster of servers that performs the steps of determining the logical topology and solving the optimization problem.

6. The method of claim 1 , wherein the network measurements are passively collected based on packets transmitted by the endpoints to the central server or server cluster.

7. The method of claim 1 , wherein the logical topology is a unidirectional tree topology.

8. The method of claim 1 , wherein the bandwidth allocation scheme is optimized to be fair in time consumed or for max-min fairness of bandwidth.

9. The method of claim 1 , wherein the bandwidth consumption is controlled by at least one of throttling uploading rates at the endpoints or limiting the rate of traffic flows at routers.

10. A non-transitory computer-readable storage medium embodying computer program instructions for managing network bandwidth in a distributed system having multiple endpoints that upload data to a central server or server cluster, the computer program instructions implementing operations comprising:

collecting network measurements from traffic flows in a network over which the endpoints upload the data to the central server or server cluster;

determining a logical topology of the network based on the network measurements, wherein determining the logical topology includes determining bandwidth bottlenecks in the network that are represented as links having corresponding capacities in the logical topology;

solving an optimization problem to determine a bandwidth allocation scheme for the endpoints uploading data, wherein the corresponding capacities of the links representing the determined bandwidth bottlenecks in the logical topology are constraints in the optimization problem; and

controlling bandwidth consumption by the endpoints based on the determined bandwidth allocation scheme.

11. The non-transitory computer-readable storage medium of claim 10 , wherein determining the bandwidth bottlenecks includes comparing network measurements of each pair of the endpoints to identify whether the pair of the endpoints shares a bottleneck.

12. The non-transitory computer-readable storage medium of claim 10 , wherein the optimization problem is a convex optimization problem that is solved to maximize or minimize a utility function.

13. The non-transitory computer-readable storage medium of claim 10 , wherein solving the optimization problem includes traversing a tree representing the logical topology with a reverse breadth-first search and allocating bandwidth during the traversing of the tree.

14. The non-transitory computer-readable storage medium of claim 10 , wherein the network measurements are collected by a plurality of servers and aggregated at a single server or server cluster that performs the steps of determining the logical topology and solving the optimization problem.

15. The non-transitory computer-readable storage medium of claim 10 , wherein the network measurements are passively collected based on packets transmitted by the endpoints to the central server or server cluster.

16. The non-transitory computer-readable storage medium of claim 10 , wherein the logical topology is a unidirectional tree topology.

17. The non-transitory computer-readable storage medium of claim 10 , wherein the bandwidth allocation scheme is optimized to be fair in time consumed or for max-min fairness of bandwidth.

18. The non-transitory computer-readable storage medium of claim 10 , wherein the bandwidth consumption is controlled by at least one of throttling uploading rates at the endpoints or limiting the rate of traffic flows at routers.

19. A system, comprising:

a processor; and

a memory, wherein the memory includes a program configured for execution by the processor to perform operations for managing network bandwidth in a distributed system having multiple endpoints that upload data to a central server or server cluster, the operations comprising:

collecting network measurements from traffic flows in a network over which the endpoints upload the data to the central server or server cluster,

determining a logical topology of the network based on the network measurements, wherein determining the logical topology includes determining bandwidth bottlenecks in the network that are represented as links having corresponding capacities in the logical topology,

solving an optimization problem to determine a bandwidth allocation scheme for the endpoints uploading data, wherein the corresponding capacities of the links representing the determined bandwidth bottlenecks in the logical topology are constraints in the optimization problem, and

controlling bandwidth consumption by the endpoints based on the determined bandwidth allocation scheme.

20. The system of claim 19 , wherein the network measurements are passively collected based on packets transmitted by the endpoints to the central server or server cluster.