The world of finance and decentralized applications has undergone a revolution with the advent of blockchain technology, resulting in the emergence of various blockchain platforms. This underscores the necessity for conducting exchanges between different blockchains to facilitate blockchain interoperability. However, the challenges linked to the scalability of individual blockchains pose negative implications during inter-chain exchanges. A prominent solution to tackle the scalability challenge in a blockchain, particularly in terms of throughput, is a Payment Channel Network. However, creating such a solution for facilitating inter-blockchain exchange presents significant challenges, as it demands atomic state updating on two different blockchains. In this paper, we introduce a novel, fully distributed mechanism for establishing cross-chain payment channels (CCPC), designated as Tombolo protocol, designed to operate seamlessly across different blockchains. Furthermore, we provided the sequence of steps that the user should follow to facilitate further exchange without contacting either of the involved blockchains. Additionally, we showcase its resilience against malicious behaviour, specifically in situations where a participant attempts to close the channel using an outdated state or becomes inactive during exchanges. Furthermore, we have demonstrated the viability of Tombolo by implementing it on an Ethereum Virtual Machine-based blockchain using Solidity v0.8.0 based smart contracts. Through comprehensive experimentation and evaluation, we illustrate that CCPC can be established with approximately 2.5 times the gas utilization and around twice the time overhead compared to Raiden, a state-of-the-art intra-chain channel.

Serverless computing is rapidly gaining popularity for provisioning composable, auto-scalable and cost-effective applications. An important mechanism for deploying serverless applications is specification of function workflows (via DAGs). The end-to-end life cycle of this process being DAG specification, DAG orchestration, execution of DAG components and persistent storage of application outputs. To the best of our knowledge, an open-source platform that offers functionality along all these components does not exist. Towards this, our primary contribution is DAGit, an open-source solution for serverless applications-as-a-service. The main features of DAGit are interfaces and specifications to register serverless functions, applications (via DAGs) and triggers to instantiate the serverless applications. DAGit provides a rich set of DAG primitives to enable a varied set of applications and also implements a scalable orchestrator for application execution. As part of this work, we present the architecture and design details of DAGit, and demonstrate its feature set via showcasing the specification and execution of a varied set of serverless applications. Further, we also present a performance and resource costs characterization of executing applications on the DAGit platform.

Derivative cloud service providers use nesting to provision virtual computational entities (VCE) within VCEs, e.g., containers runtimes within virtual machines. As part of resource management and ensuring application performance, migration of nested containers is an important and useful mechanism. Checkpoint Restore In Userspace (CRIU) is the dominant method for migration, used by Docker and other container technologies. While CRIU works well for container migration from host to host, it suffers from significant increase in resource requirements in nested setups. The overheads are primarily due to the high network virtualization overhead in nested environments. While techniques such as SR-IOV can mitigate the overheads, they require additional hardware features and tight coupling of network endpoints. Based on our insights of network virtualization being the main bottleneck, we present Portkey - a software-based solution for efficient nested container migration that significantly reduces CPU utilization at both the source and destination hosts. Our solution relies on interposing a layer that directly coordinates network IO from within a virtual machine with the hypervisor. A new set of hypercalls provide this interfacing along with a control loop that minimizes the hypercall path usage. Extensive evaluation of our solution shows that Portkey reduces CPU usage by up to 75% and 82% at the source and destination hosts, respectively.

Structuring cloud applications as collections of interacting fine-grained microservices makes them scalable and affords the flexibility of hot upgrading parts of the application. The current avatar of serverless computing (FaaS) with its dynamic resource allocation and auto-scaling capabilities make it the deployment model of choice for such applications. FaaS platforms operate with user space dispatchers that receive requests over the network and make a dispatch decision to one of multiple workers (usually a container) distributed in the data center. With the granularity of microservices approaching execution times of a few milliseconds combined with loads approaching tens of thousands of requests a second, having a low dispatch latency of less than one millisecond becomes essential to keep up with line rates. When these microservices are part of a workflow making up an application, the orchestrator that coordinates the sequence in which microservices execute also needs to operate with microsecond latency. Our observations reveal that the most significant component of the dispatch/orchestration latency is the time it takes for the request to traverse into and out of the user space from the network. Motivated by the presence of a multitude of low power cores on today's SmartNICs, one approach to keeping up with these high line rates and the stringent latency expectations is to run both the dispatcher and the orchestrator close to the network on a SmartNIC. Doing so will save valuable cycles spent in transferring requests to and back from the user space. The operating characteristics of short-lived ephemeral state and low CPU burst requirements of FaaS dispatcher/orchestrator make them ideal candidates for offloading from the server to the NIC cores. This also brings other benefit of freeing up the server CPU. In this paper, we present Speedo--- a design for offloading of FaaS dispatch and orchestration services to the SmartNIC from the user space. We implemented Speedo on ASIC based Netronome Agilio SmartNICs and our comprehensive evaluation shows that Speedo brings down the dispatch latency from ~150ms to ~140μs at a load of 10K requests per second.

