Robust scheduler for grid networks

ABSTRACT

Imprecise input data imposes additional challenges to grid scheduling. This paper introduces a novel scheduler based on fuzzy optimization called IP-FULL-FUZZY which considers uncertainties of both application demands and of resource availability. The effectiveness of the proposed scheduler is compared to those of a non-fuzzy scheduler as well as to those of a fuzzy scheduler which considers only uncertainties of application demands. Results evince the advantages of adopting the proposed scheduler.

REFERENCES

• 1: Gabrielle Allen , David Angulo , Ian Foster , Gerd Lanfermann , Chuang Liu , Thomas Radke , Ed Seidel , John Shalf, The Cactus Worm: Experiments with Dynamic Resource Discovery and Allocation in a Grid Environment, International Journal of High Performance Computing Applications, v.15 n.4, p.345-358, November 2001 [doi>10.1177/109434200101500402]
• 2: D. Antoniades, M. Athanatos, A. Papadogiannakis, E. P. Markatos, and C. Dovrolis. Available Bandwidth Measurements as Simple as Running wget. In Proc. of Passive and Active Measurement Conference (PAM 2006), pages 61--70, 2006.
• 3: Daniel M. Batista , Nelson L. S. da Fonseca , Flavio K. Miyazawa, A set of schedulers for grid networks, Proceedings of the 2007 ACM symposium on Applied computing, March 11-15, 2007, Seoul, Korea [doi>10.1145/1244002.1244057]
• 4: Daniel M. Batista , Nelson L. S. da Fonseca , Flavio K. Miyazawa , Fabrizio Granelli, Self-adjustment of resource allocation for grid applications, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.52 n.9, p.1762-1781, June, 2008 [doi>10.1016/j.comnet.2008.03.002]
• 5: Daniel M. Batista , André C. Drummond , Nelson L. S. da Fonseca, Scheduling grid tasks under uncertain demands, Proceedings of the 2008 ACM symposium on Applied computing, March 16-20, 2008, Fortaleza, Ceara, Brazil [doi>10.1145/1363686.1364181]
• 6: J. Blythe , S. Jain , E. Deelman , Y. Gil , K. Vahi , A. Mandal , K. Kennedy, Task scheduling strategies for workflow-based applications in grids, Proceedings of the Fifth IEEE International Symposium on Cluster Computing and the Grid (CCGrid'05) - Volume 2, p.759-767, May 09-12, 2005
• 7: M. Doar and I. M. Leslie. How Bad is Naive Multicast Routing? In Proc. of IEEE INFOCOM'93, pages 82--89, 1993.
• 8: C. Fayad, J. M. Garibaldi, and D. Ouelhadj. Fuzzy Grid Scheduling Using Tabu Search. In Proc. of IEEE Int. Fuzzy Systems Conference, pages 1--6, Jul 2007.
• 9: I. González-Rodrígues, C. R. Vela, and J. Puente. A Memetic Approach to Fuzzy Job Shop Based on Expectation Model. In Proc. of IEEE Int. Fuzzy Systems Conference, pages 7--12, Jul 2007.
• 10: Manish Jain , Constantinos Dovrolis, End-to-end available bandwidth: measurement methodology, dynamics, and relation with TCP throughput, ACM SIGCOMM Computer Communication Review, v.32 n.4, October 2002
• 11: NASA. Applications of Montage. http://montage.ipac.caltech.edu/applications.html. Accessed at July 6, 2008.
• 12: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 13: Rizos Sakellariou , Henan Zhao, A low-cost rescheduling policy for efficient mapping of workflows on grid systems, Scientific Programming, v.12 n.4, p.253-262, December 2004
• 14: Sathish S. Vadhiyar , Jack J. Dongarra, A Performance Oriented Migration Framework For The Grid, Proceedings of the 3st International Symposium on Cluster Computing and the Grid, p.130, May 12-15, 2003

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Uncertainty, "fuzzy," and probabilistic reasoning

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling

Keywords:
bandwidth estimation, fuzzy optimization, grid networks, linear programming, task scheduling, uncertainty