Publications from 2005

As computers become more ubiquitous in large corporate, government, and academic organizations, the cost of owning and maintaining them is becoming unmanageable. Computers are increasingly networked, which only complicates the management problem given the myriad of viruses and other attacks commonplace in today’s networks. Security problems can wreak havoc on an organization’s comput- ing infrastructure. To prevent this, software vendors frequently release patches that can be applied to address security and mainte- nance issues that have been discovered. This becomes a management nightmare for administrators who take care of large sets of machines.

Patching, upgrading, and maintaining operating system software is a growing management complexity problem that can result in unacceptable system downtime. We introduce AutoPod, a system that enables unscheduled operating system updates while preserving application service availability. AutoPod provides a group of processes and associated users with an isolated machine- independent virtualized environment that is decoupled from the underlying operating system instance. This virtualized environment is integrated with a novel checkpoint-restart mechanism which allows processes to be suspended, resumed, and migrated across operating system kernel versions with different security and maintenance patches. AutoPod incorporates a system status service to determine when operating system patches need to be applied to the current host, then automatically migrates application services to another host to preserve their availability while the current host is updated and rebooted. We have implemented AutoPod on Linux without requiring any application or operating system kernel changes. Our measurements on real world desktop and server applications demonstrate that AutoPod imposes little overhead and provides sub-second suspend and resume times that can be an order of magnitude faster than starting applications after a system reboot. AutoPod enables systems to autonomically stay updated with relevant maintenance and security patches, while ensuring no loss of data and minimizing service disruption.

Software that covertly monitors user actions, also known as spyware, has become a first-level security threat due to its ubiquity and the difficulty of detecting and removing it. Such software may be inadvertently installed by a user that is casually browsing the web, or may be purposely installed by an attacker or even the owner of a system. This is particularly problematic in the case of utility computing, early manifestations of which are Internet cafes and thin-client computing. Traditional trusted computing approaches offer a partial solution to this by significantly increasing the size of the trusted computing base (TCB) to include the operating system and other software. We examine the problem of protecting a user accessing specific services in such an environment. We focus on secure video broadcasts and remote desktop access when using any convenient, and often untrusted, terminal as two example appli- cations. We posit that, at least for such applications, the TCB can be confined to a suitably modified graphics processing unit (GPU). Specifically, to prevent spy- ware on untrusted clients from accessing the user’s data, we restrict the boundary of trust to the client’s GPU by moving image decryption into GPUs. This allows us to leverage existing capabilities as opposed to designing a new component from scratch. We discuss the applicability of GPU-based decryption in the two scenarios. We identify limitations due to current GPU capabilities and propose straightf

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 com- putational complexity. GRR combines its grouping strategy with a specialized round-robin scheduling algorithm that utilizes the prop- erties of GRR groups to schedule flows within groups in a man- ner 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.

Rapid improvements in network bandwidth, cost, and ubiq- uity 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 trans- parently intercept application display commands and trans- late 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 ar- chitecture 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 environ- ment and compared its performance against widely used commercial approaches, including Citrix MetaFrame, Mi- crosoft 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 bet- ter audio/video performance. THINC is the only thin client capable of transparently playing full-screen video and au- dio 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 have created ZapC, a novel system for transparent coordinated checkpoint-restart of distributed network ap- plications on commodity clusters. ZapC provides a thin virtualization layer on top of the operating system that de- couples a distributed application from dependencies on the cluster nodes on which it is executing. This decoupling en- ables ZapC to checkpoint an entire distributed application across all nodes in a coordinated manner such that it can be 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, provid- ing 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 virtualization overhead and fast checkpoint- restart times for distributed network applications without any application, library, kernel, or network protocol modi- fications.

The increasing popularity of online courses has highlighted the lack of collaborative tools for student groups. In addition, the intro- duction of lecture videos into the online curriculum has drawn attention to the disparity in the network resources used by students. We present an e-Learning architecture and adaptation model called AI² TV (Adaptive Internet Interactive Team Video), which allows virtual students, possi- bly some or all disadvantaged in network resources, to collaboratively view a video in synchrony. AI² TV upholds the invariant that each stu- dent will view semantically equivalent content at all times. Video player actions, like play, pause and stop, can be initiated by any student and their results are seen by all the other students. These features allow group members to review a lecture video in tandem, facilitating the learning process. Experimental trials show that AI² TV can successfully synchro- nize video for distributed students while, at the same time, optimizing the video quality, given fluctuating bandwidth, by adaptively adjusting the quality level for each student.

File systems, RAID systems, and applications that care about data consistency, among others, assure data integrity by carefully forcing valuable data to stable storage. Unfortunately, verifying that a system recovers from a crash to a valid state at any program counter is very difficult. Previous techniques for finding data integrity bugs have been heavyweight, requiring extensive effort for each OS and file system to be checked. We demonstrate a lightweight, flexible, easy-to-apply technique by developing a tool called eXplode and show how we used it to find 25 serious bugs in eight Linux file systems, Linux software RAID 5, Linux NFS, and three version control systems.

Patching, upgrading, and maintaining operating system software is a growing management complexity problem that can result in unacceptable system downtime. We introduce AutoPod, a system that enables unscheduled operating sys- tem updates while preserving application service availabil- ity. AutoPod provides a group of processes and associated users with an isolated machine-independent virtualized en- vironment that is decoupled from the underlying operating system instance. This virtualized environment is integrated with a novel checkpoint-restart mechanism which allows processes to be suspended, resumed, and migrated across operating system kernel versions with different security and maintenance patches. AutoPod incorporates a system status service to determine when operating system patches need to be applied to the current host, then automatically migrates application services to another host to preserve their avail- ability while the current host is updated and rebooted.