A statistical approach to risk mitigation in computational markets

ABSTRACT

We study stochastic models to mitigate the risk of poor Quality-of-Service (QoS) in computational markets. Consumers whopurchase services expect both price and performance guarantees. They need to predict future demand to budget for sustained performance despite price fluctuations. Conversely, providers need to estimate demand to price future usage. The skewed and bursty nature of demand in large-scale computer networks challenges the common statistical assumptions of symmetry, independence, and stationarity. This discrepancy leads to under estimation of investment risk. We confirm this non-normal distribution behavior in our study of demand in computational markets.

The high agility of a dynamic resource market requires flexible, efficient, and adaptable predictions. Computational needs are typically expressed using performance levels, hence we estimate worst-case bounds of price distributions to mitigate the risk of missing execution deadlines.

To meet these needs, we use moving time windows of statistics to approximate price percentile functions. We use snapshots of summary statistics to calculate prediction intervals and estimate model uncertainty. Our approach is model-agnostic, distribution-free both in prices and prediction errors, and does not require extensive sampling nor manual parameter tuning. Our simulations and experiments show that a Chebyshev inequality model generates accurate predictions with minimal sample data requirements. We also show that this approach mitigates the risk of dropped service level performance when selecting hosts to run a bag-of-task Grid application simulation in a live computational market cluster.

REFERENCES

• 1: An Algorithm for Computing the Inverse Normal Cumulative Distribution Function. http://home.online.no/Ü pjacklam/notes/invnorm/,2007.
• 2: Parallel Workloads Archive. http://www.cs.huji.ac.il/labs/parallel/workload/, 2007.
• 3: M. Bodruzzaman, J. Cadzow, R. Shiavi, A. Kilroy, B. Dawant, and M. Wilkes. Hurst's rescaled-range (r/s) analysis and fractal dimension of electromyographic (emg) signal. In Proceedings of IEEE Souteastcon '91, pages 1121--1123, Williamsburg, VA, USA, 1991. IEEE.
• 4: John Brevik , Daniel Nurmi , Rich Wolski, Predicting bounds on queuing delay for batch-scheduled parallel machines, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA [doi>10.1145/1122971.1122989]
• 5: R. Buyya, D. Abramson, and S. Venugopal. The Grid Economy. Proceedings of the IEEE, Special Issue on Grid Computing, 93(3):479--484, March 2005.
• 6: Chaki Ng , Philip Buonadonna , Brent N. Chun , Alex C. Snoeren , Amin Vahdat, Addressing strategic behavior in a deployed microeconomic resource allocator, Proceeding of the 2005 ACM SIGCOMM workshop on Economics of peer-to-peer systems, August 22-22, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080192.1080195]
• 7: S. Clearwater and B. A. Huberman. Swing Options. In Proceedings of 11th International Conference on Computing in Economics, June 2005.
• 8: S. Clearwater and S. D. Kleban. Heavy-tailed distributions in supercomputer jobs. Technical Report SAND2002-2378C, Sandia National Labs, 2002.
• 9: David C. Parkes , Ruggiero Cavallo , Nick Elprin , Adam Juda , Sébastien Lahaie , Benjamin Lubin , Loizos Michael , Jeffrey Shneidman , Hassan Sultan, ICE: an iterative combinatorial exchange, Proceedings of the 6th ACM conference on Electronic commerce, p.249-258, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064036]
• 10: Paul Barham , Boris Dragovic , Keir Fraser , Steven Hand , Tim Harris , Alex Ho , Rolf Neugebauer , Ian Pratt , Andrew Warfield, Xen and the art of virtualization, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 11: Michal Feldman , Kevin Lai , Li Zhang, A price-anticipating resource allocation mechanism for distributed shared clusters, Proceedings of the 6th ACM conference on Electronic commerce, p.127-136, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064023]
• 12: W. Feller. An Introduction to Probability Theory and its Applications, volume II. Wiley Eastern Limited, 1988.
• 13: G. J. Hahn and W. Q. Meeker. Statistical Intervals: A Guide for Practitioners. John Wiley & Sons, Inc, New York, NY, USA, 1991.
• 14: H. Hurst. Long term storage capacity of reservoirs. Proc. American Society of Civil Engineers, 76(11), 1950.
• 15: Laxmikant V. Kale , Sameer Kumar , Mani Potnuru , Jayant DeSouza , Sindhura Bandhakavi, Faucets: Efficient Resource Allocation on the Computational Grid, Proceedings of the 2004 International Conference on Parallel Processing (ICPP'04), p.396-405, August 15-18, 2004 [doi>10.1109/ICPP.2004.35]
• 16: Kevin Lai, Markets are dead, long live markets, ACM SIGecom Exchanges, v.5 n.4, p.1-10, July, 2005 [doi>10.1145/1120717.1120719]
• 17: J. K. MacKie-Mason, A. Osepayshvili, D. M. Reeves, and M. P. Wellman. Price prediction strategies for market-based scheduling. In ICAPS, pages 244--252, 2004.
• 18: B. Mandelbrot, A. Fisher, and L. Calvet. The multifractal model of asset returns. In Cowles Foundation Discussion Papers: 1164. Yale University, 1997.
• 19: B. Mandelbrot and R. L. Hudson. The (Mis)behavior of Markets: A Fractal View of Risk, Ruin, and Reward. Basic Books, New York, NY, USA, 2004.
• 20: L. Peterson, T. Anderson, D. Culler, , and T. Roscoe. Blueprint for Introducing Disruptive Technology into the Internet. In First Workshop on Hot Topics in Networking, 2002.
• 21: Ori Regev , Noam Nisan, The POPCORN market—an online market for computational resources, Proceedings of the first international conference on Information and computation economies, p.148-157, October 25-28, 1998, Charleston, South Carolina, United States [doi>10.1145/288994.289027]
• 22: T. Sandholm, K. Lai, J. Andrade, and J. Odeberg. Market-based resource allocation using price prediction in a high performance computing grid for scientific applications. In HPDC '06: Proceedings of the 15th IEEE International Symposium on High Performance Distributed Computing, pages 132--143, June 2006. http://hpdc.lri.fr/index.php.
• 23: O. Smirnova, P. Erola, T. Ekelöf, M. Ellert, J. Hansen, A. Konsantinov, B. Konya, J. Nielsen, F. Ould-Saada, and A. Wäänänen. The NorduGrid Architecture and Middleware for Scientific Applications. Lecture Notes in Computer Science, 267: 264--273, 2003.
• 24: D. F. Vysochanskij and Y. I. Petunin. Justification of the 3 sigma rule for unimodal distributions. Theory of Probability and Mathematical Statistics, 21:25--36, 1980.
• 25: Carl A. Waldspurger , Tad Hogg , Bernardo A. Huberman , Jeffrey O. Kephart , W. Scott Stornetta, Spawn: A Distributed Computational Economy, IEEE Transactions on Software Engineering, v.18 n.2, p.103-117, February 1992 [doi>10.1109/32.121753]
• 26: M. P. Wellman, D. M. Reeves, K. M. Lochner, and Y. Vorobeychik. Price prediction in a trading agent competition. J. Artif. Intell. Res. (JAIR), 21:19--36, 2004.
• 27: W. Williams and M. Goodman. A simple method for the construction of empirical confidence limits for economic forecasts. Journal of the American Statistical Association, 66(336):752--754, 1971.
• 28: R. Wolski, G. Obertelli, M. Allen, D. Nurmi, and J. Brevik. Predicting Grid Resource Performance On-Line. In Handbook of Innovative Computing: Models, Enabling Technologies, and Applications. Springer Verlag, 2005.
• 29: Richard Wolski , James S. Plank , John Brevik , Todd Bryan, G-commerce: Market Formulations Controlling Resource Allocation on the Computational Grid, Proceedings of the 15th International Parallel & Distributed Processing Symposium, p.46, April 23-27, 2001
• 30: F. Wu, L. Zhang, and B. A. Huberman. Truth-telling Reservations. http://arxiv.org/abs/cs/0508028, 2005.
• 31: Lijuan Xiao , Yanmin Zhu , Lionel M. Ni , Zhiwei Xu, GridIS: An Incentive-Based Grid Scheduling, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers, p.65.2, April 04-08, 2005 [doi>10.1109/IPDPS.2005.237]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Modeling and prediction

General Terms:
Management, Performance

Keywords:
QoS, resource allocation, service level management