Simulating a computational grid with networked animat agents

ABSTRACT

Computational grids are now widespread, but their large-scale behaviour is still poorly understood. We report on some calculations of loading, scaling and utilisation behaviours of computational grids, based on simulations. We employ animat agents on a topologically detailed graph representing a grid overlay network. Agents are used to represent computational jobs, users and resources. We can obtain realistic behaviours by endowing user agents with time-varying microscopic behaviour patterns.We are able to study the static flow and dynamical macroscopic properties of the network including emergent pathological behaviours and other anomalies that arise when parts of the network become temporarily unavailable. Our model is based on graph theory with various attributes decorating the edges and nodes which have physical locations. We develop some overall grid utility metrics that can be analysed. Our work suggests that grids do need to be treated as complex adaptive systems.

REFERENCES

• 1: R. Buyya, & M. Murshed (2002), GridSim: a Toolkit for the Modeling and Simulation of Distributed Resource Management and Scheduling for Grid Computing, Concurrency Computat. Pract. Exper. 2002; 14 1175-1220.
• 2: Ian Foster , Carl Kesselman, The Grid 2: Blueprint for a New Computing Infrastructure, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 3: C. Girault & R. Valk, (2003), Petri Nets for Systems Engineering, Spring Verlag, ISBN 3-540-41217-4.
• 4: K. A. Hawick , H. A. James , A. J. Silis , D. A. Grove , C. J. Patten , J. A. Mathew , P. D. Coddington , K. E. Kerry , J. F. Hercus , F. A. Vaughan, DISCWorld: an environment for service-based matacomputing, Future Generation Computer Systems, v.15 n.5-6, p.623-635, Oct. 1999 [doi>10.1016/S0167-739X(99)00014-X]
• 5: K.A. Hawick (2004), GraViz A Graph Visualisation Tool, unpublished.
• 6: Hewlett-Packard Company, (1994), Standard Template Library Programmer's Guide, Available from http://www.sgi.com/tech/stl Last visited September 2005.
• 7: C. A. R. Hoare, Communicating sequential processes, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985
• 8: R.N. Ibbett & P.E. Heywood & F.W. Howell, (1996), HASE: A Flexible Toolset for Computer Architects, The Computer Journal Vol 38, (10).
• 9: T. Pratchett, (2000), The Color of Magic, Harper-Torch, ISBN 0061020710.
• 10: A. W. Roscoe , C. A. R. Hoare, The laws of Occam programming, Theoretical Computer Science, v.60 n.2, p.177-229, September 1988 [doi>10.1016/0304-3975(88)90049-7]
• 11: A.R. Robertson & R.N. Ibbett, (1993), HASE: A Hierarchical Architecture Design and Simulation Environment for Computer Architects, UKSS '93, Keswick, UK, UK Simulation Society, 1993.
• 12: A. Sulistio & G. Poduval & R. Buyya & C.-K. Tham, (2005), Constructing A Grid Simulation with Differentiated Network Service using GridSim, Proc. of the 6th International Conference on Internet Computing (ICOMP'05), June 27-30, 2005, Las Vegas, USA.
• 13: Anthony Sulistio , Chee Shin Yeo , Rajkumar Buyya, A taxonomy of computer-based simulations and its mapping to parallel and distributed systems simulation tools, Software—Practice & Experience, v.34 n.7, p.653-673, June 2004 [doi>10.1002/spe.585]
• 14: Sun Microsystems, (2005), Java Development Kit (JDK) 1.5, available from http://java.sun.com. Last visited September 2005.
• 15: University of Chicago, (2005), Globus Toolkit, available from http://www.globus.org. Last visited September 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.11 Software Architectures
            Subjects: Domain-specific architectures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Monte Carlo

General Terms:
Design, Management

Keywords:
Monte Carlo simulation, network graph, networked agents, spatial complexity