For many applications with inter-datacenter Cloud deployments it is important to rely on an accurate model of delay times across different geolocations. Unfortunately, such a model is currently not available to researchers and practitioners. To fill that gap, we analyzed real-life latency values collected between different Amazon datacenter locations, and propose a novel Gaussian mixture approximation model of the round-trip time distribution based on Relaxed Boxed Approximation (RBA) algorithm. The proposed model can be effectively used for emulation/simulation of cross-Cloud application and service deployments.
where t is the RTT expressed in milliseconds; a_i is the amplitude coefficient of the i-th
Gaussian component, incorporating the weight wi and variance ci2
coefficients; bi is the mean (or shift) coefficient; ci is the standard deviation coefficient.
As for the quality of the approximation, we empirically established that a value greater than 0.945 for the adjusted R2 coefficient of determination, calculated using RTT values in the dataset and sampled from fRTT, provides a more than adequate level of accuracy.
Note that the components of the equation above are "common" Gaussians, with support in ℝ, as opposed to truncated Gaussians, with support in (0,+∞), even if the RTT metric clearly has only positive values. This is because a truncated Gaussian mixture model would be significantly more difficult to deal with from the parameter fitting perspective, while at the same time it would provide only a very limited accuracy increase. In the practical adoption of our model, we assume that any negative values sampled from fRTT will be simply dropped and a new sampling will immediately follow.
More specifically, using standard solutions and n=4 Gaussian components we achieved sufficient accuracy in only about 35% of the ping traces we analyzed. This suggests that, while some of the AWS inter-datacenter connections experience a quite stable latency over time, most of them is subject to higher delay variability. Then, we increased the number of Gaussians up to n=8, which resulted in sufficient accuracy in about 50% of traces.
For more information, please refer to W. Cerroni, G. Ya. Grabarnik, L. Foschini, L. Shwartz, M. Tortonesi, "Estimating Delay Times between Cloud Datacenters: A Pragmatic Modelling Approach", to appear in IEEE Communication Letters.
A Gaussian Mixture Model (GMM) for latency modeling
Starting from a dataset of measured RTTs, our solution applies a Gaussian mixture approximation to estimate the RTT probability density function (PDF):
As for the quality of the approximation, we empirically established that a value greater than 0.945 for the adjusted R2 coefficient of determination, calculated using RTT values in the dataset and sampled from fRTT, provides a more than adequate level of accuracy.
Note that the components of the equation above are "common" Gaussians, with support in ℝ, as opposed to truncated Gaussians, with support in (0,+∞), even if the RTT metric clearly has only positive values. This is because a truncated Gaussian mixture model would be significantly more difficult to deal with from the parameter fitting perspective, while at the same time it would provide only a very limited accuracy increase. In the practical adoption of our model, we assume that any negative values sampled from fRTT will be simply dropped and a new sampling will immediately follow.
Problems in standard GMM parameter fitting solutions
Unfortunately, when we tried to identify the parameters for the GMM presented above by feeding the latency datasets we colleted to standard fitting solutions, such as those available in the MATLAB Curve Fitting Toolbox, we often achieved poor approximations - well below the treshold of for the adjusted R2 coefficient.More specifically, using standard solutions and n=4 Gaussian components we achieved sufficient accuracy in only about 35% of the ping traces we analyzed. This suggests that, while some of the AWS inter-datacenter connections experience a quite stable latency over time, most of them is subject to higher delay variability. Then, we increased the number of Gaussians up to n=8, which resulted in sufficient accuracy in about 50% of traces.
The Relaxed Boxed Approximation (RBA) Algorithm
To address these issues we designed the Relaxed Boxed Approximation (RBA) algorithm, a novel solution for the control of the Gaussian mixture parameter fitting process. Our solution is based on the introduction of bounding box constraints for each of the model parameters, according to domain-specific heuristics and controlled by a relaxation parameter ɛ. The value of ɛ is the effectively allowed error of approximation and depends on the application.For more information, please refer to W. Cerroni, G. Ya. Grabarnik, L. Foschini, L. Shwartz, M. Tortonesi, "Estimating Delay Times between Cloud Datacenters: A Pragmatic Modelling Approach", to appear in IEEE Communication Letters.
Comments
Post a Comment