Live migration is widely used in cloud platforms to transfer Virtual Machines (VMs) from one physical machine to another. Live migration is useful for workload consolidation, load balancing, failure management, and energy savings. Copy-on-write (COW) page sharing allows identical pages to be shared both within a VM and across co-located VMs to reduce their collective memory footprint. Current live migration techniques are not aware of such page sharing; thus they do not preserve pre-existing page sharing when migrating VMs to a common destination machine. Consequently, each shared page is replicated at the destination multiple times as if they were separate pages. This expansion of the memory footprint of VMs during migration can lead to problems such as migration failure, increased network traffic, and longer migration times. We propose Sharing-aware Live Migration (SLM), which preserves pre-existing COW page sharing within and across VMs that are migrated to a common destination machine. The key idea is to identify guest pages that are mapped to the same physical page at the source machine and to map them to the same physical page at the destination. We present SLM technique for both pre-copy and post-copy live migration of multiple VMs and describe its implementation on the KVM/QEMU virtualization platform. Our evaluations show that SLM successfully preserves pre-existing COW page sharing during migration, eliminates the risk of migration failure due to memory expansion, and reduces total migration time and network traffic overhead.

One of the key challenges of edge computing is managing the limited resources available at the edge, especially memory and network bandwidth. Virtual machines (VMs) can ensure both isolation and efficient resource utilization within the edge computing infrastructure.Live migration is a crucial technique in edge computing infrastructure to transfer running VMs from one physical node to another. This can occur either within the same host (Intra-host) or between different hosts (Inter-host). Current live migration techniques face challenges, such as lack of awareness of duplicated pages for inter-host migration and inefficient handling of co-located memory for intra-host migration.In this paper, we describe our work on three efficient ways to incorporate sharing-awareness in live migration of multiple VMs while avoiding memory and network resource contention. For inter-host migration, our techniques rely on existing Copy-On-Write (COW) optimization performed by the host/hypervisor. This enables the transfer of a copy of the page only once and preserves existing COW sharing by remapping them at the destination. For intra-host migration, our technique implements a mechanism to identify shared pages and transfer their ownership (via a userfaultfd-based mechanism) instead of copying them. Besides reducing network traffic and memory footprint by eliminating unwanted copying, our techniques also result in a shorter total migration time, thereby freeing additional resources involved in migration as quickly as possible.

One of the key challenges of edge computing is working with a limited amount of resources available at the edge, especially memory and bandwidth. Virtual Machine (VM) Templating is a technique to start multiple VM instances quickly from a shared pre-configured read-only image (or template). The new VM instances share the memory of the template in a copy-on-write (COW) manner. In edge computing platforms, VM templating can help to reduce the collective memory footprint and deployment time of multiple VMs. Live migration of VMs can also improve task placement on edge nodes for latency reduction, service availability, and cost-effectiveness. However, existing live migration techniques fail to maintain memory sharing among multiple templated VMs that are migrated to a common destination. Consequently, identical pages at the source are replicated several times at the destination, increasing memory pressure on the destination node, network traffic during migration, and total migration time. Lack of templating awareness can also trigger migration failure if the destination lacks sufficient memory to accommodate the increased memory footprint. To address this shortcoming of live migration, we introduce Template-aware Live Migration (TLM), which preserves preexisting COW memory sharing between templated VMs that are migrated to a common destination machine. Specifically, TLM ensures that multiple virtual pages from different VMs that are mapped to the same template page at the source are mapped to the same page at the destination. We implement TLM on the QEMU/KVM virtualization platform and demonstrate a significant reduction in memory footprint, shorter migration time, and reduced network traffic.

A Confidential Virtual Machine (CVM) is a virtual machine (VM) whose memory is encrypted using trusted hardware support to prevent unauthorized access to its contents, including by the hypervisor. AMD Secure Encrypted Virtualization (SEV) provides hardware support for CVMs on AMD processors and has been used by several cloud operators to provide trusted execution environments to cloud users. In this paper, we examine the performance overheads of CVMs across three generations of AMD SEV using a number of CPU, memory, and I/O benchmarks. Our findings indicate that CPU -intensive workloads running on a CVM do not experience significant performance difference compared to a non-confidential VM. However, we observe that some workloads that are sensitive to cache/memory latency may experience a performance drop of up to 2.5%. Pure memory-intensive workloads are observed to experience up to 4.3% overhead. Disk I/O from CVMs experiences a significant performance impact when using SEV, with up to a 56% performance penalty. Network I/O, on the other hand, experiences up to a 36% overhead. Workloads with a mix of memory and I/O accesses experience an overhead of up to 14%. Our work complements and extends the existing understanding of the performance of this important and rapidly evolving technology.

Live migration is a critical technology used in cloud infrastructures to transfer running virtual machines (VMs). When live migration fails, as it often does, it is critical that any VMs in transit are not lost. There are two primary live migration techniques – pre-copy and post-copy. Pre-copy transfers a VM's memory to the destination before its virtual CPUs are transferred, whereas post-copy does the reverse. Both pre-copy and post-copy will lose the VM if the source machine fails during migration. Additionally, post-copy can lose the VM if the destination machine or network fail since the VM's memory and execution state are split across the source and destination machines. We present V-Recover, an approach to recover a VM when the source, destination, or network fails during live migration. V-Recover consists of two techniques: (1) aforward incremental checkpointing(FIC) mechanism to handle source machine failure during both pre-copy and post-copy, and (2) areverse incremental checkpointing(RIC) mechanism to handle destination or network failure during post-copy. We present the design, implementation, and evaluation of V-Recover in the KVM/QEMU virtualization platform. Our evaluations show that V-Recover effectively recovers a VM upon migration failure with acceptable overheads on migration metrics and application performance.