In this work, we present FaaSter, an Accelerated Functions as a Service (AFaaS) offering that unifies the function-as-a-service model with GPU acceleration resources. FaaSter provides an acceleration function library as a service, which in turn is provisioned on heterogeneous GPUs. To provide seamless access to these accelerated functions and ensure that each function has the best possible response time, we utilize GPU kernel slicing to split and execute an accelerated function instance across multiple heterogeneous GPUs. The central challenge is to be able to quickly decide the number of slices to split each function into and then map the slices to the right GPUs. To this end, we present a scheduling heuristic that is able to significantly reduce the average turn-around time of functions when compared to a non-sliceable full GPU scheduling approach. Our evaluation results show that the FaaSter scheduler achieves 62 % mean and up to 80 % improvement in average turn-around time and always performs equal to or better than non-sliceable GPU scheduling.

As the popularity and relevance of the Function-as-a-Service (FaaS) model keeps growing, we believe newer avatars of the service will support computationally intensive SIMT functions that will execute on GPUs. With hardware-assisted virtualization of GPUs now possible, cloud offerings including GPUs usually bind a virtual GPU (vGPU) to a VM. While there is a choice of scheduling algorithms to multiplex vGPUs on to the physical GPU, the work-conserving best-effort scheduler helps to maintain a high level of utilization of the GPU. With this, we observe that the total share of the GPU per VM is non-deterministic and depends on how different VMs load the GPU via their vGPUs. As a result, any function-to-vGPU scheduler that does not explicitly account for this nondeterministic vGPU capacity will suffer from lower than optimal goodput - particularly when these functions are deadline bound as is the case with FaaS offerings today. In this work, we exploit a software based task slicing technique to dynamically determine task sizes for scheduling on vGPUs to maximize successful completion of functions within their deadlines. Our solution extends the conventional earliest-deadline first (EDF) scheduling algorithm by balancing scheduling opportunities (via kernel slicing) and maximizing the chances of functions finishing before their deadline. The work is motivated by the fact that static decisions that consider entire tasks as scheduling units or use a fixed, statically decided slice size as scheduling units cannot adapt to the non-deterministic vGPU capacity. A comparison of our solution with well-known deadline aware scheduling approach (earliest deadline first), yielded an improvement of up to 2.9x in goodput.

Cryptocurrency networks are a promising infrastructure for pseudonymous online payments. However, low throughput has prevented their widespread acceptance. A promising solution to scale throughput is the Payment channel network (PCN), exemplified by the Lightning Network (LN), that uses a network of off-chain bidirectional payment channels between parties that wish to transact often. Since payments use the shortest paths with sufficient funds over this network, channel balances get exhausted in the direction transactions flow and eventually become unidirectional. This results in transactions failing and consequently a lower transaction success ratio. Our observations on the production LN show that over 63% of the channels lose over 80% of the channel balance in one direction over time, which makes the success ratio of a real-world workload drop from 71% to 29%. A unidirectional channel along a path results in a failure message back to the source that recomputes the path, excluding the failed channel and reattempts the transaction, thus adding to the completion latency even for those transactions that do complete.We propose REBAL, a distributed re-balancing mechanism, and a new routing scheme to address the above issues. REBAL maximizes the extent to which channels can be re-balanced across the entire network. REBAL addresses the completion latency issue by re-routing transactions from intermediate nodes around a unidirectional channel rather than propagating the failure back to the source.Our comprehensive evaluation of REBAL shows that the success ratio improves from 30.18% to 79.54% and success volume from 3.98% to 29.99% for a real-world workload derived from the Ripple network, without adversely impacting the transaction latency. Even at very high transaction rates, REBAL outperforms Lightning Network Daemon (LND- a Golang implementation of LN) (12%) with a success ratio of 43.76%.

A Blockchain system such as Ethereum is a peer to peer network where each node works in three phases: creation, mining, and validation phases. In the creation phase, it executes a subset of locally cached transactions to form a new block. In the mining phase, the node solves a cryptographic puzzle (Proof of Work-PoW) on the block it forms. On receiving a block from another peer, it starts the validation phase, where it executes the transactions in the received block in order to ensure all transactions are valid. This execution also updates the blockchain state, which must be completed before creating the next block. A long block validation time lowers the system's overall throughput and brings the well known Verifier's dilemma into play. Additionally, this leads to wasted mining power utilization (MPU).

Organization of tasks as workflows are an essential feature to expand the applicability of the serverless computing framework. Existing serverless platforms are either agnostic to function chains (workflows as a composition of functions) or rely on naive provisioning and management mechanisms of the serverless framework---an example is that they provision resources after the trigger to each function in a workflow arrives thereby forcing a setup latency for each function in the workflow. In this work, we focus on mitigating the cascading cold start problem--- the latency overheads in triggering a sequence of serverless functions according to a workflow specification. We first establish the nature and extent of the cascading effects in cold start situations across multiple commercial server platforms and cloud providers. Towards mitigating these cascading overheads, we design and develop several optimizations, that are built into our tool Xanadu. Xanadu offers multiple instantiation options based on the desired runtime isolation requirements and supports function chaining with or without explicit workflow specifications. Xanadu's optimizations to address the cascading cold start problem are built on speculative and just-in-time provisioning of resources. Our evaluation of the Xanadu system reveals almost complete elimination of cascading cold starts at minimal cost overheads, outperforming the available state of the art platforms. For even relatively short workflows, Xanadu reduces platform overheads by almost 18x compared to Knative and 10x compared to Apache Openwhisk.

