Next-generation computation- and network-intensive collaborative applications in various science, engineering, and e-commerce fields feature large-scale computing workflows of complex structures. Efficient algorithms are needed for task scheduling, module deployment, and service provisioning to support the execution of such distributed workflows in heterogeneous network environments and optimize their end-to-end performance for fast system response or smooth data flow. However, deploying large-scale distributed applications in real network environments is extremely challenging due to the inherent dynamics in the reliability, availability, accessibility, and capacity of massively distributed system resources, which are typically shared among a broad community of users over the Internet or dedicated connections. We propose a simulation system to study the execution dynamics of distributed computing workflows and evaluate the network performance of workflow scheduling or mapping algorithms before actual deployment and experimentation. The proposed simulation system visually illustrates the dynamic execution process of workflows in network environments by simulating module execution on computer nodes and data transfer over network links in a completely distributed and parallel manner. Furthermore, the simulation system takes background traffic and workload into consideration to achieve a high level of simulation accuracy for distributed applications deployed in shared production network environments. We implement the simulation system using multi-threaded programming and conduct extensive testings on various mapping schemes using a large number of simulated workflows and networks. The simulation-based performance measurements are quantitatively confirmed by both the experimental observations collected in real networks and the theoretical results obtained by rigorous performance analysis based on well-defined mathematical models.
GuYWuQ. Optimizing distributed computing workflows in heterogeneous network environments. In Proceedings of the 11th International Conference on Distributed Computing and Networking, Kolkata, India, 3–6 January, 2010.
KimSJBrowneJC. A general approach to mapping of parallel computation upon multiprocessors architectures. In Proceedings of the International Conference on Parallel Processing, 1988, pp.1–8.
4.
RahmanMVenugopalSBuyyaR. A dynamic critical path algorithm for scheduling scientific workflow applications on global grids. In Proceedings of the 3rd IEEE International Conference on e-Science and Grid Computing, 2007, pp.35–42.
5.
KwokYAhmadI. Dynamic critical-path scheduling: An effective technique for allocating task graph to multiprocessors. IEEE Trans Parallel Distrib Syst1996; 7: 506–521.
6.
AgarwallaBAhmedNHilleyDRamachandranU. Streamline: A scheduling heuristic for streaming application on the Grid. In Proceedings of the 13th Multimedia Computing and Networking Conference, San Jose, CA, 2006.
7.
GuYWuQZhuMRaoNSV. Brief announcement: Efficient linear pipeline configuration in distributed heterogeneous computing environments. In Proceedings of the 27th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), Toronto, Canada, 18–21 August, 2008.
8.
WuQGuY. Supporting distributed application workflows in heterogeneous computing environments. In Proceedings of the 14th IEEE International Conference on Parallel and Distributed Systems, Melbourne, Australia, December, 2008, pp.3–10
.
9.
GonzalezODavisWJGonzalezFGDavisWJ. A new simulation tool for the modeling and control of distributed systems. SCS Int2002; 78: 552–567.
10.
WuQGuYWangZ. Simulation-based analysis of performance dynamics of distributed applications in heterogeneous network environments. In SpringSim’09: Proceedings of the 2009 Spring Simulation Multiconference, San Diego, CA, 22–27 March, 2009, pp.1–8.
11.
WuQZhuMLuXBrownPLinYGuY. Automation and management of scientific workflows in distributed network environments. In Proceedings of the 6th International Workshop on Systems Manangement Techniques, Processes, and Services, Atlanta, GA, 19 April, 2010.
12.
WuQGuYLuXZhuMBrownPLinW. On optimization of scientific workflows to support streaming applications in distributed network environments. In Proceedings of the 5th Workshop on Workflows in Support of Large-Scale Science (in conjunction with SC 2010), New Orleans, LA, 14 November, 2010.
13.
KappelGPröllBRausch-SchottSRetschitzeggerW. TriGSflow: Active object-oriented workflow management. In Proceedings of the 28th Hawaii International Conference on System Sciences, 1995, pp.727–736.
14.
MillerJAShethAPKochutKJWangXMuruganA. Simulation modeling within workflow technology. In Proceedings of the 27th Conference on Winter Simulation, 1995, pp.612–619.
15.
CardosoJShethA. Semantic e-Workflow Composition. Technical report 02-004, LSDIS Lab, Department of Computer Science, University of Georgia, July2002.
16.
CardosoJLeničM. Web process and workflow path mining using the multimethod approach. Int J Business Intell Data Mining2006; 1: 304–328.
17.
GeorgakopoulosDHornickMShethA. An overview of workflow management: From process modeling to workflow automation infrastructure. J Distrib Parallel Databases1995; 3: 119–153.
KacsukPFarkasZSiposGTothAHermannG. Workflow-level parameter study management in multi-Grid environments by the P-GRADE Grid portal. In International Workshop on Grid Computing Enviornments, 2006.
22.
DeelmanESinghGSuMBlytheJGilAKesselmanC. Pegasus: A framework for mapping complex scientific workflows onto distributed systems. Sci Programm J2005; 13: 219–237.
23.
LudascherBAltintasIBerkleyCHigginsDJaeger-FrankEJonesM. Scientific workflow management and the Kepler system. Concurrency Comput Practice Experience2006; 18: 1039–1605.
BuyyaRMurshedM. GridSim: A toolkit for the modeling and simulation of distributed resource management and scheduling for Grid computing. Concurrency Comput Practice Experience2002; 14: 1175–1220.
26.
WolfJLBansalNHildrumKParekhSRajanDWagleR. SODA: An optimizing scheduler for large-scale stream-based distributed computer systems. In Proceedings of the 9th ACM/IFIP/USENIX International Conference on Middleware, 2008, pp.306–325.
27.
HullDWolstencroftKStevensRGobleCPocockMLiP. Taverna: A tool for building and running workflows of services. Nucleic Acids Res2006; 34: 729–732.
ChurchesDGombasGHarrisonAMaassenJRobinsonCShieldsM. Programming scientific and distributed workflow with Triana services. Concurrency Comput Practice Experience2006; 18: 1021–1037.
LaszewskiGHateganM. Workflow concepts of the Java CoG Kit. J Grid Comput2005; 3: 239–258.
32.
WassermannBEmmerichWButchartBCameronNChenLPatelJ. Sedna: A BPEL-based environment for visual scientific workflow modeling. Workflows for e-Science: Scientific Workflows for Grids. London: Springer, 2007, pp.427–448.
33.
WieczorekMProdanRFahringerT. Scheduling of scientific workflows in the ASKALON Grid environment. ACM SIGMOD Record J2005; 34: 56–62.
34.
MeftaliSDziriACharestLMarquetPDekeyserJL. SOAP Based Distributed Simulation Environment for System-on-Chip (SoC) Design. Research paper, Universite des Sciences et Technologies de Lille, France, 2003.
35.
DeelmanECallaghanSFieldEFrancoeurHGravesRGuptaN. Managing large-scale workflow execution from resource provisioning to provenance tracking: The Cybershake example. In Proceedings of the e-Science Conference, Amsterdam, the Netherlands, December, 2006.
36.
HatzisKPapanikolaouCPentarisGSpirakisPTampakasB. DSS: A Tool for Simulation of Distributed Systems and Protocols Through Communicating Finite State Machines. CTI Internal Report, 1994.
37.
DupuyASchwartzJYeminiYBaconD. NEST: A network simulation and prototyping testbed. ACM Commun1990; 33: 63–74.
38.
BajajSBreslauLEstrinDFallKFloydSHaldarP. Improving Simulation for Nnetwork Research. Technical report, University of Southern California, 1999.
39.
RacherlaGKillianSFifeLLehmannMParekhR. PARSIT: A parallel algorithm reconfiguration simulation tool. In Proceedings of International Conference on High Performance Computing, December, 1995.
40.
UngerHYuenSKropfPBabinG. Similation of communication of nodes in a wide area distributed system. Eurosim Congress, Delft, Netherlands, June2001.
41.
KapitonovaYVGrebnevVALetichevskiiAA. Hardware simulation in distributed computing systems: Methods and tools. Cybernet Syst Anal1995; 31: 350–364.
42.
HesselFLe MarrecPValderramaCARomdhaniMJerrayaAA. MCI-Multilanguage distributed co-simulation tool. In Proceedings of the IFIP WG10.3/WG10.5 International Workshop on Distributed and Parallel Embedded Systems, 1998, pp.191–200.
43.
EstrinG. The SARA system for computer architecture design and modelling. ACM SIGSIM Sim Digest1977; 9: 25–26.
44.
MillerJACardosoJSilverG. Using simulation to facilitate effective workflow adaptation. In Proceedings of the 35th Annual Simulation Symposium, 2002, p.177.
45.
GuYWuQBenoitARobertY. Optimizing end-to-end performance of distributed applications with linear computing pipelines. In Proceedings of the 15th International Conference on Parallel and Distributed Systems, Shenzhen, China, 8–1 December, 2009.
46.
GuYWuQ. Maximizing workflow throughput for streaming applications in distributed environments. In Proceedings of the 19th International Conference on Computer Communication and Networking, Zurich, Switzerland, August, 2010.
47.
WuQGuYLiaoYLuXLinYRaoN. Latency Modeling and Minimization for Large-scale Scientific Workflows in Distributed Network Environments. To appear in Proceedings of the 44th Annual Simulation Symposium, Boston, MA, USA, 4–9 Apr, 2011.
