Regulatory policies such as EU privacy, HIPAA, and PCI-DSS place requirements on availability, integrity, migration, retention, and access of data, and compliance with such policies on stored data remains a key hurdle to cloud computing. This paper proposes a policy management service that offers scalable management of data retention policies attached to data objects stored in a cloud environment. An important aspect of any data retention service is permanent deletion of data. We achieve secure data deletion by encrypting the data when stored, and then deleting the encryption key at a specified retention time. Thus, we effectively delete the data object and its copies stored in online and offline environments. Our data retention service includes a highly scalable and secure encryption key store to manage encryption keys on-line. A prototype deployed on a 16-machine Linux cluster currently supports 56 MB/sec for encryption, 76 MB/sec for decryption, 31,000 retention policies/sec read and 15,000 retention policies/sec write.

Service composition has received significant attention in the research community, and the focus has been on service semantics and composition algorithms. Surprisingly, the problem of representation of the composition outcome has been largely ignored. Ad-hoc workflows are often employed, which typically sacrifice alternative paths and parallelism for the sake of simple representation. In this paper, we show how theory of regions, which was originally developed to derive Petri nets from finite state automata, can be applied to find the optimal representation of composition. To apply the theory, we first propose an automaton-based composition framework that incorporates most existing composition techniques without changing the service semantics or its description language. Then based on the special requirements of the composition representation, we develop our own Petri net synthesis algorithm that combines the benefits of two well known algorithms from the theory of regions. We demonstrate that AND/OR workflow nets can limit the concurrency even for simple input/output based service composition, while our Petri net representation is optimal in terms of flexibility and parallelism. Our experimental evaluations include a case study on composing Google Checkout Service, and the study on Oracle BPEL samples, for which our algorithm obtains better concurrent representations for almost all non-trivial cases.

Compliance with regulatory policies on data remains a key hurdle to cloud computing. Policies such as EU privacy, HIPAA, and PCI-DSS place requirements on data availability, integrity, migration, retention, and access, among many others. This paper proposes a policy management service that offers scalable management of data retention policies attached to data objects stored in a cloud environment. The management service includes a highly available and secure encryption key store to manage the encryption keys of data objects. By deleting the encryption key at a specified retention time associated with the data object, we effectively delete the data object and its copies stored in online and offline environments. To achieve scalability, our service uses Hadoop MapReduce to perform parallel management tasks, such as data encryption and decryption, key distribution and retention policy enforcement. A prototype deployed in a 16-machine Linux cluster currently supports 56 MB/sec for encryption, 76 MB/sec for decryption, 31,000 retention policies/sec read and 15,000 retention policies/sec write.

Wireless mesh networks are popular as a cost- effective means to provide broadband connectivity to large user populations. A mesh network placement provides coverage, such that each target client location has a link to a deployed mesh node, and connectivity, such that each mesh node wirelessly connects directly to a gateway or via intermediate mesh nodes. Prior work on placement assumes wireless propagation to be uniform in all directions, i.e., an unrealistic assumption of circular communication regions. In this paper, we present approximation algorithms to solve the NP- hard mesh node placement problem for non-uniform propagation settings. The first key challenge is incorporating non-uniform propagation, which we address by formulating the problem input as a connectivity graph consisting of discrete target coverage locations and potential mesh node locations. This graph incorporates non-uniform propagation by specifying the estimated signal quality per link. Secondly, our algorithms are the first to minimize the number of deployed mesh nodes with constant-factor approximation ratio in the non-uniform propagation setting. To achieve this, we formulate the Degree-Constrained Terminal Steiner tree problem and present approximation algorithms which leverage prior results on the Steiner tree problem. Third, it is impractical to measure all possible potential mesh links, and therefore deployment planning must rely on estimations. To address this challenge, we extend our algorithm to iteratively measure the links in the solution Steiner tree, refining the graph input on a per-link basis in order to ensure the deployed network is not disconnected. Finally, we use propagation measurements at 35,000 locations in the deployed GoogleWiFi network to investigate placement in a realistic, non-uniform propagation environment. Under this measured propagation setting, our algorithms result in up to 80% fewer mesh nodes than current algorithms and only require an average of 3 measurements per deployed mesh node to ensure backhaul connectivity.