Summary Live migrations of virtual machines are required in cloud data centers in various contexts such as evacuating a host machine for maintenance, balancing the workloads on host machines, optimizing physical resource utilization, and meeting the custom demands of the user applications. Virtual machine migrations can, however, be costly in terms of both resources consumed for the migration as well as in terms of service level agreement (SLA) violations during the migration window. The cost is determined by many factors and they, in turn, are impacted by WHEN the migration happens during the lifetime of the virtual machine. Empirical studies show that if we have a window in which the migration is to be done (proactive rather than reactive where no such window exists), we can do it by carefully choosing the starting point within the window so that the SLA violation is minimum. In this paper, we propose a model to migrate virtual machines opportunistically to minimize the SLA violations. The idea is to find the time instants, called opportunities, at which, if the migration starts, the number and extent of SLA violations are minimal. Our experiments show that the migrations time savings with opportunistic migrations are up to 25%.

IaaS providers offer virtual machines of fix granularity which has prompted the evolution of derivative clouds. With a derivative setup where containers are provisioned within virtual machines, the guest OS manages virtual resources inside a VM whereas the hypervisor manages the physical resources distributed among VMs. This results in two control centers over the set of resources used by the containers. The hypervisor takes control actions such as memory ballooning or the withdrawal of a virtual CPU to manage over-provisioning without being aware of the effect these actions will have on individual containers inside the VM. The derivative cloud provider executing containers in the VM needs a mechanism to react to such changes—based on resource management policies setup for this purpose. In this work we first show via experimental results that hypervisor actions used to manage over-commitment such as ballooning and vCPU stealing have unpredictable and non-deterministic effects on nested containers. Based on this analysis, we design a policy driven controller that smoothes over the effect of these hypervisor actions on these nested containers. We expose several useful policies for each resource type (CPU and Memory) that can help derivative cloud providers better manage container instances.

Summary The efficient use of energy is essential to address concerns of cost and sustainability. Many data centers contain MapReduce clusters to process Big Data applications. A large number of machines and fault tolerance capabilities make MapReduce clusters energy inefficient. In this paper, we present a Configurator based on performance and energy models to improve the energy efficiency of MapReduce systems. Our solution is novel as it takes into account the dependence of the performance and energy consumption of a cluster on MapReduce parameters. While this dependence is known, we are the first to model it and design a Configurator to optimize these parameter settings for maximizing the energy efficiency of MapReduce systems. Our empirical evaluations show that the Configurator can result in up to 50% improvement in the energy efficiency of typical MapReduce applications in two architecturally different clusters.

Several emerging applications such as traffic management and urban emergency response systems often need to identify groups from recent window of the moving object data. These requirements mandate algorithmic solutions that are time and memory efficient for adding new data incrementally and removing stale data. In this paper, we consider the problem of finding closed Swarms over a sliding window. The key challenges in computing closed Swarms over a sliding window are: (i) Search space for computing closed Swarms from new data is large (ii) Removal of old data leaves many non-closed Swarms which need to be identified and deleted. None of the existing methods are efficient in adding new data and removing old data for large datasets. This paper presents an efficient incremental graph based method for computing Swarms over sliding windows. We use a real dataset to show the performance of our method. The complexity analysis as well as experimental results demonstrate that our method is significantly faster than the existing incremental method over sliding windows with increased memory requirement. In particular, our method is shown to be 7-13 times faster with 3-5 times memory overhead in all the experiments.

A Virtual Data Center (VDC) is a set of virtual machines (VMs) connected by a Virtual Network (VN) topology. Today's cloud data centers support dynamic requests for VDCs, by using software defined embedding strategies thatallow them to mesh multiple VDCs onto their Physical Data Center(PDC) network and machines. In this paper, we present a solution to this VDC embedding problem that achieves a higher acceptance rate by minimizing fragmentation, compared to existing strategies, while at the same time minimally disrupting the existing VDCs.

The fixed granularity of virtual machines offered by IaaS providers has prompted the evolution of derivative clouds where resources are repackaged into smaller containers and leased out typically in PaaS mode. In such a setup, containers are provisioned within virtual machines. Such a nested setup results in two control centers for the resources used by those containers—the guest OS and the Hypervisor. The latter’s control actions are agnostic of the application executing within a VM. This lack of visibility may result in hypervisor control that has a non-uniform effect on the VM’s nested containers which is undesirable. In this work, we propose policy based control of the effect of the hypervisor’s control actions amongst the containers nested in the affected VM.

