System software is often complex and hides exploitable security vulnerabilities. Formal verification promises bug-free software but comes with a prohibitive proof cost. We present Spoq2, the first verification framework to highly automate security verification of unmodified system software. Spoq2 is based on the observation that many security properties, such as noninterference, can be reduced to establishing inductive invariants on individual transitions of a transition system that models system software. However, directly verifying such invariants for real system code overwhelms existing SMT solvers. Spoq2 makes this possible by automatically reducing verification complexity. It decomposes transitions into individual execution paths, extends cone-of-influence analysis to the individual transition level, and eliminates irrelevant machine states, clauses, and control-flow paths before invoking the SMT solver. Spoq2 further optimizes how pointer operations are modeled and verified through pointer abstractions that eliminate expensive bit-wise operations from SMT queries. We demonstrate the effectiveness of Spoq2 by verifying security properties of four unmodified, real-world system codebases with minimal manual effort.

Hands-on programming experience is crucial for students to learn about operating systems, but implementing key concepts such as file systems is perceived as being too hard to do for a real operating system in an introductory course on operating systems. To overcome these barriers, we introduce ezFS, a Linux file system that supports standard file system operations to persistent disk storage, yet is simple enough for students in an introductory operating systems course to implement in a couple weeks. ezFS takes advantage of file system and block storage interfaces in Linux that simplify file system implementation, such that its implementation requires only a few hundred lines of C code. We leverage standard file system interfaces to also develop an ezFS grader that can automatically grade ezFS implementations so that it is easy to scale its use for teaching a large course. We have successfully used ezFS as a programming assignment in an introductory operating systems course for hundreds of college students. ezFS significantly enhanced students' understanding of how file systems work in real operating systems, was simpler to implement than even pseudo Linux file systems, and was less difficult to complete than other programming assignments typically assigned for the course.

Rogue updates, an important type of software supply-chain attack in which attackers conceal malicious code inside updates to benign software, are a growing problem due to their stealth and effectiveness. We design and implement RogueOne, a system for detecting rogue updates to JavaScript packages. RogueOne uses a novel differential data-flow analysis to capture how an update changes a package's interactions with external APIs. Using an efficient form of abstract interpretation that can exclude unchanged code in a package, it constructs an object data-flow relationship graph (ODRG) that tracks data-flows among objects. RogueOne then maps objects to trust domains, a novel abstraction which summarizes trust relationships in a package. Objects are assigned a trust domain based on whether they originate in the target package, a dependency, or in a system API. RogueOne uses the ODRG to build a set of data-flows across trust domains. It compares data-flow sets across package versions to detect untrustworthy new interactions with external APIs. We evaluated RogueOne on hundreds of npm packages, demonstrating its effectiveness at detecting rogue updates and distinguishing them from benign ones. RogueOne achieves high accuracy and can be more than seven times as effective in detecting rogue updates and avoiding false positives compared to other systems built to detect malicious packages.

Distributed protocols have long been formulated in terms of their safety and liveness properties. Much recent work has focused on automatically verifying the safety properties of distributed protocols, but doing so for liveness properties has remained a challenging, unsolved problem. We present LVR, the first framework that can mostly automatically verify liveness properties for distributed protocols. Our key insight is that most liveness properties for distributed protocols can be reduced to a set of safety properties with the help of ranking functions. Such ranking functions for practical distributed protocols have certain properties that make them straightforward to synthesize, contrary to conventional wisdom. We prove that verifying a liveness property can then be reduced to a simpler problem of verifying a set of safety properties, namely that the ranking function is strictly decreasing and nonnegative for any protocol state transition, and there is no deadlock. LVR automatically synthesizes ranking functions by formulating a parameterized function of integer protocol variables, statically analyzing the lower and upper bounds of the variables as well as how much they can change on each state transition, then feeding the constraints to an SMT solver to determine the coefficients of the ranking function. It then uses an off-the-shelf verification tool to find inductive invariants to verify safety properties for both ranking functions and deadlock freedom. We show that LVR can mostly automatically verify the liveness properties of several distributed protocols, including various versions of Paxos, with limited user guidance.

Diagnosing performance issues is often difficult, especially when they occur only during some program executions. Profilers can help with performance debugging, but are ineffective when the most costly functions are not the root causes of performance issues. To address this problem, we introduce a new profiling methodology, value-assisted cost profiling, and a tool vProf. Our insight is that capturing the values of variables can greatly help diagnose performance issues. vProf continuously records values while profiling normal and buggy program executions. It identifies anomalies in the values and the functions where they occur to pinpoint the real root causes of performance issues. Using a set of 15 real-world performance bugs in four widely used applications, we show that vProf is effective at diagnosing all of the issues while other state-of-the-art tools diagnose only a few of them. We further use vProf to diagnose longstanding performance issues in these applications that have been unresolved for over four years.

As smartphones and tablets have become ubiquitous, there is a growing demand for apps that can enable users to collaboratively use multiple mobile systems. We present Tap, a framework that makes it easy for users to dynamically compose collections of mobile systems and developers to write apps that make use of those impromptu collections. Tap users control the composition by simply tapping systems together for discovery and authentication. The physical interaction mimics and supports ephemeral user interactions without the need for tediously exchanging user contact information such as phone numbers or email addresses. Tapping triggers a simple NFC-based mechanism to exchange connectivity information and security credentials that works across heterogeneous networks and requires no user accounts or cloud infrastructure support. Tap makes it possible for apps to use existing mobile platform APIs across multiple mobile systems by virtualizing data sources so that local and remote data sources can be combined together upon tapping. Virtualized data sources can be hardware or software features, including media, clipboard, calendar events, and devices such as cameras and microphones. Leveraging existing mobile platform APIs makes it easy for developers to write apps that use hardware and software features across dynamically composed collections of mobile systems. We have implemented a Tap prototype that allows apps to make use of both unmodified Android and iOS systems. We have modified and implemented various apps using Tap to demonstrate that it is easy to use and can enable apps to provide powerful new functionality by leveraging multiple mobile systems. Our results show that Tap has good performance, even for high-bandwidth features, and is user and developer friendly.

Cloud photo services are widely used for persistent, convenient, and often free photo storage, which is especially useful for mobile devices. As users store more and more photos in the cloud, significant privacy concerns arise because even a single compromise of a user's credentials give attackers unfettered access to all of the user's photos. We have created Easy Secure Photos (ESP) to enable users to protect their photos on cloud photo services such as Google Photos. ESP introduces a new client-side encryption architecture that includes a novel format-preserving image encryption algorithm, an encrypted thumbnail display mechanism, and a usable key management system. ESP encrypts image data such that the result is still a standard format image like JPEG that is compatible with cloud photo services. ESP efficiently generates and displays encrypted thumbnails for fast and easy browsing of photo galleries from trusted user devices. ESP's key management makes it simple to authorize multiple user devices to view encrypted image content via a process similar to device pairing, but using the cloud photo service as a QR code communication channel. We have implemented ESP in a popular Android photos app for use with Google Photos and demonstrate that it is easy to use and provides encryption functionality transparently to users, maintains good interactive performance and image quality while providing strong privacy guarantees, and retains the sharing and storage benefits of Google Photos without any changes to the cloud service.

