| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Measuring the Robustness of a Resource Allocation
July 2004 (vol. 15 no. 7)
pp. 630-641
Abstract—Parallel and distributed systems may operate in an environment that undergoes unpredictable changes causing certain system performance features to degrade. Such systems need robustness to guarantee limited degradation despite fluctuations in the behavior of its component parts or environment. This research investigates the robustness of an allocation of resources to tasks in parallel and distributed systems. The main contributions of this paper are 1) a mathematical description of a metric for the robustness of a resource allocation with respect to desired system performance features against multiple perturbations in multiple system and environmental conditions, and 2) a procedure for deriving a robustness metric for an arbitrary system. For illustration, this procedure is employed to derive robustness metrics for three example distributed systems. Such a metric can help researchers evaluate a given resource allocation for robustness against uncertainties in specified perturbation parameters.
[1] 630 S. Ali, J.-K. Kim, Y. Yu, S.B. Gundala, S. Gertphol, H.J. Siegel, A.A. Maciejewski, and V. Prasanna, Greedy Heuristics for Resource Allocation in Dynamic Distributed Real-Time Heterogeneous Computing Systems Proc. 2002 Int'l Conf. Parallel and Distributed Processing Techniques and Applications, vol. 2, pp. 519-530, June 2002.[2] S. Ali, H.J. Siegel, M. Maheswaran, D. Hensgen, and S. Sedigh-Ali, Representing Task and Machine Heterogeneities for Heterogeneous Computing Systems Tamkang J. Science and Eng., vol. 3, no. 3, pp. 195-207, Nov. 2000.[3] P.M. Berry, Uncertainty in Scheduling: Probability, Problem Reduction, Abstractions and the User IEE Computing and Control Division Colloquium on Advanced Software Technologies for Scheduling, Digest No: 1993/163, Apr. 1993.[4] L. Bölöni and D.C. Marinescu, Robust Scheduling of Metaprograms J. Scheduling, vol. 5, no. 5, pp. 395-412, Sept. 2002.[5] S. Boyd and L. Vandenberghe, Convex Optimization http://www.stanford.edu/class/ee364index.html , 2003.[6] T.D. Braun, H.J. Siegel, N. Beck, L.L. Bölöni, M. Maheswaran, A.I. Reuther, J.P. Robertson, M.D. Theys, B. Yao, D. Hensgen, and R.F. Freund, A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems J. Parallel and Distributed Computing, vol. 61, no. 6, pp. 810-837, June 2001.[7] A. Burns, S. Punnekkat, B. Littlewood, and D. Wright, Probabilistic Guarantees for Fault-Tolerant Real-Time Systems Technical Report, Design for Validation (DeVa) TR No. 44, Esprit Long Term Research Project No. 20072, Dept. of Computer Science, Univ. of Newcastle upon Tyne, U.K., 1997.[8] Y.X. Chen, Optimal Anytime Search for Constrained Nonlinear Programming master's thesis, Dept. of Computer Science, Univ. of Illinois, Urbana, May 2001.[9] R.L. Daniels and J.E. Carrillo, $\beta{\hbox{-}}{\rm{Robust}}$Scheduling for Single-Machine Systems with Uncertain Processing Times IIE Trans., vol. 29, no. 11, pp. 977-985, 1997.[10] A.J. Davenport, C. Gefflot, and J.C. Beck, Slack-Based Techniques for Robust Schedules Proc. Sixth European Conf. Planning, pp. 7-18, Sept. 2001.[11] J. DeVale and P. Koopman, Robust Software No More Excuses Proc. IEEE Int'l Conf. Dependable Systems and Networks, pp. 145-154, June 2002.[12] S. Ghosh, Guaranteeing Fault Tolerance through Scheduling in Real-Time Systems PhD thesis, Faculty of Arts and Sciences, Univ. of Pittsburgh, 1996.[13] S.D. Gribble, Robustness in Complex Systems Proc. Eighth Workshop Hot Topics in Operating Systems, pp. 21-26, May 2001.[14] E. Hart, P.M. Ross, and J. Nelson, Producing Robust Schedules via an Artificial Immune System Proc. 1998 Int'l Conf. Evolutionary Computing, pp. 464-469, May 1998.[15] R. Harrison, L. Zitzman, and G. Yoritomo, High Performance Distributed Computing Program (HiPer-D) Engineering Testbed One (T1) Report technical report, Naval Surface Warfare Center, Dahlgren, Va., Nov. 1995.[16] E. Jen, Stable or Robust? What is the Difference? Complexity, to appear.[17] M. Jensen, Improving Robustness and Flexibility of Tardiness and Total Flowtime Job Shops Using Robustness Measures J. Applied Soft Computing, vol. 1, no. 1, pp. 35-52, June 2001.[18] V.J. Leon, S.D. Wu, and R.H. Storer, Robustness Measures and Robust Scheduling for Job Shops IEE Trans., vol. 26, no. 5, pp. 32-43, Sept. 1994.[19] G.L. Nemhauser and L.A. Wolsey, Integer and Combinatorial Optimization. New York: John Wiley&Sons, 1988.[20] M. Sevaux and K. Sörensen, Genetic Algorithm for Robust Schedules Proc. Eighth Int'l Workshop Project Management and Scheduling, pp. 330-333, Apr. 2002.[21] G.F. Simmons, Calculus With Analytic Geometry, second ed. New York: McGraw-Hill, 1995.[22] Y.N. Sotskov, V.S. Tanaev, and F. Werner, Stability Radius of an Optimal Schedule: A Survey and Recent Developments Industrial Applications of Combinatorial Optimization, G. Yu, ed., Norwell, Mass.: Kluwer Academic Publishers, pp. 72-108, 1998.
Index Terms:
Robustness, robustness metric, resource allocation, resource management systems, parallel and distributed systems.
Citation:
Shoukat Ali, Anthony A. Maciejewski, Howard Jay Siegel, Jong-Kook Kim, "Measuring the Robustness of a Resource Allocation," IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 7, pp. 630-641, July 2004, doi:10.1109/TPDS.2004.24
