Stochastic scheduling for multiclass applications with availability requirements in heterogeneous clusters
High availability plays an important role in heterogeneous clusters, where processors operate at different speeds and are not continuously available for processing. Existing scheduling algorithms designed for heterogeneous clusters do not factor in availability. We address in this paper the stochastic scheduling problem for heterogeneous clusters with availability constraints. Each node in a heterogeneous cluster is modeled by its speed and availability, and different classes of tasks submitted to the cluster are characterized by their execution times and availability requirements. To incorporate availability and heterogeneity into stochastic scheduling, we introduce metrics to quantify availability and heterogeneity in the context of multiclass tasks. A stochastic scheduling algorithm SSAC (stochastic scheduling with availability constraints) is then proposed to improve availability of heterogeneous clusters while reducing average response time of tasks. Experimental results show that our algorithm achieves a good trade-off between availability and responsiveness.

title: A file assignment strategy independent of workload characteristic assumptions
abstract: The problem of statically assigning nonpartitioned files in a parallel I/O system has been extensively investigated. A basic workload characteristic assumption of most existing solutions to the problem is that there exists a strong inverse correlation between file access frequency and file size. In other words, the most popular files are typically small in size, while the large files are relatively unpopular. Recent studies on the characteristics of Web proxy traces suggested, however, the correlation, if any, is so weak that it can be ignored. Hence, the following two questions arise naturally. First, can existing algorithms still perform well when the workload assumption does not hold? Second, if not, can one develop a new file assignment strategy that is immune to the workload assumption? To answer these questions, we first evaluate the performance of three well-known file assignment algorithms with and without the workload assumption, respectively. Next, we develop a novel static nonpartitioned file assignment strategy for parallel I/O systems, called static round-robin (SOR), which is immune to the workload assumption. Comprehensive experimental results show that SOR consistently improves the performance in terms of mean response time over the existing schemes.

title: Dynamic relocation of hybrid tasks: Strategies and methodologies
abstract: Reconfiguration-based architectures are increasingly gaining attention of designers due to their benefits of flexibility, re-programmability and high computational performance. The combination of general purpose processors and reconfigurable fabrics (e.g., FPGAs), may provide those valuable characteristics, which are becoming essential for modern and future embedded systems. Such hybrid systems permit the existence of hardware tasks, which shall be properly managed by the operating system, thus allowing for their coexistence with software tasks. Nevertheless, in order to completely exploit this feature, the operating system must be capable of relocating a task between hardware and software execution domains. Runtime relocation of tasks (including preemption and resumption) between two devices following different computation paradigms (parallel vs. instruction based) however is a challenging job. In this work we propose a comprehensive and embracing methodology, which starts from a unified task representation, and goes to the final implementation of such hybrid tasks. For its accomplishment, a framework is proposed to help the user in designing a hybrid task, which also generates automatically the underlying infrastructure that is in charge of performing the dynamic relocation of a hybrid task. In order to prove the applicability of our concept and the efficiency of our framework, a case study is presented including its results.

title: Scheduling security-critical real-time applications on clusters
abstract: Security-critical real-time applications such as military aircraft flight control systems have mandatory security requirements in addition to stringent timing constraints. Conventional real-time scheduling algorithms, however, either disregard applications' security needs and thus expose the applications to security threats or run applications at inferior security levels without optimizing security performance. In recognition that many applications running on clusters demand both real-time performance and security, we investigate the problem of scheduling a set of independent real-time tasks with various security requirements. We build a security overhead model that can be used to reasonably measure security overheads incurred by the security-critical tasks. Next, we propose a security-aware real-time heuristic strategy for clusters (SAREC), which integrates security requirements into the scheduling for real-time applications on clusters. Further, to evaluate the performance of SAREC, we incorporate the earliest deadline first (EDF) scheduling policy into SAREC to implement a novel security-aware real-time scheduling algorithm (SAEDF). Experimental results from both real-world traces and a real application show that SAEDF significantly improves security over three existing scheduling algorithms (EDF, least laxity first, and first come first serve) by up to 266.7 percent while achieving high schedulability.