Concurrent systems software is widely-used, complex, and error-prone, posing a significant security risk. We introduce VRM, a new framework that makes it possible for the first time to verify concurrent systems software, such as operating systems and hypervisors, on Arm relaxed memory hardware. VRM defines a set of synchronization and memory access conditions such that a program that satisfies these conditions can be mostly verified on a sequentially consistent hardware model and the proofs will automatically hold on relaxed memory hardware. VRM can be used to verify concurrent kernel code that is not data race free, including code responsible for managing shared page tables in the presence of relaxed MMU hardware. Using VRM, we verify the security guarantees of a retrofitted implementation of the Linux KVM hypervisor on Arm. For multiple versions of KVM, we prove KVM's security properties on a sequentially consistent model, then prove that KVM satisfies VRM's required program conditions such that its security proofs hold on Arm relaxed memory hardware. Our experimental results show that the retrofit and VRM conditions do not adversely affect the scalability of verified KVM, as it performs similar to unmodified KVM when concurrently running many multiprocessor virtual machines with real application workloads on Arm multiprocessor server hardware. Our work is the first machine-checked proof for concurrent systems software on Arm relaxed memory hardware.

Commodity hypervisors are widely deployed to support virtual machines (VMs) on multiprocessor hardware. Their growing complexity poses a security risk. To enable formal verification over such a large codebase, we introduce microverification, a new approach that decomposes a commodity hypervisor into a small core and a set of untrusted services so that we can prove security properties of the entire hypervisor by verifying the core alone. To verify the multiprocessor hypervisor core, we introduce security-preserving layers to modularize the proof without hiding information leakage so we can prove each layer of the implementation refines its specification, and the top layer specification is refined by all layers of the core implementation. To verify commodity hypervisor features that require dynamically changing information flow, we introduce data oracles to mask intentional information flow. We can then prove noninterference at the top layer specification and guarantee the resulting security properties hold for the entire hypervisor implementation. Using microverification, we retrofitted the Linux KVM hypervisor with only modest modifications to its codebase. Using Coq, we proved that the hypervisor protects the confidentiality and integrity of VM data, while retaining KVM’s functionality and performance. Our work is the first machine-checked security proof for a commodity multiprocessor hypervisor.

Nested virtualization, running virtual machines and hypervisors on top of other virtual machines and hypervisors, is increasingly important because of the need to deploy virtual machines running software stacks on top of virtualized cloud infrastructure. However, performance remains a key impediment to further adoption as application workloads can perform many times worse than native execution. To address this problem, we introduce DVH (Direct Virtual Hardware), a new approach that enables a host hypervisor, the hypervisor that runs directly on the hardware, to directly provide virtual hardware to nested virtual machines without the intervention of multiple levels of hypervisors. We introduce four DVH mechanisms, virtual-passthrough, virtual timers, virtual inter-processor interrupts, and virtual idle. DVH provides virtual hardware for these mechanisms that mimics the underlying hardware and in some cases adds new enhancements that leverage the flexibility of software without the need for matching physical hardware support. We have implemented DVH in the Linux KVM hypervisor. Our experimental results show that DVH can provide near native execution speeds and improve KVM performance by more than an order of magnitude on real application workloads.

With the continued proliferation of drones, unmanned aerial vehicles, additional uses for them are growing and the demand for their services is on the rise. We present AnDrone, a drone-as-a-service solution that makes drones accessible in the cloud. AnDrone pairs a cloud service with the first drone virtualization architecture. This enables a physical drone to run multiple virtual drones simultaneously in an isolated and secure manner at little additional cost, as computational costs are cheap compared to the operational and energy costs of putting a drone in the air. AnDrone virtualizes drones using a novel Linux container architecture. Android Things virtual drone containers provide a familiar user and development environment that can run existing Android apps. A real-time Linux flight controller container supports existing drone flight software and provides virtual drones with geofenced flight control. A device container transparently multiplexes access from virtual drones to a full range of drone hardware devices, including cameras and other sensors. Upon flight completion, virtual drones and their data can be uploaded to the cloud for offline access. We have implemented an AnDrone prototype based on Raspberry Pi 3 drone hardware. We demonstrate that it incurs minimal runtime performance and energy overhead, supports real-time virtual drone flight control, and runs untrusted third-party software in virtual drones in a secure manner while ensuring that the service provider maintains control of the drone hardware.

Email privacy is of crucial importance. Existing email encryption approaches are comprehensive but seldom used due to their complexity and inconvenience. We take a new approach to simplify email encryption and improve its usability by implementing receiver-controlled encryption: newly received messages are transparently downloaded and encrypted to a locally-generated key; the original message is then replaced. To avoid the problem of moving a single private key between devices, we implement per-device key pairs: only public keys need be synchronized via a simple verification step. Compromising an email account or server only provides access to encrypted emails. We implemented this scheme on several platforms, showing it works with PGP and S/MIME, is compatible with widely used mail clients and email services including Gmail, has acceptable overhead, and that users consider it intuitive and easy to use.

As smartphones and tablets proliferate, there is a growing demand for multi-mobile computing, the ability to combine multiple mobile systems into more capable ones. We present M2, a system for multi-mobile computing that enables existing unmodified mobile apps to share and combine multiple devices, including cameras, displays, speakers, microphones, sensors, GPS, and input. M2 introduces a new data-centric approach that leverages higher-level device abstractions and hardware acceleration to efficiently share device data, not API calls. To support heterogeneous devices, M2 introduces device transformation, a new technique to mix and match different types of devices. Example transformations include combining multiple displays into a single larger display for better viewing, or substituting accelerometer for touchscreen input to provide a Nintendo Wii-like experience with existing mobile gaming apps. We have implemented M2 and show that it (1) operates across heterogeneous systems, including multiple versions of Android and iOS, (2) can enable unmodified Android apps to use multiple mobile devices in new and powerful ways, including supporting users with disabilities and better audio conferencing, and (3) can run apps across mobile systems with modest overhead and qualitative performance indistinguishable from using local device hardware.

As smartphones and tablets proliferate, there is a growing demand for multi-mobile computing [1, 2], the ability to combine multiple commodity mobile systems into more capable ones, including using multiple hardware devices such as cameras, displays, speakers, microphones, sensors, GPS, and input. However, the tremendous device, hardware, and software heterogeneity of mobile systems makes this difficult. In this demo, we present M2, a system for multi-mobile computing that enables existing unmodified mobile apps to make use of new ways of sharing and combining multiple devices. M2 introduces a new data-centric approach that leverages higher-level device abstractions and encoding/decoding hardware to efficiently share device data as opposed to low-level device-specific APIs.

Mobile apps make extensive use of GPUs on smartphones and tablets to access Web content. To support pervasive Web content, we introduce three key OS techniques for binary graphics compatibility necessary to build a real-world system to run iOS and Android apps together on the same smartphone or tablet. First diplomat usage patterns manage resources to bridge proprietary iOS and Android graphics implementations. Second, thread impersonation allows a single thread-specific context to be shared amongst multiple threads using multiple iOS and Android personas. Third, dynamic library replication allows multiple, independent instances of the same library to be loaded in a single process to support iOS apps on Android while using multiple graphics API versions at the same time. We use these techniques to build a system prototype, and demonstrate that it runs widely-used iOS apps, including apps such as Safari that use the popular GPU-accelerated WebKit framework, using a Google Nexus tablet running Android.

