Centralized application-layer routing at the edge of an online application service provider network

1. A method comprising:

storing data representing a directed graph, the directed graph representing a data communications network, the directed graph comprising a plurality of nodes and a plurality of directed edges, each directed edge of the plurality of directed edges associated with a respective cost and a respective capacity;

based at least on the respective cost and the respective capacity associated with each directed edge of the plurality of directed edges, determining a respective edge flow value for each directed edge of the plurality of directed edges;

based at least on the respective edge flow value for a particular directed edge of the plurality of directed edges that connects a first node of the plurality of nodes to a second node of the plurality of nodes, determining a weight for a location in the data communications network represented by the second node;

receiving an application-layer request message at a location in the data communications network represented by the first node; and

selecting, based at least on the weight, the location in the data communications network represented by the second node to which to route the application-layer request message in the data communications network.

2. The method of claim 1 , further comprising:

determining the respective cost associated with the particular directed edge based at least on a network round-trip time in the data communications network between (a) a location in the data communications network represented by the first node and (b) a location in the data communications network represented by the second node.

3. The method of claim 1 , further comprising:

determining the respective capacity associated with the particular directed edge based at least on a network bandwidth in the data communications network between (a) a location in the data communications network represented by the first node and (b) a location in the data communications network represented by the second node.

4. The method of claim 1 , further comprising:

determining the respective edge flow value for the particular directed edge based at least on an output of an execution of a minimum cost maximum flow algorithm where the respective cost and the respective capacity associated with the particular directed edge are provided as part of an input to the execution of the minimum cost maximum flow algorithm.

5. The method of claim 1 , wherein:

the location in the data communications network represented by the first node is at an edge of the data communications network.

6. The method of claim 1 , wherein:

the location in the data communications network represented by the first node is a point-of-presence in the data communications network; and

the location in the data communications network represented by the second node is a data center in the data communications network.

7. The method of claim 1 , wherein the sum of the respective edge flow values determined for all edges, of the plurality of directed edges, incoming in the directed graph to the first node equals the sum of the respective edge flow values determined for all edges, of the plurality of edges, outgoing in the directed graph from the first node.

8. The method of claim 1 , further comprising:

determining the weight for the location in the data communications network represented by the second node based on the respective edge flow value for each directed edge of the plurality of directed edges.

9. The method of claim 1 , further comprising:

sending, over the data communications network from a location in the data communications network, the weight for the location in the data communications network represented by the second node to the location in the data communications network represented by the first node.

10. A computing system comprising:

one or more processors;

storage media; and

instructions stored in the storage media which, when executed by the computing system, cause the computing system to perform:

storing data representing a directed graph, the directed graph representing a data communications network, the directed graph comprising a plurality of nodes and a plurality of directed edges, each directed edge of the plurality of directed edges associated with a respective cost and a respective capacity;

based at least on the respective cost and the respective capacity associated with each directed edge of the plurality of directed edges, determining a respective edge flow value for each directed edge of the plurality of directed edges;

based at least on the respective edge flow value for a particular directed edge of the plurality of directed edges that connects a first node of the plurality of nodes to a second node of the plurality of nodes, determining a weight for a destination location in the data communications network represented by the second node;

receiving a first application-layer request message at an edge location in the data communications network represented by the first node; and

response to receiving the first application-layer request message, selecting, based at least on the weight, the destination location in the data communications network represented by the second node to which to send a second application-layer request message in the data communications network.

11. The computing system of claim 10 , further comprising instructions which, when executed by the computing system, cause the computing system to perform:

determining the respective cost associated with the particular directed edge based at least on a network round-trip time in the data communications network between (a) the edge location in the data communications network represented by the first node and (b) the destination location in the data communications network represented by the second node.

12. The computing system of claim 10 , further comprising instructions which, when executed by the computing system, cause the computing system to perform:

determining the respective capacity associated with the particular directed edge based at least on a network bandwidth in the data communications network between (a) the edge location in the data communications network represented by the first node and (b) the destination location in the data communications network represented by the second node.

13. The computing system of claim 10 , further comprising instructions which, when executed by the computing system, cause the computing system to perform:

determining the respective edge flow value for the particular directed edge based at least on an output of an execution of a minimum cost maximum flow algorithm where the respective cost and the respective capacity associated with the particular directed edge are provided as part of an input to the execution of the minimum cost maximum flow algorithm.

14. The computing system of claim 10 , wherein:

the edge location in the data communications network is a point-of-presence in the data communications network.

15. The computing system of claim 10 , wherein:

the destination location in the data communications network is a data center in the data communications network.

16. The computing system of claim 10 , wherein the first application-layer request message is a hypertext transfer protocol (HTTP) request message or a secure hypertext transfer protocol (HTTPS) request message.

17. The computing system of claim 10 , further comprising instructions which, when executed by the computing system, cause the computing system to perform:

determining the weight for the destination location in the data communications network represented by the second node based on the respective edge flow value for each directed edge of the plurality of directed edges.

18. The computing system of claim 10 , further comprising instructions which, when executed by the computing system, cause the computing system to perform:

sending, over the data communications network from a location in the data communications network, the weight for the destination location in the data communications network represented by the second node to the edge location in the data communications network represented by the first node.

19. One or more non-transitory storage media storing instructions which, when executed by a computing system comprising one or more processors and storage media, cause the computing system to perform:

storing data representing a directed graph, the directed graph representing a data communications network, the directed graph comprising a plurality of nodes and a plurality of directed edges, each directed edge of the plurality of directed edges associated with a respective cost and a respective capacity;

based at least on the respective cost and the respective capacity associated with each directed edge of the plurality of directed edges, determining a respective edge flow value for each directed edge of the plurality of directed edges;

based at least on the respective edge flow value for each directed edge of the plurality of directed edges, determining a respective weight for each of a plurality of destination locations in the data communications network;

sending, over the data communications network from a location in the data communications network, the respective weights for the plurality of destination locations to an edge location in the data communications network;

receiving a first application-layer request message at the edge location in the data communications network; and

selecting, based at least on the respective weights for the plurality of destination locations, a particular destination of the plurality of destination locations to which to send a second application-layer request message in the data communications network that is based at least on the first application-layer request message.

20. The one or more non-transitory storage media of claim 19 , further comprising instructions which, when executed by the computing system, cause the computing system to perform:

determining the respective edge flow value for each directed edge of the plurality of directed edges based at least on an output of an execution of a minimum cost maximum flow algorithm where the respective cost and the respective capacity associated with the each directed edge of the plurality of directed edges are provided as part of an input to the execution of the minimum cost maximum flow algorithm.