Search

The utilization bounds for partitioned multiprocessor scheduling are a function of task allocation algorithms and the schedulability conditions selected for uniprocessor scheduling algorithms. In this paper, we use rate-monotonic scheduling on each processor and present the lower and upper limits of the utilization bounds for all reasonable task allocation heuristics. Unlike previous work, the hyperbolic bound due to Bini , instead of the Liu & Layland bound, is adopted to do the schedulability test on uniprocessors. We also derive the utilization bounds with respect to the worst fit allocation algorithm and reasonable allocation decreasing heuristics, and the two bounds are found to coincide with the worst and best achievable multiprocessor utilization bounds, respectively. Analytical and experimental results show that the proposed utilization bound performs better than the existing bound under quite a lot of parameter settings, and combining these two bounds together can significantly (up to 3 times) increase the number of schedulable task sets with little extra overhead. [ABSTRACT FROM AUTHOR]

In attempts to exploit a diverse set of resources in grids efficiently, numerous assays in resource management, particularly scheduling, have been made. The primary objective of these efforts is the minimization of application completion time; however, they tend to achieve this objective at the expense of redundant resource usage. This paper investigates the problem of scheduling workflow applications on grids and presents a novel scheduling algorithm for the solution of this problem. Our algorithm performs the scheduling by accounting for both completion time and resource usage-dual objectives. Since the performance of grid resources changes dynamically and the accurate estimation of their performance is very difficult, our algorithm incorporates rescheduling to deal with unforeseen performance fluctuations effectively. The paper provides a comparative evaluation study conducted by using an extensive set of experiments. The study demonstrates that the proposed algorithm delivers promising performance in three respects: completion time, resource utilization, and robustness to resource-performance fluctuations. [ABSTRACT FROM AUTHOR]

In the complex software systems, software agents always need to negotiate with other agents within their physical and social contexts when they execute tasks. Obviously, the capacity of a software agent to execute tasks is determined by not only itself but also its contextual agents; thus, the number of tasks allocated on an agent should be directly proportional to its self-owned resources as well as its contextual agents' resources. This paper presents a novel task allocation model based on the contextual resource negotiation. In the presented task allocation model, while a task comes to the software system, it is first assigned to a principal agent that has high contextual enrichment factor for the required resources; then, the principal agent will negotiate with its contextual agents to execute the assigned task. However, while multiple tasks come to the software system, it is necessary to make load balancing to avoid overconvergence of tasks at certain agents that are rich of contextual resources. Thus, this paper also presents a novel load balancing method: if there are overlarge number of tasks queued for a certain agent, the capacities of both the agent itself and its contextual agents to accept new tasks will be reduced. Therefore, in this paper, the task allocation and load balancing are implemented according to the contextual resource distribution of agents, which can be well suited for the characteristics of complex software systems; and the presented model can reduce more communication costs between allocated agents than the previous methods based on self-owned resource distribution of agents. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the fundamental trade-offs in aggregate packet scheduling for support of guaranteed delay service. In our study, we consider two classes of aggregate packet scheduling algorithms: the static earliest time first (SETF) and dynamic earliest time first (DETF). Through these two classes of aggregate packet scheduling (and together with the simple FIFO packet scheduling algorithm), we show that, with additional timestamp information encoded in the packet header for scheduling purposes, we can significantly increase the maximum allowable network utilization level, while, at the same time, reducing the worst- case edge-to-edge delay bound. Furthermore, we demonstrate how the number of the bits used to encode the timestamp information affects the trade-off between the maximum allowable network utilization level and the worst-case edge-to-edge delay bound. In addition, the more complex DETF algorithms have far superior performance than the simpler SETF algorithms. These results illustrate the fundamental trade-offs in aggregate packet scheduling algorithms and shed light on their provisioning power in support of guaranteed delay service. [ABSTRACT FROM AUTHOR]

Virtualization-based multi-tenant database consolidation is an important technique for database-as-a-service (DBaaS) providers to minimize their total cost which is composed of SLA penalty cost, infrastructure cost and action cost. Due to the bursty and diverse tenant workloads, over-provisioning for the peak or under-provisioning for the off-peak often results in either infrastructure cost or service level agreement (SLA) penalty cost. Moreover, although the process of scaling out database systems will help DBaaS providers satisfy tenants’ service level agreement, its indiscriminate use has performance implications or incurs action cost. In this paper, we propose SmartSLA, a cost-sensitive virtualized resource management system for CPU-bound database services which is composed of two modules. The system modeling module uses machine learning techniques to learn a model for predicting the SLA penalty cost for each tenant under different resource allocations. Based on the learned model, the resource allocating module dynamically adjusts the resource allocation by weighing the potential reduction of SLA penalty cost against increase of infrastructure cost and action cost. SmartSLA is evaluated by using the TPC-W and modified YCSB benchmarks with dynamic workload trace and multiple database tenants. The experimental results show that SmartSLA is able to minimize the total cost under time-varying workloads compared to the other cost-insensitive approaches. [ABSTRACT FROM AUTHOR]

Network virtualization has emerged as a promising approach to overcome the ossification of the Internet. A major challenge in network virtualization is the so-called virtual network embedding problem, which deals with the efficient embedding of virtual networks with resource constraints into a shared substrate network. A number of heuristics have been proposed to cope with the NP-hardness of this problem; however, all of the existing proposals reserve fixed resources throughout the entire lifetime of a virtual network. In this paper, we re-examine this problem with the position that time-varying resource requirements of virtual networks should be taken into consideration, and we present an opportunistic resource sharing-based mapping framework, ORS, where substrate resources are opportunistically shared among multiple virtual networks. We formulate the time slot assignment as an optimization problem; then, we prove the decision version of the problem to be NP-hard in the strong sense. Observing the resemblance between our problem and the bin packing problem, we adopt the core idea of first-fit and propose two practical solutions: first-fit by collision probability (CFF) and first-fit by expectation of indicators' sum (EFF). Simulation results show that ORS provides a more efficient utilization of substrate resources than two state-of-the-art fixed-resource embedding schemes. [ABSTRACT FROM AUTHOR]

While the concept of collaboration provides a natural defense against massive spam e-mails directed at large numbers of recipients, designing effective collaborative anti-spam systems raises several important research challenges. First and foremost, since e-mails may contain confidential information, any collaborative anti-spam approach has to guarantee strong privacy protection to the participating entities. Second, the continuously evolving nature of spam demands the collaborative techniques to be resilient to various kinds of camouflage attacks. Third, the collaboration has to be lightweight, efficient, and scalable. Toward addressing these challenges, this paper presents ALPACAS—a privacy-aware framework for collaborative spam filtering. In designing the ALPACAS framework, we make two unique contributions. The first is a feature-preserving message transformation technique that is highly resilient against the latest kinds of spam attacks. The second is a privacy-preserving protocol that provides enhanced privacy guarantees to the participating entities. Our experimental results conducted on a real e-mail data set shows that the proposed framework provides a 10 fold improvement in the false negative rate over the Bayesian-based Bogofilter when faced with one of the recent kinds of spam attacks. Further, the privacy breaches are extremely rare. This demonstrates the strong privacy protection provided by the ALPACAS system. [ABSTRACT FROM AUTHOR]

In this paper, we propose a comprehensive framework for mining Wireless Ad Hoc Sensor Networks (WASNs), which is able to extract patterns regarding the sensors' behaviors. The main goal of determining behavioral patterns is to use them to generate rules that will improve the WASN's Quality of Service by participating in the resource management process or compensating for the undesired side effects of wireless communication. The proposed framework consists of 1) a formal definition of sensor behavioral patterns and sensor association rules, 2) a novel representation structure that we refer to as the Positional Lexicographic Tree (PLT) that is able to compress the data gathered for the mining process and thus allows the fast and efficient mining of sensor behavioral patterns, and 3) a distributed data extraction mechanism to prepare the data required for mining sensor behavioral patterns. Several experimental studies have been conducted to evaluate our PLT structure and our proposed data extraction algorithms for mining wireless sensor networks. [ABSTRACT FROM AUTHOR]