Nested virtualization, the ability to run a virtual machine inside another virtual machine, is increasingly important because of the need to deploy virtual machines running software stacks on top of virtualized cloud infrastructure. As ARM servers make inroads in cloud infrastructure deployments, supporting nested virtualization on ARM is a key requirement, which has been met recently with the introduction of nested virtualization support to the ARM architecture. We build the first hypervisor to use ARM nested virtualization support and show that despite similarities between ARM and x86 nested virtualization support, performance on ARM is much worse than on x86. This is due to excessive traps to the hypervisor caused by differences in non-nested virtualization support. To address this problem, we introduce a novel paravirtualization technique to rapidly prototype architectural changes for virtualization and evaluate their performance impact using existing hardware. Using this technique, we propose Nested Virtualization Extensions for ARM (NEVE), a set of simple architectural changes to ARM that can be used by software to coalesce and defer traps by logging the results of hypervisor instructions until the results are actually needed by the hypervisor or virtual machines. We show that NEVE allows hypervisors running real application workloads to provide an order of magnitude better performance than current ARM nested virtualization support and up to three times less overhead than x86 nested virtualization. NEVE will be included in ARMv8.4, the next version of the ARM architecture.

The POSIX standard, developed 25 years ago, comprises a set of operating system (OS) abstractions that aid application portability across UNIX-based OSes. While OSes and applications have evolved tremendously over the last 25 years, POSIX, and the basic set of abstractions it provides, has remained largely unchanged. Little has been done to measure how and to what extent traditional POSIX abstractions are being used in modern OSes, and whether new abstractions are taking form, dethroning traditional ones. We explore these questions through a study of POSIX usage in modern desktop and mobile OSes: Android, OS X, and Ubuntu. Our results show that new abstractions are taking form, replacing several prominent traditional abstractions in POSIX. While the changes are driven by common needs and are conceptually similar across the three OSes, they are not converging on any new standard, increasing fragmentation.

ARM servers are becoming increasingly common, making server technologies such as virtualization for ARM of growing importance. We present the first study of ARM virtualization performance on server hardware, including multi-core measurements of two popular ARM and x86 hypervisors, KVM and Xen. We show how ARM hardware support for virtualization can enable much faster transitions between VMs and the hypervisor, a key hypervisor operation. However, current hypervisor designs, including both Type 1 hypervisors such as Xen and Type 2 hypervisors such as KVM, are not able to leverage this performance benefit for real application workloads. We discuss the reasons why and show that other factors related to hypervisor software design and implementation have a larger role in overall performance. Based on our measurements, we discuss changes to ARM's hardware virtualization support that can potentially bridge the gap to bring its faster VM-to-hypervisor transition mechanism to modern Type 2 hypervisors running real applications. These changes have been incorporated into the latest ARM architecture.

With the continued proliferation of mobile devices, apps will increasingly become multi-surface, running seamlessly across multiple user devices (e.g., phone, tablet, etc.). Yet general systems support for multi-surface app is limited to (1) screencasting, which relies on a single master device's computing power and battery life or (2) cloud backing, which is unsuitable in the face of disconnected operation or untrusted cloud providers. We present an alternative approach: Flux, an Android-based system that enables any app to become multi-surface through app migration. Flux overcomes device heterogeneity and residual dependencies through two key mechanisms. Selective Record/Adaptive Replay records just those device-agnostic app calls that lead to the generation of app-specific device-dependent state in system services and replays them on the target. Checkpoint/Restore in Android (CRIA) transitions an app into a state in which device-specific information can be safely discarded before checkpointing and restoring the app. Our implementation of Flux can migrate many popular, unmodified Android apps---including those with extensive device interactions like 3D accelerated graphics---across heterogeneous devices and is fast enough for interactive use.

The growing demand for data-driven features in today's Web applications -- such as targeting, recommendations, or predictions -- has transformed those applications into complex conglomerates of services operating on each others' data without a coherent, manageable architecture. We present Synapse, an easy-to-use, strong-semantic system for large-scale, data-driven Web service integration. Synapse lets independent services cleanly share data with each other in an isolated and scalable way. The services run on top of their own databases, whose layouts and engines can be completely different, and incorporate read-only views of each others' shared data. Synapse synchronizes these views in real-time using a new scalable, consistent replication mechanism that leverages the high-level data models in popular MVC-based Web applications to replicate data across heterogeneous databases. We have developed Synapse on top of the popular Web framework Ruby-on-Rails. It supports data replication among a wide variety of SQL and NoSQL databases, including MySQL, Oracle, PostgreSQL, MongoDB, Cassandra, Neo4j, and Elasticsearch. We and others have built over a dozen microservices using Synapse with great ease, some of which are running in production with over 450,000 users.

We present Cider, an operating system compatibility architecture that can run applications built for different mobile ecosystems, iOS or Android, together on the same smartphone or tablet. Cider enhances the domestic operating system, Android, of a device with kernel-managed, per-thread personas to mimic the application binary interface of a foreign operating system, iOS, enabling it to run unmodified foreign binaries. This is accomplished using a novel combination of binary compatibility techniques including two new mechanisms: compile-time code adaptation, and diplomatic functions. Compile-time code adaptation enables existing unmodified foreign source code to be reused in the domestic kernel, reducing implementation effort required to support multiple binary interfaces for executing domestic and foreign applications. Diplomatic functions leverage per-thread personas, and allow foreign applications to use domestic libraries to access proprietary software and hardware interfaces. We have built a Cider prototype, and demonstrate that it imposes modest performance overhead and runs unmodified iOS and Android applications together on a Google Nexus tablet running the latest version of Android.

As ARM CPUs become increasingly common in mobile devices and servers, there is a growing demand for providing the benefits of virtualization for ARM-based devices. We present our experiences building the Linux ARM hypervisor, KVM/ARM, the first full system ARM virtualization solution that can run unmodified guest operating systems on ARM multicore hardware. KVM/ARM introduces split-mode virtualization, allowing a hypervisor to split its execution across CPU modes and be integrated into the Linux kernel. This allows KVM/ARM to leverage existing Linux hardware support and functionality to simplify hypervisor development and maintainability while utilizing recent ARM hardware virtualization extensions to run virtual machines with comparable performance to native execution. KVM/ARM has been successfully merged into the mainline Linux kernel, ensuring that it will gain wide adoption as the virtualization platform of choice for ARM. We provide the first measurements on real hardware of a complete hypervisor using ARM hardware virtualization support. Our results demonstrate that KVM/ARM has modest virtualization performance and power costs, and can achieve lower performance and power costs compared to x86-based Linux virtualization on multicore hardware.

Learning about operating systems often involves modifying a large and complex code base. Grading student projects can be difficult and time consuming, yet students often do not learn from their programming errors and struggle to understand core operating system concepts. We present GradeBoard, a code review system designed to simplify grading for instructors and enable students to understand and learn from their errors. GradeBoard provides an easy-to-use Web interface that allows instructors to annotate student code submissions with grading comments and scores, and students to discuss the comments and scores with instructors. GradeBoard presents student code changes with syntax highlighting and lets users collapse or expand code sections to provide a desired level of context, making it easier to read and understand student programming project submissions. Comments and scores are easily identifiable by visual cues, improving interaction between instructors and students. We have deployed and used GradeBoard in a large operating systems course involving Linux kernel programming projects. GradeBoard provided robust, easy-to-use functionality for reviewing Linux kernel code changes, improved the instructional staff grading experience, and over 90% of students surveyed indicated that GradeBoard improved their understanding of the kernel programming projects better than other alternatives.

