Content delivery network capacity estimation

1 . A computer implemented method comprising:

determining a topology of a content delivery network (CDN), wherein the topology of the CDN comprises a plurality of edge nodes, a plurality of proxy nodes, a plurality of intermediate nodes, a plurality of first edges connecting the proxy nodes to the intermediate nodes, and a plurality of second edges connecting the intermediate nodes to the edge nodes;

generating a graph model of the CDN using the topology of the CDN;

determining a first proxy node to test;

testing the first proxy node at a test data rate to determine a first tested capacity of the first proxy node by:

distributing the test data rate across intermediate nodes connected to the first proxy node;

determining the first tested capacity of the first proxy node based on whether a total available capacity of edge nodes connected to an intermediate node connected to the first proxy node exceeds a distributed test data rate at the intermediate node;

determining a second proxy node to test;

testing the second proxy node to determine a second tested capacity of the second proxy node; and

determining a capacity of the graph model based on the first tested capacity of the first proxy node and the second tested capacity of the second proxy node.

2 . The method of claim 1 , comprising:

receiving an available capacity for each edge node of the plurality of edge nodes; and

determining the total available capacity of the edge nodes connected to the intermediate node connected to the first proxy node based on respective available capacities of the edge nodes connected to the intermediate node connected to the first proxy node.

3 . The method of claim 1 , comprising:

in response to determining that the total available capacity of the edge nodes connected to each intermediate node connected to the first proxy node exceeds the distributed test data rate at each intermediate node:

reducing an available capacity of the edge nodes connected to each intermediate node connected to the first proxy node by the distributed test data rate.

4 . The method of claim 1 comprising:

in response to determining that the total available capacity of the edge nodes connected to each intermediate node connected to the first proxy node does not exceed the distributed test data rate at each intermediate node:

reducing the test data rate by half and using the reduced test data rate in future tests.

5 . The method of claim 4 , wherein testing is performed iteratively until the test data rate is below a predetermined threshold.

6 . The method of claim 1 , wherein determining the topology of the CDN, comprises determining the topology of the CDN based on data of the plurality of edge nodes, the plurality of proxy nodes, the plurality of intermediate nodes, the plurality of first edges, and the plurality of second edges, and wherein the data is received from an online service in response to an application programming interface (API) call.

7 . The method of claim 1 , comprising:

receiving traffic usage data for each proxy node of the plurality of proxy nodes; and

wherein determining the first proxy node to test and determining the second proxy node to test are based on the traffic usage data for each proxy node of the plurality of proxy nodes.

8 . The method of claim 7 , wherein determining the first proxy node and determining the second proxy node to test comprise performing a weighted round robin algorithm, and wherein weights for the weighted round robin algorithm are selected based on the traffic usage data for each proxy node.

9 . The method of claim 1 , comprising:

determining traffic usage data for each intermediate node of the plurality of intermediate nodes; and

wherein distributing the test data rate across the intermediate nodes connected to the first proxy node based on their respective traffic usage data comprises distributing the test data rate proportionally to the respective traffic usage data of the intermediate nodes connected to the first proxy node.

10 . The method of claim 1 , wherein determining the capacity of the graph model comprises: summing tested capacities of the plurality of proxy nodes.

11 . A non-transitory, computer-readable medium storing one or more instructions executable by a computer system to perform operations comprising:

determining a topology of a content delivery network (CDN), wherein the topology of the CDN comprises a plurality of edge nodes, a plurality of proxy nodes, a plurality of intermediate nodes, a plurality of first edges connecting the proxy nodes to the intermediate nodes, and a plurality of second edges connecting the intermediate nodes to the edge nodes;

generating a graph model of the CDN using the topology of the CDN;

determining a first proxy node to test;

testing the first proxy node at a test data rate to determine a first tested capacity of the first proxy node by:

distributing the test data rate across intermediate nodes connected to the first proxy node;

