EMPEROR: An OGSA Grid Meta-Scheduler Based on Dynamic Resource Predictions

Scheduling constitutes an integral feature of Grid computing infrastructures, being also a key to realizing several of the Grid promises. In particular, scheduling can maximize the resources available to end users, accelerate the execution of jobs, while also supporting scalable and autonomic management of the resources comprising a Grid. Grid scheduling functionality hinges on middleware components called meta-schedulers, which undertake to automatically distribute jobs across the dispersed heterogeneous resources of a Grid. In this paper we present the design and implementation of a Grid meta-scheduler, which we call EMPEROR. EMPEROR provides a framework for implementing scheduling algorithms based on performance criteria. In implementing a particular instantiation of this framework, we have devised models for predicting host load and memory resources, and accordingly for estimating the running time of a task. These models hinge on time series analysis techniques and take into account results of the cluster computing literature. Apart from incorporating these models, EMPEROR provides fully fledged Grid scheduling functionality, which complies with OGSA standards as the later are reflected in the Globus toolkit. Specifically, EMPEROR interfaces to Globus middleware services (i.e., GSI, MDS, GRAM) towards discovering resources, implementing the scheduling algorithm and ultimately submitting jobs to local scheduling systems. By and large, EMPEROR is one of the few standards based meta-schedulers making use of dynamic scheduling information.     

Job Allocation Strategies with User Run Time Estimates for Online Scheduling in Hierarchical Grids

We address non-preemptive non-clairvoyant online scheduling of parallel jobs on a Grid. We consider a Grid scheduling model with two stages. At the first stage, jobs are allocated to a suitable Grid site, while at the second stage, local scheduling is independently applied to each site. We analyze allocation strategies depending on the type and amount of information they require. We conduct a comprehensive performance evaluation study using simulation and demonstrate that our strategies perform well with respect to several metrics that reflect both user- and system-centric goals. Unfortunately, user run time estimates and information on local schedules does not help to significantly improve the outcome of the allocation strategies. When examining the overall Grid performance based on real data, we determined that an appropriate distribution of job processor requirements over the Grid has a higher performance than an allocation of jobs based on user run time estimates and information on local schedules. In general, our experiments showed that rather simple schedulers with minimal information requirements can provide a good performance.     

A Resource Selection System for Cycle Stealing in GPU Grids

This paper presents a resource selection system for exploiting graphics processing units (GPUs) as general-purpose computational resources in desktop Grid environments. Our system allows Grid users to share remote GPUs, which are traditionally dedicated to local users who directly see the display output. The key contribution of the paper is to develop this novel system for non-dedicated environments. We first show criteria for defining idle GPUs from the Grid users’ point of view. Based on these criteria, our system uses a screensaver approach with some sensors that detect idle resources at a low overhead. The idea for this lower overhead is to avoid GPU intervention during resource monitoring. Detected idle GPUs are then selected according to a matchmaking service, making the system adaptive to the rapid advance of GPU architecture. Though the system itself is not yet interoperable with current desktop Grid systems, our idea can be applied to screensaver-based systems such as BOINC. We evaluate the system using Windows PCs with three generations of nVIDIA GPUs. The experimental results show that our system achieves a low overhead of at most 267 ms, minimizing interference to local users while maximizing the performance delivered to Grid users. Some case studies are also performed in an office environment to demonstrate the effectiveness of the system in terms of the amount of detected idle time.     

Online algorithms for advance resource reservations

We consider the problem of providing QoS guarantees to Grid users through advance reservation of resources. Advance reservation mechanisms provide the ability to allocate resources to users based on agreed-upon QoS requirements and increase the predictability of a Grid system, yet incorporating such mechanisms into current Grid environments has proven to be a challenging task due to the resulting resource fragmentation. We use concepts from computational geometry to present a framework for tackling the resource fragmentation, and for formulating a suite of scheduling strategies. We also develop efficient implementations of the scheduling algorithms that scale to large Grids. We conduct a comprehensive performance evaluation study using simulation, and we present numerical results to demonstrate that our strategies perform well across several metrics that reflect both user- and system-specific goals. Our main contribution is a timely, practical, and efficient solution to the problem of scheduling resources in emerging on-demand computing environments.     

Resource scheduling with conflicting objectives in grid environments: Model and evaluation