Bare-metal cloud platforms allow customers to rent remote physical servers and install their preferred operating systems and software to make the best of servers' raw hardware capabilities. However, this quest for bare-metal performance compromises cloud manageability. To avoid overheads, cloud operators cannot install traditional hypervisors that provide common manageability functions such as live migration and introspection. We aim to bridge this gap between performance, isolation, and manageability for bare-metal clouds. Traditional hypervisors are designed to limit and emulate hardware access by virtual machines (VM). In contrast, we propose Directvisor - a hypervisor that maximizes a VM's ability to directly access hardware for near-native performance, yet retains hardware control and manageability. Directvisor goes beyond traditional direct-assigned (pass-through) I/O devices by allowing VMs to directly control and receive hardware timer interrupts and inter-processor interrupts (IPIs) besides eliminating most VM exits. At the same time, Directvisor supports seamless (low-downtime) live migration and introspection for such VMs having direct hardware access.

Cloud platforms are increasingly using containers for lightweight virtualization. Unlike full system virtual machines (VMs) that each runs its own operating system, containers share a stateful operating system to reduce their memory footprint and execution overheads. However, mainstream operating systems are currently limited in their ability to customize a container's memory management, since they lack the necessary abstractions and mechanisms to accurately track and isolate a container's memory footprint. We propose a new abstraction, called the Container-Level Address Space (CLAS), that provides a unified view of a container's memory across all of its constituent processes. We present the design of ContainerVisor, a per-container resource management system that leverages CLAS to provide customized memory management services. We describe a ContainerVisor prototype on Linux for running unmodified applications and demonstrate three proof-of-concept customized services, namely process-level memory limits and reservations, container-specific page replacement policies, and privacy-aware memory de-allocation. Our evaluations show that ContainerVisor can provide these customized services within reasonable overheads.

Post-copy is one of the two key techniques (besides pre-copy) for live migration of virtual machines in data centers. Post-copy provides deterministic total migration time and low downtime for write-intensive VMs. However, if post-copy migration fails for any reason, the migrating VM is lost because the VM's latest consistent state is split between the source and destination nodes during migration. In this paper, we present PostCopyFT, a new approach to recover a VM after a destination or network failure during post-copy live migration using an efficient reverse incremental checkpointing mechanism. We have implemented and evaluated our approach in the KVM/QEMU platform. Our experimental results show that the total migration time of post-copy remains unchanged while maintaining low failover time, downtime, and application performance overhead.

Hypervisors are increasingly complex and must be often updated for applying security patches, bug fixes, and feature upgrades. However, in a virtualized cloud infrastructure, updates to an operational hypervisor can be highly disruptive. Before being updated, virtual machines (VMs) running on a hypervisor must be either migrated away or shut down, resulting in downtime, performance loss, and network overhead. We present a new technique, called HyperFresh, to transparently replace a hypervisor with a new updated instance without disrupting any running VMs. A thin shim layer, called the hyperplexor, performs live hypervisor replacement by remapping guest memory to a new updated hypervisor on the same machine. The hyperplexor leverages nested virtualization for hypervisor replacement while minimizing nesting overheads during normal execution. We present a prototype implementation of the hyperplexor on the KVM/QEMU platform that can perform live hypervisor replacement within 10ms. We also demonstrate how a hyperplexor-based approach can used for sub-second relocation of containers for live OS replacement.

Virtual Machines (VM) frequently run parallel applications in cloud environments, and high performance computing platforms. It is well known that configuring a VM with too many virtual processors (vCPUs) worsens application performance due to scheduling cross-talk between the hypervisor and the guest OS. Specifically, when the number of vCPUs assigned to a VM exceeds available physical CPUs then parallel applications in the VM experience worse performance, even when number of application threads remains fixed. In this paper, we first track the root cause of this performance loss to inefficient hypervisor-level emulation of inter-vCPU synchronization events. We then present three techniques to minimize hypervisor-induced overheads on parallel workloads in large-VCPU VMs. The first technique pins application threads to dedicated vCPUs to eliminate inter-vCPU thread migrations, reducing the overhead of emulating inter-processor interrupts (IPIs). The second technique para-virtualizes inter-vCPU TLB flush operations. The third technique enables faster reactivation of idle vCPUs by prioritizing the delivery of rescheduling IPIs. Unlike existing solutions which rely on heavyweight and slow vCPU hotplug mechanisms, our techniques are lightweight and provide more flexibility in migrating large-vCPU VMs. Using several parallel benchmarks, we demonstrate the effectiveness of our prototype implementation in the Linux KVM/QEMU virtualization platform. Specifically, we demonstrate that with our techniques, parallel applications can maintain their performance even when up to 255 VCPUs are assigned to a VM running on as few as 6 physical cores.

We introduce a new metric for live migration of virtual machines (VM) called eviction time defined as the time to evict the state of one or more VMs from the source host. Eviction time determines how quickly the source can be taken offline or its resources repurposed for other VMs. In traditional live migration, such as pre-copy and post-copy, eviction time equals the total migration time because the source is tied up until the destination receives the entire VM. We present Scatter-Gather live migration which decouples the source and destination during migration to reduce eviction time when the destination is slow. The source scatters the memory of VMs to multiple nodes, including the destination and one or more intermediaries. Concurrently, the destination gathers the VMs' memory from the intermediaries and the source. Thus eviction from the source is no longer bottlenecked by the reception speed of the destination. We support simultaneous live eviction of multiple VMs and exploit deduplication to reduce network overhead. Our Scatter-Gather implementation in the KVM/QEMU platform reduces the eviction time by up to a factor of 6 against traditional pre-copy and post-copy while maintaining comparable total migration time when the destination is slower than the source.