In this paper, we argue the need for effective resource management mechanisms for sharing resources in commodity clusters. To address this issue, we present the design of Share-a system that enables resource sharing among applications in such clusters. Share depends on single node resource management mechanisms such as reservations or shares, and extends the benefits of such mechanisms to clustered environments. We present techniques for managing two important resources-CPU and network interface bandwidth-on a cluster-wide basis. Our techniques allow Share to 1) support reservation of CPU and network interface bandwidth for distributed applications, 2) dynamically allocate resources based on past usage, and 3) provide performance isolation to applications. Our experimental evaluation has shown that Share can scale to 256 node clusters running 100,000 applications. These results demonstrate that Share can be an effective approach for sharing resources among competing applications in moderate size clusters. [ABSTRACT FROM AUTHOR]

Distributed continuous media server (DCMS) architectures are proposed to minimize the communication-storage cost for those continuous media applications that serve a large number of geographically distributed clients. Typically, a DCMS is designed as a pure hierarchy (tree) of centralized continuous media servers. In an earlier work, we proposed a redundant hierarchical topology for DCMS networks, termed RedHi, which can potentially result in higher utilization and better reliability over pure hierarchy. In this paper, we focus on the design of a resource management system for RedHi that can exploit the resources of its DCMS network to achieve these performance objectives. Our proposed resource management system is based on a fully decentralized approach to achieve optimal scalability and robustness. In general, the major drawback of a fully decentralized design is the increase in latency time and communication overhead to locate the requested object. However, as compared to the typically long duration and high resource/ bandwidth requirements of continuous media objects, the extra latency and overhead of a decentralized resource management approach become negligible. Moreover, our resource management system collapses three management tasks, 1) object location, 2) path selection, and 3) resource reservation, into one fully decentralized object delivery mechanism, reducing the latency even further. In sum, decentralization of the resource management satisfies our scalability and robustness objectives, whereas collapsing the management tasks helps alleviate the latency and overhead constraints. To achieve a high resource utilization, the object delivery scheme uses our proposed cost function, as well as various object location and resource reservation policies to select and allocate the best streaming path to serve each request. The object delivery scheme is designed as an application layer resource management middleware for the DCMS architecture to be... [ABSTRACT FROM AUTHOR]

Primary storage dedup is difficult to be accomplished because of challenges to achieve low IO latency and high throughput while eliminating data redundancy effectively in the critical IO Path. In this paper, we design and implement the PDFS, a partially dedupped file system for primary workloads, which is built on a generalized framework using partial data lookup for efficient searching of redundant data in quickly chosen data subsets instead of the whole data. PDFS improves IO latency and throughput systematically by techniques including write path optimization, data dedup parallelization and write order preserving. Such design choices bring dedup to the masses for general primary workloads. Experimental results show that PDFS achieves 74-99 percent of the theoretical maximum dedup ratio with very small or even negative performance degradations compared with main stream file systems without dedup support. Discussions about varied configuring experiences of PDFS are also carried out. [ABSTRACT FROM PUBLISHER]

Cloud data center management is a key problem due to the numerous and heterogeneous strategies that can be applied, ranging from the VM placement to the federation with other clouds. Performance evaluation of cloud computing infrastructures is required to predict and quantify the cost-benefit of a strategy portfolio and the corresponding quality of service (QoS) experienced by users. Such analyses are not feasible by simulation or on-the-field experimentation, due to the great number of parameters that have to be investigated. In this paper, we present an analytical model, based on stochastic reward nets (SRNs), that is both scalable to model systems composed of thousands of resources and flexible to represent different policies and cloud-specific strategies. Several performance metrics are defined and evaluated to analyze the behavior of a cloud data center: utilization, availability, waiting time, and responsiveness. A resiliency analysis is also provided to take into account load bursts. Finally, a general approach is presented that, starting from the concept of system capacity, can help system managers to opportunely set the data center parameters under different working conditions. [ABSTRACT FROM AUTHOR]