determining the first tested capacity of the first proxy node based on whether a total available capacity of edge nodes connected to an intermediate node connected to the first proxy node exceeds a distributed test data rate at the intermediate node;

determining a second proxy node to test;

testing the second proxy node to determine a second tested capacity of the second proxy node; and

determining a capacity of the graph model based on the first tested capacity of the first proxy node and the second tested capacity of the second proxy node.

12 . The non-transitory, computer-readable medium of claim 11 , the operations comprising:

receiving an available capacity for each edge node of the plurality of edge nodes; and

determining the total available capacity of the edge nodes connected to the intermediate node connected to the first proxy node based on respective available capacities of the edge nodes connected to the intermediate node connected to the first proxy node.

13 . The non-transitory, computer-readable medium of claim 11 , the operations comprising:

in response to determining that the total available capacity of the edge nodes connected to each intermediate node connected to the first proxy node exceeds the distributed test data rate at each intermediate node:

reducing an available capacity of the edge nodes connected to each intermediate node connected to the first proxy node by the distributed test data rate.

14 . The non-transitory, computer-readable medium of claim 11 , the operations comprising:

in response to determining that the total available capacity of the edge nodes connected to each intermediate node connected to the first proxy node does not exceed the distributed test data rate at each intermediate node:

reducing the test data rate by half and using the reduced test data rate in future tests.

15 . The non-transitory, computer-readable medium of claim 14 , wherein testing is performed iteratively until the test data rate is below a predetermined threshold.

16 . The non-transitory, computer-readable medium of claim 11 , wherein determining the topology of the CDN, comprises determining the topology of the CDN based on data of the plurality of edge nodes, the plurality of proxy nodes, the plurality of intermediate nodes, the plurality of first edges, and the plurality of second edges, and wherein the data is received from an online service in response to an application programming interface (API) call.

17 . A computer-implemented system, comprising:

one or more computers; and

one or more computer memory devices interoperably coupled with the one or more computers and having tangible, non-transitory, machine-readable media storing one or more instructions that, when executed by the one or more computers, perform one or more operations comprising:

determining a topology of a content delivery network (CDN), wherein the topology of the CDN comprises a plurality of edge nodes, a plurality of proxy nodes, a plurality of intermediate nodes, a plurality of first edges connecting the proxy nodes to the intermediate nodes, and a plurality of second edges connecting the intermediate nodes to the edge nodes;

generating a graph model of the CDN using the topology of the CDN;

determining a first proxy node to test;

testing the first proxy node at a test data rate to determine a first tested capacity of the first proxy node by:

distributing the test data rate across intermediate nodes connected to the first proxy node;

determining the first tested capacity of the first proxy node based on whether a total available capacity of edge nodes connected to an intermediate node connected to the first proxy node exceeds a distributed test data rate at the intermediate node;

determining a second proxy node to test;

testing the second proxy node to determine a second tested capacity of the second proxy node; and

determining the capacity of the graph model based on the first tested capacity of the first proxy node and the second tested capacity of the second proxy node.

18 . The computer-implemented system of claim 17 , wherein the operations comprise:

receiving an available capacity for each edge node of the plurality of edge nodes; and

determining the total available capacity of the edge nodes connected to the intermediate node connected to the first proxy node based on respective available capacities of the edge nodes connected to the intermediate node connected to the first proxy node.

19 . The computer-implemented system of claim 17 , wherein the operations comprise:

in response to determining that the total available capacity of the edge nodes connected to each intermediate node connected to the first proxy node exceeds the distributed test data rate at each intermediate node:

reducing an available capacity of the edge nodes connected to each intermediate node connected to the first proxy node by the distributed test data rate.

20 . The computer-implemented system of claim 17 , wherein the operations comprise:

in response to determining that the total available capacity of the edge nodes connected to each intermediate node connected to the first proxy node does not exceed the distributed test data rate at each intermediate node:

reducing the test data rate by half and using the reduced test data rate in future tests.