title: Modeling and improving security of a local disk system for write-intensive workloads
abstract: Since security is of critical importance for modern storage systems, it is imperative to protect stored data from being tampered with or disclosed. Although an increasing number of secure storage systems have been developed, there is no way to dynamically choose security services to meet disk requests' flexible security requirements. Furthermore, existing security techniques for disk systems are not suitable to guarantee desired response times of disk requests. We remedy this situation by proposing an adaptive strategy (referred to as AWARDS) that can judiciously select the most appropriate security service for each write request, while endeavoring to guarantee the desired response times of all disk requests. To prove the efficiency of the proposed approach, we build an analytical model to measure the probability that a disk request is completed before its desired response time. The model also can be used to derive the expected value of disk requests' security levels. Empirical results based on synthetic workloads as well as real I/O-intensive applications show that AWARDS significantly improves overall performance over an existing scheme by up to 358.9% (with an average of 213.4%).

title: No More Energy-Performance Trade-Off: A New Data Placement Strategy for RAID-Structured Storage Systems
abstract: Many real-world applications like Video-On-Demand (VOD) and Web servers require prompt responses to access requests. However, with an explosive increase of data volume and the emerging of faster disks with higher power requirements, energy consumption of disk based storage systems has become a salient issue. To achieve energy-conservation and prompt responses simultaneously, in this paper we propose a novel energy-saving data placement strategy, called Striping-based Energy-Aware (SEA), which can be applied to RAID-structured storage systems to noticeably save energy while providing quick responses. Further, we implement two SEA-powered RAID-based data placement algorithms, SEA0 and SEA5, by incorporating the SEA strategy into RAID-0 and RAID-5, respectively. Extensive experimental results demonstrate that compared with three well-known data placement algorithms Greedy, SP, and HP, SEA0 and SEA5 reduce mean response time on average at least 52.15% and 48.04% while saving energy on average no less than 10.12% and 9.35%, respectively.

title: Approximate Top-k Structural Similarity Search over XML Documents
abstract: With the development of XML applications, such as Digital Library, XML subscribe/publish system, and other XML repositories, top-k structural similarity search over XML documents is attracting more attention. The similarity of two XML documents can be measured by using the edit distance defined between XML trees in previous work. Since the computation of edit distances is time consuming, some recent work presented some approaches to calculate edit distance by using structural summaries to improve the algorithm performance. However, most existing algorithms for calculating edit distance between trees ignore the fact that nodes in a tree may be of different significance, and the same edit operation costs are assumed inappropriately for all nodes in XML document tree. This paper addresses this problem by proposing a summary structure which could be used to make the tree-based edit distance more rational; furthermore, a novel weighting scheme is proposed to indicate that some nodes are more important than others with respect for structural similarity. We introduce a new cost model for computing structural distance and takes weight information into account for nodes in distance computation in this paper. Compared with former techniques, our approach can approximately answer the top-k queries efficiently. We verify this approach through a series of experiments, and the results show that using weighted structural summaries for top-k queries is efficient and practical.

title: A Reinforcement Learning Approach for Host-Based Intrusion Detection Using Sequences of System Calls
abstract: Intrusion detection has emerged as an important technique for network security. Due to the complex and dynamic properties of intrusion behaviors, machine learning and data mining methods have been widely employed to optimize the performance of intrusion detection systems (IDSs). However, the results of existing work still need to be improved both in accuracy and in computational efficiency. In this paper, a novel reinforcement learning approach is presented for host-based intrusion detection using sequences of system calls. A Markov reward process model is introduced for modeling the behaviors of system call sequences and the intrusion detection problem is converted to predicting the value functions of the Markov reward process. A temporal different learning algorithm using linear basis functions is used for value function prediction so that abnormal temporal behaviors of host processes can be predicted accurately and efficiently. The proposed method has advantages over previous algorithms in that the temporal property of system call data is well captured in a natural and simple way and better intrusion detection performance can be achieved. Experimental results on the MIT system call data illustrate that compared with previous work, the proposed method has better detection accuracy with low training costs.