# US 10,320,698 B1 · Determining network connectivity for placement decisions > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,320,698 B1 - Document ID: US10320698B1 - Status: Granted - Kind: B1 - Application number: 14/180,275 - Filed: 2014-02-13 - Granted: 2019-06-11 - Earliest claimed: 2014-02-13 - Assignees: Amazon Technologies, Inc. - Applicants: Amazon Technologies, Inc. - Inventors: Nicholas Alexander Allen - Web page: https://patentgrep.com/patent/US10320698B1 ## CPC - H04L 41/122: of virtualised topologies, e.g. software-defined networks [SDN] or network function virtualisation [NFV] - H04L 45/02: Topology update or discovery - H04L 45/48: Routing tree calculation - H04L 47/70: Admission control; Resource allocation - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract Techniques for making placement decisions for the placement of computing resources in a computer network utilize approximations of the network. A simplified representation of the network is used to determine a placement that satisfies a set of connectivity requirements. The simplified representation may be generated, at least in part, probabilistically based on the network. ## Claims ### Claim 1 A computer implemented method, comprising: obtaining a representation of a graph based at least in part on a network that includes a plurality of computing devices, the graph comprising: a plurality of vertices, each vertex of the plurality of vertices associated with a computing device of the plurality of computing devices, and a plurality of edges, each edge of the plurality of edges having a weight associated with a characteristic of a connection between respective devices of the plurality of computing devices; generating, based at least in part on a set of connectivity requirements associated with a set of virtual machines and weights associated with the plurality of edges, a second representation that comprises a second plurality of edges having fewer members than the plurality of edges; generating, based at least in part on the second representation, the set of connectivity requirements, and a second set of weights associated with the second representation, a placement decision that includes an assignment of each virtual machine in the set of virtual machines to a device of the plurality of computing devices; and causing instantiation of the set of virtual machines using respective devices of the plurality of computing devices in accordance with the placement decision. ### Claim 2 (depends on 1) The computer implemented method of claim 1, wherein the representation of the graph is based at least in part on a Laplacian matrix of the graph. ### Claim 3 (depends on 1) The computer implemented method of claim 1, wherein processing the representation of the graph comprises probabilistically removing edges from the graph. ### Claim 4 (depends on 3) The computer implemented method of claim 3, wherein probabilistically removing edges from the graph is performed in accordance with a set of edges specified for exclusion from deletion from the graph. ### Claim 5 (depends on 1) The computer implemented method of claim 1, wherein: processing the representation of the graph comprises: determining a subgraph of a spanning tree of the graph; and probabilistically adding edges back to the subgraph; and processing the representation of the graph is based at least in part on the subgraph with the probabilistically added edges. ### Claim 6 (depends on 5) The computer implemented method of claim 5, wherein: probabilistically adding edges back to the subgraph comprises probabilistically selecting edges from a set of edges, each edge of at least a subset of the edges corresponding to a bandwidth; and probabilistically selecting the edges from the set of edges is based at least in part on a probability distribution that, at least in part, increases as a function of bandwidth. ### Claim 7 A system, comprising: one or more processors; and memory with instructions that, if executed by the one or more processors, cause the system to: obtain a first representation of a network comprising a plurality of computing devices, the representation of connections between devices in the network indicating: a plurality of vertices, each vertex of the plurality of vertices associated with a respective computing device of the plurality of computing devices, and a plurality of edges, each edge of the plurality of edges having a respective weight associated with a characteristic of a connection between respective devices of the plurality of computing devices: generate, based at least in part on weights associated with the plurality of edges and the first representation, a second representation of the network that indicates fewer network connections than the first representation; generate, based at least in part on network connectivity requirements of a set of computing resources, the second representation, and a second set of weights associated with the second representation, a placement decision that indicates an assignment of a member of the set of computing resources with other respective members of the plurality of computing devices; and cause the instantiation of the plurality of computing resources based at least in part on the placement decision. ### Claim 8 (depends on 7) The system of claim 7, wherein: the first representation of the network is a matrix of a graph of the network; and the second representation of the network is generated by transforming the matrix to be more sparse than the first representation. ### Claim 9 (depends on 8) The system of claim 8, wherein the matrix is based at least in part on a Laplacian of the graph of the network. ### Claim 10 (depends on 7) The system of claim 7, wherein: the first representation of the network is based at least in part on a graph of the network; and the second representation of the network is generated based at least in part on a subgraph of a spanning tree of the graph. ### Claim 11 (depends on 7) The system of claim 7, wherein the placement decision is generated by performing an iterative method of solving a system of linear equations, the system of linear equations based at least in part on the second representation. ### Claim 12 (depends on 11) The system of claim 11, wherein the iterative method of solving the system of linear equations solves the system of linear equations by approximating a solution to within a threshold value based at least in part on the network connectivity requirements. ### Claim 13 (depends on 7) The system of claim 7, wherein the second representation of the network is generated based at least in part on one or more probabilistic modifications of a subgraph of a graph of the network. ### Claim 14 (depends on 13) The system of claim 13, wherein the one or more probabilistic modifications of the subgraph include: probabilistic deletions of edges from the graph; determination of the subgraph after performing the probabilistic deletions; and probabilistic additions of deleted edges to the subgraph. ### Claim 15 (depends on 14) The system of claim 14, wherein one or more edges of the graph have one or more weights associated with the edges of the graph, the one or more weights based at least in part on an inverse of one or more probabilities associated with the probabilistic modification of the subgraph of the graph of the network. ### Claim 16 (depends on 14) The system of claim 14, wherein probabilistic additions of deleted edges to the subgraph includes probabilistic additions of the deleted edges with replacement. ### Claim 17 (depends on 16) The system of claim 16, wherein one or more edges of the graph have one or more weights associated with the probabilistic additions of the deleted edges with replacement, the one or more weights based at least in part on a number of selections of the deleted edges. ### Claim 18 A non-transitory computer readable storage medium having collectively stored thereon executable instructions that, if executed by one or more processors of a computer system, cause the computer system to at least: obtain a representation of a network associated with a plurality of computing devices, the network comprising: a plurality of vertices, each vertex of the plurality of vertices associated with a respective computing device of the plurality of computing devices, and a plurality of edges, each edge of the plurality of edges having a respective weight associated with a characteristic of a connection between respective devices of the plurality of computing devices: generate a simplified representation of the network based at least in part on a probabilistic selection of a subset of a plurality of network connections between respective computing devices in the network and respective weights associated with the plurality of edges, the subset having fewer members than the connections of the network; use the simplified representation of the network and the weights determine a placement indicating an assignment of each of a plurality of computing resources to a device among a subset of the one or more computing devices; and cause provisioning of the plurality of computing resources according to the placement. ### Claim 19 (depends on 18) The non-transitory computer readable storage medium of claim 18, wherein the instructions that cause the computer system to determine the placement further cause the computer system to solve a system of linear equations, the system of linear equations based at least in part on the simplified representation and a set of requirements for the placement. ### Claim 20 (depends on 18) The non-transitory computer readable storage medium of claim 18, wherein the simplified representation is based at least in part on a subgraph of a graph of the network. ### Claim 21 (depends on 20) The non-transitory computer readable storage medium of claim 20, wherein the instructions that cause the computer system to generate the simplified representation of the network further cause the computer system to generate the simplified representation by probabilistically adding edges to a subgraph of a spanning tree of the graph. ### Claim 22 (depends on 21) The non-transitory computer readable storage medium of claim 21, wherein probabilistically adding edges to the subgraph of the spanning tree is based at least in part on probabilities correlating to bandwidth values assigned to edges in the graph. ### Claim 23 (depends on 22) The non-transitory computer readable storage medium of claim 22, wherein the edges in the graph have weights assigned, such weights based at least in part on an inverse of the probabilities correlating to the bandwidth values assigned to the edges in the graph. ### Claim 24 (depends on 18) The non-transitory computer readable storage medium of claim 18, wherein the instructions, if executed by the one or more processors, further cause the computer system to: generate a plurality of simplified representations of the network; calculate a score for each generated simplified representation of the network of the plurality of simplified representations of the network; and select the simplified representation based at least in part on a corresponding calculated score for the simplified representation. ### Claim 25 (depends on 24) The non-transitory computer readable storage medium of claim 24, wherein the instructions that cause the computer system to calculate the score further cause the computer system to calculate the score based at least in part on a measurement of sparsity and a measurement of fidelity to the network.