Although millions of users download and use third-party Android applications from the Google Play store, little information is known on an aggregated level about these applications. We have built PlayDrone, the first scalable Google Play store crawler, and used it to index and analyze over 1,100,000 applications in the Google Play store on a daily basis, the largest such index of Android applications. PlayDrone leverages various hacking techniques to circumvent Google's roadblocks for indexing Google Play store content, and makes proprietary application sources available, including source code for over 880,000 free applications. We demonstrate the usefulness of PlayDrone in decompiling and analyzing application content by exploring four previously unaddressed issues: the characterization of Google Play application content at large scale and its evolution over time, library usage in applications and its impact on application portability, duplicative application content in Google Play, and the ineffectiveness of OAuth and related service authentication mechanisms resulting in malicious users being able to easily gain unauthorized access to user data and resources on Amazon Web Services and Facebook.

We present Dora, a mutable record-replay system which allows a recorded execution of an application to be replayed with a modified version of the application. This feature, not available in previous record-replay systems, enables powerful new functionality. In particular, Dora can help reproduce, diagnose, and fix software bugs by replaying a version of a recorded application that is recompiled with debugging information, reconfigured to produce verbose log output, modified to include additional print statements, or patched to fix a bug.

As more and more information is designed for human visual consumption through computer displays, the need to capture and process display-centric content is becoming increasingly important, especially for visually impaired users. We present Capture, a novel display-centric text recorder that facilitates real-time access to onscreen text and its structure and contextual information, including data associated with both foreground and background windows. Capture provides an intelligent caching architecture that integrates with the standard accessibility framework available on modern operating systems to continuously track onscreen text and metadata. This enables fast, semantic information recording without any modifications to applications, window systems, or operating system kernels. The recorded data is useful for a variety of problem domains, including assistive technologies, desktop search, auditing, and predictive graphical user interfaces. We have implemented a Capture prototype on Linux with the GNOME Accessibility Toolkit. Our results on real desktop applications demonstrate that Capture provides low runtime overhead and much more complete recording of onscreen text than modern desktop screen readers used for visually impaired users.

Clouds commonly store Virtual Machine (VM) images on networked storage. This poses a serious potential scalability bottleneck as launching a single fresh VM instance requires, at minimum, several hundred MB of network reads. As this bottleneck occurs most severely during read-intensive launching of new VMs, we focus on scalably minimizing time to boot a VM and load its critical applications.

The computing landscape is shifting towards mobile devices. To learn about operating systems, it is increasingly important for students to gain hands-on kernel programming experience in these environments, which are quite different from traditional desktops and servers. We present our work at Columbia University to teach operating systems using Android, an open, commercially supported software platform increasingly used on mobile and embedded devices. We introduce a series of five Android kernel programming projects suitable for a one semester introductory operating systems course. Each project teaches a core operating system concept infused with Android or mobile device specific context, such as Android specific process relationships, use of sensors, and design considerations for resource constrained mobile devices. We also introduce an Android virtual laboratory based on virtual appliances, distributed version control, and live demonstrations which gives students hands-on Android experience, with minimal computing infrastructure. We have used these Android kernel programming projects and the Android virtual lab to teach an introductory operating systems course. Although this was our first time teaching the course using Android, over 80% of students surveyed enjoyed using Android and the majority of students preferred Android to traditional desktop development.

Smartphones are increasingly ubiquitous, and many users carry multiple phones to accommodate work, personal, and geographic mobility needs. We present Cells , a virtualization architecture for enabling multiple virtual smartphones to run simultaneously on the same physical cellphone in an isolated, secure manner. Cells introduces a usage model of having one foreground virtual phone and multiple background virtual phones. This model enables a new device namespace mechanism and novel device proxies that integrate with lightweight operating system virtualization to multiplex phone hardware across multiple virtual phones while providing native hardware device performance. Cells virtual phone features include fully accelerated 3D graphics, complete power management features, and full telephony functionality with separately assignable telephone numbers and caller ID support. We have implemented a prototype of Cells that supports multiple Android virtual phones on the same phone. Our performance results demonstrate that Cells imposes only modest runtime and memory overhead, works seamlessly across multiple hardware devices including Google Nexus 1 and Nexus S phones, and transparently runs Android applications at native speed without any modifications.

Peer-to-peer file-sharing applications suffer from a fundamental problem of unfairness. Free-riders cause slower download times for others by contributing little or no upload bandwidth while consuming much download bandwidth. Previous attempts to address this fair bandwidth allocation problem suffer from slow peer discovery, inaccurate predictions of neighboring peers' bandwidth allocations, underutilization of bandwidth, and complex parameter tuning. We present FairTorrent, a new deficit-based distributed algorithm that accurately rewards peers in accordance with their contribution. A FairTorrent peer simply uploads the next data block to a peer to whom it owes the most data as measured by a deficit counter. FairTorrent is resilient to exploitation by free-riders and strategic peers, is simple to implement, requires no bandwidth overallocation, no prediction of peers' rates, no centralized control, and no parameter tuning. We implemented FairTorrent in a BitTorrent client without modifications to the BitTorrent protocol and evaluated its performance against other widely used BitTorrent clients. Our results show that FairTorrent provides up to two orders of magnitude better fairness, up to five times better download times for contributing peers, and 60%-100% better performance on average in live BitTorrent swarms.

Linux has emerged as a widely-used platform for enabling hands-on kernel programming experience to learn about operating system concepts. However, developing pedagogically-effective programming projects in the context of a complex, production operating system can be a challenge. We present a structured series of five Linux kernel programming projects suitable for a one semester introductory operating systems course to address this issue. Each assignment introduces students to a core topic and major component of an operating system while implicitly teaching them about various aspects of a real-world operating system. Projects are of modest coding complexity, but require students to understand and leverage core components of the Linux operating system. The learning benefits for students from this approach include learning from real-world operating system code examples by expert kernel designers and gaining software engineering experience managing production code complexity. We have successfully used these structured Linux kernel projects to teach over a thousand students in the introductory operating systems course at Columbia University.

Software bugs that occur in production are often difficult to reproduce in the lab due to subtle differences in the application environment and nondeterminism. To address this problem, we present Transplay, a system that captures production software bugs into small per-bug recordings which are used to reproduce the bugs on a completely different operating system without access to any of the original software used in the production environment. Transplay introduces partial checkpointing, a new mechanism that efficiently captures the partial state necessary to reexecute just the last few moments of the application before it encountered a failure. The recorded state, which typically consists of a few megabytes of data, is used to replay the application without requiring the specific application binaries, libraries, support data, or the original execution environment. Transplay integrates with existing debuggers to provide standard debugging facilities to allow the user to examine the contents of variables and other program state at each source line of the application's replayed execution. We have implemented a Transplay prototype that can record unmodified Linux applications and replay them on different versions of Linux as well as Windows. Experiments with several applications including Apache and MySQL show that Transplay can reproduce real bugs and be used in production with modest recording overhead.

