Synthesizing Realistic Computational Grids

ABSTRACT

Realistic workloads are essential in evaluating middleware for computational grids. One important component is the raw grid itself: a network topology graph annotated with the hardware and software available on each node and link. This paper defines our requirements for grid generation and presents GridG, our extensible generator. We describe GridG in two steps: topology generation and annotation. For topology generation, we have both model and mechanism. We extend Tiers, an existing tool from the networking community, to produce graphs that obey recently discovered power laws of Internet topology. We also contribute to network topology theory by illustrating a contradiction between two laws and proposing a new version of one of them. For annotation, GridG captures intra- and inter-host correlations between attributes using conditional probability rules. We construct a set of rules, including one based on empirical evidence of OS concentration in subnets, that produce sensible host annotations.

REFERENCES

• 1: Kento Aida , Atsuko Takefusa , Hidemoto Nakada , Satoshi Matsuoka , Satoshi Sekiguchi , Umpei Nagashima, Performance Evaluation Model for Scheduling in Global Computing Systems, International Journal of High Performance Computing Applications, v.14 n.3, p.268-279, August 2000 [doi>10.1177/109434200001400308]
• 2: William Aiello , Fan Chung , Linyuan Lu, A random graph model for massive graphs, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.171-180, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335326]
• 3: [3] ALBERT, R., AND LASZLO BARABASI, A. Statistical mechanics of complex networks. Reviews of modern physics 74 (2002).
• 4: Suman Banerjee , Seungjoon Lee , Bobby Bhattacharjee , Aravind Srinivasan, Resilient multicast using overlays, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 5: [5] BARABASI, A., AND R. ALBERT. Emergence of scaling in random networks. Science (1999), 509-512.
• 6: [6] BUYYA, R., AND MURSHED, M. Gridsim: A toolkit for the modeling and simulation of distributed resource management and scheduling for grid computing. The Journal of Concurrency and Computation: Practice and Experience (CCPE) (May 2002 (to appear)).
• 7: [7] CALVERT, K. L., DOAR, M. B., AND ZEGURA, E. W. Modeling internet topology. IEEE Communications Magazine 35, 6 (June 1997), 160-168.
• 8: Henri Casanova, Simgrid: A Toolkit for the Simulation of Application Scheduling, Proceedings of the 1st International Symposium on Cluster Computing and the Grid, p.430, May 15-18, 2001
• 9: Steven Fitzgerald, Grid Information Services for Distributed Resource Sharing, Proceedings of the 10th IEEE International Symposium on High Performance Distributed Computing, p.181, August 07-09, 2001
• 10: Peter A. Dinda , Thomas Gross , Roger Karrer , Bruce Lowekamp , Nancy Miller , Peter Steenkiste , Dean Sutherland, The Architecture of the Remos System, Proceedings of the 10th IEEE International Symposium on High Performance Distributed Computing, p.252, August 07-09, 2001
• 11: [11] DINDA, P., AND PLALE, B. A unified relational approach to grid information services. Grid Forum Informational Draft GWD-GIS-012-1 (February 2001).
• 12: Peter A. Dinda, Online Prediction of the Running Time of Tasks, Cluster Computing, v.5 n.3, p.225-236, July 2002 [doi>10.1023/A:1015634802585]
• 13: Peter A. Dinda , Dong Lu, Nondeterministic Queries in a Relational Grid Information Service, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.12, November 15-21, 2003
• 14: [14] DOAR, M. B. A better model for generating test networks. IEEE GLOBECOM (1996).
• 15: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 16: [16] FOSTER, I. The anatomy of the grid: Enabling scalable virtual organizations. Lecture Notes in Computer Science 2150 (2001), 1-25.
• 17: [17] FOSTER, I., AND KESSELMAN, C. Globus: A metacomputing infrastructure toolkit. The International Journal of Supercomputer Applications and High Performance Computing 11, 2 (Summer 1997), 115-128.
• 18: Ian Foster , Carl Kesselman, The grid: blueprint for a new computing infrastructure, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 19: [19] FYODOR. Remote os detection via tcp/ip stack fingerprinting. (web page). http://www.insecure.org/nmap/nmapfingerprinting-article.html.
• 20: Andrew S. Grimshaw , Wm. A. Wulf , CORPORATE The Legion Team, The Legion vision of a worldwide virtual computer, Communications of the ACM, v.40 n.1, p.39-45, Jan. 1997 [doi>10.1145/242857.242867]
• 21: [21] JIN, C., CHEN, Q., AND JAMIN, S. Inet: Internet topology generator. Tech. Rep. CSE-TR443-00, Department of EECS, University of Michigan Ann Arbor, 2000.
• 22: [22] KLEINBERG, J. M., KUMAR, R., RAGHAVAN, P., RAJAGOPALAN, S., AND TOMKINS, A. S. The web as a graph: Measurements, models and methods. Lecture Notes in Computer Science 1627 (1999), 1-18.
• 23: Bruce B. Lowekamp, Combining active and passive network measurements to build scalable monitoring systems on the grid, ACM SIGMETRICS Performance Evaluation Review, v.30 n.4, March 2003 [doi>10.1145/773056.773061]
• 24: Alberto Medina , Anukool Lakhina , Ibrahim Matta , John Byers, BRITE: An Approach to Universal Topology Generation, Proceedings of the Ninth International Symposium in Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS'01), p.346, August 15-18, 2001
• 25: Alberto Medina , Ibrahim Matta , John Byers, On the origin of power laws in Internet topologies, ACM SIGCOMM Computer Communication Review, v.30 n.2, April 2000 [doi>10.1145/505680.505683]
• 26: [26] MIHAIL, M., AND PAPADIMITRIOU, C. On the eigenvalue power law. Springer-Verlag Lecture Notes in Computer Science (2002).
• 27: [27] PALMER, C. R., AND STEFFAN, J. G. Generating network topologies that obey power laws. In GLOBECOM '2000 (2000).
• 28: Matei Ripeanu , Ian T. Foster, Mapping the Gnutella Network: Macroscopic Properties of Large-Scale Peer-to-Peer Systems, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.85-93, March 07-08, 2002
• 29: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 30: Warren Smith , Abdul Waheed , David Meyers , Jerry Yan, An Evaluation of Alternative Designs for a Grid Information Service, Cluster Computing, v.4 n.1, p.29-37, March 2001 [doi>10.1023/A:1011460125780]
• 31: H. J. Song , X. Liu , D. Jakobsen , R. Bhagwan , X. Zhang , K. Taura , A. Chien, The MicroGrid: a scientific tool for modeling computational gridsr, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.53-es, November 04-10, 2000, Dallas, Texas, United States
• 32: Hongsuda Tangmunarunkit , Ramesh Govindan , Sugih Jamin , Scott Shenker , Walter Willinger, Network topology generators: degree-based vs. structural, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 33: [33] WAXMAN, B. Routing of multipoint connections. IEEE J. of Selected Areas in Communications 6, 9 (1988), 1622-1671.
• 34: [34] WINICK, J., AND JAMIN, S. Inet-3.0: Internet topology generator. Tech. Rep. CSE-TR-456-02, Department of EECS, University of Michigan Ann Arbor, 2002.
• 35: Rich Wolski , Neil T. Spring , Jim Hayes, The network weather service: a distributed resource performance forecasting service for metacomputing, Future Generation Computer Systems, v.15 n.5-6, p.757-768, Oct. 1999 [doi>10.1016/S0167-739X(99)00025-4]