The paper is to consider resource scheduling with conflicting objectives in the grid environment. The objectives of the grid users, the grid resources and the grid system clash with each other. Grid users want to access enough system resources to achieve the desired level of quality of service (QoS). Resource providers pay more attention to the performance of their resources. Our resource scheduling employs market strategies to determine which jobs are executed at what time on which resources and at what prices. A grid resource provider uses its utility function to maximize its profit and a grid user uses its utility function to complete tasks while minimizing its spending. The paper proposes grid system objective optimization scheduling that provides a joint optimization of objectives for both the resource provider and grid user, which combines the benefits of both resource provider objective optimization and user objective optimization. Experiments are designed to study the performances of three resource-scheduling optimization algorithms. Performance metrics are classified into efficiency metrics, utility metrics and time metrics.     

A multi-dimensional scheduling scheme in a Grid computing environment

In this paper, we propose a novel distributed resource-scheduling algorithm capable of handling multiple resource requirements for jobs that arrive in a Grid computing environment. In our proposed algorithm, referred to as multiple resource scheduling (MRS) algorithm, we take into account both the site capabilities and the resource requirements of jobs. The main objective of the algorithm is to obtain a minimal execution schedule through efficient management of available Grid resources. We first propose a model in which the job and site resource characteristics can be captured together and used in the scheduling algorithm. To do so, we introduce the concept of a n-dimensional virtual map and resource potential. Based on the proposed model, we conduct rigorous simulation experiments with real-life workload traces reported in the literature to quantify the performance. We compare our strategy with most of the commonly used algorithms in place on performance metrics such as job wait times, queue completion times, and average resource utilization. Our combined consideration of job and resource characteristics is shown to render high-performance with respect to above-mentioned metrics in the environment. Our study also reveals the fact that MRS scheme has a capability to adapt to both serial and parallel job requirements, especially when job fragmentation occurs. Our experimental results clearly show that MRS outperforms other strategies and we highlight the impact and importance of our strategy.     

Meeting security and user behavior requirements in Grid scheduling

Most of current research in Grid computing is still focused on the improvement of the performance of Grid schedulers. However, unlike traditional scheduling, in Grid systems there are other important requirements to be taken into account. One such a requirement is the secure scheduling, namely achieving an efficient allocation of tasks to reasonable trustful resources. In this paper we formalize the Grid scheduling problem as a non-cooperative non-zero sum game of the Grid users in order to address the security requirements. The premise of this model is that in a large-scale Grid, the cooperation among all users in the system is unlikely to happen. The users’ cost of playing the game is interpreted as a total cost of the secure job execution in Grid. The game cost function is minimized, at global (Grid) and local (users) levels, by using four genetic-based hybrid meta-heuristics. We have evaluated the proposed model under the heterogeneity, the large-scale and dynamics conditions using a Grid simulator. The relative performance of four hybrid schedulers is measured by the makespan and flowtime metrics. The obtained results suggested that it is more resilient for the Grid users to pay some additional scheduling cost, due to verification of the security conditions, instead of taking the risk of assigning their tasks to unreliable resources.     

Market-oriented Grids and Utility Computing: The State-of-the-art and Future Directions

Traditional resource management techniques (resource allocation, admission control and scheduling) have been found to be inadequate for many shared Grid and distributed systems, that consist of autonomous and dynamic distributed resources contributed by multiple organisations. They provide no incentive for users to request resources judiciously and appropriately, and do not accurately capture the true value, importance and deadline (the utility) of a user’s job. Furthermore, they provide no compensation for resource providers to contribute their computing resources to shared Grids, as traditional approaches have a user-centric focus on maximising throughput and minimising waiting time rather than maximising a providers own benefit. Consequently, researchers and practitioners have been examining the appropriateness of ‘market-inspired’ resource management techniques to address these limitations. Such techniques aim to smooth out access patterns and reduce the chance of transient overload, by providing a framework for users to be truthful about their resource requirements and job deadlines, and offering incentives for service providers to prioritise urgent, high utility jobs over low utility jobs. We examine the recent innovations in these systems (from 2000–2007), looking at the state-of-the-art in price setting and negotiation, Grid economy management and utility-driven scheduling and resource allocation, and identify the advantages and limitations of these systems. We then look to the future of these systems, examining the emerging ‘Catallaxy’ market paradigm. Finally we consider the future directions that need to be pursued to address the limitations of the current generation of market oriented Grids and Utility Computing systems.     

