To Infinity and Beyond: Time-Warped Network Emulation

of 12

Please download to get full document.

View again

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
PDF
12 pages
0 downs
3 views
Share
Description
To Infinity and Beyond: Time-Warped Network Emulation Diwaker Gupta, Kenneth Yocum, Marvin McNett, Alex C. Snoeren, Amin Vahdat, and Geoffrey M. Voelker University of California, San Diego
Transcript
To Infinity and Beyond: Time-Warped Network Emulation Diwaker Gupta, Kenneth Yocum, Marvin McNett, Alex C. Snoeren, Amin Vahdat, and Geoffrey M. Voelker University of California, San Diego Abstract The goal of this work is to subject unmodified applications running on commodity operating systems and stock hardware to network speeds orders of magnitude faster than available at any given point in time. This paper describes our approach to time dilation, atechnique to uniformly and accurately slow the passage of time from the perspective of an operating system by a specified factor. As a side effect, physical devices including the network appear relatively faster to both applications and operating systems. Both qualitative and statistical evaluations indicate our prototype implementation is accurate across several orders of magnitude. We demonstrate time dilation s utility by conducting highbandwidth head-to-head TCP stack comparisons and application evaluation. 1 Introduction This work explores the viability and benefits of time dilation providing the illusion to an operating system and its applications that time is passing at a rate different from physical time. For example, we may wish to convince a system that, for every 1 seconds of wall clock time, only one second of time passes in the operating system s dilated time frame. Time dilation does not, however, change the arrival rate of physical events such as those from I/O devices like a network interface or disk controller. Hence, from the operating system s perspective, physical resources appear 1 times faster: in particular, data arriving from a network interface at a physical rate of 1 Gbps appears to the OS to be arriving at 1 Gbps. We refer to the ratio between the rate at which time passes in the physical world to the operating system s perception of time as the time dilation factor, ortdf;a TDF greater than one indicates the external world appears faster than it really is. Figure 1 illustrates the Figure 1: This figure compares a system operating in real time (left) and a system running with a TDF of 2 (right). Note that time dilation does not affect the timing of external events, such as network packet arrival. difference between an undilated (TDF of 1) operating system on the left and a dilated OS with TDF of 2 on the right. The same period of physical time passes for both machines. Each OS receives external events such as timer (on top) and device (on bottom) interrupts. Timer interrupts update the operating systems notion of time; in this example, time dilation halves the frequency of delivered timer interrupts. Critically, physical devices such as the network continue to deliver events at the same rate to both OSes. The dilated OS, therefore, perceives twice the network I/O rate because it experiences only half the delay between I/O events. In particular, the undilated OS observes a delay of 1 ms between packet arrivals, while the dilated OS observes only 5 ms between packet arrivals. From the dilated frame of reference, time dilation scales the observed I/O rate by the TDF (in this case two). Interestingly, time dilation scales the perceived available processing power as well. A system will experience TDF times as many cycles per perceived second from the processor. Such CPU scaling is particularly relevant to CPU-bound network processing because the number of cycles available to each arriving byte remains constant. For instance, a machine with TDF of 1 sees a 1 times USENIX Association NSDI 6: 3rd Symposium on Networked Systems Design & Implementation 87 faster network, but would also experience a tenfold increase in CPU cycles per second. By employing large TDF values, time dilation enables external stimuli to appear to take place at higher rates than would be physically possible, presenting a number of interesting applications. Consider the following scenarios: Emerging I/O technologies. Imagine a complex cluster-based service interconnected by 1-Mbps and 1-Gbps Ethernet switches. The system developers suspect overall service performance is limited by network performance. However, upgrading to 1- GigE switches and interfaces involves substantial expense and overhead. The developers desire a lowcost mechanism for determining the potential benefits of higher performance network interconnects before committing to the upgrade. Scalable network emulation. Today large ISPs cannot evaluate the effects of modifications to their topology or traffic patterns outside of complex and high-level simulations. While they would like to evaluate internal network behavior driven by realistic traffic traces, this often requires accurate emulation of terabits per second of bisection bandwidth. High bandwidth-delay networking. We have recently seen the emergence of computational grids [4, 12] inter-connected by high-speed and high-latency wide-area interconnects. For instance, 1-Gbps links with 1 2 ms round-trip times are currently feasible. Unfortunately, existing transport protocols, such as TCP, deliver limited throughput to one or more flows sharing such a link. A number of research efforts have proposed novel protocols for high bandwidth-delay product settings [11, 14, 16 18, 28, 3]. However, evaluation of the benefits of such efforts is typically relegated to simulation or to those with access to expensive wide-area links. This work develops techniques to perform accurate time dilation for unmodified applications running on commodity operating systems and stock hardware with the goal of supporting the above scenarios. To facilitate dilating time perceived by a host, we utilize virtual machine (VM) technology. Virtual machines traditionally have been used for their isolation capabilities: applications and operating systems running inside a VM can only access physical hardware through the virtual machine monitor. This interposition provides the additional potential to independently dilate time for each hosted virtual machine. In this paper, we are particularly interested in time dilation with respect to network devices; we leave faithful scaling of other subsystems to future work. This paper makes the following contributions: Time-dilated virtual machines. We show how to use virtual machines to completely encapsulate a host running a commodity operating system in an arbitrarily dilated time frame. We allow processing power and I/O performance to be scaled independently (e.g., to hold processing power constant while scaling I/O performance by a factor of 1, or vice versa). Accurate network dilation. We perform a detailed comparison of TCP s complex end-to-end protocol behavior in isolation, under loss, and with competing flows under dilated and real time frames. We find that both the micro and macro behavior of the system are indistinguishable under dilation. To demonstrate our ability to predict the performance of future hardware scenarios, we show that the timedilated performance of an appropriately dilated sixyear old machine with 1-Mbps Ethernet is indistinguishable from a modern machine with Gigabit Ethernet. End-to-end experimentation. Finally we demonstrate the utility of time dilation by experimenting with a content delivery overlay service. In particular, we explore the impact of high-bandwidth network topologies on the performance of BitTorrent [9], emulating multi-gigabit bisection bandwidths using a traffic shaper whose physical capacity is limited to 1Gbps. The remainder of the paper is organized as follows: We present our prototype implementation in Section 2. We evaluate the accuracy of time dilation with comprehensive micro-benchmarks in Section 3 and present application results in Section 4. Section 5 presents related work before concluding in Section 6. 2 Design and implementation Before describing the details of our implementation, we first define some key terminology. A Virtual Machine (VM) or domain is a software layer that exports the interface of a target physical machine. Multiple VM s may be multiplexed on a single physical machine. A Guest OS is the Operating System that runs within a VM. Finally, a Virtual Machine Monitor (VMM) or hypervisor is the hardware/software layer responsible for multiplexing several VMs on the same physical machine. Critical to time dilation is a VMM s ability to modify the perception of time within a guest OS. Fortunately, VMMs must already perform this functionality, for example, because a guest OS may develop a backlog of lost ticks if it is not scheduled on the physical 88 NSDI 6: 3rd Symposium on Networked Systems Design & Implementation USENIX Association processor when it is due to receive a timer interrupt. VMMs typically periodically synchronize the guest OS time with the physical machine s clock. One challenge is that operating systems often use multiple time sources for better precision. For example, Linux uses up to five different time sources [19]. Exposing so many different mechanisms for time keeping in virtual machines becomes challenging (see [27] for a discussion). To be useful, time dilation must be pervasive and transparent. Pervasiveness implies that the system is completely isolated from the passage of physical time. Similarly, transparency implies that network protocols and applications require no modification to be used in a dilated time frame. To address these requirements, we implemented a time dilation prototype using the Xen VMM [7] (Our implementation is based on Xen 2..7). We chose Xen for the following reasons: (1) it is easier to modify behavior of timer interrupts in software than in hardware; (2) we can observe time dilation in isolated, controlled environments; (3) Xen allows us to provide each virtual machine with an independent time frame; (4) Xen source code is publicly available; and iv) the VMM CPU scheduler provides a facility for scaling CPU. Though our implementation is Xen-specific, we believe the concepts can apply to other virtual machine environments. Alternative implementation targets for time dilation include directly modifying the operating system, simulation packages, and emulation environments. As discussed below, our modifications to Xen are compact and portable, giving us confidence that our techniques will be applicable to any operating system that Xen supports. In some sense, time dilation is free in many simulation packages: extrapolating to future scenarios is as simple as setting appropriate bandwidth values on particular links. However, we explicitly target running unmodified applications and operating systems for necessary realism. Finally, while network emulation does allow experimentation with a range of network conditions, it is necessarily limited by the performance of currently available hardware. For this reason, time dilation is a valuable complement to network emulation, allowing an experimenter to easily extrapolate evaluations to future, faster environments. We now give a brief overview of time keeping in Xen, describe our modifications to it, and discus the applicability of time dilations to other virtualization platforms. 2.1 Time flow in Xen The Xen VMM exposes two notions of time to VMs. Real time is the number of nanoseconds since boot. Wall clock time is the traditional Unix time-since-epoch (midnight, January 1, 197 UTC). Xen also delivers periodic timer interrupts to the VM to support the time keeping mechanisms within the guest OS. While Xen allows the guest OS to maintain and update its own notion of time via an external time source (such as NTP), the guest OS often relies solely on Xen to maintain accurate time. Real and wall clock time pass between the Xen hypervisor and the guest operating system via a shared data structure. There is one data structure per VM written by the VMM and read by the guest OS. The guest operating system updates its local time values on demand using the shared data structure for instance, when servicing timer interrupts or calling getttimeofday. However, the VMM updates the shared data structure only at certain discrete events, and thus it may not always contain the current value. In particular, the VMM updates the shared data structure when it delivers a timer interrupt to the VM or schedules the VM to run on an available CPU. Xen uses paravirtualization to achieve scalable performance with virtual machines without sacrificing functionality or isolation. With paravirtualization, Xen does not provide a perfect virtualization layer. Instead, it exposes some features of the underlying physical hardware to gain significant performance benefits. For instance, on the x86 architecture, Xen allows guest OSes (for our tests, we use XenoLinux as our guest OS) to read the Time-Stamp Count (TSC) register directly from hardware (via the RDTSC instruction). The TSC register stores the number of clock cycles since boot and is incremented on every CPU cycle. The Guest OS reads the TSC to maintain accurate time between timer interrupts. By contrast, kernel variables such as Linux jiffies or BSD ticks only advance on timer interrupts. In this case, we modify the guest OS to prevent them from reading the true value of the TSC, as described in the next section. 2.2 Dilating time in Xen We now outline our modifications to the Xen hypervisor and the XenoLinux kernel to support time dilation. We focus on slowing down the passage of time so that the external world appears faster. It is also possible to speed the passage of time from the OS s perspective, thereby slowing processes in the external world. In general, however, speeding the passage of time is less useful for our target scenarios and we do not explore it in this paper. Our modifications to Xen are small: in all, we added/modified approximately 5 lines of C and Python code. More than 5% of our changes are to non-critical tools and utilities; the core changes to Xen and Xeno- Linux are less than 2 lines of code. Our modifications are less than.5% of the base code size of each component. USENIX Association NSDI 6: 3rd Symposium on Networked Systems Design & Implementation 89 Variable Original Dilated Real time stime irq stime irq/tdf Wall clock wc sec, wc usec wc sec/tdf, wc usec/tdf Timer interrupts HZ/sec (HZ/tdf)/sec Table 1: Basic Dilation Summary Modifications to the Xen hypervisor. Our modified VMM maintains a TDF variable for each hosted VM. For our applications, we are concerned with the relative passage of time rather than the absolute value of real time; in particular, we allow indeed, require that the host s view of wall clock time diverge from reality. Thus the TDF divides both real and wall clock time. We modify two aspects of the Xen hypervisor. First we extend the shared data structure to include the TDF field. Our modified Xen tools, such as xm, allow specifying a positive, integral value for the TDF on VM creation. When the hypervisor updates the shared data structure, it uses this TDF value to modify real and wall clock time. In this way, real time is never exposed to the guest OS through the shared data structure. Dilation also impacts the frequency of timer interrupts delivered to the VM. The VMM controls the frequency of timer interrupts delivered to an undilated VM (timer interrupts/second); in most OS s a HZ variable, set at compile time, defines the number of timer interrupts delivered per second. For transparency, we need to maintain the invariant that HZ accurately reflects the number of timer interrupts delivered to the VM during a second of dilated time. Without adjusting timer interrupt frequency, the VMM will deliver TDF-times too many interrupts. For example, the VMM will deliver HZ interrupts in one physical time second, which will look to the dilated VMM as HZ/(second/TDF) = TDF*HZ. Instead, we reduce the number of interrupts a VM receives by a factor of TDF (as illustrated earlier in Figure 1). Table 1 summarizes the discussion so far. Finally, Xen runs with a default HZ value of 1, and configures guests with the same value. However, HZ = 1 gives only a 1-ms precision on system timer events. In contrast, current 2.6 series of Linux kernels uses a HZ value of 1 by default the CPU overhead is not significant, but the accuracy gains are tenfold. This increase in accuracy is desirable for time dilation because it enables guests to measure time accurately even in the dilated time frame. Thus, we increase the HZ value to 1 in both Xen and the guest OS. Modifications to XenoLinux. One goal of our implementation was to minimize required modifications to the guest OS. Because the VMM appropriately updates the shared data structure, one primary aspect of OS timekeeping is already addressed. We further modify the guest OS to read an appropriately scaled version of the hardware Time Stamp Counter (TSC). XenoLinux now reads the TDF from the shared data structure and adjusts the TSC value in the function get offset tsc. The Xen hypervisor also provides guest OS programmable alarm timers. Our last modification to the guest OS adjusts the programmable timer events. Because guests specify timeout values in their dilated time frames, we must scale the timeout value back to physical time. Otherwise they may set the timer for the wrong (possibly past) time. 2.3 Time dilation on other platforms Architectures: Our implementation should work on all platforms supported by Xen. One remark regarding transparency of time dilation to user applications on the x86 platform is in order: recall that we intercept calls to read the TSC within the guest kernel. However, since the RDTSC instruction is not a privileged x86 instruction, guest user applications might still issue assembly instructions to read the hardware TSC register. It is possible to work around this by watching the instruction stream emanating from a VM and trapping to the VMM on a RDTSC instruction, and then returning the appropriate value to the VM. However, this approach would go against Xen s paravirtualization philosophy. Fortunately, the current generation of x86-compatible hardware (such as the AMD Pacifica [6] and Intel VT [13]) provides native virtualization support, making it possible to make time dilation completely transparent to applications. For instance, both VT and Pacifica have hardware support for trapping the RDTSC instruction. VMMs: The only fundamental requirement from a VMM for supporting time dilation is that it have mechanisms to update/modify time perceived by a VM. As mentioned earlier, due to the difficulties in maintaining time within a VM, all VMMs already have similar mechanisms so that they can periodically bring the guest OS time in sync with real time. For instance, VMWare has explicit support for keeping VMs in a fictitious time frame that is at a constant offset from real time [27]. Thus, it should be straightforward to implement time dilation for other VMMs. Operating systems: Our current implementation provides dilation support for XenoLinux. Our experience so far and a preliminary inspection of the code for other guest OSes indicate that all of the guest OSes that Xen supports can be easily modified to support time dilation. It is important to note that modifying the guest OSes is not a fundamental requirement. Using binary rewriting, 9 NSDI 6: 3rd Symposium on Networked Systems Design & Implementation USENIX Association it would be possible to use unmodified guest OS executables. We expect that with better hardware and operating system support for virtualization, unmodified guests would be able to run under dilation. 2.4 Limitations This section discusses some of the limitations of time dilation. One obvious limitation is time itself: a 1-second experiment would run for a 1 seconds for a dilation factor of 1. Real-life experiments running for hours are not uncommon, so the time required to run experiments at high TDFs is substantial. Below we discuss other, more subtle limitations Other devices and nonlinear scaling Time dilation uniformly scales the perceived perfo
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks