This paper presents a new MapReduce cloud service model, Cura, for provisioning cost-effective MapReduce services in a cloud. In contrast to existing MapReduce cloud services such as a generic compute cloud or a dedicated MapReduce cloud, Cura has a number of unique benefits. First, Cura is designed to provide a cost-effective solution to efficiently handle MapReduce production workloads that have a significant amount of interactive jobs. Second, unlike existing services that require customers to decide the resources to be used for the jobs, Cura leverages MapReduce profiling to automatically create the best cluster configuration for the jobs. While the existing models allow only a per-job resource optimization for the jobs, Cura implements a globally efficient resource allocation scheme that significantly reduces the resource usage cost in the cloud. Third, Cura leverages unique optimization opportunities when dealing with workloads that can withstand some slack. By effectively multiplexing the available cloud resources among the jobs based on the job requirements, Cura achieves significantly lower resource usage costs for the jobs. Cura's core resource management schemes include cost-aware resource provisioning, VM-aware scheduling and online virtual machine reconfiguration. Our experimental results using Facebook-like workload traces show that our techniques lead to more than 80 percent reduction in the cloud compute infrastructure cost with upto 65 percent reduction in job response times.

With more data generated and collected in a geographically distributed manner, combined by the increased computational requirements for large scale data-intensive analysis, we have witnessed the growing demand for geographically distributed Cloud datacenters and hybrid Cloud service provisioning, enabling organizations to support instantaneous demand of additional computational resources and to expand inhouse resources to maintain peak service demands by utilizing cloud resources. A key challenge for running applications in such a geographically distributed computing environment is how to efficiently schedule and perform analysis over data that is geographically distributed across multiple datacenters. In this paper, we first compare multi-datacenter Hadoop deployment with single-datacenter Hadoop deployment to identify the performance issues inherent in a geographically distributed cloud. A generalization of the problem characterization in the context of geographically distributed cloud datacenters is also provided with discussions on general optimization strategies. Then we describe the design and implementation of a suite of system-level optimizations for improving performance of Hadoop service provisioning in a geo-distributed cloud, including prediction-based job localization, configurable HDFS data placement, and data prefetching. Our experimental evaluation shows that our prediction based localization has very low error ratio, smaller than 5%, and our optimization can improve the execution time of Reduce phase by 48.6%.

Public storage clouds have become a popular choice for archiving certain classes of enterprise data - for example, application and infrastructure logs. These logs contain sensitive information like IP addresses or user logins due to which regulatory and security requirements often require data to be encrypted before moved to the cloud. In order to leverage such data for any business value, analytics systems (e.g. Hadoop/MapReduce) first download data from these public clouds, decrypt it and then process it at the secure enterprise site. We propose VNCache: an efficient solution for MapReduceanalysis of such cloud-archived log data without requiring an apriori data transfer and loading into the local Hadoop cluster. VNcache dynamically integrates cloud-archived data into a virtual namespace at the enterprise Hadoop cluster. Through a seamless data streaming and prefetching model, Hadoop jobs can begin execution as soon as they are launched without requiring any apriori downloading. With VNcache's accurate pre-fetching and caching, jobs often run on a local cached copy of the data block significantly improving performance. When no longer needed, data is safely evicted from the enterprise cluster reducing the total storage footprint. Uniquely, VNcache is implemented with NO changes to the Hadoop application stack.

We propose a new MapReduce cloud service model, Cura, for data analytics in the cloud. We argue that performing MapReduce analytics in existing cloud service models - either using a generic compute cloud or a dedicated MapReduce cloud - is inadequate and inefficient for production workloads. Existing services require users to select a number of complex cluster and job parameters while simultaneously forcing the cloud provider to use those potentially sub-optimal configurations resulting in poor resource utilization and higher cost. In contrast Cura leverages MapReduce profiling to automatically create the best cluster configuration for the jobs so as to obtain a global resource optimization from the provider perspective. Secondly, to better serve modern MapReduce workloads which constitute a large proportion of interactive real-time jobs, Cura uses a unique instant VM allocation technique that reduces response times by up to 65%. Thirdly, our system introduces deadline-awareness which, by delaying execution of certain jobs, allows the cloud provider to optimize its global resource allocation and reduce costs further. Cura also benefits from a number of additional performance enhancements including cost-aware resource provisioning, VMaware scheduling and online virtual machine reconfiguration. Our experimental results using Facebook-like workload traces show that along with response time improvements, our techniques lead to more than 80% reduction in the compute infrastructure cost of the cloud data center.

Mix-zones are recognized as an alternative and complementary approach to spatial cloaking based approach to location privacy protection. Mix-zones break the continuity of location exposure by ensuring that users' movements cannot be traced while they reside in a mix-zone. In this paper we provide an overview of various known attacks that make mix-zones on road networks vulnerable and illustrate a set of counter measures to make road network mix-zones attack resilient. Concretely, we categorize the vulnerabilities of road network mix-zones into two classes: one due to the road network characteristics and user mobility, and the other due to the temporal, spatial and semantic correlations of location queries. For instance, the timing information of users' entry and exit into a mix-zone provides information to launch a timing attack. The non-uniformity in the transitions taken at the road intersection may lead to transition attack. An example query correlation attack is the basic continual query (CQ) attacks, which attempt to break the anonymity of road network aware mix-zones by performing query correlation based inference. The CQ-timing attacks carry out inference attacks based on both query correlation and timing correlation, and the CQ-transition attacks execute inference attacks based on both query correlation and transition correlation. We study the factors that impact on the effectiveness of each of these attacks and evaluate the efficiency of the counter measures, such as non-rectangle mix-zones and delay tolerant mix-zones, through extensive experiments on traces produced by GTMobiSim at different scales of geographic maps.

MapReduce is a distributed computing paradigm widely used for building large-scale data processing applications. When used in cloud environments, MapReduce clusters are dynamically created using virtual machines (VMs) and managed by the cloud provider. In this paper, we study the energy efficiency problem for such MapReduce clouds. We describe a unique spatio-temporal tradeoff that includes efficient spatial fitting of VMs on servers to achieve high utilization of machine resources, as well as balanced temporal fitting of servers with VMs having similar runtimes to ensure a server runs at a high utilization throughout its uptime. We propose VM placement algorithms that explicitly incorporate these tradeoffs. Further, we propose techniques that dynamically scale MapReduce clusters to further improve energy consumption while ensuring that jobs meet or improve their expected runtimes. Our algorithms achieve energy savings over existing placement techniques, and an additional optimization technique further achieves savings while simultaneously improving job performance.

MapReduce is a distributed computing paradigm widely used for building large-scale data processing applications. When used in cloud environments, MapReduce clusters are dynamically created using virtual machines (VMs) and managed by the cloud provider. In this paper, we study the energy efficiency problem for such MapReduce clusters in private cloud environments, that are characterized by repeated, batch execution of jobs. We describe a unique spatio-temporal tradeoff that includes efficient spatial fitting of VMs on servers to achieve high utilization of machine resources, as well as balanced temporal fitting of servers with VMs having similar runtimes to ensure a server runs at a high utilization throughout its uptime. We propose VM placement algorithms that explicitly incorporate these tradeoffs. Our algorithms achieve energy savings over existing placement techniques, and an additional optimization technique further achieves savings while simultaneously improving job performance.

MapReduce has gained in popularity as a distributed data analysis paradigm, particularly in the cloud, where MapReduce jobs are run on virtual clusters. The provisioning of MapReduce jobs in the cloud is an important problem for optimizing several user as well as provider-side metrics, such as runtime, cost, throughput, energy, and load. In this paper, we present an intelligent provisioning framework called STEAMEngine that consists of provisioning algorithms to optimize these metrics through a set of common building blocks. These building blocks enable spatio-temporal tradeoffs unique to MapReduce provisioning: along with their resource requirements (spatial component), a MapReduce job runtime (temporal component) is a critical element for any provisioning algorithm. We also describe tw o novel provisioning algorithms - a user-driven performance optimization and a provider-driven energy optimization - that leverage these building blocks. Our experimental results based on an Amazon EC2 cluster and a local Xen/Hadoop cluster show the benefits of STEAMEngine through improvements in performance and energy via the use of these algorithms and building blocks.

We present Purlieus, a MapReduce resource allocation system aimed at enhancing the performance of MapReduce jobs in the cloud. Purlieus provisions virtual MapReduce clusters in a locality-aware manner enabling MapReduce virtual machines (VMs) access to input data and importantly, intermediate data from local or close-by physical machines. We demonstrate how this locality-awareness during both map and reduce phases of the job not only improves runtime performance of individual jobs but also has an additional advantage of reducing network traffic generated in the cloud data center. This is accomplished using a novel coupling of, otherwise independent, data and VM placement steps. We conduct a detailed evaluation of Purlieus and demonstrate significant savings in network traffic and almost 50% reduction in job execution times for a variety of workloads.

We present the design and implementation of ENDEAVOUR - a framework for integrated end-to-end disaster recovery (DR) planning. Unlike existing research that provides DR planning within a single layer of the IT stack (e.g. storage controller based replication), ENDEAVOUR can choose technologies and composition of technologies across multiple layers like virtual machines, databases and storage controllers. ENDEAVOUR uses a canonical model of available replication technologies at all layers, explores strategies to compose them, and performs a novel map-search-reduce heuristic to identify the best DR plans for given administrator requirements. We present a detailed analysis of ENDEAVOUR including empirical characterization of various DR technologies, their composition, and a end-to-end case study.

Virtualization technologies like VMware and Xen provide features to specify the minimum and maximum amount of resources that can be allocated to a virtual machine (VM) and a shares based mechanism for the hypervisor to distribute spare resources among contending VMs. However much of the existing work on VM placement and power consolidation in data centers fails to take advantage of these features. One of our experiments on a real testbed shows that leveraging such features can improve the overall utility of the data center by 47% or even higher. Motivated by these, we present a novel suite of techniques for placement and power consolidation of VMs in data centers taking advantage of the min-max and shares features inherent in virtualization technologies. Our techniques provide a smooth mechanism for power-performance tradeoffs in modern data centers running heterogeneous applications, wherein the amount of resources allocated to a VM can be adjusted based on available resources, power costs, and application utilities. We evaluate our techniques on a range of large synthetic data center setups and a small real data center testbed comprising of VMware ESX servers. Our experiments confirm the end-to-end validity of our approach and demonstrate that our final candidate algorithm, PowerExpandMinMax, consistently yields the best overall utility across a broad spectrum of inputs - varying VM sizes and utilities, varying server capacities and varying power costs - thus providing a practical solution for administrators.

We introduce the coupled placement problem for modern data centers spanning placement of application computation and data among available server and storage resources. While the two have traditionally been addressed independently in data centers, two modern trends make it beneficial to consider them together in a coupled manner: (a) rise in virtualization technologies, which enable applications packaged as VMs to be run on any server in the data center with spare compute resources, and (b) rise in multi-purpose hardware devices in the data center which provide compute resources of varying capabilities at different proximities from the storage nodes. We present a novel framework called CPA for addressing such coupled placement of application data and computation in modern data centers. Based on two well-studied problems - Stable Marriage and Knapsacks - the CPA framework is simple, fast, versatile and automatically enables high throughput applications to be placed on nearby server and storage node pairs. While a theoretical proof of CPA's worst-case approximation guarantee remains an open question, we use extensive experimental analysis to evaluate CPA on large synthetic data centers comparing it to Linear Programming based methods and other traditional methods. Experiments show that CPA is consistently and surprisingly within 0 to 4% of the Linear Programming based optimal values for various data center topologies and workload patterns. At the same time it is one to two orders of magnitude faster than the LP based methods and is able to scale to much larger problem sizes. The fast running time of CPA makes it highly suitable for large data center environments where hundreds to thousands of server and storage nodes are common. LP based approaches are prohibitively slow in such environments. CPA is also suitable for fast interactive analysis during consolidation of such environments from physical to virtual resources.

Many enterprise environments have databases running on network-attached storage infrastructure (referred to as Storage Area Networks or SANs ). Both the database and the SAN are complex subsystems that are managed by separate teams of administrators. As often as not, database administrators have limited understanding of SAN configuration and behavior, and limited visibility into the SAN's run-time performance; and vice versa for the SAN administrators. Diagnosing the cause of performance problems is a challenging exercise in these environments. We propose to remedy the situation through a novel tool, called Diads, for database and SAN problem diagnosis. This demonstration proposal summarizes the technical innovations in Diads: (i) a powerful abstraction called Annotated Plan Graphs (APGs) that ties together the execution path of queries in the database and the SAN using low-overhead monitoring data, and (ii) a diagnosis workflow that combines domain-specific knowledge with machine-learning techniques. The scenarios presented in the demonstration are also described.

With fast-paced growth of digital data and exploding storage management costs, enterprises are looking for new ways to effectively manage their data. One such cost-effective paradigm is the cloud storage model also referred to as Storage-as-a-Service, in which enterprises outsource their storage to a storage service provider (SSP) by storing data (usually encrypted) at a remote SSP-managed site and accessing it over a high speed network. Along with storage capacity used, the SSP often charges clients on the amount of data that is accessed from the SSP site. Thus, it is in the interest of the client enterprise to download only relevant content. This makes search over outsourced storage an important capability. Searching over encrypted outsourced storage, however, is a complex challenge. Each enterprise has different access privileges for different users and this access control needs to be preserved during search (for example, ensuring that a user cannot search through data that is inaccessible from the filesystem due to its permissions). Secondly, the search mechanism has to preserve confidentiality from the SSP and indices can not be stored in plain text. In this article, we present a new filesystem search technique that integrates access control and indexing/search mechanisms into a unified framework to support access control aware search. Our approach performs indexing within the trusted enterprise domain and uses a novel access control barrel (ACB) primitive to encapsulate access control within these indices. The indices are then systematically encrypted and shipped to the SSP for hosting. Unlike existing enterprise search techniques, our approach is resilient to various common attacks that leak private information. Additionally, to the best of our knowledge, our approach is a first such technique that allows search indices to be hosted at the SSP site, thus effectively providing search-as-a-service . This does not require the client enterprise to fully trust the SSP for data confidentiality. We describe the architecture and implementation of our approach and a detailed experimental analysis comparing with other approaches.

With fast paced growth of digital data and exploding storage management costs, enterprises are looking for new ways to effectively manage their data. One such cost-effective paradigm is the storage-as-a-service model, in which enterprises outsource their storage to a storage service provider (SSP) by storing data at a remote SSP-managed site and accessing it over a high speed network. Often for a variety of reasons, enterprises find it unacceptable to fully trust the SSP and prefer to store data in an encrypted form. This typically limits collaboration and data sharing among enterprise users due to complex key management and access control challenges. In this paper, we propose a platform called SHAROES that provides data sharing capability over such outsourced storage environments. SHAROES provide rich *nix-like data sharing semantics over SSP stored data, without trusting the SSP for data confidentiality or access control. SHAROES is unique in its ability in reducing user involvement during setup and operation through the use of in-band key management and allows a near-seamless transition of existing storage environments to the new model. It is also superior in performance by minimizing the use of expensive public-key cryptography in metadata management. We present the architecture and implementation of various SHAROES components and our experiments demonstrate performance superior to other proposals by over 40% on a number of benchmarks.

We describe the design of an agile data center with integrated server and storage virtualization technologies. Such data centers form a key building block for new cloud computing architectures.We also show how to leverage this integrated agility for non-disruptive load balancing in data centers across multiple resource layers - servers, switches, and storage. We propose a novel load balancing algorithm called VectorDot for handling the hierarchical and multi-dimensional resource constraints in such systems. The algorithm, inspired by the successful Toyoda method for multi-dimensional knapsacks, is the first of its kind. We evaluate our system on a range of synthetic and real data center testbeds comprising of VMware ESX servers, IBM SAN Volume Controller, Cisco and Brocade switches. Experiments under varied conditions demonstrate the end-to-end validity of our system and the ability of VectorDot to efficiently remove overloads on server, switch and storage nodes.

In this paper, we analyse the data sharing mechanisms of *nix systems and identify an immediate need for better privacy support. For example, using a simple insider attack we were able to access over 84 GB of private data at one organisation of 825 users, including 300 000 e-mails and 579 passwords to financial and other private services websites, without exploiting any technical vulnerability. We present two solutions to address this problem: 1. an administrative auditing tool which can alert administrators and users when their private data is at risk; 2. a new View Based Access Control (VBAC) mechanism which provides stronger and yet convenient privacy support. We also describe a proof-of-concept filesystem-based implementation and performance analysis of VBAC. Our evaluations with three well-known filesystem benchmarks show little overhead of using VBAC.

We describe DSphere - a decentralized system for crawling, indexing, searching and ranking of documents in the World Wide Web. Unlike most of the existing search technologies that depend heavily on a page-centric view of the Web, we advocate a source-centric view of the Web and propose a decentralized architecture for crawling, indexing and searching the Web in a distributed source-specific fashion. A fully decentralized crawler is developed to crawl the World Wide Web where each peer is assigned the responsibility of crawling a specific set of documents referred to as a source collection. Link analysis techniques are used for ranking documents. Traditional link analysis techniques suffer from problems like slow refresh rate and vulnerabilities to Web Spam. We propose a source-based link analysis approach, which computes fast and accurate ranking scores for all crawled documents.

With fast paced growth of digital data, keyword based search has become a critical enterprise application. Research has shown that nearly 85% of enterprise data lies in flat filesystems [10] that allow multiple users with different access privileges. Any search tool for such systems needs to be efficient and yet cognizant of access control semantics imposed by the underlying filesystem. Current enterprise search techniques use two disjoint search and access- control components by creating a single system-wide index and filtering search results for access control. This approach is ineffective as index and query statistics subtly leak private information. The other approach of using separate indices for each user is undesirable as it not only increases disk consumption due to shared files, but also increases overheads of updating indices whenever a file changes. We propose a distributed approach that couples search and access-control into a unified framework and pro vides secure multiuser search. Our scheme (logically) divides data into independent access-privileges based chunks, called access-control barrels (ACB). ACBs not only manage security but also improve overall efficiency as they can be indexed and searched in parallel by distributing them to multiple enterprise machines. We describe the architecture of ACBs based search and propose an optimization that ensures the scalability of our approach. We validate our design with a detailed evaluation using industry benchmarks and datasets. Our initial experiments show secure search with 38% improved indexing efficiency and low overheads for ACB processing.

Modern data centers are complex distributed environments with application workloads requiring multiple resources like processing (CPU), storage and network. Allocation of these resources to workloads needs to be handled in an integrated manner to adequately capture the relationships between different resource nodes like connectivity between an application server and storage controller in the storage area network (SAN). As data centers grow over time, heterogeneous resources coexist at the same time and this heterogeneity adds further complexity to manual resource allocation.

We present an architecture of a trust framework that can be used to intelligently tradeoff between security and performance in a SAN file system. The primary idea is to differentiate between various clients in the system based on their trustworthiness and provide them with differing levels of security and performance. Client trustworthiness reflects its expected behavior and is evaluated in an online fashion using a customizable trust model. We also describe the interface of the trust framework with an example block level security solution for an out-of-band virtualization based SAN file system (SAN FS). The proposed framework can be easily extended to provide differential treatment based on data sensitivity, using a configurable parameter of the trust model. This allows associating stringent security requirements for more sensitive data, while trading off security for better performance for less critical data, a situation regularly desired in an enterprise.

We present HSAN & a hybrid storage area network, which uses both in-band (like NFS (R. Sandberg et al., 1985)) and out-of-band visualization (like SAN FS (J. Menon et al., 2003)) access models. HSAN uses hybrid servers that can serve as both metadata and NAS servers to intelligently decide the access model per each request, based on the characteristics of requested data. This is in contrast to existing efforts that merely provide concurrent support for both models and do not exploit model appropriateness for requested data. The HSAN hybrid model is implemented using low overhead cache-admission and cache-replacement schemes and aims to improve overall response times for a wide variety of workloads. Preliminary analysis of the hybrid model indicates performance improvements over both models.

A core area of P2P systems research is the topology of the overlay network. It has ranged from random unstructured networks like Gnutella to Super-Peer architectures to the recent trend of structured overlays based on distributed hash tables (DHTs) (I. Stoica et al., 2001), (A. Rowstron et al., 2001), (S. Ratnasamy et al., 2001). While the unstructured networks have excessive lookup costs and un-guaranteed lookups, the structured systems offer no anonymity and delegate control over data items to unrelated peers. We present an in-the-middle hybrid architecture which uses a mix of both topologies to create a decentralized P2P infrastructure. The system provides scalable and guaranteed lookups in addition to mutual anonymity and also allows hosting content with the content-owner. We validate our architecture through a thorough analytical and performance analysis of the system.

Session initiation protocol (SIP) is being widely adopted for VoIP, IM and other collaborative applications due to its simple yet rich functional design. However, one of the main drawbacks has been its per-application deployment (each application using its own SIP stack), leading to narrowly focused development of SIP based services. In this paper, we propose a client-side SIP service and supporting network infrastructure blocks that provide unified mechanisms to execute generic SIP functions. The composition of these building blocks allows for creating richer applications, e.g. a conferencing server coupled with a gaming server provides dynamic conferencing between current occupants of a game room. The main feature of our framework is its availability to all applications including the ones not inherently based on SIP. Also, the SIP service API is designed to be extensible and in addition to providing novel higher level functional primitives like adhoc conferencing and seamless transition of sessions, it also exports a low level interface for specialized applications. Another feature of the service is that it allows a user to plug-in an end device of his/her choice on a per-session basis. We demonstrate the richness of the API by describing prototypes for enhancing various applications as well as new converged applications.

Decentralized peer to peer (P2P) networks offer both opportunities and threats. Its open and decentralized nature makes it extremely susceptible to malicious users spreading harmful content like viruses, trojans or, even just wasting valuable resources of the network. In order to minimize such threats, the use of community-based reputations as trust measurements is fast becoming a de-facto standard. The idea is to dynamically assign each peer a trust rating based on its performance in the network and store it at a suitable place. Any peer wishing to interact with another peer can make an informed decision based on such a rating. An important challenge in managing such trust relationships are to design a protocol to secure the placement and access of these trust ratings. Surprisingly, all the related work in this area either support very limited anonymity or assume anonymity to be an undesired feature and neglect it. We motivate the importance of anonymity, especially in such trust based systems. We then present TrustMe: a secure and anonymous underlying protocol for trust management. The protocol provides mutual anonymity for both the trust host and the trust querying peer. Through a series of simulation-based experiments, we show that the TrustMe protocol is extremely secure in the face of a variety of possible attacks and present a thorough analysis of the protocol.

Advances in computing and communication technologies have resulted in a wide variety of networked mobile devices that access data over the Internet. We argue that servers by themselves may not be able to handle this diversity in client characteristics and intermediate proxies should be employed to handle the mismatch between server-supplied data and client capabilities. Since existing proxies are primarily designed to handle traditional wired hosts, such proxy architectures will need to be enhanced to handle mobile devices. We propose such an enhanced proxy architecture that is capable of handling the heterogeneity in client needs - specifically the variations in client bandwidth and display capabilities. Our architecture combines transcoding (which is used to match the fidelity of the requested object to client capabilities) and caching (which is used to reduce the latency for accessing popular objects). Our proxies can intelligently adapt to prevailing system conditions using learning techniques to intelligently decide whether to transcode locally or fetch an appropriate version from the server. Our experimental results indicate that such strategies produce significant improvements in client response times. Further we find that even simple learning techniques can lead to significant performance improvements.