Intelligent transportation systems have become increasingly important for the public transportation in Shanghai. In response, ShanghaiGrid (SG) project aims to provide abundant intelligent transportation services to improve the traffic condition. A challenging service in SG is to accurately locate the positions of moving vehicles in real time. In this paper, we present an innovative scheme, Hierarchical Exponential Region Organization (HERO), to tackle this problem. In SG, the location information of individual vehicles is actively logged in local nodes which are distributed throughout the city. For each vehicle, HERO dynamically maintains an advantageous hierarchy on the overlay network of local nodes to conservatively update the location information only in nearby nodes. By bounding the maximum number of hops the query is routed, HERO guarantees to meet the real-time constraint associated with each vehicle. A small-scale prototype system implementation and extensive simulations based on the real road network and trace data of vehicle movements from Shanghai demonstrate the efficacy of HERO. [ABSTRACT FROM AUTHOR]

High-end parallel and multicore processors rely on compilers to perform the necessary optimizations and exploit concurrency in order to achieve higher performance. However, the source code for high-performance computers is extremely complex to analyze and optimize. In particular, program analysis techniques often do not take into account complex expressions during the data dependence analysis phase. Most data dependence tests are only able to analyze linear expressions, even though nonlinear expressions occur very often in practice. Therefore, considerable amounts of potential parallelism remain unexploited. In this paper, we propose new data dependence analysis techniques to handle such complex instances of the dependence problem and increase program parallelization. Our method is based on a set of polynomial-time techniques that can prove or disprove dependences in source codes with nonlinear and symbolic expressions, complex loop bounds, arrays with coupled subscripts, and if-statement constraints. In addition, our algorithm can produce accurate and complete direction vector information, enabling the compiler to apply further transformations. To validate our method, we performed an experimental evaluation and comparison against the I-Test, the Omega test, and the Range test in the Perfect and SPEC benchmarks. The experimental results indicate that our dependence analysis tool is accurate, efficient, and more effective in program parallelization than the other dependence tests. The improved parallelization results into higher speedups and better program execution performance in several benchmarks. [ABSTRACT FROM AUTHOR]

One of the most prominent and comprehensive ways of data collection in sensor networks is to periodically extract raw sensor readings. This way of data collection enables complex analysis of data, which may not be possible with in-network aggregation or query processing. However, this flexibility in data analysis comes at the cost of power consumption. In this paper, we develop ASAP, which is an adaptive sampling approach to energy-efficient periodic data collection in sensor networks. The main idea behind ASAP is to use a dynamically changing subset of the nodes as samplers such that the sensor readings of the sampler nodes are directly collected, whereas the values of the nonsampler nodes are predicted through the use of probabilistic models that are locally and periodically constructed. ASAP can be effectively used to increase the network lifetime while keeping the quality of the collected data high in scenarios where either the spatial density of the network deployment is superfluous, which is relative to the required spatial resolution for data analysis, or certain amount of data quality can be traded off in order to decrease the power consumption of the network. The ASAP approach consists of three main mechanisms: First, sensing-driven cluster construction is used to create clusters within the network such that nodes with close sensor readings are assigned to the same clusters. Second, correlation-based sampler selection and model derivation are used to determine the sampler nodes and to calculate the parameters of the probabilistic models that capture the spatial and temporal correlations among the sensor readings. Last, adaptive data collection and model-based prediction are used to minimize the number of messages used to extract data from the network. A unique feature of ASAP is the use of in-network schemes, as opposed to the protocols requiring centralized control, to select and dynamically refine the subset of the sensor nodes serving as samplers and to adjust the value prediction models used for nonsampler nodes. Such runtime adaptations create a data collection schedule, which is self-optimizing in response to the changes in the energy levels of the nodes and environmental dynamics. We present simulation-based experimental results and study the effectiveness of ASAP under different system settings. [ABSTRACT FROM AUTHOR]

