Thesis (M.S. in Engineering Science)--Naval Postgraduate School, December 2003. / Thesis advisor(s): David C. Jenn, D. Curtis Schleher. Includes bibliographical references (p. 95-96). Also available online.

published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

Cloud computing is a new computing paradigm that aims to transform computing services into a utility, just as providing electricity in a “pay-as-you-go” manner. Data centers are increasingly adopting virtualization technology for the purpose of server consolidation, flexible resource management and better fault tolerance. Virtualization-based cloud services host networked applications in virtual machines (VMs), with each VM provided the desired amount of resources using resource isolation mechanisms. Effective network performance isolation is fundamental to data centers, which offers significant benefit of performance predictability for applications. This research is application-driven. We study how network performance isolation can be achieved for latency-sensitive cloud applications. For media streaming applications, network performance isolation means both predicable network bandwidth and low-jittered network latency. The current resource sharing methods for VMs mainly focus on resource proportional share, whereas ignore the fact that I/O latency in VM-hosted platforms is mostly related to resource provisioning rate. The resource isolation with only quantitative promise does not sufficiently guarantee performance isolation. Even the VM is allocated with adequate resources such as CPU time and network bandwidth, problems such as network jitter (variation in packet delays) can still happen if the resources are provisioned at inappropriate moments. So in order to achieve performance isolation, the problem is not only how many/much resources each VM gets, but more importantly whether the resources are provisioned in a timely manner. How to guarantee both requirements to be achieved in resource allocation is challenging. This thesis systematically analyzes the causes of unpredictable network latency in VM-hosted platforms, with both technical discussion and experimental illustration. We identify that the varied network latency is jointly caused by VMM CPU scheduler and network traffic shaper, and then address the problem in these two parts. In our solutions, we consider the design goals of resource provisioning rate and resource proportionality as two orthogonal dimensions. In the hypervisor, a proportional share CPU scheduler with soft real-time support is proposed to guarantee predictable scheduling delay; in network traffic shaper, we introduce the concept of smooth window to smooth packet delay and apply closed-loop feedback control to maintain network bandwidth consumption. The solutions are implemented in Xen 4.1.0 and Linux 2.6.32.13, which are both the latest versions when this research was conducted. Extensive experiments have been carried out using both real-life applications and low-level benchmarks. Testing results show that the proposed solutions can effectively guarantee network performance isolation, by achieving both predefined network bandwidth and low-jittered network latency. / published_or_final_version / Computer Science / Master / Master of Philosophy

Within a decade, multicore processors emerged and revolutionised the world of computing. Nowadays, even a low-end computer comes with a multi-core processor and is capable running multiple threads simultaneously. It becomes impossible to make the best computation power out from a computer with a single-threaded program. Meanwhile, writing multi-threaded software is daunting to a lot of programmers as the threads share data and involve complicated synchronisation techniques such as locks and conditions. Software transactional memory is a promising alternative model that programmers simply need to understand transactional consistency and segment code into transactions. Programming becomes exciting again, without races, deadlocks and other issues that are common in lock-based paradigms. To pursue high throughput, performance-oriented computers have several multicore processors per each. A processor’s cache is not directly accessible by the cores in other processors, leading to non-uniform latency when the threads share data. These computers no longer behave like the classical symmetric multiprocessor computers. Although old programs continue to work, they do not necessary benefit from the added cores and caches. Most software transactional memory implementations fall into this category. They rely on a centralised and shared meta-variable (like logical clock) in order to provide the single-lock atomicity. On a computer with two or more multicore processors, the single and shared meta-variable gets regularly updated by different processors. This leads to a tremendous amount of cache contentions. Much time is spent on inter-processor cache invalidations rather than useful computations. Nevertheless, as computers with four processors or more are exponentially complex and expensive, people would desire solving sophisticated problems with several smaller computers whenever possible. Supporting software transactional consistency across multiple computers is a rarely explored research area. Although we have similar mature research topics such as distributed shared memory and distributed relational database, they have remarkably different characteristics so that most of the implementation techniques and tricks are not applicable to the new system. There are several existing distributed software transactional memory systems, but we feel there is much room for improvement. One crucial area is the conflict detection mechanism. Some of these systems make use of broadcast messages to commit transactions, which are certainly not scalable for large-scale clusters. Others use directories to direct messages to the relevant nodes only, but they also keep visible reader lists for invalidation per node. Updating a shared reader lists involves cache invalidations on processors. Reading shared data on such systems are more expensive compared to the conventional low-cost invisible reader validation systems. In this research, we aim to have a distributed software transactional memory system, with distributed clock validation for conflict detection purpose. As preparation, we first investigate some issues such as concurrency control and conflict detection in single-node systems. Finally, we combine the techniques with a tailor-made cache coherence protocol that is differentiated from typical distributed shared memory. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

The combination of traditional process migration and the new virtualization technology enables mobility of virtual machines and resource provisioning within data centers. While applied to wide area network (WAN), a traditional migration algorithm has to adjust itself according to the various WAN situations and VM status. This thesis identifies four performance measurements of a VM migration: total migration time, downtime, remote up time and performance degradation. It observes that the total migration time and the remote up time of traditional pre-copy over WAN is too long to tolerate. This thesis claims that even for WAN, post-copy could be used to improve the total migration time and remote up time, only by introducing tolerable, predictable and controllable performance degradation. The adaptiveness of the migration algorithm is concerned. It proposes a hybrid solution of pre-copy and post-copy, both for memory and storage, to do the migration. In the hybrid solution, a fraction of memory (Mfrac) and a fraction of storage (Sfrac) are migrated in the pre-copy and freeze-and-copy phase, and the remaining are migrated in the post-copy phase. A model-based solution with the help of profiling is proposed to adaptively find the best combination of Mfrac and Sfrac. The evaluation part suggests that the proposed solution could adapt to different application behaviors and network conditions. / published_or_final_version / Computer Science / Master / Master of Philosophy

abstract / Electrical and Electronic Engineering / Doctoral / Doctor of Philosophy

Recent years witness the proliferation of Infrastructure-as-a-Service (IaaS) cloud services, which provide on-demand resources (CPU, RAM, disk, etc.) in the form of virtual machines (VMs) for hosting services of third parties. As such, the way of enabling scalable and dynamic Internet applications has been remarkably revolutionized. More and more Application Service Providers (ASPs) are launching their applications in clouds, eliminating the need to construct and operate their owned IT hardware and software. Given the state-of-the-art IaaS offerings, it is still a problem of fundamental importance how the ASPs should rent VMs from the clouds to serve their application needs, in order to minimize the cost while meeting their job demands over a long run. Cloud providers offer different pricing options to meet computing requirements of a variety of applications. The commonly adopted cloud pricing schemes are (1) reserved instance pricing, (2) on-demand instance pricing, and (3) spot instance pricing. However, the challenge facing an ASP is how these pricing schemes can be blended to accommodate arbitrary demands at the optimal cost. In this thesis, we seek to integrate all available pricing options and design effective online algorithms for the long-term operation of ASPs. We formulate the long-term-averaged VM cost minimization problem of an ASP with time-varying and delay-tolerant workloads in a stochastic optimization model. An efficient online VM purchasing algorithm is designed to guide the VM purchasing decisions of the ASP based on the Lyapunov optimization technique. In stark contrast with the existing studies, our online VM purchasing algorithm does not require any a priori knowledge of the workload or any future information. Moreover, it addresses the possible job interruption due to uncertain availability of spot instances. Rigorous analysis shows that our algorithm can achieve a time-averaged VM purchasing cost with a constant gap from its offline minimum. Trace-driven simulations further verify the efficacy of our algorithm. / published_or_final_version / Computer Science / Master / Master of Philosophy

Not available / text

Not available / text

Not available / text