Live migration of Virtual Machines (VMs) is a key technique to quickly migrate workloads in response to events such as impending failure or load changes. Despite extensive research, state-of-the-art live migration approaches take a long time to migrate a VM, which in turn negatively impacts the application performance during migration. We present, Quick Eviction, a new approach to significantly speed up the eviction of a VM from the source host with low impact on VM's performance during migration. Before migration, Quick Eviction regularly snapshots the VM's memory to a destination or a failover node. During the actual migration, Quick Eviction has to transfer only a small amount of dirtied memory resulting in a very short time to completely evict the VM out of the source. Our experimental results show that Quick Eviction in the KVM/QEMU platform significantly reduces the eviction time.

A key attraction of virtual machines (VMs) is live migration - the ability to move their execution state across physical machines even as the VMs continue to run. Unfortunately, the traditional pre-copy and post-copy techniques are not agile in the face of resource pressures at the source host, since it takes a long time to transfer the memory state of a VM. Consequently, the performance suffers for all VMs - those being migrated as well as those being left behind. Prior works have attempted to optimize indirect measures of migration effectiveness such as downtime, total migration time, and network overhead. However, none have treated the performance of VMs impacted by migration as the primary metric of migration effectiveness. We propose an Agile live migration technique that quickly recovers the performance of all VMs under resource pressure by eliminating resource pressure faster than traditional live migration. The working set of a VM is typically much smaller than its full memory footprint. Our approach works by transparently tracking the working set of each VM and offloading the non-working set (cold pages) in advance to portable per-VM swap devices. We present a new hybrid pre/post-copy technique that reduces the performance impact on the VM's workload by transferring only the working set of the VM while enabling destination to remotely access cold pages from the per-VM swap device. We describe the challenges in the design and implementation of Agile live migration in the KVM/QEMU platform without modifying the guest OS in the VM. When live migrating under memory pressure, we demonstrate a reduction in the performance impact on VMs by a up to factor of 2, reduction in migration time by up to factor of 4 besides reduction in memory pressure on both the source and destination hosts.

When considering a hypervisor, cloud providers must balance conflicting requirements for simple, secure code bases with more complex, feature-filled offerings. This paper introduces Dichotomy, a new two-layer cloud architecture in which the roles of the hypervisor are split. The cloud provider runs a lean hyperplexor that has the sole task of multiplexing hardware and running more substantial hypervisors (called featurevisors) that implement features. Cloud users choose featurevisors from a selection of lightly-modified hypervisors potentially offered by third-parties in an "as-a-service" model for each VM. Rather than running the featurevisor directly on the hyperplexor using nested virtualization, Dichotomy uses a new virtualization technique called eemeral virtualization which efficiently (and repeatedly) transfers control of a VM between the hyperplexor and featurevisor using memory mapping techniques. Nesting overhead is only incurred when the VM is accessed by the featurevisor. We have implemented Dichotomy in KVM/QEMU and demonstrate average switching times of 80 ms, two to three orders of magnitude faster than live VM migration. We show that, for the featurevisor applications we evaluated, VMs hosted in Dichotomy deliver up to 12% better performance than those hosted on nested hypervisors, and continue to show benefit even when the featurevisor applications run as often as every 2.5~seconds.

Virtual machine (VM) migration is a technique for transferring the execution state of a VM from one physical host to another. While VM migration is critical for load balancing, consolidation, and server maintenance in virtualized data centers, it can also increase security risks. During VM migration, an attacker with sufficient privileges can compromise a VM by modifying its memory contents during transit to subvert its applications or the guest operating system. One could maintain dedicated, and presumably more secure, control networks to carry the migration traffic, but at significant hardware and administrative complexity. Alternatively, one could encrypt the migration traffic, which eliminates the need for dedicated control networks, but might introduce performance overheads. To date, there has been no systematic study of how encryption affects VM migration, especially in high-bandwidth low-delay networks that are common within data centers. In this paper, we present a study of the impact of AES and 3DES encryption algorithms on two widely used live VM migration approaches - pre-copy and post-copy. Our key findings are as follows. The encryption algorithm used can have a significant impact on the total migration time. The impact of encryption on downtime varies with the type of the migration technique. The overhead of encryption also depends upon the relative speeds of source and target machines. Finally, an application's performance within a VM during encrypted migration varies with the type of the application and the migration mechanism.

Cloud computing systems routinely process users' confidential data, but the underlying virtualization software in use today is not constructed to minimize the exposure of such data. For instance, virtual machine (VM) checkpointing can drastically prolong the lifetime and vulnerability of confidential data without users' knowledge by storing such data as part of a persistent snapshot. A key requirement for minimizing the exposure of any data is the ability to cleanly isolate such data for either exclusion or processing. Traditional mechanisms for memory taint tracking are expensive whereas those for isolating application footprint in VM-based sandboxes are not transparent. In this paper, we propose a transparent and lightweight mechanism for isolating a confidential application's memory footprint in a VM. The key idea is for a parent VM to spawn a child VM, called a Privacy-preserving Virtual Machine (PPVM) within which the confidential application executes. Hypervisor features, such as VM checkpointing, that need to exclude the memory of a confidential application can safely ignore the child VM's memory footprint. Alternatively, features such as checkpoint encryption or malware tracking can operate only on the child VM's memory. We implement memory isolation for PPVM through a lightweight VM fork operation that uses copy-on-write to reduce the memory and filesystem overhead of the PPVM. Transparency is achieved through a confidential shell that allows the parent VM to spawn the confidential application in the PPVM and exercise control over it during runtime. We demonstrate the effectiveness of PPVM through its use with VM checkpointing, which can safely checkpoint the parent VM while excluding or encrypting the associated PPVM. We show that our PPVM implementation achieves effective memory isolation with low overheads on memory, CPU, and network performance.

