# US 2019/0317829 A1 · Methods and systems to proactively manage usage of computational resources of a distributed computing system

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2019/0317829 A1
- Document ID: US20190317829A1
- Status: Published application
- Kind: A1
- Application number: 16/046,706
- Filed: 2018-07-26
- Published: 2019-10-17
- Earliest claimed: 2018-04-12
- Assignees: VMware, Inc.
- Applicants: VMware, Inc.
- Inventors: Darren Brown; Junyuan Lin; Paul Pedersen; Keshav Mathur; Peng Gao; Xing Wang; Leah Nutman
- Web page: https://patentgrep.com/patent/US20190317829A1

## CPC

- G06F 9/5083: {Techniques for rebalancing the load in a distributed system}
- H04L 67/1001: for accessing one among a plurality of replicated servers
- G06F 9/4856: {resumption being on a different machine, e.g. task migration, virtual machine migration (G06F9/5088 takes precedence)}
- G06F 9/5077: {Logical partitioning of resources; Management or configuration of virtualized resources (specific details on emulation or internal functioning of virtual machines G06F9/455)}
- G06F 11/3006: {where the computing system is distributed, e.g. networked systems, clusters, multiprocessor systems (multiprogramming arrangements G06F9/46; allocation of resources G06F9/50)}
- G06F 11/3409: {for performance assessment}
- G06F 11/3442: {for planning or managing the needed capacity}
- G06F 11/3452: {Performance evaluation by statistical analysis}
- G06F 17/18: for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)}
- G06N 7/08: using chaos models or non-linear system models
- G06F 2201/815: Virtual
- G06F 2201/835: Timestamp
- G06F 2209/5019: Workload prediction
- G06F 2209/5022: Workload threshold
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

Computational methods and systems that proactively manage usage of computational resources of a distributed computing system are described. A sequence of metric data representing usage of a resource is detrended to obtain a sequence of non-trendy metric data. Stochastic process models, a pulse wave model and a seasonal model of the sequence of non-trendy metric data are computed. When a forecast request is received, a sequence of forecasted metric data is computed over a forecast interval based on the estimated trend and one of the pulse wave or seasonal model that matches the periodicity of the sequence of non-trendy metric data. Alternatively, the sequence of forecasted metric data is computed based on the estimated trend and the stochastic process model with a smallest accumulated residual error. Usage of the resource by virtual objects of the distributed computing system may be adjusted based on the sequence of forecasted metric data.

## Claims

### Claim 1

A process stored in one or more data-storage devices and executed using one or more processors of a computer system to proactively manage resources in a distributed computing system, the process comprising:
detrending a sequence of metric data to obtain a sequence of non-trendy metric data, the sequence of metric data representing latest usage of a resource in the distributed computing system;
computing stochastic process models of the sequence of non-trendy metric data and corresponding accumulated residual errors;
computing a pulse wave model based on changes in averages of metric data in two sliding adjacent time windows of the sequence of non-trendy metric data;
computing two or more seasonal models for the sequence of non-trendy metric data for two or more sample rates applied to the sequence of non-trendy metric data;
when a forecast request is received,
computing a sequence of forecasted metric data over a forecast interval based on the estimated trend and one of the pulse wave model and the seasonal models that matches periodicity of the sequence of non-trendy metric data, or
when neither pulse wave nor seasonal model matches the periodicity of the sequence of non-trendy metric data, computing the sequence of forecasted metric data over the forecast interval based on the estimated trend and the stochastic process model with a smallest corresponding accumulated residual error, and
adjusting usage of the resource by virtual objects of the distributed computing system based on the sequence of forecasted metric data.

### Claim 2 (depends on 1)

The process of claim 1 wherein detrending the sequence of metric data to obtain the sequence of non-trendy metric data comprises:
applying linear regression to the sequence of metric data to generate least squares parameters;
computing a trend estimate for each time stamp of the sequence of metric data based on the least squares parameters;
computing a goodness-of-fit parameter based the sequence of metric data and a trend estimate at each time stamp of the sequence of metric data; and
when the goodness-of-fit parameter is greater than a user-defined trend threshold, subtracting the trend estimate from corresponding metric data values in the sequence of metric data to generate the sequence of non-trendy metric data.

### Claim 3 (depends on 1)