We consider the problem of providing byzantine-tolerant storage in distributed systems where client-server links are much thinner and slower than server-server links. We provide storage algorithms that are unique in two ways. First, our algorithms take into consideration the asymmetry in network connectivity by minimizing client-server communication. To provide this property, we rely on a small amount of partial (eventual) synchrony. Second, our algorithms provide a new property called limited effect, which is important for storage systems. To provide the latter property, we use synchronized clocks, which are increasingly common due to GPS devices and NTP, even in otherwise "asynchronous systems" like the Internet. We present two algorithms called QUAD and LINEAR, which provide a trade-off between failure resiliency and efficiency. Our algorithms implement an abortable register [3], which is an abstraction used in some real storage systems, but abortable registers are weaker than atomic registers. Thus, one might wonder if we could have implemented atomic registers instead. We answer this question in the negative: we prove that there are no implementations of atomic registers that provide the limited effect property in systems with failures, even with synchronized clocks.

Wireless mesh network deployments are popular as a cost-effective means to provide broadband connectivity to large user populations. As the network usage grows, network planners need to evolve an existing mesh network to provide additional capacity. In this paper, we study the problem of adding new capacity points (e.g., gateway nodes) to an existing mesh network. We first present a new technique for calculating gateway-limited fair capacity as a function of the contention at each gateway. Then, we present two online gateway placement algorithms that use local search operations to maximize the capacity gain on an existing network. A key challenge is that each gateway's capacity depends on the locations of other gateways and cannot be known in advance of determining a gateway placement. We address this challenge with two placement algorithms with different approaches to estimating the unknown gateway capacities. Our first placement algorithm, MinHopCount, is adapted from a solution to the facility location problem. MinHopCount minimizes path lengths and iteratively estimates the wireless capacity of each gateway location. Our second algorithm, MinContention, is adapted from a solution to the uncapacitated k-median problem and minimizes average contention on mesh nodes, i.e. the number of links in contention range of a mesh node and the number of routes using each link. We show that our gateway placement algorithms outperform a greedy heuristic by up to 64% on realistic topologies. For an example topology, we study the set of all possible gateway placements and find that there is large capacity gain between near-optimal and optimal placements, but the near-optimal placements found by local search are similar in configuration to the optimal.

We present a framework for considering the problem of compressing large collections of similar sequences. In this framework, an unknown individual sequence is modified several times independently to obtain the collection of sequences to be compressed. For certain collections generated by context-dependent bit flips of the individual sequencepsilas bits, and for those generated by simple edit operations on the individual sequence, we derive universal compression algorithms that compress the collection of sequences almost as well as an optimal compressor that has knowledge of the underlying individual sequence and the modifying processes.

In order to evaluate, improve, or expand a deployed, city-wide wireless mesh network, it is necessary to assess the network's spatial performance. In this paper, we present a general framework to accurately predict a network's well-served area, termed the metric region, via a small number of measurements. Assessment of deployed networks must address two key issues: non-uniform physical-layer propagation and high spatial variance in performance. Addressing non-uniformity, our framework estimates a mesh node's metric region via a data-driven sectorization of the region. We find each sector's boundary (radius) with a two-stage process of estimation and then measurement-driven "push-pull" refinement of the estimated boundary. To address high spatial variation, our coverage estimation couples signal strength measurements with terrain information from publicly available digital maps to estimate propagation characteristics between a wireless node and the client's location. To limit measurements and yield connected metric regions, we consider performance metrics (such as signal strength) to be monotonic with distance from the wireless node within each sector. We show that despite measured violations in coverage monotonicity, we obtain high accuracy with this assumption. We validate our estimation and refinement framework with measurements from 30,000 client locations obtained in each of two currently operational mesh networks, GoogleWiFi and TFA. We study three illustrative metrics: coverage, modulation rate, and redundancy, and find that to achieve a given accuracy, our framework requires two to five times fewer measurements than grid sampling strategies. Finally, we use the framework to evaluate the two deployments and study the average size and location of their coverage holes as well as the impact of client association policies on load-balancing.

We propose a new fault tolerance metric for XOR-based erasure codes: the minimal erasures list (MEL). A minimal erasure is a set of erasures that leads to irrecoverable data loss and in which every erasure is necessary and sufficient for this to be so. The MEL is the enumeration of all minimal erasures. An XOR-based erasure code has an irregular structure that may permit it to tolerate faults at and beyond its Hamming distance. The MEL completely describes the fault tolerance of an XOR-based erasure code at and beyond its Hamming distance; it is therefore a useful metric for comparing the fault tolerance of such codes. We also propose an algorithm that efficiently determines the MEL of an erasure code. This algorithm uses the structure of the erasure code to efficiently determine the MEL. We show that, in practice, the number of minimal erasures for a given code is much less than the total number of sets of erasures that lead to data loss: in our empirical results for one corpus of codes, there were over 80 times fewer minimal erasures. We use the proposed algorithm to identify the most fault tolerant XOR-based erasure code for all possible systematic erasure codes with up to seven data symbols and up to seven parity symbols.

No abstract available.

Countering Distributed Denial of Service (DDoS) attacks is becoming ever more challenging with the vast resources and techniques increasingly available to attackers. In this paper, we consider sophisticated attacks that are protocol-compliant, non-intrusive, and utilize legitimate application-layer requests to overwhelm system resources. We characterize application-layer resource attacks as either request flooding, asymmetric, or repeated one-shot, on the basis of the application workload parameters that they exploit. To protect servers from these attacks, we propose a counter-mechanism that consists of a suspicion assignment mechanism and a DDoS-resilient scheduler, DDoS Shield. In contrast to prior work, our suspicion mechanism assigns a continuous valued vs. binary measure to each client session, and the scheduler utilizes these values to determine if and when to schedule a session’s requests. Using testbed experiments on a web application, we demonstrate the potency of these resource attacks and evaluate the efficacy of our counter-mechanism. For instance, we effect an asymmetric attack which overwhelms the server resources, increasing the response time of legitimate clients from 0.1 seconds to 10 seconds. Under the same attack scenario, DDoS Shield limits the effects of false-negatives and false-positives and improves the victims’ performance to 0.8 seconds.

No abstract available.

We describe a new class of utility-maximization scheduling problem with precedence constraints, the disconnected staged scheduling problem (DSSP). DSSP is a nonpreemptive multiprocessor deadline scheduling problem that arises in several commercially-important applications, including animation rendering, protein analysis, and seismic signal processing. DSSP differs from most previously-studied deadline scheduling problems because the graph of precedence constraints among tasks within jobs is disconnected, with one component per job. Another difference is that in practice we often lack accurate estimates of task execution times, and so purely offline solutions are not possible. However we do know the set of jobs and their precedence constraints up front and therefore some offline planning is possible.Our solution decomposes DSSP into an offline job selection phase followed by an online task dispatching phase. We model the former as a knapsack problem and explore several solutions to it, describe a new dispatching algorithm for the latter, and compare both with existing methods. Our theoretical results show that while DSSP is NP-hard and inapproximable in general, our two-phase scheduling method guarantees a good performance bound for many special cases. Our empirical results include an evaluation of scheduling algorithms on a real animation-rendering workload; we present a characterization of this workload in a companion paper. The workload records eight weeks of activity on a 1,000-CPU cluster used to render portions of the full-length animated feature film Shrek 2 in 2004. We show that our improved scheduling algorithms can substantially increase the aggregate value of completed jobs compared to existing practices. Our new task dispatching algorithm LCPF performs well by several metrics, including job completion times as well as the aggregate value of completed jobs.

Despite the importance of storage in enterprise computer systems, there are few adequate tools to design and configure a storage system to meet application data requirements efficiently. Storage system design involves choosing the disk arrays to use, setting the configuration options on those arrays, and determining an efficient mapping of application data onto the configured system. This is a complex process because of the multitude of disk array configuration options, and the need to take into account both capacity and potentially contending I/O performance demands when placing the data. Thus, both existing tools and administrators using rules of thumb often generate designs that are of poor quality.This article presents the Disk Array Designer (DAD), which is a tool that can be used both to guide administrators in their design decisions and to automate the design process. DAD uses a generalized best-fit bin packing heuristic with randomization and backtracking to search efficiently through the huge number of possible design choices. It makes decisions using device models that estimate storage system performance. We evaluate DAD's designs based on traces from a variety of database, filesystem, and e-mail workloads. We show that DAD can handle the difficult task of configuring midrange and high-end disk arrays, even with complex real-world workloads. We also show that DAD quickly generates near-optimal storage system designs, improving in both speed and quality over previous tools.

Tutte introduced a decomposition of 2-connected graphs which has widely been used in solving various graph-theoretic problems. In this paper, we extend it to a class of graph-layout problems, namely, determining the bandwidth, cutwidth, and pagenumber of graphs. In particular, we present linear-time algorithms for testing and, if so, constructing linear layouts of 2-edge-connected bandwidth-2 and cut-width-3 graphs. We also present a simple linear-time algorithm for embedding series-parallel graphs in two pages. The interesting feature of these algorithms is that they use a divide-and-conquer paradigm with Tutte decomposition of 2-connected graphs as a common framework; thus, they are different from the previously known algorithms. Moreover, since Tutte decomposition can be computed efficiently in parallel, all three proposed algorithms parallelize naturally. © 1996 John Wiley & Sons, Inc.