Traditional metrics for live migration of virtual machines (VM) include total migration time, downtime, network overhead, and application degradation. In this paper, we introduce a new metric, "eviction time", defined as the time to evict the entire state of a VM from the source host. Eviction time determines how quickly the source host can be taken offline, or the freed resources re-purposed for other VMs. In traditional approaches for live VM migration, such as pre-copy and post-copy, eviction time is equal to the total migration time, because the source and destination hosts are coupled for the duration of the migration. Eviction time increases if the destination host is slow to receive the incoming VM, such as due to insufficient memory or network bandwidth, thus tying up the source host. We present a new approach, called "Scatter-Gather" live migration, which reduces the eviction time when the destination host is resource constrained. The key idea is to decouple the source and the destination hosts. The source scatters the VM's memory state quickly to multiple intermediaries (hosts or middleboxes) in the cluster. Concurrently, the destination gathers the VM's memory from the intermediaries using a variant of post-copy VM migration. We have implemented a prototype of Scatter-Gather in the KVM/QEMU platform. In our evaluations, Scatter-Gather reduces the VM eviction time by up to a factor of 6 while maintaining comparable total migration time against traditional pre-copy and post-copy for a resource constrained destination.

Virtualization has been widely adopted in recent years in the cloud computing platform to improve server consolidation and reduce operating cost. Virtual Machine (VM) checkpointing refers to the act of saving a persistent snapshot (or checkpoint) of a VM's state at any instant. VM checkpointing can drastically prolong the lifetime and vulnerability of confidential or private user data in applications that execute within VMs. Simply encrypting the checkpoint does not reduce the lifetime of confidential data that should be quickly discarded after its use. In this paper, we present an application-level approach, called Privacy-preserving Checkpointing (PPC), which excludes confidential data from VM checkpoints, instead of encrypting such data. PPC enables an application programmer to register memory locations that represent the origins of confidential data. During the VM's execution, PPC performs information flow analysis to automatically track the propagation of confidential data through the application and various components of the VM, including the guest operating system. During VM checkpointing, the locations identified during the information flow analysis are excluded from the persistent checkpoint. We present the design and implementation of the PPC system in VirtualBox VMs running the commodity Linux operating system. We demonstrate the use of our system using the vim and gedit text editors. We also show that PPC introduces acceptable performance overhead.

Gang migration refers to the simultaneous live migration of multiple Virtual Machines (VMs) from one set of physical machines to another in response to events such as load spikes and imminent failures. Gang migration generates a large volume of network traffic and can overload the core network links and switches in a data center. In this paper, we present an approach to reduce the network overhead of gang migration using global deduplication (GMGD). GMGD identifies and eliminates the retransmission of duplicate memory pages among VMs running on multiple physical machines in the cluster. We describe the design, implementation and evaluation of a GMGD prototype using QEMU/KVM VMs. Evaluations on a 30-node Gigabit Ethernet cluster having 10GigE core links shows that GMGD can reduce the network traffic on core links by up to 65% and the total migration time of VMs by up to 42% when compared to the default migration technique in QEMU/KVM. Furthermore, GMGD has a smaller adverse performance impact on network-bound applications.

Network protocol developers typically go through a tedious and error-prone process of testing and debugging their protocol implementation for various settings. They perform a number of tasks manually such as configuration of numerous network settings, controlled reproduction of unexpected protocol behavior, and traffic capture and analysis. We present a Protocol Testing and Evaluation System (PTES) to assist developers in transparently testing their protocol implementations. PTES enables a protocol developer to construct and execute various controlled and repeatable testing scenarios. The developer can use simple iptables- like rules to specify various local and distributed network events and actions. During protocol execution, PTES triggers these events and actions in a coordinated manner and records the protocol responses to these events which can later be examined by the developer. We present the design and implementation of three variants of PTES for native, simulated, and emulated platforms for both wired and wireless networks. We demonstrate the utility of PTES by automating the testing of TCP/IP and Optimized Link State Routing (OLSR) protocols.

This paper addresses the problem of simultaneously migrating a group of co-located and live virtual machines (VMs), i.e, VMs executing on the same physical machine. We refer to such a mass simultaneous migration of active VMs as live gang migration. Cluster administrators may often need to perform live gang migration for load balancing, system maintenance, or power savings. Application performance requirements may dictate that the total migration time, network traffic overhead, and service downtime, be kept minimal when migrating multiple VMs. State-of-the-art live migration techniques optimize the migration of a single VM. In this paper, we optimize the simultaneous live migration of multiple co-located VMs. We present the design, implementation, and evaluation of a de-duplication based approach to perform concurrent live migration of co-located VMs. Our approach transmits memory content that is identical across VMs only once during migration to significantly reduce both the total migration time and network traffic. Using the QEMU/KVM platform, we detail a proof-of-concept prototype implementation of two types of de-duplication strategies (at page level and sub-page level) and a differential compression approach to exploit content similarity across VMs. Evaluations over Gigabit Ethernet with various types of VM workloads demonstrate that our prototype for live gang migration can achieve significant reductions in both network traffic and total migration time. Categories andSubjectDescriptors

Large cluster-based cloud computing platforms increasingly use commodity Ethernet technologies, such as Gigabit Ethernet, 10GigE, and Fibre Channel over Ethernet (FCoE), for intra-cluster communication. Traffic congestion can become a performance concern in the Ethernet due to consolidation of data, storage, and control traffic over a common layer-2 fabric, as well as consolidation of multiple virtual machines (VMs) over less physical hardware. Even as networking vendors race to develop switch-level hardware support for congestion management, we make the case that virtualization has opened up a complementary set of opportunities to reduce or even eliminate network congestion in cloud computing clusters. We present the design, implementation, and evaluation of a system called XCo, that performs explicit coordination of network transmissions over a shared Ethernet fabric to proactively prevent network congestion. XCo is a software-only distributed solution executing only in the end-nodes. A central controller uses explicit permissions to temporally separate (at millisecond granularity) the transmissions from competing senders through congested links. XCo is fully transparent to applications, presently deployable, and independent of any switch-level hardware support. We present a detailed evaluation of our XCo prototype across a number of network congestion scenarios, and demonstrate that XCo significantly improves network performance during periods of congestion.

We present MemX -- a distributed system that virtualizes cluster-wide memory to support data-intensive and large memory workloads in virtual machines (VMs). MemX provides a number of benefits in virtualized settings: (1) VM workloads that access large datasets can perform low-latency I/O over virtualized cluster-wide memory; (2) VMs can transparently execute very large memory applications that require more memory than physical DRAM present in the host machine; (3) MemX reduces the effective memory usage of the cluster by de-duplicating pages that have identical content; (4) existing applications do not require any modifications to benefit from MemX such as the use of special APIs, libraries, recompilation, or relinking; and (5) MemX supports live migration of large-footprint VMs by eliminating the need to migrate part of their memory footprint resident on other nodes. Detailed evaluations of our MemX prototype show that large dataset applications and multiple concurrent VMs achieve significant performance improvements using MemX compared against virtualized local and iSCSI disks.

The proliferation of wireless-enabled portable computing devices has spurred a growing need for efficient and powerful networking protocols. The key challenge in the development of robust wireless networking protocols is an ability to conduct effective and efficient evaluation of the protocol in order to ensure its successful working in real-world settings. We proposed MiNT-2, a fresh re-design of the original MiNT framework developed at Stony Brook University. One of the fundamental requirements of MiNT-2 is to provide location awareness of all the nodes within the network. In this paper, we demonstrate the use of radio-frequency identification (RFID) technology in order to carry out localization of the mobile nodes within the system. We also demonstrate the application of the localization system of constructing different scenarios for wireless protocols evaluation.

We present the design, implementation, and evaluation of post-copy based live migration for virtual machines (VMs) across a Gigabit LAN. Live migration is an indispensable feature in today's virtualization technologies. Post-copy migration defers the transfer of a VM's memory contents until after its processor state has been sent to the target host. This deferral is in contrast to the traditional pre-copy approach, which first copies the memory state over multiple iterations followed by a final transfer of the processor state. The post-copy strategy can provide a "win-win" by reducing total migration time closer to its equivalent time achieved by non-live VM migration. This is done while maintaining the liveness benefits of the pre-copy approach. We compare post-copy extensively against the traditional pre-copy approach on top of the Xen Hypervisor. Using a range of VM workloads we show improvements in several migration metrics including pages transferred, total migration time and network overhead. We facilitate the use of post-copy with adaptive pre-paging in order to eliminate all duplicate page transmissions. Our implementation is able to reduce the number of network-bound page faults to within 21% of the VM's working set for large workloads. Finally, we eliminate the transfer of free memory pages in both migration schemes through a dynamic self-ballooning (DSB) mechanism. DSB periodically releases free pages in a guest VM back to the hypervisor and significantly speeds up migration with negligible performance degradation.

Advances in virtualization technology have focused mainly on strengthening the isolation barrier between virtual machines (VMs) that are co-resident within a single physical machine. At the same time, a large category of communication intensive distributed applications and software components exist, such as web services, high performance grid applications, transaction processing, and graphics rendering, that often wish to communicate across this isolation barrier with other endpoints on co-resident VMs. State of the art inter-VM communication mechanisms do not adequately address the requirements of such applications. TCP/UDP based network communication tends to perform poorly when used between co-resident VMs, but has the advantage of being transparent to user applications. Other solutions exploit inter-domain shared memory mechanisms to improve communication latency and bandwidth, but require applications or user libraries to be rewritten against customized APIs - something not practical for a large majority of distributed applications. In this paper, we present the design and implementation of a fully transparent and high performance inter-VM network loopback channel, called XenLoop, in the Xen virtual machine environment. XenLoop does not sacrifice user-level transparency and yet achieves high communication performance between co-resident guest VMs. XenLoop intercepts outgoing network packets beneath the network layer and shepherds the packets destined to co-resident VMs through a high-speed inter-VM shared memory channel that bypasses the virtualized network interface. Guest VMs using XenLoop can migrate transparently across machines without disrupting ongoing network communications, and seamlessly switch between the standard network path and the XenLoop channel. In our evaluation using a number of unmodified benchmarks, we observe that XenLoop can reduce the inter-VM round trip latency by up to a factor of 5 and increase bandwidth by a up to a factor of 6.

Most existing wireless ad hoc routing protocols rely upon the use of backward learning technique with explicit control messages to route packets. In this paper we propose a set of techniques that can be applied in a backward learning routing algorithm in order to minimize or even eliminate explicit control messages for route discovery, setup, and maintenance, while minimally using implicit data-like control messages that need no special processing. We also show that such an algorithm does not need to prevent routing loops at all costs, such as by means of extensive network-wide spanning trees in traditional LAN bridges, or destination sequence numbers in AODV, or source- routing in DSR. In fact, we prove that transient loops can be safely allowed to occur when a simple route refresh mechanism is coupled with the use of packet identification field to effectively bound the lifetime of such transient loops without negatively impacting the network performance. Results demonstrate that even a routing algorithm without explicit control messages can perform competitively in comparison to AODV and DSR protocols while significantly reducing the protocol complexity.

By analyzing a two-month trace of more than 25 million emails received at a large US university campus network, of which more than 18 million are spam messages, we characterize the spammer behavior at both the mail server and the network levels. We also correlate the arrivals of spam with the BGP route updates to study the network reachability properties of spammers. Among others, our significant findings are: (a) the majority of spammers (93% of spam only mail servers and 58% of spam only networks) send only a small number of spam messages (no more than 10); (b) the vast majority of both spam messages (91.7%) and spam only mail servers (91%) are from mixed networks that send both spam and non-spam messages; (c) the majority of both spam messages (68%) and spam mail servers (74%) are from a few regions of the IP address space (top 20 "/8" address spaces); (d) a large portion of spammers (81% of spam only mail servers and 27% of spam only networks) send spam only within a short period of time (no longer than one day out of the two months); and (e) network prefixes for a non-negligible portion of spam only networks (6%) are only visible for a short period of time (within 7 days), coinciding with the spam arrivals from these networks. We discuss the implications of the findings for the current anti-spam efforts, and more importantly, for the design of future email delivery architectures.

While wireless vehicular ad hoc networks (VANETs) are attracting greater commercial interest, current research has not adequately captured the real-world urban constraints in VANET deployment. In this work, we evaluated the feasibility and benefits of deploying a VANET in urban settings with a wireless mesh backbone infrastructure. We modeled urban street layouts, traffic rules, RF attenuation due to physical obstacles, and the use of multiple radio channels Our results indicate that the performance improves in dense networks when routing decisions are limited to mesh nodes, whereas it improves in sparse networks when mobile nodes also participate in routing. We also show that the effect of signal attenuation due to physical obstacles can potentially be parametrized in simulations using empirical real-world measurements.

As both end-to-end network reliability and performance becomes a growing concern for large distributed organizations, carriers face an increasing pressure to offer enhanced network services with higher quality of service (QoS). Such premier services are exemplified by wide-area virtual private networks (VPN) with QoS guarantees, or QVPNs, for which users can specify bandwidth, latency, and reliability requirements. From a carrier's standpoint, the primary challenge is to set up fault-tolerant routes for each QVPN request across its network with user-specified reliability and performance guarantees and, at the same time, maximize the total number of QVPNs that its network can support at any instant. We propose a fault tolerant load balancing routing (FTLBR) algorithm to select fault-tolerant routes for QVPNs. FTLBR maintains network-wide load balance while selecting primary and backup routes for QVPNs and performs resource sharing along backup routes to achieve an overall high network resource utilization efficiency. FTLBR is able to avoid formation of bottleneck links during primary-backup route selection by employing a simple quantitative metric that effectively captures network-wide load balance. Simulation results show that FTLBR can support significantly higher number of QVPNs when compared with existing traffic engineering algorithms.

The growing interest in wireless Vehicular Ad Hoc Networks (VANETs) has prompted greater research into simulation models that better reflect urban VANET deployments. Still, we lack a systematic understanding of the required level of simulation details in modeling various real-world urban constraints. In this work, we developed a series of simulation models that account for street layout, traffic rules, multilane roads, acceleration-deceleration, and RF attenuation due to obstacles. Using real and controlled synthetic maps, we evaluated the sensitivity of the simulation results toward these details. Our results indicate that the delivery ratio and packet delays in VANETs are more sensitive to the clustering effect of vehicles at intersections and their acceleration/deceleration. The VANET performance appears to be only marginally affected by the simulation of multiple lanes and careful synchronization at traffic signals. We also found that the performance in dense VANETs improves significantly when routing decisions are limited to a wireless backbone of mesh nodes, whereas in sparse VANETs, performance improves when vehicles also participate in ad hoc routing. Finally, through measurement and analysis of signal strengths around urban city blocks, we show that the effect of signal attenuation due to physical obstacles can potentially be parameterized in simulations. Our work provides a starting point for further understanding and development of more accurate VANET simulation model.

Device drivers are integral components of operating systems. The computational workloads imposed by device drivers tend to be aperiodic and unpredictable because they are triggered in response to events that occur in the device, and may arbitrarily block or preempt other time-critical tasks. This characteristic poses significant challenges in real-time systems, where schedulability analysis is essential to guarantee system-wide timing constraints. At the same time, device driver workloads cannot be ignored. Demand-based schedulability analysis is a technique that has been successful in validating the timing constraints in both single and multiprocessor systems. In this paper we present two approaches to demand-based schedulability analysis of systems that include device drivers. First, we derive load-bound functions using empirical measurement techniques. Second, we modify the scheduling of network device driver tasks in Linux to implement an algorithm for which a load-bound function can be derived analytically. We demonstrate the practicality of our approach through detailed experiments with a network device under Linux. Our results show that, even though the network device driver does not conform to conventional periodic or sporadic task models, it can be successfully modeled using hyperbolic load-bound functions that are fitted to empirical performance measurements

As wide-area network connectivity becomes commoditized, network service providers are offering premium services that generate higher revenues by supporting performance sensitive traffic (such as voice, multimedia, and online trading). An emerging example is a virtual private network path with quality of service (QoS) guarantees, or QVPN. The main technical challenge in offering the QVPN service is how to allocate a physical route for each QVPN so as to maximize the total number of QVPNs that a given physical network infrastructure can support simultaneously. We make the case that the key to addressing this challenge is to maintain network-wide load balance when selecting QVPN routes. By ensuring that different parts of the network are evenly loaded, no single critical link will tend to become a bottleneck resource. This paper describes a Link Criticality Based Routing (LCBR) algorithm, which achieves high network resource utilization efficiency while supporting QVPNs with end-to-end delay and bandwidth guarantees. In addition, LCBR can select primary and backup routes for each QVPN simultaneously to support fast recovery from node or link failures. Using a simple yet effective metric that accurately quantifies network-wide load balance, LCBR significantly improves the total number of supported QVPNs when compared to state-of-the-art traffic engineering approaches.

Growth of performance sensitive applications, such as voice and multimedia, has led to widespread adoption of resource virtualization by a variety of service providers (xSPs). For instance, Internet Service Providers (ISPs) increasingly differentiate their offerings by means of customized services, such as virtual private networks (VPN) with Quality of Service (QoS) guarantees or QVPNs. Similarly Storage Service Providers (SSPs) use storage area networks (SAN)/network attached storage (NAS) technology to provision virtual disks with QoS guarantees or QVDs. The key challenge faced by these xSPs is to maximize the number of virtual resource units they can support by exploiting the statistical multiplexing nature of the customers' input request load.While a number of measurement-based admission control algorithms utilize statistical multiplexing along the bandwidth dimension, they do not satisfactorily exploit statistical multiplexing along the delay dimension to guarantee distinct per-virtual-unit delay bounds. This article presents Delay Distribution Measurement (DDM) based admission control algorithm, the first measurement-based approach that effectively exploits statistical multiplexing along the delay dimension. In other words, DDM exploits the well-known fact that the actual delay experienced by most service requests (packets or disk I/O requests) for a virtual unit is usually far smaller than its worst-case delay bound requirement because multiple virtual units rarely send request bursts at the same time. Additionally, DDM supports virtual units with distinct probabilistic delay guarantees---virtual units that can tolerate more delay violations can reserve fewer resources than those that tolerate less, even though they require the same delay bound. Comprehensive trace-driven performance evaluation of QVPNs (using Voice over IP traces) and QVDs (using video stream, TPC-C, and Web search I/O traces) shows that, when compared to deterministic admission control, DDM can potentially increase the number of admitted virtual units (and resource utilization) by up to a factor of 3.

There is a constant battle to break-even between continuing improvements in DRAM capacities and the demands for even more memory by modern memory-intensive high-performance applications. Such applications do not take long to hit the physical memory limit and start paging to disk, which in turn considerably slows down their performance. We tackle this problem in the Adaptive Network Memory Engine (Anemone) project by pooling together the distributed memory resources of multiple machines across a gigabit network based cluster. Anemone is a distributed memory virtualization system that can dramatically improve application performance by paging over the gigabit network to the unused memory of remote clients. Anemone provides clients with completely transparent access to a potentially unlimited amount of collective memory pool. Earlier research efforts in this area advocate significant modifications to client systems, either in terms of a specific programming interface for applications, or in terms of extensive changes to the operating systems and device drivers. In contrast, Anemone requires no modifications to either the client system or the memory-intensive application.

Provisioning techniques for network flows with end-to-end QoS guarantees need to address the interpath and intrapath load balancing problems to maximize the resource utilization efficiency. This paper focuses on the intrapath load balancing problem: How to partition the end-to-end QoS requirement of a network flow along the links of a given path such that the deviation in the loads on these links is as small as possible? We propose a new algorithm to solve the end-to-end QoS partitioning problem for unicast and multicast flows that takes into account the loads on the constituent links of the chosen flow path. This algorithm can simultaneously partition multiple end-to-end QoS requirements such as the end-to-end delay and delay violation probability bound. The key concept in our proposal is the notion of slack, which quantifies the extent of flexibility available in partitioning the end-to-end delay requirement across the links of a selected path (or a multicast tree). We show that one can improve network resource usage efficiency by carefully selecting a slack partition that explicitly balances the loads on the underlying links. A detailed simulation study demonstrates that, compared with previous approaches, the proposed delay budget partitioning algorithm can increase the total number of long-term flows that can be provisioned along a network path by up to 1.2 times for deterministic and 2.8 times for statistical delay guarantees

Simplicity, cost effectiveness, scalability, and the economies of scale make Ethernet a popular choice for local area networks, as well as for storage area networks and increasingly metropolitan-area networks. These applications of Ethernet elevate it from a LAN technology to a ubiquitous networking technology, thus prompting a rethinking of some of its architectural features. One weakness of existing Ethernet architecture is its use of single spanning tree, which, while useful at avoiding routing loops, leads to low link utilization and long failure recovery time. To apply Ethernet to cluster networks and MANs, these problems need to be addressed. We propose a multi-spanning-tree Ethernet architecture, called Viking, that improves both aggregate throughput and fault tolerance by exploiting standard virtual LAN technology in a novel way. By supporting multiple spanning trees through VLAN, Viking makes the most of the inherent redundancies in most mesh-like networks and delivers a multi-fold throughput gain over single-spanning-tree Ethernet with the same physical network topology. It also provides much faster failure recovery, reducing the down-time to a sub-second range from that of multiple seconds in single-spanning-tree Ethernet architecture. Finally, based only on standard mechanisms, Viking is readily implementable on commodity Ethernet switches without any firmware modifications.

Carriers increasingly differentiate their wide-area connectivity offerings by means of customized services, such as virtual private networks (VPN) with Quality of Service (QoS) guarantees, or QVPNs. The key challenge faced by carriers is to maximize the number of QVPNs admitted by exploiting the statistical multiplexing nature of input traffic. While existing measurement-based admission control algorithms utilize statistical multiplexing along the bandwidth dimension, they do not satisfactorily exploit statistical multiplexing along the delay dimension to guarantee distinct per-QVPN delay bounds. This paper presents Delay Distribution Measurement (DDM) based admission control algorithm, the first measurement-based approach that effectively exploits statistical multiplexing along the delay dimension. In other words, DDM exploits the well known fact that the actual delay experienced by most packets of a QVPN is usually far smaller than its worst-case delay bound requirement since multiple QVPNs rarely send traffic bursts at the same time. Additionally, DDM supports QVPNs with distinct probabilistic delay guarantees -- QVPNs that can tolerate more delay violations can reserve fewer resource than those that tolerate less, even though they require the same delay bound. A comprehensive performance evaluation using Voice over IP traces shows that, when compared to deterministic admission control, DDM can potentially increase the number of admitted QVPNs (and link utilization) by up to a factor of 3.0 even when the delay violation probability is as small as 10-5.

As web-based transactions become an essential element of everyday corporate and commerce activities, it becomes increasingly important that the performance of web-based services be predictable and guaranteed even in the presence of wildly fluctuating input loads. In this paper, we propose a general implementation framework to provide quality of service (QoS) guarantee for cluster-based Internet services, such as E-commerce or directory service. We describe the design, implementation, and evaluation of a web request distribution system called Gage, which can provide every subscriber with distinct guarantee on the number of generic web requests that are serviced per second regardless of the total input loads at run time. Gage is one of the first systems that can support QoS guarantee involving multiple system resources, i.e., CPU, disk, and network. The frontend request distribution server of Gage distributes incoming requests among a cluster of back-end web server nodes so as to maintain per-subscriber QoS guarantee and load balance among the back-end servers. Each back-end web server node includes a Gage module, which performs distributed TCP splicing and detailed resource usage accounting. Performance evaluation of the fully operational Gage prototype demonstrates that the proposed architecture can indeed provide the guaranteed request throughput for different classes of web accesses, even in the presence of excessive input loads. The additional performance overhead associated with QoS support in Gage is merely 3.06%.

A growing variety of edge network access devices appear on the marketplace that perform various functions which are meant to complement generic routers' capabilities, such as firewalling, intrusion detection, virus scanning, network address translation, traffic shaping and route optimization. Because these edge network access devices are deployed on the critical path between a user site and its Internet service provider, high availability is crucial to their design. This paper describes the design, construction and evaluation of a general implementation framework for supporting fault tolerance on edge network devices. This implementation framework, called Duplex, is designed to be independent of the functionality of the hosting edge network access device, such that only a minimal amount of programming is required to tailor this framework to a specific edge network access device implementation. Duplex can tolerate power failure, hardware failure, and software failure by supporting device mirroring and watchdog timer-based link bypassing. Empirical performance measurements of an instance of Duplex that is embedded in a commercial bandwidth management device show that the run-time overhead of its fault tolerance mechanisms is less than 1 msec 90% of the time, and the failure detection and recovery period is less than 1.3 sec when running at 100 Mbps.

As web-based transactions become an essential element of everyday corporate and commerce activities, it becomes increasingly important that the performance of web-based services be predictable and guaranteed even in the presence of wildly fluctuating input loads. In this paper, we propose a general implementation framework to provide quality of service (QoS) guarantee for cluster-based Internet services, such as E-commerce or directory service. We describe the design, implementation, and evaluation of a web request distribution system called Gage, which can provide every subscriber with distinct guarantee on the number of generic web requests that are serviced per second regardless of the total input loads at run time. Gage is one of the first systems that can support QoS guarantee involving multiple system resources, i.e., CPU, disk, and network. The frontend request distribution server of Gage distributes incoming requests among a cluster of back-end web server nodes so as to maintain per-subscriber QoS guarantee and load balance among the back-end servers. Each back-end web server node includes a Gage module, which performs distributed TCP splicing and detailed resource usage accounting. Performance evaluation of the fully operational Gage prototype demonstrates that the proposed architecture can indeed provide the guaranteed request throughput for different classes of web accesses, even in the presence of excessive input loads. The additional performance overhead associated with QoS support in Gage is merely 3.06%.

Content replication and distribution is an effective technology to reduce the response time for Web accesses and has been proven quite popular among large Internet content providers. However, existing content distribution systems assume a store-and-forward delivery model and is mostly based on static content. This paper describes the design, implementation, and initial evaluation of a network resource management system for real-time Internet content distribution called Sago, which provides facilities to provision and allocate network resources so that multiple bandwidth-guaranteed and fault-tolerant multicast connections can be multiplexed on a single physical network. Sago includes a novel network resource mapping algorithm that takes into account both physical network topology and dynamic traffic demands, a network-wide fault tolerance mechanism that supports both node-level and link-level fault tolerance, and a hierarchical network link scheduler that provides performance protection among multicast connections sharing the same physical network link. Moreover, Sago does not require any IP multicasting support from underlying network routers because it performs application-level multicasting. The technologies underlying Sago are important building blocks for real-time content distribution networks, end-to-end quality of service guarantee over global corporate intranets, and application-specific adaptation of wide-area network services.

As Web-based transactions become an essential element of everyday corporate and commerce activity, it becomes increasingly important for the performance of Web application services to be predictable and adequate even in the presence of wildly fluctuating input loads. In this work we propose a general implementation framework to provide quality of service (QoS) guarantee for cluster-based Web application services, such as e-commerce or directory services, that is largely independent of the Web application and the hardware/software platform used in the cluster. This paper describes the design, implementation, and evaluation of a Web request distribution system called Gage, which is able to guarantee a service subscriber a pre-defined number of generic Web requests serviced per second regardless of the total input loads at run time. Gage is one of the first, if not the first system that can support QoS guarantees which involves multiple system resources, i.e., CPU, disk, and network. The fully operational Gage prototype shows that the proposed architecture can indeed provide a guaranteed level of service for specific classes of Web accesses according to their QoS requirements in the presence of excessive input loads. In addition, empirical measurement on the Gage prototype demonstrates that the additional performance overhead associated with Gage's QoS guarantee support for Web service is merely 3.06%.

Earlier research has shown that the route lookup performance of a network processor can be significantly improved by caching ranges of lookup/classification keys rather than individual keys. While the previous work focused specifically on reducing capacity misses, we address two other important aspects - (a) reducing conflict misses and (b) cache consistency during frequent route updates. We propose two techniques to minimize conflict misses that aim to balance the number of cacheable entries mapped to each cache set. They offer different tradeoffs between performance and simplicity while improving the average route lookup time by 76% and 45.2% respectively. To maintain cache consistency during frequent route updates, we propose a selective cache invalidation technique that can limit the degradation in lookup latency to within 10.2%. Our results indicate potentially large improvement in lookup performance for network processors used at Internet edge and motivate further research into caching at the Internet core.

Placement of computation inside the network is a powerful computation model that can improve the overall performance of network applications. The authors address the problem of providing sound and efficient system support for placing computation in a network router We identify a set of requirements, related to protection, resource control, scheduling and efficiency, that are relevant to the design of this system support. We have developed a system that attempts to meet these requirements, and have used it to write a router application that performs aggregated congestion control.