# US 11,121,966 B2 · Centralized application-layer routing at the edge of an online application service provider network > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,121,966 B2 - Document ID: US11121966B2 - Status: Granted - Kind: B2 - Application number: 16/911,219 - Filed: 2020-06-24 - Published: 2020-10-15 - Granted: 2021-09-14 - Earliest claimed: 2019-01-04 - Assignees: Dropbox, Inc. - Applicants: Dropbox, Inc. - Inventors: Haowei Yuan - Web page: https://patentgrep.com/patent/US11121966B2 ## CPC - H04L 45/34: {Source routing} - H04L 43/0864: Round trip delays - H04L 45/126: {minimising geographical or physical path length} - H04L 45/306: {Route determination based on the nature of the carried application} - H04L 45/38: {Flow based routing} - H04L 47/283: in response to processing delays, e.g. caused by jitter or round trip time [RTT] - H04L 67/02: based on web technology, e.g. hypertext transfer protocol [HTTP] - H04L 43/0817: by checking functioning - H04L 45/64: using an overlay routing layer - H04L 47/245: {using preemption} - H04L 47/2475: for supporting traffic characterised by the type of applications - H04L 67/12: specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract Techniques for centralized application-layer routing at the edge of an online application service provider network. In one embodiment, for example, a method comprises storing data representing a directed graph; based at least on a respective cost and the respective capacity associated with directed edges in the directed graph, determining a respective edge flow value for each directed edge; based at least on the respective edge flow value for a particular directed edge that connects a first node in directed graph to a second node in the directed graph, determining a weight for a location in a data communications network represented by the second node; receiving an application-layer request message at a location in the network represented by the first node; and selecting, based at least on the weight, the location represented by the second node to which to route the application-layer request message in the network. ## Claims ### Claim 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 1) 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. ### Claim 4 (depends on 1) 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. ### Claim 5 (depends on 1) 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. ### Claim 6 (depends on 1) 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. ### Claim 7 (depends on 1) 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. ### Claim 8 (depends on 1) 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. ### Claim 9 (depends on 1) 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. ### Claim 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. ### Claim 11 (depends on 10) 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. ### Claim 12 (depends on 10) 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. ### Claim 13 (depends on 10) 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. ### Claim 14 (depends on 10) 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. ### Claim 15 (depends on 10) The computing system of claim 10, wherein: the destination location in the data communications network is a data center in the data communications network. ### Claim 16 (depends on 10) 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. ### Claim 17 (depends on 10) 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. ### Claim 18 (depends on 10) 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. ### Claim 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. ### Claim 20 (depends on 19) 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.