The big challenges facing the search techniques on Gnutella-like peer-to-peer networks are search efficiency and quality of search results. In this paper, leveraging information retrieval (IR) algorithms such as Vector Space Model (VSM) and relevance ranking algorithms, we present GES (Gnutella with Efficient Search) to improve search performance. The key idea is that GES uses a distributed topology adaptation algorithm to organize semantically relevant nodes into same semantic groups by using the notion of node vector. Given a query, GES employs an efficient search protocol to direct the query to the most relevant semantic groups for answers, thereby achieving high recall with probing only a small fraction of nodes. To the best of our knowledge, GES is the first to identify node vector size as an important role in impacting search performance and to show that the node vector size offers a good trade-off between search performance and bandwidth cost. Moreover, GES adopts automatic query expansion and local data clustering to improve search performance. We show that GES is efficient and even outperforms the centralized node clustering system SETS. For example, in the scenario where node capacity is heterogeneous, GES can achieve 73 percent recall when probing only 20 percent nodes, outperforming SETS by about 18 percent. [ABSTRACT FROM AUTHOR]

Demand for content served by a provider can fluctuate with time, complicating the task of provisioning serving resources so that requests for its content are not rejected. One way to address this problem is to have providers form a collective in which they pool together their serving resources to assist in servicing requests for one another's content. In this paper, we determine the conditions under which a provider's participation in a collective reduces the rejection rate of requests for its content-a property that is necessary for such a provider to justify its participation within the collective. We show that all request rejection rates are reduced when the collective is formed from a homogeneous set of providers, but that some rates can increase within heterogeneous sets. We also show that, asymptotically, growing the size of the collective will sometimes, but not always, resolve this problem. We explore the use of thresholding techniques, where each collective participant sets aside a portion of its serving resources to serve only requests for its own content. We show that thresholding allows a more diverse set of providers to benefit from the collective model, making collectives a more viable option for content delivery services. [ABSTRACT FROM AUTHOR]

We consider whether cooperative caching may reduce the transit traffic costs of Internet service providers (ISPs) due to peer-to-peer (P2P) content distribution systems. We formulate two game-theoretic models for cooperative caching, one in which ISPs follow their selfish interests, and one in which they act altruistically. We show the existence of pure strategy Nash equilibria for both games, and evaluate the gains of cooperation on various network topologies, among them the AS level map of Northern Europe, using measured traces of P2P content popularity. We find that cooperation can lead to significant improvements of the cache efficiency with little communication overhead even if ISPs follow their selfish interests. [ABSTRACT FROM AUTHOR]

Measures for anonymity in systems must be, on one hand, simple and concise and, on the other hand, reflect the realities of real systems. Such systems are heterogeneous, as are the ways they are used, the deployed anonymity measures, and finally, the possible attack methods. Implementation quality and topologies of the anonymity measures must be considered as well. We therefore propose a new measure for the anonymity degree that takes into account these various aspects of design and operation of anonymity systems. We model the effectiveness of single mixes or of mix networks in terms of information leakage, and we measure it in terms of covert-channel capacity. The relationship between the anonymity degree and information leakage is described, and an example is shown. [ABSTRACT FROM AUTHOR]

An ad hoc grid is a wireless heterogeneous computing environment without a fixed infrastructure. This study considers wireless devices that have different capabilities, have limited battery capacity, support dynamic voltage scaling, and are expected to be used for eight hours at a time and then recharged. To maximize the performance of the system, it is essential to assign resources to tasks (match) and order the execution of tasks on each resource (schedule) in a manner that exploits the heterogeneity of the resources and tasks while considering the energy constraints of the devices. In the single-hop ad hoc grid heterogeneous environment considered in this study, tasks arrive unpredictably, are independent (i.e., no precedent constraints for tasks) and have priorities and deadlines. The problem is to map (match and schedule) tasks onto devices such that the number of highest priority tasks completed by their deadlines during eight hours is maximized while efficiently utilizing the overall system energy. A model for dynamically mapping tasks onto wireless devices is introduced. Seven dynamic mapping heuristics for this environment are designed and compared to each other and to a mathematical bound. [ABSTRACT FROM AUTHOR]

