Back to results
US 11,778,053 B1Granted
Fault-tolerant function placement for edge computing
AssigneeAmazon Technologies, Inc.
InventorNicholas Alexander Allen
Life of this patent
Estimating the term…
Abstract
Techniques for fault-tolerant function placement across multiple computing placement locations are described. An application placement service obtains a latency-based placement of functions of an application and utilizes resource information associated with the placement locations to determine error rates for flows of the placement. For flows having an error rate falling outside of an allowable range, the application placement service can modify the placement to improve the error rate, e.g., by adding additional redundancy for functions in higher-error placement locations within those placement location tiers, and/or by adding additional redundancy for functions in higher-error placement locations within different placement location tiers.
Claims17
A computer-implemented method comprising:
- obtaining, at an application placement service of a multi-tenant provider network, an application configuration including identifiers of a plurality of functions of an application and a deployment criterion specified by a user and indicating at least a desired error rate associated with a valid placement of the plurality of functions;
- generating a data structure representing an initial placement configuration for the plurality of functions of the application, the initial placement configuration specifying, for each of the plurality of functions, one or more computing placement locations where an instance of the function is to be deployed, the generating comprising:
- obtaining a directed acyclic graph representing a plurality of execution flows of the application,
- generating a plurality of linear flows based on the directed acyclic graph,
- determining one or more execution latency values for at least one linear flow of the plurality of linear flows,
- training a machine learning (ML) model based on the one or more execution latency values,
- inferring, via use of the ML model, a set of one or more additional execution latency values for a different one or more linear flows of the plurality of linear flows, and
- utilizing at least the inferred set of additional execution latency values to generate the data structure representing the initial placement configuration;
- determining, based at least in part on the initial placement configuration, that an error rate probability associated with the application does not satisfy the deployment criterion;
- modifying the initial placement configuration to yield a modified placement configuration having an error rate probability that satisfies the deployment criterion and to create instance redundancy, the modifying including adding, to the initial placement configuration, one or more duplicate instances of one instance of the instances of the initial placement configuration at a same computing placement location tier as the one instance or at a different computing placement location tier, wherein the instances of the initial placement configuration do not include the one or more duplicate instances added;
- and
- transmitting at least the modified placement configuration to a computing device.
9 more elements
A computer-implemented method comprising:
- obtaining a directed acyclic graph representing a plurality of execution flows of an application;
- generating a plurality of linear flows based on the directed acyclic graph;
- determining one or more execution latency values for at least one linear flow of the plurality of linear flows;
- training a machine learning (ML) model based on the one or more execution latency values;
- inferring, via use of the ML model, a set of one or more additional execution latency values for a different one or more linear flows of the plurality of linear flows;
- utilizing at least the inferred set of additional execution latency values to generate a data structure representing an initial placement configuration that specifies, for each function of a plurality of functions of an application, one or more computing placement locations where an instance of the function should be deployed;
- determining that a deployment criterion based at least on an error rate probability associated with the initial placement configuration is not satisfied;
- modifying the initial placement configuration to yield a modified placement configuration having an error rate probability that satisfies the criterion and to create instance redundancy, the modifying including adding one or more duplicate instances of one of the instances of the initial placement configuration at a same computing placement location tier as the one instance or at a different computing placement location tier, wherein the instances of the initial placement configuration do not include the one or more duplicate instances added;
- and
- transmitting or storing the modified placement configuration.
7 more elements
A system comprising:
- a first one or more electronic devices to implement a first computing placement location located within a multi-tenant service provider network;
- a second one or more electronic devices to implement a second computing placement location located outside the multi-tenant service provider network;
- and
- an application placement service, implemented by a third one or more electronic devices, including instructions that upon execution cause the application placement service to:
- obtain a directed acyclic graph representing a plurality of execution flows of an application;
- generate a plurality of linear flows based on the directed acyclic graph;
- determine one or more execution latency values for at least one linear flow of the plurality of linear flows;
- train a machine learning (ML) model based on the one or more execution latency values;
- infer, via use of the ML model, a set of one or more additional execution latency values for a different one or more linear flows of the plurality of linear flows;
- utilize at least the inferred set of additional execution latency values to generate a data structure representing an initial placement configuration that specifies, for each function of a plurality of functions of an application, one or more computing placement locations where an instance of the function should be deployed;
- determine that an error rate probability associated with the initial placement configuration does not satisfy a deployment criterion;
- modify the initial placement configuration to yield a modified placement configuration having an error rate probability that satisfies the criterion and to create instance redundancy, the modifying including adding one or more duplicate instances of one of the instances of the initial placement configuration at a same computing placement location tier as the one instance or at a different computing placement location tier, wherein the modified placement configuration indicates that an instance of a first function is to be deployed to the first computing placement location and an instance of a second function is to be deployed to the second computing placement location, wherein the instances of the initial placement configuration do not include the one or more duplicate instances added;
- and
- transmitting or storing the modified placement configuration.
11 more elements
Dependencies are inferred from the claim text.