Service-oriented Architecture (SOA) has been recognized as a key technology for operating IoT-based systems, by abstracting sensing and actuation capabilities of IoT resources via services or microservices. However, such systems being dynamic in nature, must be proactive in responding to changing circumstances, hence they need to be autonomic in nature. Therefore this requires the design and deployment of an autonomic serviceoriented middleware that can mediate interactions, and control sensing & actuation, within the IoT-based system. To that end, in this paper, we present our vision of an autonomic service-oriented middleware AUSOM (pronounced "awesome") for IoT based systems. The key features of AUSOM are: incorporation of the well-known MAPE-K loop (Monitor, Analyze, Plan, Act, using stored Knowledge) from autonomic computing for proactive adaptation, incorporation of a multilayered context model, and using contextual information to facilitate adaptation at the IoT device (sensor and actuator) layer. We present the architecture of AUSOM and also illustrate how it would function via a simple yet realistic example.

While the challenge of connecting Internet of Things (IoT) devices at the lowest layer has been widely studied, integrating and interoperating huge amounts of sensed data of heterogeneous IoT devices is becoming increasingly important because of the possibility of consuming such data in supporting many potential novel IoT applications. A common approach to processing and consuming IoT data is a centralized paradigm: sensor data is sent over the network to a comparatively powerful central server or a cloud service, where all processing takes place. However, this approach has some limitations as it requires devices to interact directly with a cloud which is not cost effective. First, it has high demands on the device's storage and computational capabilities. Second, as devices grow rapidly in a deployment area, sending all the data to a centralized cloud server requires high network bandwidth. Moreover, this often creates data privacy concerns as all raw data will be sent to a centralized place. To address the above limitations for building future Internet of Things applications, we present an early design of a novel framework that combines Internet of Things, Semantic Web, and Big Data concepts. We not only present the core components to build an IoT system, but also list existing alternatives with their merits. This framework aims to incorporate open standards to address the potential challenges in building future IoT applications. Therefore, our discussion revolves around open standards to build the framework, rather than proprietary standards.

The Internet of Things (IoT) phenomenon is creating a world of billions of connected devices generating enormous amounts of data items. In particular, for purposes of high availability and disaster recovery, replication of this data on cloud storage needs to be implemented efficiently. To that end, in this paper, we investigate the combined problem of uploading IoT data from a set of sensor gateways and efficient replication of this data on distributed cloud storage. While other efforts do exist in this space, either they do not consider replication in context of small size and high number of data items, which is inherent nature of IoT data or they concentrate on the access time after replication. Our solution assumes the existence of multiple distributed cloud data centers, called mini-Clouds, among which data can be replicated. We model our problem comprehensively based on various parameters such as effective bandwidth of the IoT network, available number and size of data items at each mini-Cloud, and we present our problem as a collection of various sub-problems based on subsets of these parameters. We prove that the exact solution to the problem is intractable, and we present a number of heuristic strategies to solve it. Our results show that the performance of any heuristic is bounded by the read and write latency of mini-Clouds and the best we can do is often 12 times the worst we can do for a given number of data items to be uploaded and replicated from the gateways to the mini-Clouds in test setup.

Existing Virtual Machine (VM) placement schemes have looked to conserve either CPU and Memory on the physical machine (PM) OR network resources (bandwidth) but not both. However, real applications use all resource types to varying degrees. The result of applying existing placement schemes to VMs running real applications is a fragmented data center where resources along one dimension become unusable even though they are available because of the unavailability of resources along other dimensions. An example of this fragmentation is unusable CPU because of a bottlenecked network link from the PM which has available CPU. To date, evaluations of the efficacy of VM placement schemes has not recognized this fragmentation and it's ill effects, let alone try to measure it and avoid it. In this paper, we first define the notion of what we term "relative resource fragmentation" and illustrate how it can be measured in a data center. The metric we put forth for capturing the degree of fragmentation is comprehensive and includes all key data center resource types. We then propose a VM placement scheme that minimizes this fragmentation and therefore maximizes the utility of data center resources. Results of empirical evaluations of our placement scheme compared to existing placement schemes show a reduction of fragmentation by as much as 15% and an increase in the number of successfully placed applications by as much as 20%.

In an Infrastructure-as-a-Service cloud, cloud block storage offers conventional, block-level storage resources via a storage area network. However, compared to local storage, this multilayered cloud storage model imposes considerable I/O overheads due to much longer I/O path in the virtualized cloud. In this paper, we propose a novel byte-addressable storage stack, BASS, to bridge the addressability gap between the storage and network stacks in cloud, and in return boost I/O performance for cloud block storage. Equipped with byte-addressability, BASS not only avails the benefits of using variable-length I/O requests that avoid unnecessary data transfer, but also enables a highly efficient non-blocking approach that eliminates the blocking of write processes. We have developed a generic prototype of BASS based on Linux storage stack, which is applicable to traditional VMs, lightweight containers and physical machines. Our extensive evaluation with micro-benchmarks, I/O traces and real-world applications demonstrates the effectiveness of BASS, with significantly improved I/O performance and reduced storage network usage.

