Grid applications require allocating a large number of heterogeneous tasks to distributed resources. A good allocation is critical for efficient execution. However, many existing grid toolkits use matchmaking strategies that do not consider overall efficiency for the set of tasks to be run. We identify two families of resource allocation algorithms: task-based algorithms, that greedily allocate tasks to resources, and workflow-based algorithms, that search for an efficient allocation for the entire workflow. We compare the behavior of workflow-based algorithms and task-based algorithms, using simulations of workflows drawn from a real application and with varying ratios of computation cost to data transfer cost. We observe that workflow-based approaches have a potential to work better for data-intensive applications even when estimates about future tasks are inaccurate.
Embedding virtual topologies in physical network infrastructure has been an area of active research for the future Internet and network testbeds. Virtual network embedding is also useful for linking virtual compute clusters allocated from cloud providers. Using advanced networking technologies to interconnect distributed cloud sites is a promising way to provision on-demand large-scale virtualized networked systems for production and experimental purposes. In this paper, we study the virtual topology embedding problem in a networked cloud environment, in which a number of cloud provider sites are connected by multi-domain wide-area networks that support virtual networking technology. A user submits a request for a virtual topology, and the system plans a low-cost embedding and orchestrates requests to multiple cloud providers and network transit providers to instantiate the virtual topology according to the plan. We describe an efficient heuristic algorithm design and a prototype implementation within a GENI control framework candidate called ORCA.
Summary form only given. The goal of the Grid Application Development Software (GrADS) project is to provide programming tools and an execution environment to ease program development for the grid. We present recent extensions to the GrADS software framework: 1. A new approach to scheduling workflow computations, applied to a 3D image reconstruction application; 2. A simple stop/migrate/restart approach to rescheduling grid applications, applied to a QR 3. A process-swapping approach to rescheduling, applied to an N-body simulation. Experiments validating these methods were carried out on both the GrADS MacroGrid (a small but functional grid) and the MicroGrid (a controlled emulation of the grid) and the results were demonstrated at the SC2003 conference.
In this paper, we describe the design and implementation of two mechanisms for fault-tolerance and recovery for complex scientific workflows on computational grids. We present our algorithms for over-provisioning and migration, which are our primary strategies for fault-tolerance. We consider application performance models, resource reliability models, network latency and bandwidth and queue wait times for batch-queues on compute resources for determining the correct fault-tolerance strategy. Our goal is to balance reliability and performance in the presence of soft real-time constraints like deadlines and expected success probabilities, and to do it in a way that is transparent to scientists. We have evaluated our strategies by developing a Fault-Tolerance and Recovery (FTR) service and deploying it as a part of the Linked Environments for Atmospheric Discovery (LEAD) production infrastructure. Results from real usage scenarios in LEAD show that the failure rate of individual steps in workflows decreases from about 30% to 5% by using our fault-tolerance strategies.