The group mutual exclusion problem extends the traditional mutual exclusion problem by associating a type (or a group) with each critical section. In this problem, processes requesting critical sections of the same type can execute their critical sections concurrently. However, processes requesting critical sections of different types must execute their critical sections in a mutually exclusive manner. We present a distributed algorithm for solving the group mutual exclusion problem based on the notion of surrogate-quorum. Intuitively, our algorithm uses the quorum that has been successfully locked by a request as a surrogate to service other compatible requests for the same type of critical section. Unlike the existing quorum-based algorithms for group mutual exclusion, our algorithm achieves a low message complexity of O(q) and a low (amortized) bit-message complexity of O(bqr), where q is the maximum size of a quorum, b is the maximum number of processes from which a node can receive critical section requests, and r is the maximum size of a request while maintaining both synchronization delay and waiting time at two message hops. As opposed to some existing quorum-based algorithms, our algorithm can adapt without performance penalties to dynamic changes in the set of groups. Our simulation results indicate that our algorithm outperforms the existing quorum-based algorithms for group mutual exclusion by as much as 45 percent in some cases. We also discuss how our algorithm can be extended to satisfy certain desirable properties such as concurrent entry and unnecessary blocking freedom. [ABSTRACT FROM AUTHOR]

A commonly employed abstraction for studying the object placement problem for the purpose of Internet content distribution is that of a distributed replication group. In this work, the initial model of the distributed replication group of Left et al. [1] is extended to the case that individual nodes act selfishly, i.e., cater to the optimization of their individual local utilities. Our main contribution is the derivation of equilibrium object placement strategies that 1) can guarantee improved local utilities for all nodes concurrently as compared to the corresponding local utilities under greedy local object placement, 2) do not suffer from potential mistreatment problems, inherent to centralized strategies that aim at optimizing the social utility, and 3) do not require the existence of complete information at all nodes. We develop a baseline computationally efficient algorithm for obtaining the aforementioned equilibrium strategies and then extend it to improve its performance with respect to fairness. Both algorithms are realizable, in practice, through a distributed protocol that requires only a limited exchange of information. [ABSTRACT FROM AUTHOR]

We propose a massively parallel framework termed a parallel-pipeline model of execution that can be employed on a homogeneous computational cluster. We show that speedups near-linear in the number of processors are achievable for applications involving reduction operations based On a novel, parallel-pipeline model of execution. As computational clusters become viable alternative platforms for solving large computational problems, the research community acknowledges that the cluster environment can be used effectively when adaptive resource management is employed. This requires the ability to estimate the resource requirements of applications before scheduling decisions are made. We propose a resource estimation model for applications executed in the parallel-pipeline model of execution. We develop a performance model that predicts the resource utilization (i.e., computation and communication complexity) for applications executing under the parallel-pipeline model on a homogeneous computational cluster. This performance prediction model can provide information to a cluster scheduler. [ABSTRACT FROM AUTHOR]

PC clusters have become popular in parallel processing. They do not involve specialized interprocessor networks, so the latency of data communications is rather long. The programming models for PC clusters are often different than those for parallel machines or supercomputers containing sophisticated interprocessor communication networks. For PC clusters, load balancing among the nodes becomes a more critical issue in attempts to yield high performance. We introduce a new model for program development on PC clusters, namely, the Super-Programming Model (SPM). The workload is modeled as a collection of Super-Instructions (Sls). We propose that a set of SIs be designed for each application domain. They should constitute an orthogonal set of frequently used high-level operations in the corresponding application domain. Each SI should normally be implemented as a high- level language routine that can execute on any PC. Application programs are modeled as Super-Programs (SPs), which are coded using Sis. SIs are dynamically assigned to available PCs at runtime. Because of the known granularity of Sls, an upper bound on their execution time can be estimated at static time. Therefore, dynamic load balancing becomes an easier task. Our motivation is to support dynamic load balancing and code porting, especially for applications with diverse sets of inputs such as data mining. We apply here SPM to the implementation of an Apriori-like algorithm for mining association rules. Our experiments show that the average idle time per node is kept very low. [ABSTRACT FROM AUTHOR]