Smartphones are increasingly ubiquitous, and many users carry multiple phones to accommodate work, personal, and geographic mobility needs. We present Cells, a virtualization architecture for enabling multiple virtual smartphones to run simultaneously on the same physical cellphone in an isolated, secure manner. Cells introduces a usage model of having one foreground virtual phone and multiple background virtual phones. This model enables a new device namespace mechanism and novel device proxies that integrate with lightweight operating system virtualization to multiplex phone hardware across multiple virtual phones while providing native hardware device performance. Cells virtual phone features include fully accelerated 3D graphics, complete power, management features, and full telephony functionality with separately assignable telephone numbers and caller ID support. We have implemented a prototype of Cells that supports multiple Android virtual phones on the same phone. Our performance results demonstrate that Cells imposes only modest runtime and memory overhead, works seamlessly across multiple hardware devices including Google Nexus 1 and Nexus S phones, and transparently runs Android applications at native speed without any modifications.

Process races occur when multiple processes access shared operating system resources, such as files, without proper synchronization. We present the first study of real process races and the first system designed to detect them. Our study of hundreds of applications shows that process races are numerous, difficult to debug, and a real threat to reliability. To address this problem, we created RacePro, a system for automatically detecting these races. RacePro checks deployed systems in-vivo by recording live executions then deterministically replaying and checking them later. This approach increases checking coverage beyond the configurations or executions covered by software vendors or beta testing sites. RacePro records multiple processes, detects races in the recording among system calls that may concurrently access shared kernel objects, then tries different execution orderings of such system calls to determine which races are harmful and result in failures. To simplify race detection, RacePro models under-specified system calls based on load and store micro-operations. To reduce false positives and negatives, RacePro uses a replay and go-live mechanism to distill harmful races from benign ones. We have implemented RacePro in Linux, shown that it imposes only modest recording overhead, and used it to detect a number of previously unknown bugs in real applications caused by process races.

Virtual Appliances (VAs) are Virtual Machines (VMs) geared towards a specific set of tasks. They require little or no configuration, working out-of-the-box. VAs fit neatly into the Cloud Computing paradigm - many copies of an identical machine can be launched in a data center, or home/business users can grab the appliance they need from the cloud to run locally just for so long as required. Companies and projects whose sole offerings are VAs ready for either desktop or data center use [3, 11] attest to the growing popularity of VAs. VMware's Appliance directory alone currently lists over 1400 VAs available for the VMware family of Virtual Machine Monitors (VMMs) [13].

Students learn more through hands-on project experience for computer science courses such as operating systems, but providing the infrastructure support for a large class to learn by doing can be hard. To address this issue, we introduce a new approach to managing and grading operating system homework assignments based on virtual appliances, a distributed version control system, and live demonstrations. Our solution is easy to deploy and use with students' personal computers, and obviates the need to provide a computer laboratory for teaching purposes. It supports the most demanding course projects, such as those that involve operating system kernel development, and can be used by both on-campus and remote distance learning students even with intermittent network connectivity. Our experiences deploying and using this solution to teach operating systems at Columbia University show that it is easier to use, more flexible, and more pedagogically effective than other approaches.

We present Scribe, the first system to provide transparent, lowoverhead application record-replay and the ability to go live from replayed execution. Scribe introduces new lightweight operating system mechanisms, rendezvous and sync points, to efficiently record nondeterministic interactions such as related system calls, signals, and shared memory accesses. Rendezvous points make a partial ordering of execution based on system call dependencies sufficient for replay, avoiding the recording overhead of maintaining an exact execution ordering. Sync points convert asynchronous interactions that can occur at arbitrary times into synchronous events that are much easier to record and replay. We have implemented Scribe without changing, relinking, or recompiling applications, libraries, or operating system kernels, and without any specialized hardware support such as hardware performance counters. It works on commodity Linux operating systems, and commodity multi-core and multiprocessor hardware. Our results show for the first time that an operating system mechanism can correctly and transparently record and replay multi-process and multi-threaded applications on commodity multiprocessors. Scribe recording overhead is less than 2.5 % for server applications including Apache and MySQL, and less than 15 % for desktop applications including Firefox, Acrobat, OpenOffice, parallel kernel compilation, and movie playback.

We present RSIO, a processor scheduling framework for improving the response time of latency-sensitive applications by monitoring accesses to I/O channels and inferring when user interactions occur. RSIO automatically identifies processes involved in a user interaction and boosts their priorities at the time the interaction occurs to improve system response time. RSIO also detects processes indirectly involved in processing an interaction, automatically accounting for dependencies and boosting their priorities accordingly. RSIO works with existing schedulers and requires no application modifications to identify periods of latency-sensitive application activity. We have implemented RSIO in Linux and measured its effectiveness on microbenchmarks and real applications. Our results show that RSIO is easy to use and can provide substantial improvements in system performance for latency-sensitive applications.

Operating system (OS) virtualization can provide a number of important benefits, including transparent migration of applications, server consolidation, online OS maintenance, and enhanced system security. However, the construction of such a system presents a myriad of challenges, even for the most cautious developer, that if overlooked may result in a weak, incomplete virtualization. We present a detailed discussion of key implementation issues in providing OS virtualization in a commodity OS, including system call interposition, virtualization state management, and race conditions. We discuss our experiences in implementing such functionality across two major versions of Linux entirely in a loadable kernel module without any kernel modification. We present experimental results on both uniprocessor and multiprocessor systems that demonstrate the ability of our approach to provide fine-grain virtualization with very low overhead.

Software failures in server applications are a significant problem for preserving system availability. We present ASSURE, a system that introduces rescue points that recover software from unknown faults while maintaining both system integrity and availability, by mimicking system behavior under known error conditions. Rescue points are locations in existing application code for handling a given set of programmer-anticipated failures, which are automatically repurposed and tested for safely enabling fault recovery from a larger class of (unanticipated) faults. When a fault occurs at an arbitrary location in the program, ASSURE restores execution to an appropriate rescue point and induces the program to recover execution by virtualizing the program's existing error-handling facilities. Rescue points are identified using fuzzing, implemented using a fast coordinated checkpoint-restart mechanism that handles multi-process and multi-threaded applications, and, after testing, are injected into production code using binary patching. We have implemented an ASSURE Linux prototype that operates without application source code and without base operating system kernel changes. Our experimental results on a set of real-world server applications and bugs show that ASSURE enabled recovery for all of the bugs tested with fast recovery times, has modest performance overhead, and provides automatic self-healing orders of magnitude faster than current human-driven patch deployment methods.

Peer-to-Peer file-sharing applications suffer from a fundamental problem of unfairness. Free-riders cause slower download times for others by contributing little or no upload bandwidth while consuming much download bandwidth. Previous attempts to address this fair bandwidth allocation problem suffer from slow peer discovery, inaccurate predictions of neighboring peers' bandwidth allocations, underutilization of bandwidth, and complex parameter tuning. We present FairTorrent, a new deficit-based distributed algorithm that accurately rewards peers in accordance with their contribution. A FairTorrent peer simply uploads the next data block to a peer to whom it owes the most data as measured by a deficit counter. FairTorrent is resilient to exploitation by free-riders and strategic peers, is simple to implement, requires no bandwidth over-allocation, no prediction of peers' rates, no centralized control, and no parameter tuning. We implemented FairTorrent in a BitTorrent client without modifications to the BitTorrent protocol, and evaluated its performance against other widely-used BitTorrent clients. Our results show that FairTorrent provides up to two orders of magnitude better fairness, up to five times better download times for contributing peers, and 60% to 100% better performance on average in live BitTorrent swarms.

