Back to results
US 10,320,698 B1Granted
Determining network connectivity for placement decisions
AssigneeAmazon Technologies, Inc.
InventorNicholas Alexander Allen
Life of this patent
Estimating the term…
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.
Claims25
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.
4 more elements
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.
7 more elements
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.
4 more elements
Dependencies are inferred from the claim text.