Methods and apparatus for predicting impact of proposed changes and implementations in distributed networks

• US 7,886,046 B1
• Filed: 05/16/2008
• Issued: 02/08/2011
• Est. Priority Date: 05/16/2008
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Zeitoun, Amgad, Tariq, Muhammad Mukarram Bin
• Primary Examiner(s): SHIN, KYUNG H
• Application Number:
  US12/152,861
• Time in Patent Office: 998 Days
• Field of Search: 709/224, 706/50, 706/56, 370/230.1, 370/241
• US Class Current: 709/224
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network

Abstract

The present invention pertains to specifying, analyzing and evaluating systems such as distributed content distribution networks. Systems and methods are provided to predict how new deployments and changes to existing architectures will impact the networks. A network design may prepare a “what-if” scenario and the impact of this scenario may be predicted. Various tools are provided to determine relevant network variables and collect data about such variables, to learn what dependencies may exist among relevant variables, to prepare an input distribution and to output a predicted impact for the what-if scenario. Thus, a system designer is able to see a predicted impact that a network change or new deployment will have without having to resort to back of the envelope calculation or costly field deployments.

Claims

1. A method of predicting a service criterion in a distributed computer network, the method comprising:

collecting a set of features about at least one of requests and responses that arrive at an input of the network;

collecting a set of data associated with the requests or responses, the data set including at least one of network data and system data;

determining a subset of the features which are relevant based upon the collected data set;

learning dependencies between features of the subset;

specifying a scenario associated with the service criterion of the network, the scenario including one or more conditions;

preparing an input distribution, including;

filtering the collected data set based on the conditions specified in the scenario, and;

executing subsequent requirements in the scenario specification such that the data set is updated to be consistent with both the specified conditions and the dependencies among the subset of features; and

outputting a predicted data set for evaluating expected operation of the scenario based on the input distribution.

2. The method of claim 1, wherein specifying the scenario includes identifying changes to values of the features of the subset.

3. The method of claim 1, wherein specifying the scenario includes receiving a use parameter and at least one scenario update parameter.

4. The method of claim 3, wherein the use parameter specifies a condition that describes a subset of the network.

5. The method of claim 4, wherein the use parameter specifies the subset of the network based on a location of one or more client devices.

6. The method of claim 4, wherein the use parameter specifies the subset of the network based on a location of at least one network server.

7. The method of claim 4, wherein the use parameter specifies the subset of the network based on properties of a service session.

8. The method of claim 3, wherein the at least one scenario update parameter represents values for one or more of the subset of features.

9. A system for predicting a service criterion in a distributed computer network, the system comprising:

a scenario input module for receiving a what-if scenario from a user, the what-if scenario identifying a use parameter and at least one scenario update parameter associated with the network;

a relevant feature module for receiving a dataset of features associated with the network and for determining which ones of the features of the dataset are relevant to the what-if scenario;

a dependencies module for identifying which ones of the relevant features have parent or child dependencies to other ones of the relevant features;

an input distribution module for filtering data associated with the relevant features and for executing subsequent requirements in the what-if scenario;

a processor for managing operation of the scenario input module, the relevant feature module, the dependencies module and the input distribution module; and

memory for storing instructions and data for execution by the processor, the scenario input module, the relevant feature module, the dependencies module and the input distribution module.

10. The system of claim 9, wherein the input distribution module filters the data by re-sampling and re-weighing the data using a causal structure identified by the dependencies module as a guideline.

11. The system of claim 10, wherein the re-sampling and re-weighing is done recursively and if a first relevant feature has a child dependency to a second relevant feature then a distribution of the first relevant feature is not updated until a distribution of the second relevant feature is updated.

12. The system of claim 9, wherein the filtered data forms an initial test dataset and the input distribution module updates the initial test dataset based on values specified in the subsequent requirements of the what-if scenario.

13. The system of claim 9, wherein identifying the parent and child dependencies by the dependencies module includes identifying an undirected graph and orienting edges of the undirected graph.

14. The system of claim 9, wherein identifying the parent and child dependencies by the dependencies module includes identifying which of the relevant features are cause variables and which are no-cause variables.

15. The system of claim 9, wherein identifying the parent and child dependencies employs a causal discovery algorithm.

16. The system of claim 15, wherein the causal discovery algorithm executes a series of instructions using a processor, the series of instruction comprising:

generating a fully connected undirected graph whereby all nodes representing the relevant features are connected;

removing edges between nodes that are uncorrelated;

progressively finding separating nodes between a frontier set of variables from the set of relevant features and all other variables from the set of relevant features; and

adding the separating nodes to the frontier set.

17. A system for predicting a service criterion in a distributed computer network, the system comprising:

means for receiving a what-if scenario from a user, the what-if scenario identifying a use parameter and at least one scenario update parameter associated with the network;

means for receiving a set of features associated with the network and for determining which ones of the features are relevant to the what-if scenario;

means for identifying which ones of the relevant features have parent or child dependencies to other ones of the relevant features; and

means for filtering data associated with the relevant features and for executing subsequent requirements in the what-if scenario.

18. A method for determining relevant variables of a distributed computer network, the method comprising:

obtaining a dataset of variables;

identifying a first variable of the dataset;

determining whether the first variable is a categorical variable or a real-valued variable;

if the first variable is categorical;

generating a conditional distribution for the first variable, and

determining whether the conditional distribution of the first variable is statistically similar.

19. The method of claim 18, wherein upon determining whether the conditional distribution of the first variable is statistically similar, the method further comprises:

discarding the first variable if the conditional distribution of the first variable is statistically similar; and

storing the first variable in memory if the conditional distribution of the first variable is not statistically similar.

20. The method of claim 18, wherein if the first variable is real-valued, the method further comprises:

determining whether a correlation satisfies a threshold; and

if the correlation satisfies the threshold, storing the first variable in the memory.

21. The method of claim 20, wherein if the correlation does not satisfy the threshold, the method further comprises:

dividing a range of the variable into a series of buckets, wherein each bucket operates as a category;

generating the conditional distribution for the first variable; and

determining whether the conditional distribution of the first variable is statistically similar.

22. The method of claim 21, wherein upon determining whether the conditional distribution of the first variable is statistically similar, the method further comprises:

discarding the first variable if the conditional distribution of the first variable is statistically similar, and

storing the first variable in memory if the conditional distribution of the first variable is not statistically similar.

23. A method of processing data of a distributed computing network, the method comprising:

receiving a what-if scenario indicating a change to the distributed computing network, the what-if scenario identifying a use parameter and at least one scenario update parameter associated with the network;

obtaining a global set of data for the distributed computing network;

filtering the global dataset to obtain an initial test dataset using the use parameter;

applying the at least one scenario update parameter to the initial test dataset to obtain an updated test dataset; and

processing the updated test dataset to output a predicted scenario result to a user.

24. The method of claim 23, wherein the at least one scenario update parameter comprises a plurality of scenario update parameters which are applied sequentially to the initial test dataset.

25. The method of claim 23, wherein the at least one scenario update parameter comprises a plurality of scenario update parameters, at least some of the plurality of scenario update parameters being executed in parallel.

26. The method of claim 25, wherein variables updated for each of the scenario update parameters executed in parallel do not share any common descendents other than a target variable and the updated variables are not descendents of one another.

27. A system for processing data of a distributed computing network, the system comprising:

at least one processor;

at least one memory for storing instructions and data for execution by the at least one processor;

a first module for receiving a what-if scenario indicating a change to the distributed computing network, the what-if scenario identifying a use parameter and at least one scenario update parameter associated with the network;

a second module for obtaining a global set of data for the distributed computing network and for filtering the global dataset to obtain an initial test dataset using the use parameter; and

a third module for applying the at least one scenario update parameter to the initial test dataset to obtain an updated test dataset and for processing the updated test dataset to output a predicted scenario result to a user;

wherein the data stored by the at least one memory includes the global dataset, the initial test dataset and the updated test dataset and the instructions comprise module instructions of the first, second and third modules.

28. The system of claim 27, wherein the at least one memory comprises a plurality of distributed memories and the global dataset, the initial test dataset and the updated test dataset are stored among the plurality of distributed memories.

29. The system of claim 28, wherein the at least one processor comprises a plurality of processors, each of the processors being associated with a respective one of the plurality of distributed memories.

30. The system of claim 29, wherein the plurality of processors performs a piecewise regression on the global dataset, each of the plurality of processors performing a regression independently for a given tile to prune the global dataset to obtain the initial test dataset.

31. A method of predicting a service criterion in a distributed computing network, the method comprising:

filtering a collected data set based on at least one condition specified in a network scenario, the collected data set including information associated with network operation;

executing requirements of the specified network scenario to prepare an input distribution so that the collected data set is updated to be consistent with the at least one condition and with dependencies among features associated with the collected data set; and

outputting a predicted data set for evaluating expected operation of the network scenario based on the input distribution.

32. An apparatus for predicting a service criterion in a distributed computer network, the apparatus comprising:

a relevant feature module for receiving a dataset of features associated with the network and for determining which ones of the features of the dataset are relevant to a what-if scenario;

a dependencies module for identifying which ones of the relevant features have parent or child dependencies to other ones of the relevant features;

an input distribution module for filtering data associated with the relevant features and for executing subsequent requirements in the what-if scenario; and

a processor operable to control execution of the relevant feature module, the dependencies module and the input distribution module.