We present MediaPod, a portable system that allows mobile users to maintain the same persistent, personalized multimedia desktop environment on any available computer. Regardless of which computer is being used, MediaPod provides a consistent multimedia desktop session, maintaining all of a user's applications, documents and configuration settings. This is achieved by leveraging rapid improvements in capacity, cost, and size of portable storage devices. MediaPod provides a virtualization and checkpoint-restart mechanism that decouples a desktop environment and its applications from the host, enabling multimedia desktop sessions to be suspended to portable storage, carried around, and resumed from the storage device on another computer. MediaPod virtualization also isolates desktop sessions from the host, protecting the privacy of the user and preventing malicious applications from damaging the host. We have implemented a Linux MediaPod prototype and demonstrate its ability to quickly suspend and resume multimedia desktop sessions, enabling a seamless computing experience for mobile users as they move among computers.

Developing CPU scheduling algorithms and understanding their impact in practice can be difficult and time consuming due to the need to modify and test operating system kernel code and measure the resulting performance on a consistent workload of real applications. To address this problem, we have developed WARP, a trace-driven virtualized scheduler execution environment that can dramatically simplify and speed the development of CPU schedulers. WARP is easy to use as it can run unmodified kernel scheduling code and can be used with standard user-space debugging and performance monitoring tools. It accomplishes this by virtualizing operating system and hardware events to decouple kernel scheduling code from its native operating system and hardware environment. A simple kernel tracing toolkit can be used with WARP to capture traces of all CPU scheduling related events from a real system. WARP can then replay these traces in its virtualized environment with the same timing characteristics as in the real system. Traces can be used with different schedulers to provide accurate comparisons of scheduling performance for a given application workload. We have implemented a WARP Linux prototype. Our results show that WARP can use application traces captured from its toolkit to accurately reflect the scheduling behavior of the real Linux operating system. Furthermore, testing scheduler behavior using WARP with application traces can be two orders of magnitude faster than running the applications using Linux.

As users interact with the world and their peers through their computers, it is becoming important to archive and later search the information that they have viewed. We present DejaView, a personal virtual computer recorder that provides a complete record of a desktop computing experience that a user can playback, browse, search, and revive seamlessly. DejaView records visual output, checkpoints corresponding application and file system state, and captures displayed text with contextual information to index the record. A user can then browse and search the record for any visual information that has been displayed on the desktop, and revive and interact with the desktop computing state corresponding to any point in the record. DejaView combines display, operating system, and file system virtualization to provide its functionality transparently without any modifications to applications, window systems, or operating system kernels. We have implemented DejaView and evaluated its performance on real-world desktop applications. Our results demonstrate that DejaView can provide continuous low-overhead recording without any user noticeable performance degradation, and allows browsing, search and playback of records fast enough for interactive use.

We present a new technique that enables software recovery in legacy applications by retrofitting exception-handling capabilities, error virtualization using rescue points. We introduce the idea of "rescue points" as program locations to which an application can recover its execution in the presence of failures. The use of rescue points reduces the chance of unanticipated execution paths thereby making recovery more robust by mimicking system behavior under controlled error conditions. These controlled error conditions can be thought of as a set erroneous inputs, like the ones used by most quality-assurance teams during software development, designed to stress-test an application. To discover rescue points applications are profiled and monitored during tests that bombard the program with bad/random inputs. The intuition is that by monitoring application behavior during these runs, we gain insight into how programmer-tested program points are used to propagate faults gracefully.

We present DeskPod, a portable system that provides a highly reliable desktop computing environment for mobile users by leveraging rapid improvements in capacity, cost, and size of portable storage devices. DeskPod enables a user's live computing environment to be suspended to portable storage, carried around, easily copied for fault-resilience, and resumed from the storage device to provide the user with the same persistent, personalized computing environment on another computer DeskPod achieves this by providing a virtualization and checkpoint/restart mechanism that decouples a desktop computing environment from any single hardware device so that it can be stored and executed anywhere, improving desktop computing reliability by eliminating a potential single point of failure. We have implemented a Linux DeskPod prototype and demonstrate its ability to quickly suspend and resume desktop sessions, enabling a seamless mobile experience

We present Grouped Distributed Queues (GDQ), the first proportional share scheduler for multiprocessor systems that scales well with a large number of processors and processes. GDQ uses a distributed queue architecture, and achieves accurate proportional fairness scheduling with only O(1) scheduling overhead. GDQ takes a novel approach to distributed queuing: instead of creating per-processor queues that need to be constantly balanced to achieve any measure of proportional sharing fairness, GDQ uses a simple grouping strategy to organize processes into groups based on similar processor time allocation rights, and then assigns processors to groups based on aggregate group shares. Group membership of processes is static, and fairness is achieved by dynamically migrating processors among groups. The set of processors working on a group use simple, low-overhead round-robin queues, while processor reallocation among groups is achieved using a new multiprocessor adaptation of Weighted Fair Queuing. By commoditizing processors and decoupling their allocation from process scheduling, GDQ provides, with only constant scheduling overhead, fairness within a constant of the ideal generalized processor sharing model for process weights with a fixed upper bound. We have implemented GDQ in Linux and measured its performance. Our experimental results show that GDQ has low overhead and scales well with the number of processors and processes.

Although web applications are gaining popularity on mobile wireless PDAs, web browsers on these systems can be quite slow and often lack adequate functionality to access many web sites. We have developed pTHINC, a PDA thin-client solution that leverages more powerful servers to run full-function web browsers and other application logic, then sends simple screen updates to the PDA for display. pTHINC uses server-side screen scaling to provide high-fidelity display and seamless mobility across a broad range of different clients and screen sizes, including both portrait and landscape viewing modes. pTHINC also leverages existing PDA control buttons to improve system usability and maximize available screen resolution for application display. We have implemented pTHINC on Windows Mobile and evaluated its performance on mobile wireless devices. Our results compared to local PDA web browsers and other thin-client approaches demonstrate that pTHINC provides superior web browsing performance and is the only PDA thin client that effectively supports crucial browser helper applications such as video playback.

While many application service providers have proposed using thin-client computing to deliver computational services over the Internet, little work has been done to evaluate the effectiveness of thin-client computing in a wide-area network. To assess the potential of thin-client computing in the context of future commodity high-bandwidth Internet access, we have used a novel, noninvasive slow-motion benchmarking technique to evaluate the performance of several popular thin-client computing platforms in delivering computational services cross-country over Internet2. Our results show that using thin-client computing in a wide-area network environment can deliver acceptable performance over Internet2, even when client and server are located thousands of miles apart on opposite ends of the country. However, performance varies widely among thin-client platforms and not all platforms are suitable for this environment. While many thin-client systems are touted as being bandwidth efficient, we show that network latency is often the key factor in limiting wide-area thin-client performance. Furthermore, we show that the same techniques used to improve bandwidth efficiency often result in worse overall performance in wide-area networks. We characterize and analyze the different design choices in the various thin-client platforms and explain which of these choices should be selected for supporting wide-area computing services.