The process of claim 1 wherein computing the stochastic process models comprises:
fitting weight parameters of each of the stochastic process models to a different number of most recent subsequence of metric data in the sequence of non-trendy metric data;
when a new metric data value is received, detrending new metric data value to obtain a non-trendy metric data value and computing estimated non-trendy metric data values from the stochastic process models;
for each of the stochastic process models, computing a residual error between the estimated non-trendy metric data value and the new non-trendy metric data value; and
for each of the stochastic process models, summing the residual errors to generate the corresponding accumulated residual error.

### Claim 4 (depends on 1)

The process of claim 1 wherein computing the pulse wave model comprises:
computing an exponentially weighted moving average of absolute differences between consecutive pairs of the sequence of non-trendy metric data;
computing an absolute difference between a new non-trendy metric data value and a most recent metric data value in the sequence of non-trendy metric data;
when the absolute difference between the new non-trendy metric data value and the most recent metric data value is greater than a spike threshold, applying edge detection to determine if the sequence of non-trendy metric data is a pulse wave based on the two sliding adjacent windows; and
if the sequence of non-trendy metric data is a pulse wave, determining the pulse width and the period of the sequence of non-trendy metric data.

### Claim 5 (depends on 4)

The process of claim 4 wherein applying edge detection to determine if the sequence of non-trendy metric data is a pulse wave comprises:
applying a smoothing filter to the sequence of non-trendy metric data;
for each location of the previous and next sliding windows,
computing an average of metric data values in the previous time window,
computing an average of metric data values in the next time window,
computing a change parameter as an absolute difference between the average of metric data values in the previous time window and the average of metric data values in the previous time window,
when the change parameter is greater than a maximum amplitude range of metric data values threshold and is greater than a change parameter exponentially weighted moving average threshold, determining a time stamp of a pulse edge in a time interval of the previous and next sliding windows, and
identifying pulse edge as upward or downward;
determining each pulse width as a difference between different pairs of consecutive upward and downward edges;
determining each period as a difference between different pairs of consecutive upward edges;
recording counts of the pulse widths and periods in bins of corresponding back-sliding pulse width and period histograms; and
identifying the most recent pulse width and most recent period with counts in corresponding bins of the pulse width and period histograms that are greater than corresponding histogram thresholds.

### Claim 6 (depends on 1)

The process of claim 1 wherein computing the two or more seasonal model for the sequence of non-trendy metric data comprises:
for each of the two or more sampling rates applied to the sequence of non-trendy metric data,
resampling the sequence of non-trendy metric data at a sampling rate to obtain a subsequence of the non-trendy metric data,
computing a periodogram of the subsequence,
identifying each frequency of the periodogram that is greater than a principle frequency threshold as a candidate principle frequency,
computing autocorrelation function values in a neighborhood of a candidate period, the candidate period corresponding to a largest of the principle candidate frequencies,
estimating curvature of the autocorrelation function in the neighborhood of the candidate period,
when the estimated curvature of the autocorrelation function is concave down, determining a principle period that corresponds to a maximum of the autocorrelation function value in the neighborhood, otherwise, identifying the subsequence as not having a principle period, and
recording counts of principle frequencies in a back-sliding principle frequency histogram,
rank ordering counts of principle frequencies; and
when a largest count is greater than a dominant principle frequency threshold computed as a function of the second largest count, the principle period of the principle frequency with the largest count is used as the seasonal period of the sequence of non-trendy metric data.

### Claim 7 (depends on 1)

The process of claim 1 wherein computing the sequence of forecasted metric data over the forecast interval based on the estimated trend and one of the pulse wave model or seasonal model comprises:
computing the sequence of forecasted metric data over the forecast interval as a combination of the estimated trend and the pulse wave model, when the sequence of metric data is a pulse wave sequence of metric data; and
computing the sequence of forecasted metric data over the forecast interval as a combination of the estimated trend and the seasonal model, when the sequence of metric data is a seasonal sequence of metric data.

### Claim 8 (depends on 1)

The process of claim 1 wherein adjusting usage of the resource by virtual objects comprises one or more of
adjusting use of the resource by the virtual objects when the sequence of forecasted metric data approaches a resource threshold limit over the forecast interval;
increasing resource allocation to the virtual objects when the sequence of forecasted metric data approaches a resource threshold limit over the forecast interval; and
migrating virtual objects to a different server computer within the distributed computing system when the sequence of forecasted metric data approaches a resource threshold limit over the forecast interval.

### Claim 9

A computer system to proactively manage resources in a distributed computing system, the system comprising:
one or more processors;
one or more data-storage devices; and
machine-readable instructions stored in the one or more data-storage devices that when executed using the one or more processors controls the system to carry out
detrending a sequence of metric data to obtain a sequence of non-trendy metric data, the sequence of metric data representing latest usage of a resource in the distributed computing system;
computing stochastic process models of the sequence of non-trendy metric data and corresponding accumulated residual errors;
computing a pulse wave model based on changes in averages of metric data in two sliding adjacent time windows of the sequence of non-trendy metric data;
computing two or more seasonal models for the sequence of non-trendy metric data for two or more sample rates applied to the sequence of non-trendy metric data;
when a forecast request is received,
computing a sequence of forecasted metric data over a forecast interval based on the estimated trend and one of the pulse wave model and the seasonal models that matches periodicity of the sequence of non-trendy metric data, or
when neither pulse wave nor seasonal model matches the periodicity of the sequence of non-trendy metric data, computing the sequence of forecasted metric data over the forecast interval based on the estimated trend and the stochastic process model with a smallest corresponding accumulated residual error, and
adjusting usage of the resource by virtual objects of the distributed computing system based on the sequence of forecasted metric data.

### Claim 10 (depends on 9)

The system of claim 9 wherein detrending the sequence of metric data to obtain the sequence of non-trendy metric data comprises:
applying linear regression to the sequence of metric data to generate least squares parameters;
computing a trend estimate for each time stamp of the sequence of metric data based on the least squares parameters;
computing a goodness-of-fit parameter based the sequence of metric data and a trend estimate at each time stamp of the sequence of metric data; and
when the goodness-of-fit parameter is greater than a user-defined trend threshold, subtracting the trend estimate from corresponding metric data values in the sequence of metric data to generate the sequence of non-trendy metric data.

### Claim 11 (depends on 9)

The system of claim 9 wherein computing the stochastic process models comprises:
fitting weight parameters of each of the stochastic process models to a different number of most recent subsequence of metric data in the sequence of non-trendy metric data;
when a new metric data value is received, detrending new metric data value to obtain a non-trendy metric data value and computing estimated non-trendy metric data values from the stochastic process models;
for each of the stochastic process models, computing a residual error between the estimated non-trendy metric data value and the new non-trendy metric data value; and
for each of the stochastic process models, summing the residual errors to generate the corresponding accumulated residual error.

### Claim 12 (depends on 9)

The system of claim 9 wherein computing the pulse wave model comprises:
computing an exponentially weighted moving average of absolute differences between consecutive pairs of the sequence of non-trendy metric data;
computing an absolute difference between a new non-trendy metric data value and a most recent metric data value in the sequence of non-trendy metric data;
when the absolute difference between the new non-trendy metric data value and the most recent metric data value is greater than a spike threshold, applying edge detection to determine if the sequence of non-trendy metric data is a pulse wave based on the two sliding adjacent windows; and
if the sequence of non-trendy metric data is a pulse wave, determining the pulse width and the period of the sequence of non-trendy metric data.

### Claim 13 (depends on 12)

The system of claim 12 wherein applying edge detection to determine if the sequence of non-trendy metric data is a pulse wave comprises:
applying a smoothing filter to the sequence of non-trendy metric data;
for each location of the previous and next sliding windows,
computing an average of metric data values in the previous time window,
computing an average of metric data values in the next time window,
computing a change parameter as an absolute difference between the average of metric data values in the previous time window and the average of metric data values in the previous time window,
when the change parameter is greater than a maximum amplitude range of metric data values threshold and is greater than a change parameter exponentially weighted moving average threshold, determining a time stamp of a pulse edge in a time interval of the previous and next sliding windows, and
identifying pulse edge as upward or downward;
determining each pulse width as a difference between different pairs of consecutive upward and downward edges;
determining each period as a difference between different pairs of consecutive upward edges;
recording counts of the pulse widths and periods in bins of corresponding back-sliding pulse width and period histograms; and
identifying the most recent pulse width and most recent period with counts in corresponding bins of the pulse width and period histograms that are greater than corresponding histogram thresholds.

### Claim 14 (depends on 9)

The system of claim 9 wherein computing the two or more seasonal model for the sequence of non-trendy metric data comprises:
for each of the two or more sampling rates applied to the sequence of non-trendy metric data,
resampling the sequence of non-trendy metric data at a sampling rate to obtain a subsequence of the non-trendy metric data,
computing a periodogram of the subsequence,
identifying each frequency of the periodogram that is greater than a principle frequency threshold as a candidate principle frequency,
computing autocorrelation function values in a neighborhood of a candidate period, the candidate period corresponding to a largest of the principle candidate frequencies,
estimating curvature of the autocorrelation function in the neighborhood of the candidate period,
when the estimated curvature of the autocorrelation function is concave down, determining a principle period that corresponds to a maximum of the autocorrelation function value in the neighborhood, otherwise, identifying the subsequence as not having a principle period, and
recording counts of principle frequencies in a back-sliding principle frequency histogram,
rank ordering counts of principle frequencies; and
when a largest count is greater than a dominant principle frequency threshold computed as a function of the second largest count, the principle period of the principle frequency with the largest count is used as the seasonal period of the sequence of non-trendy metric data.

### Claim 15 (depends on 9)

The system of claim 9 wherein computing the sequence of forecasted metric data over the forecast interval based on the estimated trend and one of the pulse wave model or seasonal model comprises:
computing the sequence of forecasted metric data over the forecast interval as a combination of the estimated trend and the pulse wave model, when the sequence of metric data is a pulse wave sequence of metric data; and
computing the sequence of forecasted metric data over the forecast interval as a combination of the estimated trend and the seasonal model, when the sequence of metric data is a seasonal sequence of metric data.

### Claim 16 (depends on 9)

The process of claim 9 wherein adjusting usage of the resource by virtual objects comprises one or more of
adjusting use of the resource by the virtual objects when the sequence of forecasted metric data approaches a resource threshold limit over the forecast interval;
increasing resource allocation to the virtual objects when the sequence of forecasted metric data approaches a resource threshold limit over the forecast interval; and
migrating virtual objects to a different server computer within the distributed computing system when the sequence of forecasted metric data approaches a resource threshold limit over the forecast interval.

### Claim 17

A non-transitory computer-readable medium encoded with machine-readable instructions that implement a method carried out by one or more processors of a computer system to perform the operations of
detrending a sequence of metric data to obtain a sequence of non-trendy metric data, the sequence of metric data representing latest usage of a resource in the distributed computing system;
computing stochastic process models of the sequence of non-trendy metric data and corresponding accumulated residual errors;
computing a pulse wave model based on changes in averages of metric data in two sliding adjacent time windows of the sequence of non-trendy metric data;
computing two or more seasonal models for the sequence of non-trendy metric data for two or more sample rates applied to the sequence of non-trendy metric data;
when a forecast request is received,
computing a sequence of forecasted metric data over a forecast interval based on the estimated trend and one of the pulse wave model and the seasonal models that matches periodicity of the sequence of non-trendy metric data, or
when neither pulse wave nor seasonal model matches the periodicity of the sequence of non-trendy metric data, computing the sequence of forecasted metric data over the forecast interval based on the estimated trend and the stochastic process model with a smallest corresponding accumulated residual error, and
adjusting usage of the resource by virtual objects of the distributed computing system based on the sequence of forecasted metric data.

### Claim 18 (depends on 17)

The medium of claim 17 wherein detrending the sequence of metric data to obtain the sequence of non-trendy metric data comprises:
applying linear regression to the sequence of metric data to generate least squares parameters;
computing a trend estimate for each time stamp of the sequence of metric data based on the least squares parameters;
computing a goodness-of-fit parameter based the sequence of metric data and a trend estimate at each time stamp of the sequence of metric data; and
when the goodness-of-fit parameter is greater than a user-defined trend threshold, subtracting the trend estimate from corresponding metric data values in the sequence of metric data to generate the sequence of non-trendy metric data.

### Claim 19 (depends on 17)

The medium of claim 17 wherein computing the stochastic process models comprises:
fitting weight parameters of each of the stochastic process models to a different number of most recent subsequence of metric data in the sequence of non-trendy metric data;
when a new metric data value is received, detrending new metric data value to obtain a non-trendy metric data value and computing estimated non-trendy metric data values from the stochastic process models;
for each of the stochastic process models, computing a residual error between the estimated non-trendy metric data value and the new non-trendy metric data value; and
for each of the stochastic process models, summing the residual errors to generate the corresponding accumulated residual error.

### Claim 20 (depends on 17)

The medium of claim 17 wherein computing the pulse wave model comprises:
computing an exponentially weighted moving average of absolute differences between consecutive pairs of the sequence of non-trendy metric data;
computing an absolute difference between a new non-trendy metric data value and a most recent metric data value in the sequence of non-trendy metric data;
when the absolute difference between the new non-trendy metric data value and the most recent metric data value is greater than a spike threshold, applying edge detection to determine if the sequence of non-trendy metric data is a pulse wave based on the two sliding adjacent windows; and
if the sequence of non-trendy metric data is a pulse wave, determining the pulse width and the period of the sequence of non-trendy metric data.

### Claim 21 (depends on 20)

The medium of claim 20 wherein applying edge detection to determine if the sequence of non-trendy metric data is a pulse wave comprises:
applying a smoothing filter to the sequence of non-trendy metric data;
for each location of the previous and next sliding windows,
computing an average of metric data values in the previous time window,
computing an average of metric data values in the next time window,
computing a change parameter as an absolute difference between the average of metric data values in the previous time window and the average of metric data values in the previous time window,
when the change parameter is greater than a maximum amplitude range of metric data values threshold and is greater than a change parameter exponentially weighted moving average threshold, determining a time stamp of a pulse edge in a time interval of the previous and next sliding windows, and
identifying pulse edge as upward or downward;
determining each pulse width as a difference between different pairs of consecutive upward and downward edges;
determining each period as a difference between different pairs of consecutive upward edges;
recording counts of the pulse widths and periods in bins of corresponding back-sliding pulse width and period histograms; and
identifying the most recent pulse width and most recent period with counts in corresponding bins of the pulse width and period histograms that are greater than corresponding histogram thresholds.

### Claim 22 (depends on 17)

The medium of claim 17 wherein computing the two or more seasonal model for the sequence of non-trendy metric data comprises:
for each of the two or more sampling rates applied to the sequence of non-trendy metric data,
resampling the sequence of non-trendy metric data at a sampling rate to obtain a subsequence of the non-trendy metric data,
computing a periodogram of the subsequence,
identifying each frequency of the periodogram that is greater than a principle frequency threshold as a candidate principle frequency,
computing autocorrelation function values in a neighborhood of a candidate period, the candidate period corresponding to a largest of the principle candidate frequencies,
estimating curvature of the autocorrelation function in the neighborhood of the candidate period,
when the estimated curvature of the autocorrelation function is concave down, determining a principle period that corresponds to a maximum of the autocorrelation function value in the neighborhood, otherwise, identifying the subsequence as not having a principle period, and
recording counts of principle frequencies in a back-sliding principle frequency histogram,
rank ordering counts of principle frequencies; and
when a largest count is greater than a dominant principle frequency threshold computed as a function of the second largest count, the principle period of the principle frequency with the largest count is used as the seasonal period of the sequence of non-trendy metric data.

### Claim 23 (depends on 17)

The medium of claim 17 wherein computing the sequence of forecasted metric data over the forecast interval based on the estimated trend and one of the pulse wave model or seasonal model comprises:
computing the sequence of forecasted metric data over the forecast interval as a combination of the estimated trend and the pulse wave model, when the sequence of metric data is a pulse wave sequence of metric data; and
computing the sequence of forecasted metric data over the forecast interval as a combination of the estimated trend and the seasonal model, when the sequence of metric data is a seasonal sequence of metric data.

### Claim 24 (depends on 17)

The medium of claim 17 wherein adjusting usage of the resource by virtual objects comprises one or more of
adjusting use of the resource by the virtual objects when the sequence of forecasted metric data approaches a resource threshold limit over the forecast interval;
increasing resource allocation to the virtual objects when the sequence of forecasted metric data approaches a resource threshold limit over the forecast interval; and
migrating virtual objects to a different server computer within the distributed computing system when the sequence of forecasted metric data approaches a resource threshold limit over the forecast interval.