Energy efficiency is a major concern in today's data centers that house large scale distributed processing systems such as data parallel MapReduce clusters. Modern power aware systems utilize the dynamic voltage and frequency scaling mechanism available in processors to manage the energy consumption. In this paper, we initially characterize the energy efficiency of MapReduce jobs with respect to built-in power governors. Our analysis indicates that while a built-in power governor provides the best energy efficiency for a job that is CPU as well as IO intensive, a common CPU-frequency across the cluster provides best the energy efficiency for other types of jobs. In order to identify this optimal frequency setting, we derive energy and performance models for MapReduce jobs on a HPC cluster and validate these models experimentally on different platforms. We demonstrate how these models can be used to improve energy efficiency of the machine learning MapReduce applications running on the Yarn platform. The execution of jobs at their optimal frequencies improves the energy efficiency by average 25% over the default governor setting. In case of mixed workloads, the energy efficiency improves by up to 10% when we use an optimal CPU-frequency across the cluster.

To reduce the migration time of a virtual machine and network traffic generated during migration, existing works have proposed a number of optimizations to pre-copy live migration. These optimizations are delta compression, page skip, deduplication, and data compression. The cost-benefit analysis of these optimizations may preclude the use of certain optimizations in specific scenarios. However, no study has compared the performance & cost of these optimizations, and identified the impact of application behaviour on performance gain. Hence, it is not clear for a given migration scenario and an application, what is the best optimization that one must employ?

To date, virtual machine (VM) placement has traditionally been viewed as a bin packing problem where a number of virtual machines need to be placed on a given number of physical machines. The goal of bin packing based approach is to minimize the number of physical machines (PMs) used. However, the resource utilization of VMs is dynamic unlike static artifacts in the bin packing problem and varies with the workload being handled by applications on the VM. This means that tight packing may result in a situation where the applications run out of resources needed to handle the workload since there is no room to expand. This will trigger a VM migration to another PM having sufficient resources to allow the VM to expand. Migration is an expensive process both in terms of the resources needed for migration as well as in terms of the degradation of application performance during migration. A simple solution to this is to simply provision every VM for its peak usage-however this results in wasted resources since peaks occur infrequently and only for short durations of time. This peak usage based approach is one of very loose packing which is inefficient but provides stability of the VM in the context of migration. What we need is a balance between the tightness of packing (to optimize the number of physical machines used) and VM stability (to minimize the number of the migrations resulting from a given placement). In this paper we propose a metric to quantify this notion of balance and an algorithm to place VMs so as to minimize “imbalance”. We show through extensive experiments that balanced placement is not so loose as to be inefficient while giving us good stability as measured from the number of resource shortfalls that would occur with a given placement. In our experiments we found that balanced placement results in 15 to 80 percent lesser resource shortfalls and upto 90 percent less severe resource shortfalls when compared to other placement schemes.

While virtualized solutions are firmly entrenched in cloud data centers to provide isolated execution environments, the chief overhead it suffers from is that of memory consumption. Even pages that are common in multiple virtual machines (VMs) on the same physical machine (PM) are not shared and multiple copies exist thereby draining valuable memory resources and capping the number of VMs that can be instantiated on a PM. Lightweight containers (LWCs) on the other hand does not suffer from this situation since virtually everything is shared via Copy on Write semantics. As a result the capacity of a PM to host LWCs is far higher than hosting equivalent VMs. In this paper, we evaluate a solution using uKSM to exploit memory page redundancy amongst multiple VMs on a PM executing the same operating system thereby enabling a comparison of the two technologies as far as its capacity to instantiate multiple instances is concerned. We performed a thorough empirical evaluation of the two solutions and present comprehensive results.

Although many models exist to predict the time taken to migrate a virtual machine from one physical machine to another, our empirical validation of these models has shown the 90th percentile error to be 46% (43 secs) and 159% (112 secs) for KVM and Xen live migration, respectively. Our analysis reveals that these models are fundamentally flawed as they all fail to take into account the following three critical parameters: (i) the writable working set size, (ii) the number of pages eligible for the skip technique, (iii) the relation of the number of skipped pages with the page dirty rate and the page transfer rate, and incorrectly model the key parameter---the number of new pages dirtied per unit time. In this paper, we propose a novel model that takes all these parameters into account. We present a thorough validation with 53 workloads and show that the 90th percentile error in the estimated migration times is only 12% (8 secs) and 19% (14 secs) for KVM and Xen live migration, respectively.

Power consumption costs takes up to half of the operational expenses of data centers, making power management a critical concern. Advances in processor technology provide fine-grained control over operating frequency of processors and this control can be used to trade off power for performance. We show that existing power models incorrectly assume quadratic relationship between power and frequency, leading to higher inaccuracy in prediction. Moreover, existing performance models have significant error margins while predicting performance of memory or file-intensive tasks and HPC applications due to negligence of the combined effects of frequency and CPU variations on the task execution time. In this paper, we empirically derive power and completion time models using linear regression with CPU utilization and operating frequency as parameters. We validate our power model on several Intel and AMD processors by predicting within 2-7% of measured power. We validate our completion time model using five kernels of NASA Parallel Benchmark suite and five CPU, memory and file-intensive benchmarks on four heterogeneous systems and predicting within 1-6% of observed performance.