We present Group Round-Robin (GRR) scheduling, a hybrid fair packet scheduling framework based on a grouping strategy that narrows down the traditional trade-off between fairness and computational complexity. GRR combines its grouping strategy with a specialized round-robin scheduling algorithm that utilizes the properties of GRR groups to schedule flows within groups in a manner that provides O(1) bounds on fairness with only O(1) time complexity. Under the practical assumption that GRR employs a small constant number of groups, we apply GRR to popular fair queuing scheduling algorithms and show how GRR can be used to achieve constant bounds on fairness and time complexity for these algorithms. We also present and prove new results on the fairness bounds for several of these fair queuing algorithms using a consistent fairness measure. We analyze the behavior of GRR and present experimental results that demonstrate how GRR can be combined with existing scheduling algorithms to provide much lower scheduling overhead and more than an order of magnitude better scheduling accuracy in practice than scheduling algorithms without GRR.

We have created ZapC, a novel system for transparent coordinated checkpoint-restart of distributed network applications on commodity clusters. ZapC provides a thin visualization layer on top of the operating system that decouples a distributed application from dependencies on the cluster nodes on which it is executing. This decoupling enables ZapC to checkpoint an entire distributed application across all nodes in a coordinated manner such that it can he restarted from the checkpoint on a different set of cluster nodes at a later time. ZapC checkpoint-restart operations execute in parallel across different cluster nodes, providing faster checkpoint-restart performance. ZapC uniquely supports network state in a transport protocol independent manner, including correctly saving and restoring socket and protocol state for both TCP and UDP connections. We have implemented a ZapC Linux prototype and demonstrate that it provides low visualization overhead and fast checkpoint-restart times for distributed network applications without any application, library, kernel, or network protocol modifications

Operating system courses teach students much more when they provide hands-on kernel-level project experience with a real operating system. However, enabling a large class of students to do kernel development can be difficult. To address this problem, we created a virtual kernel development environment in which operating systems can be developed, debugged, and rebooted in a shared computer facility without affecting other users. Using virtual machines and remote display technology, our virtual kernel development laboratory enables even distance learning students at remote locations to participate in kernel development projects with on-campus students. We have successfully deployed and used our virtual kernel development environment together with the open-source Linux kernel to provide kernel-level project experiences for over nine hundred students in the introductory operating system course at Columbia University.

Rapid improvements in network bandwidth, cost, and ubiquity combined with the security hazards and high total cost of ownership of personal computers have created a growing market for thin-client computing. We introduce THINC, a virtual display architecture for high-performance thin-client computing in both LAN and WAN environments. THINC virtualizes the display at the device driver interface to transparently intercept application display commands and translate them into a few simple low-level commands that can be easily supported by widely used client hardware. THINC's translation mechanism efficiently leverages display semantic information through novel optimizations such as offscreen drawing awareness, native video support, and server-side screen scaling. This is integrated with an update delivery architecture that uses shortest command first scheduling and non-blocking operation. THINC leverages existing display system functionality and works seamlessly with unmodified applications, window systems, and operating systems.We have implemented THINC in an X/Linux environment and compared its performance against widely used commercial approaches, including Citrix MetaFrame, Microsoft RDP, GoToMyPC, X, NX, VNC, and Sun Ray. Our experimental results on web and audio/video applications demonstrate that THINC can provide up to 4.8 times faster web browsing performance and two orders of magnitude better audio/video performance. THINC is the only thin client capable of transparently playing full-screen video and audio at full frame rate in both LAN and WAN environments. Our results also show for the first time that thin clients can even provide good performance using remote clients located in other countries around the world.

We present WebPod, a portable system that enables mobile users to use the same persistent, personalized web browsing session on any Internet-enabled device. No matter what computer is being used, WebPod provides a consistent browsing session, maintaining all of a user's plugins, bookmarks, browser web content, open browser windows, and browser configuration options and preferences. This is achieved by leveraging rapid improvements in capacity, cost, and size of portable storage devices. WebPod provides a virtualization and checkpoint/restart mechanism that decouples the browsing environment from the host, enabling web browsing sessions to be suspended to portable storage, carried around, and resumed from the storage device on another computer. WebPod virtualization also isolates web browsing sessions from the host, protecting the browsing privacy of the user and preventing malicious web content from damaging the host. We have implemented a Linux WebPod prototype and demonstrate its ability to quickly suspend and resume web browsing sessions, enabling a seamless web browsing experience for mobile users as they move among computers.

We present MobiDesk, a mobile virtual desktop computing hosting infrastructure that leverages continued improvements in network speed, cost, and ubiquity to address the complexity, cost, and mobility limitations of today's personal computing infrastructure. MobiDesk transparently virtualizes a user's computing session by abstracting underlying system resources in three key areas: display, operating system, and network. It provides a thin virtualization layer that decouples a user's computing session from any particular end-user device, and moves all application logic to hosting providers. The virtualization layer decouples a user's computing session from the underlying operating system and server instance, enabling high-availability service by transparently migrating sessions from one server to another during server maintenance or upgrades. We have implemented a prototype in Linux that works with existing unmodified applications and operating system kernels. Our experimental results demonstrate that MobiDesk has very low virtualization overhead, can provide a full featured desktop experience including full-motion video support, and is able to migrate users' sessions efficiently and reliably for high-availability, while maintaining existing network connections.

Web applications are becoming increasingly popular for mobile wireless PDAs. However, web browsing on these systems can be quite slow. An alternative approach is handheld thin-client computing, in which the web browser and associated application logic run on a server, which then sends simple screen updates to thePDA for display. To assess the viability of this thin-client approach, we compare the web browsing performance of thin clients against fat clients that run the web browser locally on a PDA. Our results show that thin clients can provide better web browsing performance compared to fat clients, both in terms of speed and ability to correctly display web content. Surprisingly, thin clients are faster even when having to send more data over the network. We characterize and analyze different design choices in various thin-client systems and explain why these approaches can yield superior web browsing performance on mobile wireless PDAs.

As businesses continue to grow their World Wide Web presence, it is becoming increasingly vital for them to have quantitative measures of the mean client perceived response times of their web services. We present Certes (CliEnt Response Time Estimated by the Server), an online server-based mechanism that allows web servers to estimate mean client perceived response time, as if measured at the client. Certes is based on a model of TCP that quantifies the effect that connection drops have on mean client perceived response time by using three simple server-side measurements: connection drop rate, connection accept rate and connection completion rate. The mechanism does not require modifications to HTTP servers or web pages, does not rely on probing or third party sampling, and does not require client-side modifications or scripting. Certes can be used to estimate response times for any web content, not just HTML. We have implemented Certes and compared its response time estimates with those obtained with detailed client instrumentation. Our results demonstrate that Certes provides accurate server-based estimates of mean client response times in HTTP 1.0/1.1 environments, even with rapidly changing workloads. Certes runs online in constant time with very low overhead. It can be used at websites and server farms to verify compliance with service level objectives.