CP2: Cryptographic privacy protection framework for online social networks

In Online Social Networks (OSNs), users interact with each other by sharing their personal information. One of the concerns in OSNs is how user privacy is protected since the OSN providers have full control over users’ data. The OSN providers typically store users’ information permanently; the privacy controls embedded in OSNs offer few options to users for customizing and managing the dissipation of their data over the network. In this paper, we propose an efficient privacy protection framework for OSNs that can be used to protect the privacy of users’ data and their online social relationships from third parties. The recommended framework shifts the control over data sharing back to the users by providing them with flexible and dynamic access policies. We employ a public-key broadcast encryption scheme as the cryptographic tool for managing information sharing with a subset of a user’s friends. The privacy and complexity evaluations show the superiority of our approach over previous.     

Scalable dimensioning of resilient Lambda Grids

Grids consist of the aggregation of numerous dispersed computational, storage and network resources, able to satisfy even the most demanding computing jobs. Due to the data-intensive nature of Grid jobs, there is an increasing interest in Grids using optical transport networks as this technology allows for the timely delivery of large amounts of data. Such Grids are commonly referred to as Lambda Grids.

An important aspect of Grid deployment is the allocation and activation of installed network capacity, needed to transfer data and jobs to and from remote resources. However, the exact nature of a Grid’s network traffic depends on the way arriving workload is scheduled over the various Grid sites. As Grids possibly feature high numbers of resources, jobs and users, solving the combined Grid network dimensioning and workload scheduling problem requires the use of scalable mathematical methods such as Divisible Load Theory (DLT). Lambda Grids feature additional complexity such as wavelength granularity and continuity or conversion constraints must be enforced. Additionally, Grid resources cannot be expected to be available at all times. Therefore, the extra complexity of resilience against possible resource failures must be taken into account when modelling the combined Grid network dimensioning and workload scheduling problem, enforcing the need for scalable solution methods. In this work, we tackle the Lambda Grid combined dimensioning and workload scheduling problem and incorporate single-resource failure or unavailability scenarios. We use Divisible Load Theory to tackle the scalability problem and compare non-resilient lambda Grid dimensioning to the dimensions needed to survive single-resource failures. We distinguish three failure scenarios relevant to lambda Grid deployment: computational element, network link and optical cross-connect failure. Using regular network topologies, we derive analytical bounds on the dimensioning cost. To validate these bounds, we present comparisons for the resulting Grid dimensions assuming a 2-tier Grid operation as a function of varying wavelength granularity, fiber/wavelength cost models, traffic demand asymmetry and Grid scheduling strategy for a specific set of optical transport networks.     

Cross-layer optimization policy for QoS scheduling in computational grid

This paper presents a cross-layer quality of service (QoS) optimization policy for computational grid. Efficient QoS management is critical for computational grid to meet heterogeneity and dynamics of resources and users’ requirements. There are different QoS metrics at different layers of computational grid. To improve perceived QoS by end users over computational grid, QoS supports can be addressed in different layers, including application layer, collective layer, fabric layer and so forth. The paper tackles cross-layer grid QoS optimization as optimization decomposition, each layer corresponds to a decomposed subproblem. The proposed policy produces an optimal set of grid resources, service compositions and user's payments at the fabric layer, collective layer and application layer respectively to maximize global grid QoS. The cross-layer optimization problem decomposes into three subproblems: grid resource allocation problem, service composing and user satisfaction degree maximization problem, all of which interact through the optimal variables for capacities of grid resources and service demand. In order to coordinate the subproblems, cross-layer QoS feedback mechanism is established to ensure different layer interactions. The simulations are conducted to validate the efficiency of the proposed policy.     

On designing usable and secure recognition-based graphical authentication mechanisms

In this article we present the development of a new, web-based, graphical authentication mechanism called ImagePass. The authentication mechanism introduces a novel feature based on one-time passwords that increases the security of the system without compromising its usability. Regarding usability, we explore the users’ perception of recognition-based, graphical authentication mechanisms in a web environment. Specifically, we investigate whether the memorability of recognition-based authentication keys is influenced by image content. We also examine how the frequency of use affects the usability of the system and whether user training via mnemonic instructions improves the graphical password recognition rate. The design and development process of the proposed system began with a study that assessed how the users remember abstract, face or single-object images, and showed that single-object images have a higher memorability rate. We then proceeded with the design and development of a recognition-based graphical authentication mechanism, ImagePass, which uses single-objects as the image content and follows usable security guidelines. To conclude the research, in a follow-up study we evaluated the performance of 151 participants under different conditions. We discovered that the frequency of use had a great impact on users’ performance, while the users’ gender had a limited task-specific effect. In contrast, user training through mnemonic instructions showed no differences in the users’ authentication metrics. However, a post-study, focus-group analysis revealed that these instructions greatly influenced the users’ perception for memorability and the usability of the graphical authentication. In general, the results of these studies suggest that single-object graphical authentication can be a complementary replacement for traditional passwords, especially in ubiquitous environments and mobile devices.     

Using a Simple Prioritisation Mechanism to Effectively Interoperate Service and Opportunistic Grids in the EELA-2 e-Infrastructure

Grids currently in production can be broadly classified as either service Grids, composed of dedicated resources, or opportunistic Grids that harvest the computing power of non-dedicated resources when they are idle. While a service Grid provides high and well defined levels of quality of service, an opportunistic Grid provides only a best-effort service. Nevertheless, since opportunistic Grids do not require resources to be fully dedicated to the Grid, they have the potential to assemble a much larger number of resources. Moreover, these Grids cater very well to the execution of the so-called embarrassingly parallel applications, a type of application that is frequently found in practice, and that comprises the largest portion of the typical workload processed in production Grid systems. The EELA-2 e-infrastructure is comprised of a service Grid and an opportunistic Grid that federates computing resources from scientific institutions in both Europe and Latin America. Due to the complementary characteristics of these two types of Grids, a lot of attention has recently been placed in how to interoperate them. In this paper we focus on the less studied problem of assessing the feasibility of such interoperation. We analyse different prioritisation policies that define when the resources of one Grid can be used to run jobs originating from the other. Our results show that in the absence of a suitable prioritisation policy, the benefits that the users of one Grid may have, frequently come with an important negative impact on the users of the other Grid. We also show that a simple reciprocation mechanism is capable of arbitrating the interoperation in such a way that, whenever possible, users profit from the interoperation and, in no case, this benefit leads to a noticeable reduction on the quality of service that the users would experience were the Grids not to interoperate. We conclude discussing how we have implemented, in the context of the EELA-2 project, this prioritisation mechanism, allowing the effective interoperation of a service Grid based on the gLite middleware with an opportunistic Grid that uses the OurGrid middleware.     

A Grid resource brokering strategy based on resource and network performance in Grid

To achieve high performance distributed data access and computing in Grid environment, monitoring of resource and network performance is vital. Our proposed Grid network monitoring architecture is modeled by the Grid scheduler. The proposed Grid network monitoring retrieves network metrics using sensors as network monitoring tools. The mobile agents are migrated to start the sensors to measure the network metrics in all Grid Resources from the Resource Broker. The raw data provided by the monitoring tools is used to produce a high level view of the Grid through the set of internal cost functions. The network cost function is formed by combining various network metrics such as bandwidth, Round Trip Time, jitter and packet loss to measure the network performance. This paper presents the Grid Resource Brokering strategy which analyzes the network metrics along with the resource metrics for the selection of the Grid resource to submit the job and the proposed approach is integrated with CARE Resource Broker (CRB) for job submission. The experimental results are evident for the minimization of job completion time for the submitted job. The simulation results also prove that the more number of jobs are completed with the proposed strategy which influences the better utilization of the Grid resources.     

Resource brokering using a multi‐site resource allocation strategy for computational grids

Grid computing employs heterogeneous resources which may be installed on different platforms, hardware/software, computer architectures, and perhaps using different computer languages to solve large‐scale computational problems. As many more Grids are being developed worldwide, the number of multi‐institutional collaborations is growing rapidly. However, to realize Grid computing's full potential, it is expected that Grid participants must be able to share one another's resources. This paper presents a resource broker that employs the multi‐site resource allocation (MSRA) strategy and the dynamic domain‐based network information model that we propose to allocate Grid resources to submitted jobs, where the Grid resources may be dispersed at different sites, and owned and governed by different organizations or institutes. The jobs and resources may also belong to different clusters/sites. Resource statuses collected by the Ganglia, and network bandwidths gathered by the Network Weather Service, are both considered in the proposed scheduling approach. A dynamic domain‐based model for network information measurement is also proposed to choose the most appropriate resources that meet the jobs' execution requirements. Experimental results show that MSRA outperformed the other tested strategies. Copyright © 2010 John Wiley & Sons, Ltd.     

Model-based services convergence and multi-clouds integration

With the development of cloud computing, IT users (individuals, enterprises and even public services providers) are transferring their jobs or businesses to public online services provided by professional information service companies. These information service companies provide applications as public resources to support the business operation of their customers. However, no cloud computing service vendor (CCSV) can satisfy the full functional information system requirements of its customers. As a result, its customers often have to simultaneously use services distributed in different clouds and do some connectivity jobs manually. Services convergence and multi-clouds integration will lead to new business models and trigger new integration technologies that provide solutions to satisfy IT users’ complicated requirements. This paper firstly reviews the development of cloud computing from business and technical viewpoints and then discusses requirements and challenges of services convergence and multi-clouds integrations. Thirdly, a model based architecture of multi-clouds integration is provided. Business logic modelling for cross-organizational collaboration, service modelling and operation modelling methods with relative model mapping technology are discussed in detail. Some key enabling technologies are also developed. At last, case studies are presented to illustrate the implementation of the technologies developed in the paper.     

Using clouds to scale grid resources: An economic model

Infrastructure as a Service clouds are a flexible and fast way to obtain (virtual) resources as demand varies. Grids, on the other hand, are middleware platforms able to combine resources from different administrative domains for task execution. Clouds can be used by grids as providers of devices such as virtual machines, so they only use the resources they need. But this requires grids to be able to decide when to allocate and release those resources. Here we introduce and analyze by simulations an economic mechanism (a) to set resource prices and (b) resolve when to scale resources depending on the users’ demand. This system has a strong emphasis on fairness, so no user hinders the execution of other users’ tasks by getting too many resources.Our simulator is based on the well-known GridSim software for grid simulation, which we expand to simulate infrastructure clouds. The results show how the proposed system can successfully adapt the amount of allocated resources to the demand, while at the same time ensuring that resources are fairly shared among users.     

A software tool for semi-automatic gridification of resource-intensive Java bytecodes and its application to ray tracing and sequence alignment

Computational Grids deliver the necessary computational infrastructure to perform resource-intensive computations such as the ones that solve the problems scientists are facing today. Exploiting Computational Grids comes at the expense of explicitly adapting the ordinary software implementing scientific problems to take advantage of Grid resources, which unavoidably requires knowledge on Grid programming. The recent notion of “gridifying” ordinary applications, which is based on semi-automatically deriving a Grid-aware version from the compiled code of a sequential application, promises users to be relieved from the requirement of manual usage of Grid APIs within their source codes. In this paper, we describe a novel gridification tool that allows users to easily parallelize Java applications on Grids. Extensive experiments with two real-world applications - ray tracing and sequence alignment - suggest that our approach provides a convenient balance between ease of gridification and Grid resource exploitation compared to manually using Grid APIs for gridifying ordinary applications.     

Characterization of Bandwidth-Aware Meta-Schedulers for Co-Allocating Jobs Across Multiple Clusters

In this paper, we present a bandwidth-centric job communication model that captures the interaction and impact of simultaneously co-allocating jobs across multiple clusters. We compare our dynamic model with previous research that utilizes a fixed execution time penalty for co-allocated jobs. We explore the interaction of simultaneously co-allocated jobs and the contention they often create in the network infrastructure of a dedicated computational multi-cluster.We also present several bandwidth-aware co-allocating meta-schedulers. These schedulers take inter-cluster network utilization into account as a means by which to mitigate degraded job run-time performance. We make use of a bandwidth-centric parallel job communication model that captures the time-varying utilization of shared inter-cluster network resources. By doing so, we are able to evaluate the performance of multi-cluster scheduling algorithms that focus not only on node resource allocation, but also on shared inter-cluster network bandwidth.