The rapid adoption of cloud computing has led to the proliferation of cloud providers, along with increasing options offered by them. Currently cloud providers offer a wide range of services (machine sizes, availability modes, storage etc.) with complex pricing schemes (spot pricing, reservation pricing, etc.). At the same time, customers require distributed deployments in order to meet their own SLA commitments. This has led to the concept of multi-site multi-cloud deployment schemes that allows enterprises to deploy highly performant distributed applications such as gaming using multiple cloud providers. Existing research has solved the problem of cost optimization of such deployments BUT under the assumption of a single pricing scheme for all providers. The introduction of varied and dynamic pricing introduces several complexities that needs a fresh look at this problem. In this paper we present a solution for mapping the compute and storage requirements of a set of related enterprise sites onto cloud providers who offer multiple, dynamic pricing schemes. Our goal is to optimize the cost of a multi-site deployment consisting of compute and storage components at each site while meeting SLA requirements of the application. We show that our approach can achieve cost reductions of up to 22% for the customer even for medium sized deployments consisting of tens of sites over the scheme that uses either a single cloud provider or fixed pricing schemes.

Geometric simplification is a widely used technique in the field of cartographic generalization. Many algorithms already exist in this field to simplify a geometry so that the number of points in the geometry is reduced while it retains its approximate shape. In this paper, a new algorithm, Moving Window Geometry Simplification (MWGS) algorithm is presented that can be used to reduce a geometry under a given set of constraints. The proposed algorithm uses the technique called sweep line to reduce a geometry and also ensures that none of the constraints are violated. Both computational and algorithmic aspect of the technique are considered for better performance and scaling. The method has important applications in areas relating to map generalization, map compression etc. This algorithm reduced approximately 90% of the points in all the datasets.

In an effort to bridge the gap between public and personal transportation shared cabs are becoming attractive option, especially in large metropolitan areas. Places that see an aggregation of passengers such as airports and railway stations are well suited to serve as hubs from which vehicles are dispatched. While the standard vehicular routing problem has many solutions already, in this project, we consider two major variants of the problem - (a) The dynamic arrival of requests to destinations rather than a static set of such requests being used to solve the routing problem (b) The addition of a constraint that specifies the maximal acceptable deviation from the shortest route to a given destination.

Virtual machine migration enables load balancing, hot spot mitigation and server consolidation in virtualized environments. Live VM migration can be of two types - adaptive, in which the rate of page transfer adapts to virtual machine behaviour (mainly page dirty rate), and non-adaptive, in which the VM pages are transferred at a maximum possible network rate. In either method, migration requires a significant amount of CPU and network resources, which can seriously impact the performance of both the VM being migrated as well as other VMs. This calls for building a good understanding of the performance of migration itself and the resource needs of migration. Such an understanding can help select the appropriate VMs for migration while at the same time allocating the appropriate amount of resources for migration. While several empirical studies exist, a comprehensive evaluation of migration techniques with resource availability constraints is missing. As a result, it is not clear as to which migration technique to employ under a given set of conditions. In this work, we conduct a comprehensive empirical study to understand the sensitivity of migration performance to resource availability and other system parameters (like page dirty rate and VM size). The empirical study (with the Xen Hypervisor) reveals several shortcomings of the migration process. We propose several fixes and develop the Improved Live Migration technique (ILM) to overcome these shortcomings. Over a set of workloads used to evaluate ILM, the network traffic for migration was reduced by 14-93% and the migration time was reduced by 34-87% compared to the vanilla live migration technique. We also quantified the impact of migration on the performance of applications running on the migrating VM and other co-located VMs.

Server consolidation has emerged as an important technique to save on energy costs in virtualized datacenters. The issue of instantiation of a given set of Virtual Machines (VMs) on a set of Physical Machines (PMs) can be thought of as consisting of a provisioning step where we determine the amount of resources to be allocated to a VM and a placement step which decides which VMs can be placed together on a physical machines thereby allocating VMs to PMs. In this paper, we introduce a provisioning scheme which takes into account acceptable intensity of violation of provisioned resources. In addition we identify a serious shortcoming of existing placement schemes that correct in our correlation aware placement scheme. We consider correlation among aggregated resource demands of VMs while finding the VM-PM mapping. Experimental results reveal that our approach leads to a significant amount of reduction in the number of servers (up to 32% in our settings) required to host 1000 VMs and thus enables us to turn off unnecessary servers. It achieves this by packing VMs more tightly by correlating resource requirements across the entire set of VMs to be placed. We present a comprehensive set of experimental results comparing our scheme with the existing provisioning and placement schemes.

In Software-as-a-Service (SaaS) cloud delivery model, a hosting center deploys a Virtual Machine (VM) image template on a server on demand. Image templates are usually maintained in a central repository. With geographically dispersed hosting centers, time to transfer a large, often GigaByte sized, template file from the repository faces high latency due to low Internet bandwidth. An architecture that maintains a template cache, collocated with the hosting centers, can reduce request service latency. Since templates are large in size, caching complete templates is prohibitive in terms of storage space. In order to optimize cache space requirement, as well as, to reduce transfers from the repository, we propose a differential template caching technique, called DiffCache. A difference file or a patch between two templates, that have common components, is small in size. DiffCache computes an optimal selection of templates and patches based on the frequency of requests for specific templates. A template missing in the cache can be generated if any cached template can be patched with a cached patch file, thereby saving the transfer time from the repository at the cost of relatively small patching time. We show that patch based caching coupled with intelligent population of the cache can lead to a 90% improvement in service request latency when compared with caching only template files.

Several applications in the "physical'' world are being consolidated in "virtual'' environments using different virtualization technologies. An important criteria for this exercise is to understand potential resource requirements and performance levels achieved in virtual environments. Empirical evidence of these can be gotten by benchmarking the application's performance in a controlled manner in virtual environments. These measurements can be used for a variety of purposes from virtual machine capacity planning to building sophisticated performance models to predict performance for loads that cannot be practically tested. In this paper, we present VirtPerf, an integrated workload generator and measurement tool to capture resource utilization levels and performance metrics of applications executing under controlled circumstances in virtualized environments. The tool aims to provide comprehensive measurement-based analysis for applications in different virtualization settings. Additionally, a configurable workload generator can be used to stress and profile applications under different load conditions. We present the detailed design of VirtPerf and a comprehensive empirical study to demonstrate its correctness and capabilities.

The presence of multiple services sharing a common functional interface necessitates differentiating between them on the basis of their performance. However advertised quality of service (QoS) alone cannot paint the true picture of how the service has performed so far and how it will continue to function in the near future. This information is crucial for service selection. In this paper, we outline a method of monitoring and extrapolating service performance and using the same for automated service selection process.

Web services are self-describing, platform independent applications that can be accessed over the Internet. Web services enable us to dynamically find, bind and consume the needed functionality. Semantic Web services are being developed with the vision of automating this process and to facilitate interoperable machine to machine interaction with no/minimal human intervention. Semantic descriptions provide an opportunity to derive additional functionality simply by composing existing services together. Various composition approaches have been proposed for service composition. However existing approaches have failed to take the important aspects of preconditions and effects into consideration. This reduces the accuracy of the composition process and leads to false positives which must be avoided. In this paper we first motivate the need for precondition and effect matching in composition and identify the limitations of existing approaches. We propose an algorithm for composition which addresses problems in current approaches and employs the complete semantic description of inputs, outputs, preconditions, effects. We also propose a distributed architecture for implementation of the composer. Finally we demonstrate effectiveness of our approach by comparing with existing approaches.

Guaranteeing quality of service (QoS) for event delivery has been recognized as an important but challenging issue in event based middleware (EBM), that is responsible for routing events from publishers to subscribers over an event broker network. Amongst the numerous QoS parameters, in our work, we focus on reliability as a service guarantee to subscribers in an EBM. We add to the existing body of work in this area by investigating reliability needs of type-specific subscriptions and comparing them with type-agnostic subscriptions. The broker network establishes routes by maintaining event-type specific path-quality information at every broker node occurring in the route to the destination. Each broker node measures the drop probability of a particular event type. We prove that the drop probabilities experienced by individual event types are proportional to the ratio of their inter-arrival times at the broker. Based on this, we present the TSAR (Type Specific Adaptive Reliability) algorithm. where route establishment is done in an adaptive and decentralized fashion using persistent type-specific path quality information stored as a matrix of reliability estimates. Our results show that TSAR (1) reduces the overall message complexity as compared to existing efforts in this area (2) provides subscribers with a higher level of granularity when subscribing to events and adapts to the dynamics of the broker network with varying reliabilities of broker nodes.

The promise of dynamic binding and the ability to dynamically and seamlessly move between service providers can only be realized through the path of semantic expressibility. Once we describe the semantics of a service in itpsilas advertisement, a semantic matchmaker can match a query with the set of advertisements that satisfy the query conditions. The state of the art today uses the IOPE (Inputs Outputs Preconditions and Effects) form of advertisements with languages such as OWL-S being used to represent the semantics. Inputs and outputs usually refer to concepts in an ontology. Many semantic matchmakers exist today and they focus on matching the IOPE form of the advertisement to the query. This may result in many matches and they return a set of matched advertisements without rank ordering them. We believe itpsilas important to rank the returned set of services in order to choose the best service. In this paper we present such a ranking algorithm that uses the IOPE information present in the each of the services relative to the query. Our algorithm can complement other approaches that use the history of issued queries and data mining. We have evaluated the effectiveness of the ranking algorithm against a benchmark ranking that is done manually and shown that our ranking scheme is close to the best ranking scheme possible.

Online update is a technique that reduces the disruption caused by a software update. It does so by applying a patch to a running process as opposed to shutting down the process and restarting it. The challenge here lies in ensuring correct operation during and after the update. In this paper, we present the correctness criteria involved in such situations and a solution to performing updates safely based on these correctness criteria. The approach we use avoids deadlocks during update by analyzing interthread dependencies and guarantees that the process remains in a consistent state after the update. Thus, the update procedure is guaranteed to terminate and the requests that execute during and after an update are ensured correct execution. Our literature survey reveals that this is amongst the first solutions to update concurrent programs while requests are executing and ensure correctness.

Central to the notion of dynamic binding and loose coupling that underlie service-oriented architectures is dynamic service discovery. At the heart of most service discovery mechanisms is a matchmaking algorithm that matches a semantic query to a set of compatible web service advertisements. These advertisements also describe service semantics as a set of OWL-S terms. Most current matchmaking algorithms are based on semantic matching of input and output terms alone. However, a complete description of the service profile also includes preconditions and effects and in order to find a true match the matchmaker needs to match on these aspects of the advertisement as well. In this paper, we make the case for augmenting existing matchmaking algorithms with preconditions and effects in the context of Web Services. Further, we propose an algorithm for condition matching that is layered on the top of input-output term matching that overcomes the limitations of existing work. Although the problem of condition matching is NP-Complete, we can overcome this limitation by using a set of heuristics that gives us results in polynomial time. We also analyze complexity of the algorithm by comparing it with brute force approach of matching. We show that our algorithm yields results more efficiently than brute force matching but with the same accuracy.

The ability to dynamically discover and invoke a Web service is a critical aspect of service oriented architectures. An important component of the discovery process is the matchmaking algorithm itself. In order to overcome the limitations of a syntax-based search, matchmaking algorithms based on semantic techniques have been proposed. Most of them are based on an algorithm originally proposed by M. Paolucci, et al. [19]. In this paper, we analyze this original algorithm and identify some correctness issues with it. We illustrate how these issues are an outcome of the greedy approach adopted by the algorithm. We propose a more exhaustive matchmaking algorithm, based on the concept of matching bipartite graphs, to overcome the problems faced with the original algorithm. We analyze the complexity of both the algorithms and present performance results based on our implementation of both these algorithms. We show that the complexity of our algorithm is equivalent to that of the original algorithm in spite of the improvements we have made to address the correctness issues.

Event broker networks (EBN) are a scalable incarnation of the publish subscribe paradigm for building asynchronous systems. These take the form of overlays of broker nodes and several routing schemes exist that deliver events from publishers to subscribers efficiently on different overlay structures. However quality of service based routing schemes are rare and our work addresses this gap. Specifically we look into the prospect of routing events based on reliability requirements of subscribers for an event type being delivered via the EBN. In this paper, we formally define reliability and propose a multiplicative model which calculates reliability of the P2P overlay routing substrate and an algorithm based on this model, to deliver event notifications to the client. We employ a technique called 'pruning' by which we restrict flooding the entire overlay routing substrate, when finding a reliable path. The complexity analysis of our algorithm shows that it finds a reliable path with a lower message complexity, as compared to the flooding approach. Our algorithm also determines a path with higher reliability than the path established by Hermes. We present initial simulation results, using the Hermes middleware simulator.

Agile software development practices encourage the evolutionary paradigm of software construction. The result is a series of changes made to the code and designs starting from an initial version. However, rarely do designs keep pace with the changes in code - rather they are often outdated with the first few releases. The problem is only compounded by the various design representations that together comprise the design (state diagrams, class diagrams etc.). This adversely affects development since it is best to begin the process of evolution with the latest design representation that is consistent with the code since it provides a high level view of the system that is easy to understand. Such evolutionary practices therefore present three main challenges from a development environment perspective: (1) Consistency amongst different design representations (2) Traceability of design into code and vice versa (3) Versioning of designs along with code to maintain a consistent view of the application evolution. Our research presents solutions to all three issues starting from a relational meta-model of development and design entities. We have already published results that showcase our solution to the first two problems - in this paper we present an algorithm to version design and code so that the developer always sees a consistent snapshot and prove that this algorithm satisfies the safety requirements of consistency. We also outline an architecture rooted in the layered SCM model to support our versioning scheme.

Maintenance downtime and overheads for applying patches are major concerns for systems requiring round the clock availability. Hence, methods for carrying out dynamic updates are needed. However, correctness of the system during and after every dynamic update needs to be ensured. This paper defines two safety criteria, type consistency and isolation of process execution/or dynamic software update. Updates involving one or more insertions of new classes, removals of old classes and replacements of old classes are considered. The condition for producing a type safe update schedule is defined. The parts of the program whose executions have to be isolated from process update are annotated by the user. Conditions are also provided for ensuring isolation of the update process from execution of annotated parts of the program.

In this paper, the author has presented the challenges in global software development and then identified the gaps in the academic curriculum that should be addressed in order to train software engineers to be cognizant of current issues in executing large, global software projects. We have also outlined a practically oriented academic course that will stress on the skills needed to actually execute global projects. Over multiple offerings of such a course we hope to abstract out the actual issues faced and present suitable solutions as learnings

The need to provide differentiated levels of service for e-commerce and other applications over the Internet has led to the advent of network technologies such as MPLS and Diffserv which allow us to shape traffic over a given network. However, translating the needs of an application in terms of network resources to specific network configurations still remains difficult and the task is accomplished mostly in a manual way. This is not scalable when there are many applications demanding different QoS levels of the network and these needs are changing dynamically. Our effort is focused on algorithms that can automate the translation of application needs to network configurations in MPLS networks.