Web applications are becoming increasingly popular for mobile wireless systems. However, wireless networks can have high packet loss rates, which can degrade web browsing performance on wireless systems. An alternative approach is wireless thin-client computing, in which the web browser runs on a remote thin server with a more reliable wired connection to the Internet. A mobile client then maintains a connection to the thin server to receive display updates over the lossy wireless network. To assess the viability of this thin-client approach, we compare the web browsing performance of thin clients against fat clients that run the web browser locally in lossy wireless networks. Our results show that thin clients can operate quite effectively over lossy networks. Compared to fat clients running web browsers locally, our results show surprisingly that thin clients can be faster and more resilient on web applications over lossy wireless LANs despite having to send more data over the network. We characterize and analyze different design choices in various thin-client systems and explain why these approaches can yield superior web browsing performance in lossy wireless networks.

Real-time applications such as multimedia audio and video are increasingly populating the workstation desktop. To support the execution of these applications in conjunction with traditional non-real-time applications, we have created SMART, a Scheduler for Multimedia And Real-Time applications. SMART supports applications with time constraints, and provides dynamic feedback to applications to allow them to adapt to the current load. In addition, the support for real-time applications is integrated with the support for conventional computations. This allows the user to prioritize across real-time and conventional computations, and dictate how the processor is to be shared among applications of the same priority. As the system load changes, SMART adjusts the allocation of resources dynamically and seamlessly. It can dynamically shed real-time computations and regulate the execution rates of real-time tasks when the system is overloaded, while providing better value in underloaded conditions than previously proposed schemes.We have implemented SMART in the Solaris UNIX operating system and measured its performance against other schedulers commonly used in research and practice in executing real-time, interactive, and batch applications. Our experimental results demonstrate SMART's superior performance over fair queueing and UNIX SVR4 schedulers in supporting multimedia applications.

Modern thin-client systems are designed to provide the same graphical interfaces and applications available on traditional desktop computers while centralizing administration and allowing more efficient use of computing resources. Despite the rapidly increasing popularity of these client-server systems, there are few reliable analyses of their performance. Industry standard benchmark techniques commonly used for measuring desktop system performance are ill-suited for measuring the performance of thin-client systems because these benchmarks only measure application performance on the server, not the actual user-perceived performance on the client. To address this problem, we have developed slow-motion benchmarking, a new measurement technique for evaluating thin-client systems. In slow-motion benchmarking, performance is measured by capturing network packet traces between a thin client and its respective server during the execution of a slow-motion version of a conventional benchmark application. These results can then be used either independently or in conjunction with conventional benchmark results to yield an accurate and objective measure of the performance of thin-client systems. We have demonstrated the effectiveness of slow-motion benchmarking by using this technique to measure the performance of several popular thin-client systems in various network environments on Web and multimedia workloads. Our results show that slow-motion benchmarking solves the problems with using conventional benchmarks on thin-client systems and is an accurate tool for analyzing the performance of these systems.

Summary form only given. The growing total cost of ownership has resulted in a shift away from the distributed model of desktop computing toward a more centralized server-based computing (SBC) model. In SBC, all application logic is executed on the server while clients simply process the resulting screen updates sent from the server. To provide good performance, SBC systems employ various techniques to encode the screen updates to minimize the bandwidth and processing requirements of sending the screen updates. However, existing SBC encoding techniques are not able to effectively support multimedia applications. To address this problem, we have developed a family of linear interpolation algorithms for encoding SBC screen updates. We first present an overview of an optimal linear interpolation (OLI) algorithm. Given a rectangular region of pixels to be encoded, OLI represents the region as a one-dimensional function, mapping from the cardinal number of each pixel to the color value of the pixel. To reduce encoding complexity, we developed two linear interpolation algorithms with linear encoding and decoding computational complexity. The algorithms are near optimal linear interpolation (NOLI) and 2-D lossless linear interpolation (2DLI). We have implemented our linear interpolation algorithms and compared their performance with other approaches on discrete-toned and smoothed-toned images.

Due to its reduced administrative costs and better resource utilization, server-based computing (SBC) is becoming a popular approach for delivering computational services across a network. In SBC, all application processing is done on servers while only screen updates are sent to clients. While many SBC encoding techniques have been explored for transmitting screen updates efficiently, existing approaches do not effectively support multimedia applications. To address this problem, we propose optimal linear interpolation (OLI), a new pixel-based SBC screen update coding algorithm. With OLI, the server selects and transmits only a small sample of pixels to represent a screen update. The client recovers the complete screen update from these samples using piecewise linear interpolation to achieve the best visual quality. OLI can be used to provide lossless or lossy compression for an adaptive trade-off between network bandwidth and processing time requirements. We further propose and evaluate 2D lossless linear interpolation (2DLI), which is based on OLI but additionally provides lower encoding complexity for lossless compression. Our experimental results show that when compared with other compression methods, 2DLI provides good data compression ratio with modest computational overhead, for both servers and clients.

While many application service providers have proposed using thin-client computing to deliver computational services over the Internet, little work has been done to evaluate the effectiveness of thin-client computing in a wide-area network. To assess the potential of thin-client computing in the context of future commodity high-bandwidth Internet access, we have used a novel, non-invasive slow-motion benchmarking technique to evaluate the performance of several popular thin-client computing platforms in delivering computational services cross-country over Internet2. Our results show that using thin-client computing in a wide-area network environment can deliver acceptable performance over Internet2, even when client and server are located thousands of miles apart on opposite ends of the country. However, performance varies widely among thin-client platforms and not all platforms are suitable for this environment. While many thin-client systems are touted as being bandwidth efficient, we show that network latency is often the key factor in limiting wide-area thin-client performance. Furthermore, we show that the same techniques used to improve bandwidth efficiency often result in worse overall performance in wide-area networks. We characterize and analyze the different design choices in the various thin-client platforms and explain which of these choices should be selected for supporting wide-area computing services.

As businesses continue to grow their World Wide Web presence, it is becoming increasingly vital for them to have quantitative measures of the client perceived response times of their web services. We present Certes (CliEnt Response Time Estimated by the Server), an online server-based mechanism for web servers to measure client perceived response time, as if measured at the client. Certes is based on a model of TCP that quantifies the effect that connection drops have on perceived client response time, by using three simple server-side measurements: connection drop rate, connection accept rate and connection completion rate. The mechanism does not require modifications to http servers or web pages, does not rely on probing or third party sampling, and does not require client-side modifications or scripting. Certes can be used to measure response times for any web content, not just HTML. We have implemented Certes and compared its response time measurements with those obtained with detailed client instrumentation. Our results demonstrate that Certes provides accurate server-based measurements of client response times in HTTP 1.0/1.1 [14] environments, even with rapidly changing workloads. Certes runs online in constant time with very low overhead. It can be used at web sites and server farms to verify compliance with service level objectives.

Article Free Access Share on The design, implementation and evaluation of SMART: a scheduler for multimedia applications Authors: Jason Nieh Computer Systems Laboratory, Stanford University and Sun Microsystems Laboratories Computer Systems Laboratory, Stanford University and Sun Microsystems LaboratoriesView Profile , Monica S. Lam Computer Systems Laboratory, Stanford University Computer Systems Laboratory, Stanford UniversityView Profile Authors Info & Claims SOSP '97: Proceedings of the sixteenth ACM symposium on Operating systems principlesOctober 1997 Pages 184–197https://doi.org/10.1145/268998.266677Published:01 October 1997Publication History 155citation1,144DownloadsMetricsTotal Citations155Total Downloads1,144Last 12 Months59Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF