Methods and systems to reclaim capacity of unused resources of a distributed computing system

Patent metadata

Field	Value
Publication number	US-11080093-B2
Application number	US-201816013503-A
Country	US
Kind code	B2
Filing date	Jun 20, 2018
Priority date	Apr 12, 2018
Publication date	Aug 3, 2021
Grant date	Aug 3, 2021

Abstract

Computational methods and systems to reclaim capacity of a virtual infrastructure of distributed computing system are described. Methods and systems are directed to forecasting usage of resources that form a virtual infrastructure of a distributed computing system. Streams of metric data that represent usage of resources of the virtual infrastructure assigned to a virtual object are collected. A binary sequence of active status metric data is computed for the virtual object based on the streams of metric data. Forecasted active status metric data are computed in a forecast interval based on the sequence of active status metric data. Expected active or inactive status of virtual object over the forecast interval is determined from the forecasted active status metric data. If the virtual object is expected to inactive status over the forecast interval, resources assigned to the virtual object are reclaimed for use by active virtual objects.

First claim

The invention claimed is:

1. A process stored in one or more data-storage devices and executed using one or more processors of a computer system to reclaim capacity of unused virtual resources assigned to a virtual object of a distributed computing system, the process comprising:
collecting streams of metric data in a historical window, each stream of metric data representing usage of one of the virtual resources assigned to the virtual object;
computing a sequence of active status metric data in the historical window based on the streams of metric data, each active status metric data value indicating active or inactive status of the virtual object in the historical window;
computing forecasted active status metric data in a forecast interval based on the sequence of active status metric data, each forecasted active status metric data value indicating active or inactive status of the virtual object in the forecast interval; and
assigning the virtual resources assigned to the virtual object to a prospectively active virtual object in the forecast interval based on the forecasted active status metric data values indicating inactive status of the virtual object in the forecast interval.

2. The process of claim 1 wherein computing the sequence of active status metric data comprises:
for each time stamp in the historical window,
assigning a value that indicates the virtual object is active to an active status metric data point in the sequence of active status metric data when one or more of the metric data values of the streams of metric data at the time stamp are greater than corresponding resource thresholds, and
assigning a value that indicates the virtual object is inactive to an active status metric data point in the sequence of active status metric data when none of the metric data values of the streams of metric data at the time stamp are greater than the corresponding resource thresholds.

3. The process of claim 1 , wherein computing the forecasted sequence of active status metric data in the forecast interval comprising:
computing a trend estimate in the sequence of active status metric data;
detrending the sequence of active status metric data based on the estimated trend to obtain a sequence of non-trendy metric data;
computing two or more stochastic process models of the sequence of non-trendy metric data and corresponding accumulated residual errors; and
computing a pulse wave model and a seasonal model of the sequence of non-trendy metric data;
when a forecast request is received,
determining whether the sequence of non-trendy metric data is a pulse wave or seasonal;
computing the forecasted sequence of active status metric data over the forecast interval based on the estimated trend and the pulse wave model when the sequence of non-trendy metric data is a pulse wave,
computing the forecasted sequence of active status metric data over the forecast interval based on the estimated trend and the seasonal model when the sequence of non-trendy metric data is seasonal, or
when the sequence of non-trendy metric data is not a pulse wave and not seasonal, computing the forecasted sequence of active status metric data over the forecast interval based on the estimated trend and a stochastic process model of the stochastic process models with a smallest of the corresponding accumulated residual errors.

4. The process of claim 3 wherein estimating the trend in the sequence of active status metric data comprises:
applying linear regression to the sequence of active status metric data to generate least squares parameters; and
computing a trend estimate for each time stamp of the sequence of active status metric data based on the least-squares parameters.

5. The process of claim 3 wherein detrending the sequence of metric data to obtain the sequence of non-trendy metric data comprises:
computing a goodness-of-fit parameter based the sequence of active status metric data and a trend estimate at each time stamp of the sequence of active status 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 active status metric data to generate the sequence of non-trendy metric data.

6. The process of claim 3 wherein computing the two or more stochastic process models comprises:
fining weight parameters of each of the two or more 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 the new metric data value to obtain a non-trendy metric data value and computing two or more estimated non-trendy metric data values from the two or more stochastic process models;
for each of the two or more 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 two or more stochastic process models, summing the residual errors to generate the corresponding accumulated residual error.

7. The process of claim 3 wherein computing the two periodic models 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;
if the sequence of non-trendy metric data is a pulse wave, determining a pulse width and a period that matches a pulse width and a period of the sequence of non-trendy metric data; and
if the sequence of non-trendy metric data is not a pulse wave, determining a seasonal period that matches a periodicity of the sequence of non-trendy metric data.

8. The process of claim 7 wherein determining the pulse width and the period comprises:
applying a smoothing filter to the sequence of non-trendy metric data;
computing gradients at each time stamp of the sequence of non-trendy metric data;
applying non-maximum edge suppression to the gradients at each time stamp to identify pulse edges and suppress local non-maximum gradients;
identifying upward and downward pulse edges at time stamps of pulse edges;
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.

9. The process of claim 7 wherein determining the seasonal period comprises:
for each sampling rate applied to the sequence of non-trendy metric data,
sampling the sequence of non-trendy metric data at the sampling rate to obtain a subsequence of the sequence of non-trendy metric data 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,
estima

Assignees

• Vmware Inc

Inventors

• Chandran Rachil
• Jain Lalit
• Beybutyan Harutyun
• Ang James
• Nutman Leah
• Mathur Keshav

Classifications

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• G06F9/5022 Primary

  Mechanisms to release resources · CPC title

• G06F9/5077

  Logical partitioning of resources; Management or configuration of virtualized resources (specific details on emulation or internal functioning of virtual machines G06F9/455) · CPC title

• G06F2209/5019

  Workload prediction · CPC title

• H04L43/0817

  by checking functioning · CPC title