Computing and Information Systems - Theses
Permanent URI for this collection
Search Results
1 - 7 of 7
-
ItemCost-efficient resource provisioning for large-scale graph processing systems in cloud computing environments( 2018)A large amount of data that is being generated on Internet every day is in the form of graphs. Many services and applications namely as social networks, Internet of Things (IoT), mobile applications, business applications, etc. in which every data entity can be considered as a vertex and the relationships between entities shape the edges of a graph, are in this category. Since 2010, exclusive large-scale graph processing frameworks are being developed to overcome the inefficiency of traditional processing solutions such as MapReduce. However, most frameworks are designed to be employed on high performance computing (HPC) clusters which are only available to whom can afford such infrastructure. Cloud computing is a new computing paradigm that offers unprecedented features such as scalability, elasticity and pay-as-you-go billing model and is accessible to everyone. Nevertheless, the advantages that cloud computing can bring to the architecture of large-scale graph processing systems are less studied. Resource provisioning and management is a critical part of any processing system in cloud environments. To provide the optimized amount of resources for a particular operation, several factors such as monetary cost, throughput, scalability, network performance, etc. can be taken into consideration. In this thesis, we investigate and propose novel solutions and algorithms for cost-efficient resource provisioning for large-scale graph processing systems. The outcome is a series of research works that increase the performance of such processing by making it aware of the operating environment while decreasing the dollar cost significantly. We have particularly made the following contributions: 1. We introduced iGiraph, a cost-efficient framework for processing large-scale graphs on public clouds. iGiraph also provides a new graph algorithm categorization and processes the graph accordingly. 2. To demonstrate the impact of network on the processing in cloud environment, we developed two network-aware algorithms that utilize network factors such as traffic, bandwidth and also the computation power. 3. We developed an auto-scaling technique to take advantage of resource heterogeneity on clouds. 4. We introduced a large-scale graph processing service for clouds where we consider the service level agreement (SLA) requirements in the operations. The service can handle multiple processing requests by its new prioritization and provisioning approach.
-
ItemScheduling and rostering with learning constraint solvers( 2016)In this research we investigate using Constraint Programming (CP) with Lazy Clause Generation (LCG), that is, constraint solvers with nogood learning, to tackle a number of well known scheduling, rostering, and planning problems. We extend a number of CP constraints to be useable in an LCG solver, and we investigate alternative search strategies that use the Unsatisfiable Cores, i.e. reasons for failure returned by the LCG solver, to guide the search for optimal solutions. We give comprehensive analysis and experiments. These experiments show that while adding more and more sophisticated constraint propagators to LCG delivers diminishing returns, unsatisfiable-core optimization which leverages the infrastructure provided by LCG can deliver significant benefits which are unavailable in CP without LCG. Overall, we demonstrate that LCG is a highly competitive technology for solving realistic industrial scheduling and rostering problems to optimality, allowing that the problems are smaller than those tackled by competing algorithms which do not prove optimality.
-
ItemResource provisioning and scheduling algorithms for scientific workflows in cloud computing environments( 2016)Scientific workflows describe a series of computations that enable the analysis of data in a structured and distributed manner. Their importance is exacerbated in todays big data era as they become a compelling mean to process and extract knowledge from the ever-growing data produced by increasingly powerful tools such as telescopes, particle accelerators, and gravitational wave detectors. Due to their large-scale nature, scheduling algorithms are key to efficiently automate their execution in distributed environments, and as a result, to facilitate and accelerate the pace of scientific progress. The emergence of the latest distributed system paradigm, cloud computing, brings with it tremendous opportunities to run workflows at low costs without the need of owning any infrastructure. In particular, Infrastructure as a Service (IaaS) clouds, offer an easily accessible, flexible, and scalable infrastructure for the deployment of these scientific applications by providing access to a virtually infinite pool of resources that can be acquired, configured, and used as needed and are charged on a pay-per-use basis. This thesis investigates novel resource provisioning and scheduling approaches for scientific workflows in IaaS clouds. They address fundamental challenges that arise from the multi-tenant, resource-abundant, and elastic resource model and are capable of fulfilling a set of quality of service requirements expressed in terms of execution time and cost. It advances the field by making the following key contributions: 1. A taxonomy and survey of the state-of-the-art scientific workflow scheduling algorithms designed exclusively for IaaS clouds. 2. A novel static scheduling algorithm that leverages Particle Swarm Optimization to generate a workflow execution and resource provisioning plan that minimizes the infrastructure cost while meeting a deadline constraint. 3. A hybrid algorithm based on a variation of the Unbounded Knapsack Problem that finds a trade-off between making static decisions to find better-quality schedules and dynamic decisions to adapt to unexpected delays. 4. A scalable algorithm that combines heuristics and two different Integer Programming models to generate schedules that minimize the execution time of the work- flow while meeting a budget constraint. 5. The implementation of a cloud resource management module and its integration to an existing Workflow Management System.
-
ItemRobust and fault-tolerant scheduling for scientific workflows in cloud computing environments( 2015)Cloud environments offer low-cost computing resources as a subscription-based service. These resources are elastically scalable and dynamically provisioned. Furthermore, new pricing models have been pioneered by cloud providers that allow users to provision resources and to use them in an efficient manner with significant cost reductions. As a result, scientific workflows are increasingly adopting cloud computing. Scientific workflows are used to model applications of high throughput computation and complex large scale data analysis. However, existing works on workflow scheduling in the context of clouds are either on deadline or cost optimization, ignoring the necessity for robustness. Cloud is not a utopian environment. Failures are inevitable in such large complex distributed systems. It is also well studied that cloud resources experience fluctuations in the delivered performance. Therefore, robust and fault-tolerant scheduling that handles performance variations of cloud resources and failures in the environment is essential in the context of clouds. This thesis presents novel workflow scheduling heuristics that are robust against performance variations and fault-tolerant towards failures. Here, we have presented and evaluated static and just-in-time heuristics using multiple fault-tolerant techniques. We have used different pricing models offered by the cloud providers and proposed schedules that are fault-tolerant and at the same time minimize time and cost. We have also proposed resource selection policies and bidding strategies for spot instances. The proposed heuristics are constrained by either deadline and budget or both. These heuristics are evaluated with the prominent state-of-the art workflows. Finally, we have also developed a multi-cloud framework for the Cloudbus workflow management system, which has matured with years of research and development at the CLOUDS Lab in the University of Melbourne. This multi-cloud framework is demonstrated with a private and a public cloud using an astronomy workflow that creates a mosaic of astronomic images. In summary, this thesis provides effective fault-tolerant scheduling heuristics for workflows on cloud computing platforms, such that performance variations and failures can be mitigated whilst minimizing cost and time.
-
ItemResource provisioning in spot market-based cloud computing environments( 2014)Recently, cloud computing providers have started offering unused computational resources in the form of dynamically priced virtual machines (VMs), also known as "spot instances". In spite of the apparent economical advantage, an intermittent nature is inherent to these biddable resources, which may cause VM unavailability. When an out-of-bid situation occurs, i.e. the current spot price goes above the user's maximum bid, spot instances are terminated by the provider without prior notice. This thesis presents a study on employing cloud computing spot instances as a means of executing computational jobs on cloud computing resources. We start by proposing a resource management and job scheduling policy, named SpotRMS, which addresses the problem of running deadline-constrained compute-intensive jobs on a pool of low-cost spot instances, while also exploiting variations in price and performance to run applications in a fast and economical way. This policy relies on job runtime estimations to decide what are the best types of spot instances to run each job and when jobs should run. It is able to minimise monetary spending and make sure jobs finish within their deadlines. We also propose an improvement for SpotRMS, that addresses the problem of running compute-intensive jobs on a pool of intermittent virtual machines, while also aiming to run applications in a fast and economical way. To mitigate potential unavailability periods, a multifaceted fault-aware resource provisioning policy is proposed. Our solution employs price and runtime estimation mechanisms, as well as three fault tolerance techniques, namely checkpointing, task duplication and migration. As a further improvement, we equip SpotRMS with prediction-assisted resource provisioning and bidding strategies. Our results demonstrate that both costs savings and strict adherence to deadlines can be achieved when properly combining and tuning the policy mechanisms. Especially, the fault tolerance mechanism that employs migration of VM state provides superior results in virtually all metrics. Finally, we employ a statistical model of spot price dynamics to artificially generate price patterns of varying volatility. We then analyse how SpotRMS performs in environments with highly variable price levels and more frequent changes. Fault tolerance is shown to be even more crucial in such scenarios.
-
ItemImproving scheduling by learning( 2011)Scheduling problems appear in many industrial problems with different facets and requirements of a solution. A solution is a schedule of a set of activities subject to constraints such as precedence relations and resource restrictions on the maximum number of concurrent activities. This dissertation presents new deductive techniques for precedence and cumulative resource constraints in constraint programming to improve solution processes of combinatorial scheduling problems, in particular, and combinatorial problems, in general. Due to their intractability, many schedulers either solve a simplified problem or are tailored to a specific problem, but are inflexible with respect to changes in the problem statement. Constraint Programming (CP) offers a powerful framework for combinatorial problems which also tackles the demand of flexibility of changes in the problem statement due to a strict separation of problem modelling, search algorithms, and high-specialised deduction techniques. Moreover, recent advanced CP solvers such as lazy clause generation (LCG) additionally include sophisticated conflict learning technologies. Their efficiency depends, amongst other things, on reusable explanations formulated by deductive algorithms. Unit two variable per inequality (UTVPI) constraints are one of the largest integer constraint class that is solvable in polynomial time. These constraints can model precedence relations between activities. A new theoretical result about reasoning of UTVPI systems is shown, based on that, new incremental deductive algorithms are created for manipulating UTVPI constraints including satisfiability, implication, and explanation. These algorithms are asymptotically faster on sparse UTVPI systems than current algorithms. Cumulative constraints enforce resource restrictions in scheduling problems. We show how, by adding explanation to the cumulative constraint in an LCG solver, we can solve resource-constrained project scheduling problems far faster than other comparable methods. Furthermore, a complete LCG-based approach including cumulative constraints is developed for an industrial carpet cutting problem. This approach outperforms the current incomplete method on all industrial instances provided.
-
ItemMeta scheduling for market-oriented grid and utility computing( 2010)Grid computing enables the sharing and aggregation of autonomous IT resources to deliver them as computing utilities to end users. The management of the Grid environment is a complex task as resources are geographically distributed, heterogeneous and autonomous in nature, and their users are self-interested. In utility-oriented Grids, users define their application requirements and compete to access the most efficient and cheapest resources. Traditional resource management systems and algorithms are based on system-centric approaches which do not take into account individual requirements and interests. To this end, market-oriented scheduling is an adequate way to solve the problem. But current market-oriented systems generally, either try to maximise one user’s utility or one provider’s utility. Such approaches fail to solve the problem of contention for cheap and efficient resources which may lead to unnecessary delays in job execution and underutilisation of resources. To address these problems, this thesis proposes a market-oriented meta-scheduler called “Meta-Broker”, which not only coordinates the resource demand but also allocates the best resources to users in terms of monetary and performance costs. The thesis results demonstrate that considerable cost reduction and throughput can be gained by adopting our proposed approach. The meta-broker has a semi-decentralised architecture, where only scheduling decisions are made by the meta-broker while job submission, execution and monitoring are delegated to user and provider middleware. This thesis also investigates market-oriented meta-scheduling algorithms which aim to maximise the utility of participants. The market-oriented algorithms consider Quality of Service (QoS) requirements of multiple users to map jobs against autonomous and heterogeneous resources. This thesis also presents a novel Grid Market Exchange architecture which provides the flexibility to users in choosing their own negotiation protocol for resource trading. The key research findings and contributions of this thesis are: - The consideration of QoS requirements of all users is necessary for maximising users’ utility and utilisation of resources. The uncoordinated scheduling of applications by personalised user-brokers leads to overloading of cheap and efficient resources. - It is important to exploit the heterogeneity between different resource sites/data centers while scheduling jobs to maximise the provider’s utility. This consideration not only reduce energy cost of computing infrastructure by 33% on average, but also enhance the efficiency of resources in terms of carbon emissions. - By considering both system metrics and market parameters, we can enable more effective scheduling which maximises the utility of both users and resource providers.