Fault tolerance is the key technology to achieve high availability for non-stop and long-lasting services, which is usually carried out by the virtualization technology in the era of cloud computing. However, most virtualization-based fault tolerance methods only focus on the resilience of a single server (Individual FT), which can cause great performance degradation for the services that have heavy communication among multiple nodes. One of the solutions is the Group Fault Tolerance (Group FT) technique, which synchronizes a group of VMs within single fault tolerance states to avoid the latency accumulation problem. In this paper, we present an efficient implementation of Group FT, as well as the methods to enhance the performance of Group FT's failover process. Experiments show that Group FT can reduce 88% system latency of the Individual FT when running the OLTP workload in SysBench. Similar results are also shown for a more complicated synthetic multi-tier architecture. Moreover, the performance of the failover process for Group FT is also optimized so that it is comparable to the performance of Individual FT.

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

PCI Express (PCIe) was originally designed as a local bus interconnect technology for connecting CPUs, GPUs and I/O devices inside a machine, and has since been enhanced to be a full-blown switched network that features point-to-point links, hop-by-hop flow control, end-to-end retransmission, etc. Recently, researchers have further extended PCIe into an intra-rack interconnect designed to connect multiple hosts within the same rack. To viably apply PCIe to such use cases, additional fail-over mechanisms are needed to ensure continued network operation in the presence of control plane and data plane failures. This paper presents the design, implementation and preliminary evaluation of a fault-tolerant PCIe-based rack area network architecture called Ladon, which incorporates a fail-over mechanism that takes effective advantage of PCIe architectural features to significantly reduce the service disruption time due to a control plane failure of a PCIe switch. Empirical tests on an operational Ladon prototype show that the proposed mechanism ensures that a PCIe root complex failure has zero impact on the data plane and incurs only a modest disruption time (less than 40 sec) for the control plane services.

Summary form only given. The enormous successes of deep learning in many domains such as video, audio, speech, text, sequence, etc. has swept the academia and industry alike, to the extent that many are touting deep learning training as an alternative form of programming future applications. Amid this excitement lies a more sombre question: if training for deep learning models is compared to software coding, what is the integrated development environment (IDE) for deep learning training? Specifically, what are the debugging and analysis tools required for manually refining and evolving a deep learning model towards its final form? In this presentation, I will survey related work in this area and outline the visualization requirements of a deep learning IDE that we are currently working on.

This paper presents a self-sustainable landslide surveillance system that detects hazardous water content level in soils and provides real-time landslide warnings to residents, without requiring wired electricity transmission. A self-powered soil water content sensor was applied as the trigger of alert event. It solves the energy supply problem by an environmental interrupt mechanism, which wakes up the sensor and communication circuits in a sensing node only when the water content in monitored soils exceeds a certain threshold, and thus completely eliminates the need for an ALS node to periodically wake up, sense and communicate. By tightly integrating energy harvesting, environment sensing and circuit wake-up, it may well be the most energy-efficient landslide surveillance system designed to monitor water content in soils in the world.

Virtualization plays a pivotal role in the success of cloud computing service models and is applied extensively in modern public and private data centers. However, its adoption on end user devices such as laptop/desktop computers and cell phones is relatively scarce, mainly because convincing use cases for client device virtualization have proven elusive so far. As smartphones emerge as the linchpin of everyday computing and communication for regular people and application download becomes a fact of life, the Bring Your Own Cloud (BYOD) problem, in which corporate employees connect their own smartphones to the corporate networks for office work, has put most enterprises in an unenvious position of making a difficult choice between corporate security and employee productivity. One effective solution to the BYOD problem is smartphone virtualization, which provides multiple virtual smartphones on a physical smartphone, and enables a user to use a highly secure but not so flexible virtual smartphone in the work environment and a less secure but more flexible virtual smartphone when outside the work environment. This paper describes the design and implementation of a comprehensive smartphone virtualization system called Brahma, which consists of a virtualized smartphone element and a virtual mobility infrastructure element, and presents the detailed evaluation results of the first Brahma prototype on a commercial smartphone.

Minimizing the total amount of physical memory consumption of the virtual machines (VM) concurrently running on a physical server is a key to improving a hyper visor's consolidation ratio, defined as the maximum number of VMs that can run on a physical server without performance degradation. This paper describes the design, implementation and evaluation of a memory resource manager called Gatun that constantly measures the working set size of each running VM, and exploits this information to make the best of the available physical memory on a physical server. The per-VM working set size information allows Gatun to reclaim only unused physical memory from each running VM without negatively affecting its performance, and to compress the right subset of memory pages for each VM to reduce its memory pressure to the maximal extent possible. Compared with a state-of-the-art commercial hyper visor, Gatun is able to make noticeably more efficient utilization of a virtualized server's physical memory because of its ability to capture and leverage the per-VM working set size information.

The effectiveness of a modern hyper visor on a virtualized server is measured by its consolidation ratio, which is defined as the maximum number of virtual machines (VM) that can run on a physical server without performance degradation. A key factor in determining a hyper visor's consolidation ratio is its effectiveness in fairly distributing a virtualized server's physical memory resource among the VMs running on it when the total memory demand of these VMs exceeds the server's physical memory size. This paper describes the design, implementation and evaluation of a memory pressure balancer called Gatto that constantly measures the working set size of each VM running on a virtualized server, and exploits this information to distribute the server's physical memory resource so as to balance the memory pressures experienced by these VMs. Gatto's memory pressure balancing mechanism could be generalized and applied to achieve memory quality of service (QoS) guarantee onmultitenant virtualized servers.

As the performance overhead associated with CPU and memory virtualization becomes largely negligible, research efforts are directed toward reducing the I/O virtualization overhead, which mainly comes from two sources: DMA set-up and payload copy, and interrupt delivery. The advent of SRIOV and MRIOV effectively reduces the DMA-related virtualization overhead to a minimum. Therefore, the last battleground for minimizing virtualization overhead is how to directly deliver every interrupt to its target VM without involving the hypervisor.

Disaggregation of hardware resources that are traditionally embedded within individual servers into separate resource pools is an emerging architectural trend in hyperscale data center design, as exemplified by Facebook's disaggregated rack architecture. This paper presents the design, implementation and evaluation of a PCIe-based rack area network system called Marlin, which is designed to support the communications needs of disaggregated racks. By virtue of being based on PCIe, Marlin presents a memory-based addressing model for both I/O device sharing among multiple hosts and inter-host communications, and as a result offers hardware- based remote direct memory access (HRDMA) as a first-class communications primitive between servers within a rack. Marlin supports socket-based communications for legacy network applications and cross-machine zero memory copying for applications designed specifically to take full advantage of Marlin. Empirical measurements on a fully operational Marlin prototype based on 4-lane Gen3 PCIe technology show that the one-way kernel-to-kernel latency is 8.5μsec and the end-to- end sustainable TCP throughput is 19.6 Gbps.

Wearable devices eliminate the need of physically taking out a mobile device before operating on it and are emerging as the next wave of mobile systems. Head-mounted display (HMD) is a key building block of wearable devices, and offers users immediate access to relevant information in a glance. However, most existing user input mechanisms accompanying HMDs are designed for interactive information exploration rather than for extended text entry. This paper describes the design, implementation and evaluation of a text input system for HMDs called Air Typing, which requires only a standard camera and is shown to be comparable in effectiveness to single-hand text input on tablet computers in a lab setting. Air Typing features a novel two-level virtual keyword layout, which substantially improves the typing speed by cutting down unnecessary hand movements during typing and greatly simplifies the associated image processing task by doing away with fine-grained matching between fingertips and keys. The current Air Typing prototype incorporates an OpenCV-based virtual key press detection algorithm that runs on the featured two-level virtual keyboard. In our tests, an experienced user's typing speeds of one-hand text input and of two-hand text input under Air Typing are 13 and 15 words per minute (WPM), respectively.

Because of the explosive growth of flash disk usage in portable computers and mobile devices, building data center storage systems using these commodity flash disks has become a compelling option. A vanilla approach to integrating multiple flash disks into a storage system is to put them under the control of a RAID controller. However, this approach incurs longer write latency than necessary and leads to reduction in the overall system lifetime. This paper describes a log-structured flash array architecture called SOFA (Software Orchestrated Flash Array), in which the flash translation layer (FTL) sits on top of rather than below disk array management logic, and is judiciously partitioned between a central control server and the on-disk controllers. By directly managing the resource usage in individual flash disks, SOFA is able to avoid the load and wear imbalance problems associated with existing flash disk array systems. Empirical measurements of an industrial-strength SOFA prototype show it could execute more than 7,000 random 8KB writes per second per SATA-2 flash disks, and sustains the same per-disk random write performance when the system holds up to 24 flash disks.

A distinguishing characteristic of a software-defined network is separation of the network's control plane from its data plane. Especially when the granularity of control is an individual network flow, such separation entails frequent communications between these two planes. This communication pattern demands the same level of resilience from the control plane as that from the data plane, and thus calls into question the conventional out-of-band control network design as used in many existing SDN systems. Peregrine is an Ethernet-based software-defined network that was originally designed as the internal network of a container computer, and unifies storage access, inter-server communication, and network control into a single network comprising only commodity off-the-shelf Ethernet switches. To fully utilize all available physical network links, Peregrine treats the physical network as an explicitly routed mesh and equalizes the loads of its links using a global load-balancing routing algorithm running on a centralized controller. The in-band control architecture of Peregrine leads to two issues: (1) how to evolve a Peregrine network from its initial bootstrapping mode to the explicit routing mode at run time, and (2) how to support fast fail-over for physical failures that break both the control and data plane. This paper describes how Peregrine addresses these two issues, and shows its effectiveness with performance measurements collected from a fully operational test-bed.

Virtual Machine Introspection (VMI) provides the ability to monitor virtual machines (VM) in an agentless fashion by gathering VM execution states from the hypervisor and analyzing those states to extract information about a running operating system (OS) without installing an agent inside the VM. VMI's main challenge lies in the difficulty in converting low-level byte string values into high-level semantic states of the monitored VM's OS. In this work, we tackle this challenge by developing a real-time kernel data structure monitoring (RTKDSM) system that leverages the rich OS analysis capabilities of Volatility, an open source computer forensics framework, to significantly simplify and automate analysis of VM execution states. The RTKDSM system is designed as an extensible software framework that is meant to be extended to perform application-specific VM state analysis. In addition, the RTKDSM system is able to perform real-time monitoring of any changes made to the extracted OS states of guest VMs. This real-time monitoring capability is especially important for VMI-based security applications. To minimize the performance overhead associated with real-time kernel data structure monitoring, the RTKDSM system has incorporated several optimizations whose effectiveness is reported in this paper.

OS-level virtualization generates a minimal start-up and run-time overhead on the host OS and thus suits applications that require both good isolation and high efficiency. However, multiple-member applications required for forming a system may need to occasionally communicate across this isolation barrier to cooperate with each other while they are separated in different VMs to isolate intrusion or fault. Such application scenarios are often critical to enterprise-class servers, HPC clusters and intrusion/fault-tolerant systems, etc. We make the first effort to support the inter-application interactions in an OS-level virtualization system without causing a significant compromise on VM isolation. We identify all interactive operations that impact inter-application interactions, including inter-process communications, application invocations, resource name transfers, and application dependencies. We propose Shuttle, a novel approach for facilitating inter-application interactions within and across OS-level virtual machines. Our results demonstrate that Shuttle can correctly address all necessary inter-application interactions while providing good isolation capability for all sample applications on different versions of Windows OS.

Cloud computing ushers in an era of consolidated information technology infrastructure that is elastic, available and scalable. Virtualization is a critical building block in this evolution and enables centralized, consistent, and policy-driven administration of the underlying computing resources and their protection. This paper presents a cloud-based application whitelisting system called CLAW, which leverages this centralized management flexibility to guarantee that only application binaries in a pre-approved set are allowed to run in each virtual machine under its management. In addition, by applying virtual machine introspection technology, CLAW performs this security policy enforcement without installing any agents inside the managed VMs. We describe the key techniques in the design and implementation of CLAW and compare them with previous hypervisor-based application whitelisting systems. Empirical measurements on a Xen-based CLAW prototype for Windows-based virtual machines show that the run-time performance overhead of out-of-VM application whitelisting is under 10%.

Because of its enormous popularity in embedded systems and mobile devices, ARM CPU is arguably the most used CPU in the world. The resulting economies of scale benefit entices system architects to ponder the feasibility of building lower-cost and lower-power-consumption servers using ARM CPU. In modern data centers, especially those built to host cloud applications, virtualization is a must. So how to support virtualization on ARM CPUs becomes a major issue for constructing ARM-based servers. Although the latest versions of ARM architecture (Cortex-A15 and beyond) provide hardware support for virtualization, the majority of ARM-based SOCs (system-on-chip) currently available on the market do not. This paper presents results of an evaluation study of a fully operational hypervisor that successfully runs multiple VMs on an ARM Cortex A9-based server, which is architecturally non-virtualizable, and supports VM migration. This hypervisor features several optimizations that significantly reduce the performance overhead of virtualization, including physical memory remapping, and batching of sensitive/privileged instruction emulation.

Nowadays, digital surveillance systems are ubiquitously installed and continuously generate huge amount of video data. Very often, human inspection of the recorded videois still required for threat detection. Even though automated techniques exist to facilitate the detection of potential security problems, it remains a highly computation demanding task to process these data. The emergence of cloud environments has made feasible to deploy intelligent video surveillance technologies as services through Internet to enhance public security. In this paper, we present a novel system aiming at bringing together automatic license plate recognition engines and cloud computing technology in order to realize massive data analysis and enable the detection and tracking of a target vehicle in a city with a given license plate number. It realizes a fully integrated system with a surveillance network of city scale, automatic large scale data retrieval and analysis, combination with pattern recognition technology to achieve contextual information analysis. Performance evaluation and some results of applying the proposed system to real-world data are demonstrated and the experiences we gained when implementing it are also discussed.

Buggy device drivers are a major threat to the reliability of their host operating system. There have been myriad attempts to protect the kernel, but most of them either required driver modifications or incur substantial performance overhead. This paper describes an isolated device driver execution system called SIDE (Streamlined Isolated Driver Execution), which focuses specifically on unmodified device drivers and strives to avoid changing the existing kernel code as much as possible. SIDE exploits virtual memory hardware to set up a device driver execution environment that is compatible with existing device drivers and yet is fully isolated from the kernel. SIDE is able to run an unmodified device driver for a Gigabit Ethernet NIC and the latency and throughput penalty is kept under 1% when augmented with a set of performance optimizations designed to reduce the number of protection domain crossings between an isolated device driver and the kernel.

Virtualization allows flexible mappings between physical resources and virtual entities, and improves allocation efficiency and agility. Unfortunately, most existing virtualization technologies are limited to resources in a single host. This paper presents the design, implementation and evaluation of a multi-host I/O device virtualization system called Ladon, which enables I/O devices to be shared among virtual machines running on multiple hosts in a secure and efficient way. Specifically, Ladon uses a PCIe network to connect multiple servers with PCIe devices and allows VMs running on these servers to directly interact with these PCIe devices without interfering with one another. Through an evaluation of a fully operational Ladon prototype, we show that there is no throughput and latency penalty of the multi-host I/O virtualization enabled by Ladon compared to those of the existing single-host I/O virtualization technology.

Synchronously logging updates to persistent storage first and then asynchronously committing these updates to their rightful storage locations is a well-known and heavily used technique to improve the sustained throughput of write-intensive disk-based data processing systems, whose latency and throughput accordingly are largely determined by the latency and throughput of the underlying logging mechanism. The conventional wisdom is that logging operations are relatively straightforward to optimize because the associated disk access pattern is largely sequential. However, it turns out that to achieve both high throughput and low latency for fine-grained logging operations, whose payload size is smaller than a disk sector, is extremely challenging. This paper describes the experiences and lessons we have gained from building a disk logging system that can successfully deliver over 1.2 million 256-byte logging operations per second, with the average logging latency below 1 msec.

Very large block-level data backup systems need scalable data deduplication and garbage collection techniques to make efficient use of the storage space and to minimize the performance overhead of doing so. Although the deduplication and garbage collection logic is conceptually straight-forward, their implementations pose a significant technical challenge because only a small portion of their associated data structures could fit into memory. In this paper, we describe the design, implementation and evaluation of a data deduplication and garbage collection engine called Sungem that is designed to remove duplicate blocks in incremental data backup streams. Sungem features three novel techniques to maximize the deduplication throughput without compromising the deduplication ratio. First, Sungem puts related fingerprint sequences, rather than fingerprints from the same backup stream, into the same container in order to increase the fingerprint prefetching efficiency. Second, to make the most of the memory space reserved for storing fingerprints, Sungem varies the sampling rates for fingerprint sequences based on their stability. Third, Sungem combines reference count and expiration time in a unique way to arrive at the first known incremental garbage collection algorithm whose bookkeeping overhead is proportional to the size of a disk volume's incremental backup snapshot rather than its full backup snapshot. We evaluated the Sungem prototype using a real-world data backup trace, and showed that the average throughput of Sungem is more than 200,000 fingerprint lookups per second on a standard X86 server, including the garbage collection cost.

Memory virtualization abstracts a physical machine's memory resource and presents to the virtual machines running on it a piece of physical memory that could be shared, compressed and moved. To optimize the memory resource utilization by fully leveraging the flexibility afforded by memory virtualization, it is essential that the hypervisor have some sense of how the guest VMs use their allocated physical memory. One way to do this is virtual machine introspection (VMI), which interprets byte values in a guest memory space into semantically meaningful data structures. However, identifying a guest VM's memory usage information such as free memory pool is non-trivial. This paper describes a bootstrapping VM introspection technique that could accurately extract free memory pool information from multiple versions of Windows and Linux without kernel version-specific hard-coding, how to apply this technique to improve the efficiency of memory de-duplication and memory state migration, and the resulting improvement in memory de-duplication speed, gain in additional memory pages de-duplicated, and reduction in traffic loads associated with memory state migration.

A virtual machine(VM) can be simply created upon use and disposed upon the completion of the tasks or the detection of error. The disadvantage of this approach is that if there is no malicious activity, the user has to redo all of the work in her actual workspace since there is no easy way to commit (i.e., merge) only the benign updates within the VM back to the host environment. In this work, we develop a VM commitment system called Secom to automatically eliminate malicious state changes when merging the contents of an OS-level VM to the host. Secom consists of three steps: grouping state changes into clusters, distinguishing between benign and malicious clusters, and committing benign clusters. Secom has three novel features. First, instead of relying on a huge volume of log data, it leverages OS-level information flow and malware behavior information to recognize malicious changes. As a result, the approach imposes a smaller performance overhead. Second, different from existing intrusion detection and recovery systems that detect compromised OS objects one by one, Secom classifies objects into clusters and then identifies malicious objects on a cluster by cluster basis. Third, to reduce the false-positive rate when identifying malicious clusters, it simultaneously considers two malware behaviors that are of different types and the origin of the processes that exhibit these behaviors, rather than considers a single behavior alone as done by existing malware detection methods. We have successfully implemented Secom on the feather-weight virtual machine system, a Windows-based OS-level virtualization system. Experiments show that the prototype can effectively eliminate malicious state changes while committing a VM with small performance degradation. Moreover, compared with the commercial antimalware tools, the Secom prototype has a smaller number of false negatives and thus can more thoroughly clean up malware side effects. In addition, the number of false positives of the Secom prototype is also lower than that achieved by the online behavior-based approach of the commercial tools.

ITRI container computer is a modular computer designed to be a building block for constructing cloud-scale data centers. Rather than using a traditional data center network architecture, which is typically based on a combination of Layer 2 switches and Layer 3 routers, ITRI containercomputer's internal interconnection fabric, called Peregrine, is specially architected to meet the scalability, fast fail-over and multi-tenancy requirements of these data centers. Peregrine is an all-Layer 2 network that is designed to support up to one million Layer 2 end points, provide quick recovery from any single network link/device failure, and incorporate dynamic load-balancing routing to make the best of all physical network links. Finally, the Peregrine architecture is implementable using only off-the-shelf commodity Ethernet switches. This paper describes the design and implementation of a fully operational Peregrine prototype, which is built on a folded Clos physical network topology, and the results and analysis of a performance evaluation study based on measurements taken on this prototype.

Traditional storage systems provide a simple read/write interface, which is inadequate for low-locality update-intensive workloads because it limits the disk scheduling flexibility and results in inefficient use of buffer memory and raw disk bandwidth. This paper describes an update-aware disk access interface that allows applications to explicitly specify disk update requests and associate with such requests call-back functions that will be invoked when the requested disk blocks are brought into memory. Because call-back functions offer a continuation mechanism after retrieval of requested blocks, storage systems supporting this interface are given more flexibility in scheduling pending disk update requests. In particular, this interface enables a simple but effective technique called Batching mOdifications with Sequential Commit (BOSC), which greatly improves the sustained throughput of a storage system under low-locality update-intensive workloads. In addition, together with a space-efficient low-latency disk logging technique, BOSC is able to deliver the same durability guarantee as synchronous disk updates. Empirical measurements show that the random update throughput of a BOSC-based B+ tree is more than an order of magnitude higher than that of the same B+ tree implementation on a traditional storage system.

As more and more virtual machines (VM) are packed into a physical machine, refactoring common kernel components shared by the virtual machines running on the same physical machine significantly reduces the overall resource consumption. A refactored kernel component typically runs on a special VM called a virtual appliance. Because of the semantics gap in Hardware Abstraction Layer (HAL)-based virtualization, a physical machine's virtual appliance requires the support of per-VM in-guest agents to perform VM-specific operations such as kernel data structure access and modification. To simplify deployment, these agents must be injected into guest virtual machines without requiring any manual installation. Moreover, it is essential to protect the integrity of in-guest agents at run time, especially when the underlying refactored kernel service is security-related. This paper describes the design, implementation and evaluation of a surreptitious kernel agent deployment and execution mechanism called SADE that requires zero installation effort and effectively hides the execution of agent code. To demonstrate the efficacy of SADE, we describe a signature-based memory scanning virtual appliance that uses SADE to inject its in-guest kernel agents without any support from the injected virtual machine, and show that both the start-up overhead and the run-time performance penalty of SADE are quite modest in practice.

Virtualization provides the possibility of whole machine migration and thus enables a new form of fault tolerance that is completely transparent to applications and operating systems. The most seamless virtualization-based fault tolerance configuration is an active/active master-slave configuration, in which the memory states of the master and slave virtual machine are periodically synchronized and the slave can immediately take over when the master dies without losing any on-going connections. The frequency of memory state synchronization has a direct impact on the performance overhead, the application response time, and the fail-over delay. This paper describes a speculative memory state synchronization technique that could effectively reduce the synchronization frequency without increasing the performance overhead, and presents a comprehensive performance study of these techniques under three realistic workloads, the TPC-E benchmark, the SPECsfs 2008 CIFS benchmark, and a Microsoft Exchange workload. We show that the proposed technique can effectively cut down the amount of memory state synchronization traffic by more than an order of magnitude.

This paper proposes efficient indexing and querying services on encrypted user documents stored in the cloud. We develop few sophisticated techniques to ensure that any network intruder or even the cloud service provider itself is oblivious to both user data content and the type of operations performed over the data. All data operations, including encryption and decryption of data are performed in the client environment, thereby guaranteeing complete data security. By providing, such a secure system to store and access data on the cloud, end users will be free of any security concerns and hence can easily migrate their data to the cloud. We have implemented an Encryption Domain Text Retrieval (EDTR) System that has a server positioned in the cloud to provide indexing, storage and querying services and a client tool on the end user system that processes the user documents. In order to enable the cloud server to work on encrypted data, the client tool orchestrates the user data into sets of keywords which are again encrypted. We further provide an unique measurement technique to identify unfaithful execution of user requested services by the cloud service provider. Our experiments demonstrate the practical applicability of such a sophisticated system. Though we logically explain the security implications and how the EDTR system overcomes typical cloud security issues, we do not focus on providing concrete, theoretical security proofs.

OS-level virtualization generates a minimal start-up and run-time overhead on the host OS and thus suits applications that require both good isolation and high efficiency. However, multiple-member applications required for forming a system may need to occasionally communicate across this isolation barrier to cooperate with each other while they are separated in different VMs to isolate intrusion or fault. Such application scenarios are often critical to enterprise-class servers, HPC clusters and intrusion/fault-tolerant systems, etc. We make the first effort to support the inter-application interactions in an OS-level virtualization system without causing a significant compromise on VM isolation. We identify all interactive operations that impact inter-application interactions, including inter-process communications, application invocations, resource name transfers and application dependencies. We propose Shuttle, a novel approach for facilitating inter-application interactions within and across OS-level virtual machines. Our results demonstrate that Shuttle can correctly address all necessary inter-application interactions while providing good isolation capability to all sample applications on different versions of Windows OS.

Enforcing a practical Mandatory Access Control (MAC) in a commercial operating system to tackle malware problem is a grand challenge but also a promising approach. The firmest barriers to apply MAC to defeat malware programs are the incompatible and unusable problems in existing MAC systems. To address these issues, we manually analyze 2,600 malware samples one by one and two types of MAC enforced operating systems, and then design a novel MAC enforcement approach, named Tracer, which incorporates intrusion detection and tracing in a commercial operating system. The approach conceptually consists of three actions: detecting, tracing, and restricting suspected intruders. One novelty is that it leverages light-weight intrusion detection and tracing techniques to automate security label configuration that is widely acknowledged as a tough issue when applying a MAC system in practice. The other is that, rather than restricting information flow as a traditional MAC does, it traces intruders and restricts only their critical malware behaviors, where intruders represent processes and executables that are potential agents of a remote attacker. Our prototyping and experiments on Windows show that Tracer can effectively defeat all malware samples tested via blocking malware behaviors while not causing a significant compatibility problem.

Credit and debit card payment processing systems are key elements in financial transactions. Negligence in securing these systems makes them vulnerable to hacking attacks, which may lead to significant monetary losses for both merchants and the financial organizations. To reduce this risk, mandatory security compliance regulations, such as the Payment Card Industry Data Security Standard (PCI DSS), were developed and adopted by the industry. A key pre-requisite of the PCI DSS compliance process is the ability to identify the components of the payment systems directly involved with the card data (i.e. process, transmit, or store). However, existing data flow tracking tools cannot fully automate the process of identifying system components that touch card data, because they either can not examine encrypted communications or they use an instrumentation-based approach and thus require a priori detailed knowledge of the payment card processing systems.

Enforcing a practical Mandatory Access Control (MAC) in a commercial operating system to tackle malware problem is a grand challenge but also a promising approach. The firmest barriers to apply MAC to defeat malware programs are the incompatible and unusable problems in existing MAC systems. To address these issues, we start our work by analyzing the technical details of 2,600 malware samples one by one and performing experiments over two types of MAC enforced operating systems. Based on the preliminary studies, we design a novel MAC model incorporating intrusion detection and tracing in a commercial operating system, named Tracer, in order to disable malware on hosts while offering good compatibility to existing software and good usability to common users who are not system experts. The model conceptually consists of three actions: detecting, tracing and restricting suspected intruders. One novelty is that it leverages light-weight intrusion detection and tracing techniques to automate security label configuration that is widely acknowledged as a tough issue when applying a MAC system in practice. The other is that, rather than restricting information flow as a traditional MAC does, it traces intruders and restricts only their critical malware behaviors, where intruders represent processes and executables that are potential agents of a remote attacker. Our prototyping and experiments on Windows show that Tracer can effectively defeat all malware samples tested via blocking malware behaviors while not causing a significant compatibility problem.

A powerful functionality enabled by modern virtualization technologies is the ability to move a virtual machine (VM) from one physical machine to another, which enables unprecedented flexibility for system fault tolerance and load balancing. However, no similar capability exists for physical machines. This paper describes the first known successful implementation of migrating a physical machine's state from one physical Linux machine to another. This physical machine state migration (PMSM) capability greatly decreases the amount of disruption due to scheduled shut-down for non-virtualized physical machines, and is more challenging than VM migration because it cannot rely on a separate piece of software to perform the state transfer, e.g., the hyper visor in the case of VM migration. The PMSM prototype described in this paper is adapted from Linux's hibernation facility. The current PMSM prototype can migrate a physical machine running the MySQL DBMS server under 7 seconds.

Memory de-duplication removes the memory state redundancy among virtual machines that run on the same physical machine by identifying common memory pages shared by these virtual machines and storing only one copy for each of common memory pages. A standard approach to identifying common memory pages is to hash the content of each memory page, and compare the resulting hash values. In a virtualized server, only the hyper visor is in a position to compute the hash value of every physical memory page on the server, but the memory de-duplication engine is best implemented outside the hyper visor for flexibility and simplicity reasons. A key design issue in the memory de-duplication engine is to minimize the performance impact of these hashing computations on the running VMs. To reduce this impact, memory page hashing should be performed with low overhead and when the CPU is idle. This paper describes why existing hyper visors do not provide adequate support for our memory de-duplication engine, how a new primitive called deferrable aggregate hyper call (DAH) fills the need, and what the resulting performance improvement is.

Many software security, instruction set architecture virtualization and performance enhancement techniques require instrumentation of application program binaries either to add run-time checks or to perform dynamic analysis and transformation. Unfortunately, commercially distributed application binaries on the Win32 platform are often stripped of their symbol table, and therefore cannot be easily disassembled, let alone correctly instrumented. BIRD is an instrumentation tool that applies an IA-32 disassembler both statically and dynamically, and successfully guarantees that no instruction in an input binary can be executed without being examined first. Unfortunately, the first version of BIRD has several performance problems. This paper describes our experiences of optimizing the first BIRD prototype to remove these problems. In particular, we develop a novel speculative disassembly technique that successfully reaps most of the performance benefits of static disassembly while ensuring the same level of correctness as dynamic disassembly, a bitmap-based target address check algorithm that reduces the fixed performance overhead associated with every instrumentation, and a comprehensive in-place instrumentation technique that relies mostly on instruction substitution and drastically cuts down the number of debug exceptions (int 3) invoked at run time. Together these performance optimizations reduce the average performance overhead of a set of batch Win32 programs from 23.6% to 8.8%.

A block-level continuous data protection (CDP) system logs every disk update to a network storage server it protects, so as to support more flexible recovery time objective (RTO) and recovery point objective (RPO). To provide efficient access to historical snapshots, block-level CDP systems maintain multiple index structures, each of which needs to be updated whenever a disk block update operation is logged. Because these index structures are too large to be held in memory, updating their on-disk versions in real time becomes a major performance bottleneck that prevents existing CDP systems from scaling to large data backup applications. This paper describes the design and implementation of a high-performance index update mechanism that logs index updates, batches them in memory, and commits them using mostly sequential disk I/O. Sequential commit greatly reduces the cost of bringing in and writing back each on-disk index page. Update batching further amortizes this cost over multiple index update operations. Empirical performance measurements demonstrate that the proposed technique improves the index update throughput by more than an order of magnitude and reduces the performance overhead associated with index updates from 95% to under 15%.

Credit cards are key instruments in personal financial transactions. Credit card payment systems used in these transactions and operated by merchants are often targeted by hackers to steal the card data. To address this threat, the payment card industry establishes a mandatory security compliance standard for businesses that process credit cards. A central pre-requisite for this compliance procedure is to identify the credit card data flow, specifically, the stages of the card transaction processing and the server nodes that touch credit card data as they travel through the organization. In practice, this pre-requisite poses a challenge to merchants. As the payment infrastructure is implemented and later maintained, it often deviates from the original documented design. Without consistent tracking and auditing of changes, such deviations in many cases remain undocumented. Therefore building the credit card data flow for a given payment card processing infrastructure is considered a daunting task that at this point requires significant manual efforts. This paper describes a tool that is designed to automate the task of identifying the credit card data flow in commercial payment systems running on virtualized servers hosted in private cloud environments. This tool leverages virtual machine introspection technology to keep track of credit card data flows across multiple machines in real time without requiring intrusive instrumentation of the hyper visor, virtual machines, middleware or application source code. Effectiveness of this tool is demonstrated through its successful discovery of the credit card data flow of several open and closed source payment applications.

A major challenge of the anti-virus (AV) industry is how to effectively process the huge influx of malware samples they receive every day. One possible solution to this problem is to quickly determine if a new malware sample is similar to any previously-seen malware program. In this paper, we design, implement and evaluate a malware database management system called SMIT (Symantec Malware Indexing Tree) that can efficiently make such determination based on malware's function-call graphs, which is a structural representation known to be less susceptible to instruction-level obfuscations commonly employed by malware writers to evade detection of AV software. Because each malware program is represented as a graph, the problem of searching for the most similar malware program in a database to a given malware sample is cast into a nearest-neighbor search problem in a graph database. To speed up this search, we have developed an efficient method to compute graph similarity that exploits structural and instruction-level information in the underlying malware programs, and a multi-resolution indexing scheme that uses a computationally economical feature vector for early pruning and resorts to a more accurate but computationally more expensive graph similarity function only when it needs to pinpoint the most similar neighbors. Results of a comprehensive performance study of the SMIT prototype using a database of more than 100,000 malware demonstrate the effective pruning power and scalability of its nearest neighbor search mechanisms.

Virtualization provides the possibility of whole machine migration and thus enables a new form of fault tolerance that is completely transparent to applications and operating systems. While initial prototypes show promise, virtualization-based fault-tolerant architecture still experiences substantial performance overhead especially for data-intensive workloads. The main performance challenge of virtualization-based fault tolerance is how to synchronize the memory states of the Master and Slave in a way that minimizes the end-to-end impact on the application performance. This paper describes three optimization techniques for memory state synchronization: fine-grained dirty region identification, speculative state transfer, and synchronization traffic reduction using active slave, and presents a comprehensive performance study of these techniques under three realistic workloads, the TPC-E benchmark, the SPECsfs 2008 CIFS benchmark, and a Microsoft Exchange workload. We show that these three techniques can each reduce the amount of end-of-epoch synchronization traffic by a factor of up to 7, 15 and 5, respectively.

Block-level continuous data protection (CDP) logs every disk block update so that disk updates within a time window are undoable. Standard file servers and DBMS servers can enjoy the data protection service offered by block-level CDP without any modification. Unfortunately, no existing block-level CDP systems can provide users a file versioning view on top of the block versions they maintain. As a result, the data they maintain cannot be used as an extension to the on-line system with which users routinely interact. This paper describes a name-based user-level file versioning system called UVFS that is designed to reconstruct file versions from disk block versions maintained by a block-level CDP. UVFS reconstructs file versions by following the last modified time of files and directories, a common file metadata supported by almost all modern file systems, and therefore does not require any modification to the host file system that a block-level CDP system protects. In addition, UVFS incorporates a file system-specific incremental consistency check mechanism to quickly convert an arbitrary point-in-time block-level snapshot to a file system-consistent one. Performance measurements taken from a fully operational UVFS prototype show that the average end-to-end elapsed time required to discover a file version is under 50 msec from the perspective of an NFS client serviced by an NFS server backed by a block-level CDP system.

Clock synchronization is an essential building block for many control mechanisms used in wireless networks, including frequency hopping, power management, and packet scheduling. Although the IEEE 802.11 standard provides a clock synchronization mechanism for multi-hop wireless networks, it has well-documented accuracy problems, because the beacon frames transmitted by nodes with faster clock are not prioritized at the MAC layer. This paper describes the design and implementation of the first known software-only solution that successfully eliminates the deficiency of IEEE 802.11's clock synchronization mechanism when operating on multihop wireless networks without requiring any hardware/protocol modifications. The key idea of this solution is to periodically arrange for a node to become the fastest node in the network by jumping its clock with a substantial amount, and force other nodes to synchronize their clocks with this leading node by virtue of IEEE 802.11's native clock synchronization mechanism. Empirical measurements of a working implementation of the proposed algorithm on a multi-hop wireless network testbed conclusively demonstrates its effectiveness in removing IEEE 802.11's clock synchronization accuracy problem.

An emerging class of applications for enterprise wireless LANs (WLAN) is voice over IP (VoIP) applications, which impose a stringent requirement on end-to-end delay. Because access points on an enterprise WLAN tend to be associated with different IP subnets, support for network-layer handoff is indispensable. Moreover, the handoff frequency is expected to be much higher for WLANs than for cellular networks because the coverage of a WLAN access point is much smaller. Although mobile IP is a mature solution to the network-layer handoff problem, no known mobile IP implementation on IEEE 802.11 WLANs can reduce the handoff latency below 100 msec, a nominal requirement for VoIP applications. This paper describes a novel Ethernet-over-IP overlay network architecture that completely does away with network-layer handoff, and thus reduces the end-to-end handoff delay to that of link-layer handoff, which is supported by WLAN hardware directly. In addition, the proposed wireless overlay network (WON) architecture, which has been implemented in a commercial WLAN access point, represents the first mobility solution that allows a mobile device to maintain its network connections while roaming across different IP subnets without requiring any modification on the mobile device. As a result, the proposed architecture can automatically provide seamless network-layer handoff to a wide variety of mobile devices (such as PDA, portable, cell phone) running on different operating systems, as long as they are equipped with 802.11 network interface.

Bulk file access is a read access to a large number of files in a file system. Example applications that use bulk file access extensively are anti-virus (AV) scanner, file-level data back-up agent, filesystem defragmentation tool, etc. This paper describes the design, implementation, and evaluation of an optimization to modern file systems that is designed to improve the read efficiency of bulk file accesses. The resulting scheme, called DAFT (disk geometry-aware file system traversal), provides a bulk file access application with individual files while fetching these files into memory in a way that respects the disk geometry and thus is as efficient as it can be. We have successfully implemented a fully operational DAFT prototype, and tested it with commercial AV scanners and data back-up agents. Empirical measurements on this prototype demonstrate that it can reduce the elapsed time of enumerating all files in a file system by a factor of 5 to 15 for both fragmented and non-fragmented file systems on fast and slow disks.

Network flows running on a wireless mesh network (WMN) may suffer from partial failures in the form of serious throughput degradation, sometimes to the extent of starvation, because of weaknesses in the underlying MAC protocol, dissimilar physical transmission rates or different degrees of local congestion. Most existing WMN transport protocols fail to take these factors into account. This paper describes the design, implementation and evaluation of a coordinated congestion control (C3L) algorithm that guarantees fair resource allocation under adverse scenarios and thus provides end-to-end max-min fairness among competing flows. The C3L algorithm features an advanced topology discovery mechanism that detects the inhibition of wireless communication links, and a general collision domain capacity re-estimation mechanism that effectively addresses such inhibition. A comprehensive ns-2-based simulation study as well as empirical measurements taken from an IEEE 802.11a-based multi-hop wireless testbed demonstrate that the C3L algorithm greatly improves inter-flow fairness, eliminates the starvation problem, and at the same time maintains high radio resource utilization efficiency.

A voice-over-IP (VoIP) gateway bridges IP-based packet-switched networks (i.e. Internet) with public circuitswitched telephone networks (i.e. PSTN). The key building block of a VoIP gateway is a telephony card that interfaces with the PSTN and converts signals from the PSTN to bits that can be manip

Because most Web application attacks exploit vulnerabilities that result from lack of input validation, a promising approach to thwarting these attacks is to apply validation checks on tainted portions of the operands used in security-sensitive operations, where a byte is tainted if it is data/control dependent on some network packet(s). This paper presents the design, implementation and evaluation of a dynamic checking compiler called WASC, which automatically adds checks into Web applications used in three-tier Internet services to protect them from the most common two types of Web application attacks: SQL- and script-injection attack. In addition to including a taint analysis infrastructure for multi-process and multi-language applications, WASC features the use of SQL and HTML parsers to defeat evasion techniques that exploit interpretation differences between attack detection engines and target applications. Experiments with a fully operational WASC prototype show that it can indeed stop all SQL/script injection attacks that we have tested. Moreover, the end-to-end latency penalty associated with the checks inserted by WASC is less than 30% for the test Web applications used in our performance study.

In its most general form, an attack signature is a program that can correctly determine if an input network packet sequence can successfully attack a protected network application. Filter rules used in firewall and network intrusion prevention systems (NIPS) are an abstract form of attack signature. This paper presents the design, implementation, and evaluation of an automated attack signature generation system called Trag, that automatically generates an executable attack signature program from a victim programpsilas source and a given attack input. Trag leverages dynamic data and control dependencies to extract relevant code in the victim program, accurately identifies variable initialization statements that are not executed in the given attack, is able to generate attack signatures for multi-process network applications, and reduces the size of attack signatures by exploiting responses from victim programs. Experiments with a fully working Trag prototype show that Tragpsilas signatures can indeed prevent attacks against multiple production-grade vulnerable server/Web applications, such as apache, wu-ftpd and MyBullentinBoard, with up to 65% reduction in size when compared with the victim program. In terms of performance overhead, the additional latency as observed from the client-side is no more than 25 usec for multi-process Web applications, while the overall throughput remains unaffected.

Multi-dimensional storage virtualization (MDSV) technology allows multiple virtual disks, each with a distinct combination of capacity, latency and bandwidth requirements, to be multiplexed on a physical disk storage system with performance isolation. This paper presents novel design and implementation techniques that solve the availability guarantee and fairness assurance problems in multi-dimensional storage virtualization. First, we show that a measurement-based admission control algorithm can reduce the effective resource requirement of a virtual disk with availability guarantee by accurately estimating its resource needs without prior knowledge of its input workload characteristics. Moreover, to accurately factor disk access overhead into real-time disk request scheduling algorithm, we propose a virtual disk switching overhead extraction and distribution algorithm that can derive the intrinsic disk access overhead associated with each virtual disk so as to achieve perfect performance isolation. Finally, we develop an adaptive server time leap-forward algorithm to effectively address the short-term unfairness problem of virtual clock-based disk scheduler, the only known proportional-share scheduler that is based on wall-clock time and thus enables disk utilization efficiency optimization while delivering disk QoS guarantees.

A reparable database management system has the ability to automatically undo the set of transactions that are corrupted by a human error or malicious attack. The key technical challenge to building repairable database management systems is how to accurately and efficiently keep track of inter-transaction dependencies due to data sharing through a database or through an application. In this paper, we present the design, implementation and evaluation of the inter-transaction dependency tracking mechanisms used in a repairable database management system called Blastema, which adds fast repairability in a portable way to a commercial DBMS, Oracle 9.2.0. Compared with other repairable DBMSs, Blastema eliminates false positive dependencies using fine-grained inter-transaction dependency tracking, and is able to successfully recognize two major sources of false negative dependencies, phantom dependencies and dependencies among transactions due to application data sharing. With these advanced inter-transaction dependency tracking mechanisms, Blastema significantly improves the availability of modern DBMSs by facilitating and sometimes even automating the damage repair process after a human error or a malicious attack. Performance measurements on a fully operational Blastema prototype run under the TPC-C benchmark show that the average run-time throughput penalty of the proposed inter-transaction dependency tracking mechanisms is less than 18%.

Radio channel quality of real-world wireless networks tends to exhibit both short-term and long-term temporal variations that are in general difficult to model. To maximize the utilization efficiency of radio resources, it is critical that these temporal fluctuations in radio signal quality be incorporated into wireless routing decisions. In this paper, we explore the design considerations in leveraging accurate real-time radio channel quality information when making routing decisions. Specifically, we propose a channel characteristics-aware routing protocol (CARP) that (1) uses per-packet transmission time to estimate the effective residual capacity of a wireless link, (2) employs a bandwidth probability distribution model to better approximate a wireless path's capacity profile, and (3) applies multi-path routing to exploit diversity among alternative paths and deliver more robust throughputs despite temporal fluctuations in wireless link quality. We evaluated the performance gains of incorporating each of these mechanisms on a miniaturized multi-hop wireless network testbed- MiNT-m.

A block-level continuous data protection (CDP) system logs every disk block update from an application server (e.g., a file or DBMS server) to a storage system so that any disk updates within a time window are undoable, and thus is able to provide a more flexible and efficient data protection service than conventional periodic data backup systems. Unfortunately, no existing block-level CDP systems can support arbitrary point-in-time snapshots that are guaranteed to be consistent with respect to the metadata of the application server. This deficiency seriously limits the flexibility in recovery point objective (RTO) of block-level CDP systems from the standpoint of the application servers whose data they protect. This paper describes an incremental file system check mechanism (iFSCK) that is designed to address this deficiency for file servers, and exploits file system-specific knowledge to quickly fix an arbitrary point-in-time block-level snapshot so that it is consistent with respect to file system metadata. Performance measurements taken from a fully operational iFSCK prototype show that iFSCK can turn a 10 GB point-in-time block-level snapshot to be file-system consistent in less than 1 second, and takes less than 25% of the time required by the Fsck utility for vanilla ext3 under relaxed metadata consistency requirements.

A Feather-weight Virtual Machine (FVM) is an OS-level virtualization technology that enables multiple isolated execution environments to exist on a single Windows kernel. The key design goal of FVM is efficient resource sharing among VMs so as to minimize VM startup/shutdown cost and scale to a larger number of concurrent VM instances. As a result, FVM provides an effective platform for fault-tolerant and intrusion-tolerant applications that require frequent invocation and termination of dispensable VMs. This paper presents three complete applications of the FVM technology: scalable web site testing; shared binary service for application deployment and distributed Display-Only File Server (DOFS). To identify malicious web sites that exploit browser vulnerabilities, we use a web crawler to access untrusted sites, render their pages in multiple browsers each running in a separate VM, and monitor their execution behaviors. To allow Windows-based end user machines to share binaries that are stored, managed and patched on a central location, we run shared binaries in a special VM on the end user machine whose runtime environment is imported from the central binary server. To protect confidential files in a file server against information theft by insiders, we ensure that file viewing/editing programs run in a VM, which grants file content display but prevents file content from being saved on the host machine. In this paper, we show how to customize the generic FVM framework to accommodate the needs of the three applications, and present experimental results that demonstrate their performance and effectiveness.

Control-hijacking attacks exploit vulnerabilities in network services to take control of them and eventually their underlying machines. Although much work has been done on detection and prevention of control-hijacking attacks, most of them did not address the problem of repairing the attacked network services so as to prevent the same attacks from recurring. Ideally, post-attack repair should consist of an attack signature generation component that creates a filtering rule for front-end firewall or intrusion prevention system to block the detected attack and its variants, and a patch generation component that creates a fix to permanently eliminate the vulnerabilities that the detected attack exploits. This paper describes the design, implementation and evaluation of a program transformation and execution trace analysis system called PASAN that can automatically instrument the source code of network service programs in such a way that it can detect control-hijacking attacks and automatically generate patches to seal the vulnerability being exploited by the detected attack. We have implemented the first PASAN prototype as a GNU C compiler extension that aims at stack- based buffer overflow attacks but could be easily generalized to accommodate other control-hijacking attacks. Testing this prototype with seven network daemon programs with known vulnerabilities show that the automatically generated patches can successfully fix the vulnerability. In addition, these patches are similar in their structure to those that are manually created. The run-time performance overhead of application programs instrumented by PASAN is between 10% and 23%, except two programs, whose CPU consumption is low.

A format string attack exploits the fact that variadic functions determine the exact number of input arguments based on the format string argument, and compromises the victim application's address space by accessing data areas beyond the original input argument list the caller prepares. This paper describes the design, implementation and evaluation of a Win32 binary transformation tool called Lisbon, which transparently inserts into Win32 binaries additional checks that protect them from format string vulnerabilities. Lisbon casts the format string attack prevention problem as an input argument list bound checking problem. To reduce the run-time checking overhead, Lisbon exploits the debug register hardware, which is available in most mainstream CPUs including Intel's X86 architecture, to detect if a callee accesses data outside the input argument list. Moreover, Lisbon is able to detect format string attacks without interpreting their format strings and is thus potentially applicable to similar attacks against other functions that access input arguments in the same way as printf (). The runtime throughput penalty of the first Lisbon prototype is under 2% for a set of test network applications that are known to be vulnerable to format string attacks.

Continuous data protection, which logs every update to a file system, is an enabling technology to protect file systems against malicious attacks and/or user mistakes, because it allows each file update to be undoable. Existing implementations of continuous data protection work either at disk access interface or within the file system. Despite the implementation complexity, their performance overhead is significant when compared with file systems that do not support continuous data protection. Moreover, such kernel-level file update logging implementation is complex and cannot be easily ported to other operating systems. This paper describes the design and implementation of four user-level continuous data protection implementations for NFS servers, all of which work on top of the NFS protocol and thus can be easily ported to any operating systems that support NFS. Measurements obtained from running standard benchmarks and real-world NFS traces on these user-level continuous data protection systems demonstrate a surprising result: Performance of NFS servers protected by pure user-level continuous data protection schemes is comparable to that of unprotected vanilla NFS servers.

An emerging killer application for enterprise wireless LANs (WLANs) is voice over IP (VoIP) telephony, which promises to greatly improve the reachability and mobility of enterprise telephony service at low cost. Most commercial IEEE802.11 WLAN-based VoIP products cannot support more than ten voice conversations over a single IEEE 802.11b channel, even though its peak transmission rate is more than two orders of magnitude higher than an individual VoIP connection's bandwidth requirement. There are two main reasons why these VoIP systems' effective capacity is lower than expected: stringent latency requirement and substantial per-WLAN-packet overhead. Time-Division Multiple Access (TDMA) is a well-known technique that provides per-connection QoS guarantee as well as maximizes the radio channel utilization efficiency. This paper presents a software-based TDMA (STDMA) protocol that is designed to support VoIP applications and successfully works on commodity IEEE802.11 WLAN interfaces. The resulting STDMA prototype can support more than 50 two-way G.729 voice conversations over a single IEEE 802.11b channel.

Economies of scale make IEEE 802.11 an attractive technology for building wireless mesh networks (WMNs). However, the IEEE 802.11 protocol exhibits serious link-layer unfairness when used in multi-hop networks. Existing fairness solutions either do not address this problem, or require proprietary MAC protocol to provide fairness. In this paper, we argue that an ideal transport protocol should be able to achieve fairness even on top of an unfair MAC layer such as 802.11. Towards this end, we propose a co-ordinatedcongestioncontrolalgorithm that performs global bandwidth allocation and provides end-to-end flow-level max-min fairness despite weaknesses in the MAC layer. The proposed algorithm features an advanced topology discovery mechanism that detects the inhibition of wireless communication links, and a general collision domain capacity re-estimation mechanism that effectively addresses such inhibition. Through an ns-2-based simulation study we demonstrate that the proposed algorithm substantially improves the fairness across flows, eliminates starvation problem, and simultaneously maintains a high overall network throughput.

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

An effective transport protocol for a wireless mesh network (WMN) must fairly and efficiently allocate the limited network resources among multiple flows sharing the network while minimizing the performance overhead it incurs. While many transport protocols have been proposed specifically for multi-hop wireless networks, most of them refrain from keeping state in the intermediate network nodes. In this paper, we focus on the other extreme of the design space:statefultransportprotocol, and study the research question of how much performance improvement is possible if intermediate network nodes could maintain as much state as needed. We present the design of a stateful transport protocol, namedlink-awarereliabletransportprotocol(LRTP), and examine how LRTP can fairly and efficiently allocate the network resources by accurately estimating the sending rate of each flow traversing the network using information about effective physical link capacity and the number of sharing flows. LRTP reduces the performance overhead associated with reliable packet delivery by leveraging the link-layer retransmission mechanism to eliminate per-packet end-to-end acknowledgments and unnecessary packet transmissions. Experiments conducted on anIEEE802.1la-basedmulti-channelwirelessmeshnetworktestbedas well asns-2simulationsdemonstrate that LRTP can achieve significant improvements in both overall network throughput and inter-flow fairness, especially on wireless networks with channel errors, when compared with the de facto Internet transport protocol TCP, and state-of-the-art MANET transport protocols such as ATP.

The exponential increase in the deployment of IEEE 802.11-based wireless LAN (WLAN) technology has transformed it into an essential building block of the networking infrastructure of commercial enterprises. How to effectively manage these WLAN networks and stop malicious intruders are the two main barriers for further spread of this technology. At the same time, the enormous economies of scale behind IEEE 802.11-based WLAN products also result in rapid technological advances and astounding pricing efficiencies. In this paper, we describe the design, implementation, and evaluation of a scalable wireless LAN traffic monitoring system called WIreless Network senTRY (Wintry), which provides real-time visibility of the usage of an enterprise's wireless links in a way that is completely transparent to the monitored WLAN networks. Moreover, Wintry is able to leverage low-cost programmable WLAN access points and reduce the total hardware cost to the minimum. A key feature of Wintry is an accurate radio channel busy time estimation algorithm that correctly takes into account both back-off delay and corrupted packets in WLAN traffic load computation without requiring any modification to monitored WLAN devices.

A reparable database management system has the ability to automatically undo the set of transactions that are corrupted by a human error or malicious attack. The key technical challenge to building repairable database management systems is how to accurately and efficiently keep track of inter-transaction dependencies that take place through a database as well as through application logic. In this paper, we present the design, implementation and evaluation of the inter-transaction dependency tracking mechanisms used in a repairable database management system called RDB2, which adds fast repairability in a portable way to a commercial DBMS Oracle 9.2.0. RDB2 eliminates dependencies due to false sharing using fine-grained inter-transaction dependency tracking, and is able to successfully identify a major source of false negatives, phantom dependencies. With these advanced inter-transaction dependency tracking mechanisms, RDB2 can significantly improve the availability of modern DBMSs by facilitating and sometimes even automating the damage repair process after an error or attack. Performance measurements on the fully operational prototypes under the TPC-C benchmark show that the run-time throughput penalty of these enhanced inter-transaction dependency tracking mechanisms is less than 18%.

As disk storage density increases and data availability requirements become ever more demanding, data replication is increasingly an indispensable feature of enterprise-class storage systems. For highly available storage systems, every disk block is typically replicated on a local mirror server and a remote mirror server in addition to being stored on the main storage server. In a network storage environment, this N-way data replication increases the write traffic load on the storage client's network interface by N times. Multicast is a natural solution to this problem. However, existing storage area network technologies such as fibre channel and Ethernet do not provide adequate support for linklayer multicast. This paper describes a novel reliable multicast mechanism for Ethernet-based storage area networks that effectively exploits the virtual LAN technology and is able to keep the traffic load of N-way replication roughly at the same level as the no-replication case regardless of the value of N. This technology greatly increases the appeal of using Ethernet as the physical-layer technology for storage area networking, as fibre channel networks currently do not support such in-network replication. Performance measurements on an iSCSI-based network storage system demonstrate that the proposed reliable multicast mechanism is able to reduce the end-to-end data transport time by a factor of 2.6 for three-way replication when the disk write size is more than 4 Mbytes.

Viking [13] is a multi-spanning-tree Ethernet architecture that is designed to leverage commodity Ethernet switches to support Metro-Ethernet services. In particular, it exploits VLAN switching to provide network-wide load balancing across a metro-area network. However, Viking assumes the traffic matrix is fixed; as time goes by, the input load may gradually deviate from the assumed traffic matrix because of addition/deletion of subscribers and/or changes in bandwidth requirements from existing subscribers. Therefore, dynamic resource management is required to accommodate such traffic load fluctuations. This paper describes the design, implementation and evaluation of an autonomic network resource management system called Viking2 that enables a Metro-Ethernet network to dynamically self-reconfigure itself, with minimal human intervention, to adapt to changing traffic loads. In particular, whenever possible Viking2 uses a local repair approach to eliminate congestion while minimizing the number of flows affected. If local repair cannot fix a congestion problem, Viking2 resorts to a global reconfiguration approach that recomputes a new path for every flow and deploys the new routing state in a way that reduces the disruption during the period of transition to the minimum. Simulation results show that compared with the original Viking, Viking2 can indeed significantly improve a network's ability to dynamically adapt itself to changing traffic loads, to minimize the degree of congestion during normal network operation, and to increase the total effective network capacity.

The exponential increase in the deployment of IEEE 802.11-based wireless LAN (WLAN) technology has transformed it into an essential building block of the networking infrastructure of commercial enterprises. How to effectively manage these WLAN networks and stop malicious intruders are the two main barriers for further spread of this technology. At the same time, the enormous economies of scale behind IEEE 802.11-based WLAN products also result in rapid technological advances and astounding pricing efficiencies. Today, the street price of a low-end 802.11g access point is as low as $50 USD, with an estimated manufacturing cost of less than $25. In this paper, we describe the design, implementation, and evaluation of a scalable wireless LAN traffic monitoring system called wireless network sentry (Wintry), which provides real-time visibility of the usage of an enterprise's wireless links in a way that is completely transparent to the monitored WLAN networks. Moreover, Wintry is able to leverage low-cost programmable WLAN access points and reduce the total hardware cost to the minimum. A key feature of Wintry is an accurate radio channel busy time estimation algorithm that correctly takes into account both back-off delay and corrupted packets in WLAN traffic load computation without requiring any modification to monitored WLAN devices.

Abstract Wi‐Fi based hotspots offer mobile users broadband wireless Internet connectivity in public work spaces and corporate/university campuses. Despite the aggressive deployment of these hotspots in recent years, high‐speed wireless Internet access remains restricted to small geographical areas due to the limited physical coverage of wireless LANs. On the other hand, despite their lower throughput, cellular networks have a significantly wider coverage and are thus much more available. Recognizing that 2.5G or 3G cellular networks can effectively complement wireless LANs, we set out to develop a vertical handoff system that allows mobile users to seamlessly fall back to such cellular networks as the general packet radio service (GPRS) or 3G whenever wireless LAN connectivity is not available. The resulting handoff mechanism allows a network connection of a mobile node to operate over multiple wireless access networks in a way that is transparent to end user applications. In this paper, we present the design, implementation, and evaluation of a fully operational vertical handoff system, called OmniCon, which enables mobile nodes to automatically switch between wireless LAN and GPRS, based on wireless LAN availability, by introducing a simple extension to the existing Mobile IP implementation. We discuss the design issues in the proposed vertical handoff system for heterogeneous networks, including connection setup problems due to network address translation, and the disparity in link characteristics between wireless LANs and GPRS. A detailed performance evaluation study of the OmniCon prototype demonstrates its ability to migrate active network connections between these two wireless technologies with low handoff latency and close to zero packet loss. Copyright © 2006 John Wiley & Sons, Ltd.

Many software security solutions require accurate tracking of control/data dependencies among information objects in network applications. This paper presents a general dynamic information flow tracking framework (called GIFT) for C programs that allows an application developer to associate application-specific tags with input data, instruments the application to propagate these tags to all the other data that are control/data-dependent on them, and invokes application-specific processing on output data according to their tag values. To use GIFT, an application developer only needs to implement input and output proxy functions to tag input data and to perform tag-dependent processing on output data, respectively. To demonstrate the usefulness of GIFT, we implement a complete GIFT application called Aussum, which allows selective sandboxing of network client applications based on whether their inputs are "tainted" or not. For a set of computation-intensive test applications, the measured elapsed time overhead of GIFT is less than 35%

Comparing the system call sequence of a network application against a sandboxing policy is a popular approach to detecting control-hijacking attack, in which the attacker exploits such software vulnerabilities as buffer overflow to take over the control of a victim application and possibly the underlying machine. The long-standing technical barrier to the acceptance of this system call monitoring approach is how to derive accurate sandboxing policies for Windows applications whose source code is unavailable. In fact, many commercial computer security companies take advantage of this fact and fashion a business model in which their users have to pay a subscription fee to receive periodic updates on the application sandboxing policies, much like anti-virus signatures. This paper describes the design, implementation and evaluation of a sandboxing system called BASS that can automatically extract a highly accurate application-specific sandboxing policy from a Win32/X86 binary, and enforce the extracted policy at run time with low performance overhead. BASS is built on a binary interpretation and analysis infrastructure called BIRD, which can handle application binaries with dynamically linked libraries, exception handlers and multi-threading, and has been shown to work correctly for a large number of commercially distributed Windows-based network applications, including IIS and Apache. The throughput and latency penalty of BASS for all the applications we have tested except one is under 8%

As new attacks against Windows-based machines emerge almost on a daily basis, there is an increasing need to "lock down" individual users' desktop machines in corporate computing environments. One particular way to lock down a user computer is to guarantee that only authorized binary programs are allowed to run on that computer. A major advantage of this approach is that binaries downloaded without the user's knowledge, such as spyware, ad-ware, or code entering through buffer overflow attacks, can never run on computers that are locked down this way. This paper presents the design, implementation and evaluation of FOOD, a foreign code detection system specifically for the Windows/X86platform, where foreign code is defined as any binary programs that do not go through an authorized installation procedure. FOOD verifies the legitimacy of binary images involved in process creation and library loading to ensure that only authorized binaries are used in these operations. In addition, FOOD checks the target address of every indirect branch instruction in Windows binaries to prevent illegitimate control transfers to either dynamically injected mobile code or pre-existing library functions that are potentially damaging. Combined together, these techniques strictly prevent the execution of any foreign code. Experiments with a fully working FOOD prototype show that it can indeed stop all spyware and buffer overflow attacks we tested, and its worst-case run-time performance overhead associated with foreign code detection is less than 35%

Buffer overflow attack is the main attack method that most if not all existing malicious worms use to propagate themselves from machine to machine. Although a great deal of research has been invested in defense mechanisms against buffer overflow attack, most of them require modifications to the network applications and/or the platforms that host them. Being an extension work of CTCP, this paper presents a network-based low performance overhead buffer overflow attack detection system called Nebula 1 NEtwork-based BUffer overfLow Attack detection, which can detect both known and zero-day buffer overflow attacks based solely on the packets observed without requiring any modifications to the end hosts. Moreover, instead of deriving a specific signature for each individual buffer overflow attack instance, Nebula uses a generalized signature that can capture all known variants of buffer overflow attacks while reducing the number of false positives to a negligible level. In addition, Nebula is built on a centralized TCP/IP architecture that effectively defeats all existing NIDS evasion techniques. Finally, Nebula incorporates a payload type identification mechanism that reduces further the false positive rate and scales the proposed buffer overflow attack detection scheme to gigabit network links.

The majority of security vulnerabilities published in the literature is due to software bugs. Many researchers have developed program transformation and analysis techniques to automatically detect or eliminate such vulnerabilities. So far, most of them cannot be applied to commercially distributed applications on the Windows/x86 platform, because it is almost impossible to disassemble a binary file with 100% accuracy and coverage on that platform. This paper presents the design, implementation, and evaluation of a binary analysis and instrumentation infrastructure for the Windows/x86 platform called BIRD (binary interpretation using runtime disassembly), which provides two services to developers of security-enhancing program transformation tools: converting binary code into assembly language instructions for further analysis, and inserting instrumentation code at specific places of a given binary without affecting its execution semantics. Instead of requiring a high-fidelity instruction set architectural emulator, BIRD combines static disassembly with an on-demand dynamic disassembly approach to guarantee that each instruction in a binary file is analyzed or transformed before it is executed. It takes 12 student months to develop the first BIRD prototype, which can successfully work for all applications in Microsoft office suite as well as Internet explorer and IIS Web server, including all DLLs that they use. Moreover, the additional throughput penalty of the BIRD prototype on production server applications such as Apache, IIS, and BIND is uniformly below 4%.

One way to prevent control hijacking attack is to compare a network application’s run-time system calls with a pre-defined normal system call behavior model, and raise an alert upon detecting a mismatch. This paper describes a system called PAID, which can automatically derive an accurate system call pattern from the source code of an application, and use it to detect any anomalous behavior at run time with minimal overhead. Because each application’s system call pattern is directly derived from its source code, PAID never raises false positive alarms. Moreover, its false negative rate is very close to zero because PAID uses the sequence of return addresses on the user/kernel stack to uniquely identify each system call instance. Experiments on a fully operational PAID prototype show that PAID can indeed stop all known control hijacking attacks. The run-time latency and throughput penalty of PAID are under 13.02% and 11.52%, respectively, when it is tested against a set of production-mode network applications.

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

The Domain Name System (DNS) is a critical element of the Internet infrastructure. Even a small part of the DNS infrastructure being unavailable for a very short period of time could potentially upset the entire Internet and is thus totally unacceptable. Unfortunately, because DNS queries and responses are mostly UDP-based, it is vulnerable to spoofing-based denial of service (DoS) attacks, which are difficult to defeat without incurring significant collateral damage. The key to thwart this type of DoS attacks is spoof detection, which enables selective discarding of spoofed DNS requests without jeopardizing the quality of service to legitimate requests. This paper presents spoof detection strategies for protecting DNS servers from DoS attacks. These strategies create some form of cookies for a DNS server to check if each incoming request is indeed from where the request packet says it is from. We have implemented them as a firewall module called DNS guard. Measurements on the current DNS guard prototype show that it can deliver up to 80K requests/sec to legitimate users in the presence of DoS attacks at the rate of 250K requests/sec.

Limited fidelity of software-based wireless network simulations has prompted many researchers to build testbeds for developing and evaluating their wireless protocols and mobile applications. Since most testbeds are tailored to the needs of specific research projects, they cannot be easily reused for other research projects that may have different requirements on physical topology, radio channel characteristics or mobility pattern. In this paper, we describe the design, implementation and evaluation of MiNT-m, an experimentation platform devised specifically to support arbitrary experiments for mobile multi-hop wireless network protocols. In addition to inheriting the miniaturization feature from its predecessor MiNT [9], MiNT-m enables flexible testbed reconfiguration on an experiment-by-experiment basis by putting each testbed node on a centrally controlled untethered mobile robot. To support mobility and reconfiguration of testbed nodes, MiNT-m includes a scalable mobile robot navigation control subsystem, which in turn consists of a vision-based robot positioning module and a collision avoidance-based trajectory planning module. Further, MiNT-m provides a comprehensive network/experiment management subsystem that affords a user full interactive control over the testbed as well as real-time visualization of the testbed activities. Finally, because MiNT-m is designed to be a shared research infrastructure that supports 24x7 operation, it incorporates a novel automatic battery recharging capability that enables testbed robots to operate without human intervention for weeks.

Many fault-tolerant and intrusion-tolerant systems require the ability to execute unsafe programs in a realistic environment without leaving permanent damages. Virtual machine technology meets this requirement perfectly because it provides an execution environment that is both realistic and isolated. In this paper, we introduce an OS level virtual machine architecture for Windows applications called Feather-weight Virtual Machine (FVM), under which virtual machines share as many resources of the host machine as possible while still isolated from one another and from the host machine. The key technique behind FVM is namespace virtualization, which isolates virtual machines by renaming resources at the OS system call interface. Through a copy-on-write scheme, FVM allows multiple virtual machines to physically share resources but logically isolate their resources from each other. A main technical challenge in FVM is how to achieve strong isolation among different virtual machines and the host machine, due to numerous namespaces and interprocess communication mechanisms on Windows. Experimental results demonstrate that FVM is more flexible and scalable, requires less system resource, incurs lower start-up and run-time performance overhead than existing hardware-level virtual machine technologies, and thus makes a compelling building block for security and fault-tolerant applications.

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

As the number of system vulnerabilities multiplies in recent years, vulnerability assessment has emerged as a powerful system security administration tool that can identify vulnerabilities in existing systems before they are exploited. Although there are many commercial vulnerability assessment tools in the market, none of them can formally guarantee that the assessment process never compromises the computer systems being tested. This paper proposes a featherweight virtual machine (FVM) technology to address the safety issue associated with vulnerability testing. Compared with other virtual machine technologies, FVM is designed to facilitate sharing between virtual machines but still provides strong protection between them. The FVM technology allows a vulnerability assessment tool to test an exact replica of a production-mode network service, including both hardware and system software components, while guaranteeing that the production-mode network service is fully isolated from the testing process. In addition to safety, the vulnerability assessment support system described in this paper can also automate the entire process of vulnerability testing and thus for the first time makes it feasible to run vulnerability testing autonomously and frequently. Experiments on a Windows-based prototype show that Nessus assessment results against an FVM virtual machine are identical to those against a real machine. Furthermore, modifications to the file system and registry state made by vulnerability assessment runs are completely isolated from the host machine. Finally, the performance impact of vulnerability assessment runs on production network services is as low as 3%.

With the enormous economies of scale of wireless LAN (WLAN) hardware, the price of commodity WLAN access points has dropped to the level that is even cheaper than some WLAN adapters. In this paper we propose to put together an array of off-the-shelf access points, each operating at a different radio frequency, to build a super access point that can both scale up the overall sustained throughput and improve the robustness of WLAN connectivity in the presence of failures and denial-of-service attacks. The key enabling technology for the proposed access point array architecture is a dynamic load balancing mechanism that can adaptively adjust the association between stations and access points so as to distribute the traffic load among the array's channels. We have successfully developed such a load balancing mechanism and used it to build a working access point array prototype. Measurements on this prototype show that the proposed load balancing scheme can indeed improve the overall throughput and mitigate performance impacts due to misbehaving stations. In addition, the prototype requires no modification to either the access points or the stations, making it a technology readily applicable to existing wireless LAN environments.

The ability to check memory references against their associated array/buffer bounds helps programmers to detect programming errors involving address overruns early on and thus avoid many difficult bugs down the line. This paper proposes a novel approach called Cash to the array bound checking problem that exploits the segmentation feature in the virtual memory hardware of the X86 architecture. The Cash approach allocates a separate segment to each static array or dynamically allocated buffer, and generates the instructions for array references in such a way that the segment limit check in X86's virtual memory protection mechanism performs the necessary array bound checking for free. In those cases that hardware bound checking is not possible, it falls back to software bound checking. As a result, Cash does not need to pay per-reference software checking overhead in most cases. However, the Cash approach incurs a fixed set-up overhead for each use of an array, which may involve multiple array references. The existence of this overhead requires compiler writers to judiciously apply the proposed technique to minimize the performance cost of array bound checking. This paper presents the detailed design and implementation of the Cash compiler, and a comprehensive evaluation of various performance tradeoffs associated with the proposed array bound checking technique. For the set of complicated network applications we tested, including Apache, Sendmail, Bind, etc., the latency penalty of Cash's bound checking mechanism is between 2.5% to 9.8% when compared with the baseline case that does not perform any bound checking.

A pass-through server such as an NFS server backed by an iSCSI[1] storage server only passes data between the storage server and NFS clients. Ideally it should require at most one data copying operation on sending or receiving, as in normal IP routers. In practice, pass-through servers actually incur multiple data copying operations because they are implemented using a layered architecture where each layer has its own internal data representation. This paper describes the design, implementation and evaluation of a novel network-centric buffer caching scheme called NCache that minimizes data copying overhead in pass-through servers without requiring significant changes to their existing implementation. By organizing the data being passed or cached in a network friendly format, NCache is able to eliminate all unnecessary data copying. The key innovation in NCache is that it exploits the fact that pass-through servers do not interpret data, by replacing physical copying with logical copying in a way transparent to existing software. This transparency enables NCache to be easily portable to many operating systems. We have successfully built a Linux-based NCache prototype that can be applied to in-kernel NFS and static Web servers. Empirical performance measurements collected from this prototype show that by reducing the CPU load associated with data copying, NCache is able to provide up to 92% improvement in throughput for NFS server and up to 47% for Web server.

Although conventional database management systems are designed to tolerate hardware and to a lesser extent even software errors, they cannot protect themselves against syntactically correct and semantically damaging transactions, which could arise because of malicious attacks or honest mistakes. The lack of fast post-intrusion or post-error damage repair in modern DBMSs results in a longer mean time to repair (MTTR) and sometimes permanent data loss that could have been saved by more intelligent repair mechanisms. In this paper, we describe the design and implementation of Phoenix - a system that significantly improves the efficiency and precision of database damage repair process after an intrusion or operator error and thus, increases the overall database system availability. The two key ideas underlying Phoenix are (1) maintaining persistent inter-transaction dependency information at run time to allow selective undo of database transactions that are considered "infected" by the intrusion or error in question and (2) exploiting information present in standard database logs for fast selective undo. Performance measurements on a fully operational Phoenix prototype, which is based on the PostgreSQL DBMS, demonstrate that Phoenix incurs a response time and a throughput penalty of less than 5% and 8%, respectively, under the TPC-C benchmark, but it can speed up the post-intrusion database repair process by at least an order of magnitude when compared with a manual repair process.

Most mobile wireless networking research today relies on simulations. However, fidelity of simulation results has always been a concern, especially when the protocols being studied are affected by the propagation and interference characteristics of the radio channels. Inherent difficulty in faithfully modeling the wireless channel characteristics has encouraged several researchers to build wireless network testbeds. A full-fledged wireless testbed is spread over a large physical space because of the wide coverage area of radio signals. This makes a large-scale testbed difficult and expensive to set up, configure, and manage. This paper describes a miniaturized 802.11b-based, multi-hop wireless network testbed called MiNT. MiNT occupies a significantly small space, and dramatically reduces the efforts required in setting up a multi-hop wireless network used for wireless application/protocol testing and evaluation. MiNT is also a hybrid simulation platform that can execute ns-2 simulation scripts with the link, MAC and physical layer in the simulator replaced by real hardware. We demonstrate the fidelity of MiNT by comparing experimental results on it with similar experiments conducted on a non-miniaturized testbed. We also compare the results of experiments conducted using hybrid simulation on MiNT with those obtained using pure simulation. Finally, using a case study we show the usefulness of MiNT in wireless application testing and evaluation.

Even though multiple non-overlapped channels exist in the 2.4 GHz and 5 GHz spectrum, most IEEE 802.11-based multi-hop ad hoc networks today use only a single channel. As a result, these networks rarely can fully exploit the aggregate bandwidth available in the radio spectrum provisioned by the standards. This prevents them from being used as an ISP's wireless last-mile access network or as a wireless enterprise backbone network. In this paper, we propose a multi-channel wireless mesh network (WMN) architecture (called Hyacinth) that equips each mesh network node with multiple 802.11 network interface cards (NICs). The central design issues of this multi-channel WMN architecture are channel assignment and routing. We show that intelligent channel assignment is critical to Hyacinth's performance, present distributed algorithms that utilize only local traffic load information to dynamically assign channels and to route packets, and compare their performance against a centralized algorithm that performs the same functions. Through an extensive simulation study, we show that even with just 2 NICs on each node, it is possible to improve the network throughput by a factor of 6 to 7 when compared with the conventional single-channel ad hoc network architecture. We also describe and evaluate a 9-node Hyacinth prototype that Is built using commodity PCs each equipped with two 802.11a NICs.

No abstract available.

P2P file sharing protocol and ad hoc wireless routing protocol share many intriguing similarities even though they are motivated on totally different basis. The goal of P2P file sharing system such as KaZaa is to locate a set of servers that contain a given file and disseminate it efficiently. The key problem of an ad hoc network routing protocol is to determine which route to take to reach a given remote host. P2P file sharing application on mobile ad hoc network (MANET) has gained more momentum as shown in the research of recent years. One natural way is to implement P2P application and ad hoc routing at different layers they belong to. In this paper, we argue that instead of stacking one on the top of the other, more work needs to be done to make both P2P file sharing protocol and MANET routing protocol interact with each other. We extract the commonalities of these two and design a common query/response framework on which ad hoc network routing and P2P file sharing are integrated seamlessly. The extensive experiments show that our strategy performs better than the layered approach in terms of traffic, average delay and packet delivery ratio.

Although conventional database management systems are designed to tolerate hardware and to a lesser extent even software errors, they cannot protect themselves against syntactically correct and semantically damaging transactions, which could arise because of malicious attacks or honest mistakes. The lack of fast post-intrusion or post-error damage repair in modern DBMSs results in a longer mean time to repair (MTTR) and sometimes permanent data loss that could have been saved by more intelligent repair mechanisms. In this paper, we describe the design and implementation of Phoenix - a system that significantly improves the efficiency and precision of a database damage repair process after an intrusion or operator error and thus, increases the overall database system availability. The two key ideas underlying Phoenix are (1) maintaining persistent intertransaction dependency information at run time to allow selective undo of database transactions that are considered "infected" by the intrusion or error in question and (2) exploiting information present in standard database logs for fast selective undo. Performance measurements on a fully operational Phoenix prototype, which is based on the PostgreSQL DBMS, demonstrate that Phoenix incurs a response time and a throughput penalty of less than 5% and 8%, respectively, under the TPC-C benchmark, but it can speed up the post-intrusion database repair process by at least an order of magnitude when compared with a manual repair process.

Many nework security problems can be solved in a centralized TCP (CTCP) architecture, in which an organization's edge router transparently proxies every TCP connection between an internal host and an external host on the Internet. This paper describes the design, implementation, and evaluation of a CTCP router prototype that is built on the Linux kernel. By redirecting all packets targeting at nonexistent or nonopen-to-public ports to a CTCP socket which pretends to be the original receivers, CTCP could confirm the real identification of the packet sources, collect suspicious traffic from them, and make an illusion that the scanned target ports are all open, thus renders port scanning an useless effort. Under CTCP architecture, external hosts only interacts with a secure CTCP router; therefore, any OS fingerprinting attempt and DoS/DDoS attack targeting at TCP/IP implementation bugs could be thwarted. Moreover, By further checking traffic originating from confirmed scanners, the CTCP router can actually identify buffer overflow attack traffic. Finally, the CTCP router solves the TCP connection hijacking problem by introducing an additional check on the sequence number filed of incoming packets. Despite providing a rich variety of protection, the CTCP architecture does not incur much overhead. On a 1.1 GHz Pentium-3 machine with gigabit Ethernet interfaces, the throughput of the CTCP router is 420.3 Mbits/sec, whereas the throughput of a generic Linux router on the same hardware is only 409.1 Mbits/sec.

In most existing systems, the authorization check for system resource access is based on the user ID of the running processes. Such systems are vulnerable to password stealing/cracking attacks. Considering that remote attackers usually do not have physical access to local machines, we propose a security architecture called NPTrace (network-wide process tracing), which requires a user to know the root password and to prove that he is within some physical proximity in order to exercise the root privilege. More specifically, NPTrace attaches a privilege-level attribute to every process, and propagates this attribute across machines on demand. The privilege-level attribute of a process is set to rootable if the system can trace back its origin to a process started by a user that has physically logged on from a specific set of hosts on the network. Only a root process with this privilege-level attribute set to rootable, is allowed to perform privileged operations. The NPTrace architecture essentially exploits physical security to strengthen password-based security. This paper describes the design and implementation of the NPTrace prototype, which features a distributed mechanism to identify the entry point of a user into a network. The prototype is implemented under Linux and has been tested under many attack scenarios. The system shows correct behavior in these tests with negligible performance overhead.

The ability to deliver digital video over wireless networks is an enabling technology for many useful applications, ranging from home entertainment and security monitoring to enterprise messaging and military reconnaissance, and thus represents the holy grail of wireless technology development. We describe a wireless video delivery system, WiVision, which uses IEEE 802.11 wireless LANs as the last mile for both real-time video distribution and on-demand video playback. WiVision can air both live events, such as on-campus seminars and sports activities, and prestored video streams, such as course lectures and financial analysis sessions, to mobile users, who can tune in to selected channels of their choice from their laptops or PDAs. An innovative feature of WiVision is the support for random video access based on keyword-search, where keywords are extracted from the closed-caption text embedded in TV programs. In addition, WiVision is able to broadcast video streams on the wireless link while seamlessly working with commercially available media players. The paper presents the implementation details of the real-time acquisition and network transport components of a fully operational WiVision prototype, and the results of a performance evaluation study on that prototype.

Data conferencing is one of the more commercially successful conferencing applications, because of its effectiveness and relatively modest resource requirements. Existing data conferencing applications are built almost exclusively on IP-based packet switched networks. While they are very effective in office communications, their use in the home is still quite limited because data conferencing end-points are mostly personal computers and are thus not particularly people friendly. In contrast, many more people are quite comfortable with conventional telephones. The paper describes the design, implementation, and evaluation of an information appliance, called DataPhone, that can be used both as a regular phone and a data conferencing device. A DataPhone consists of a touch sensitive screen, an SVD (simultaneous voice and data) modem and a microcontroller-based single board computer. DataPhone allows two parties to have a regular voice communications channel, as well as a shared whiteboard for sketching and document sharing. One of the key design decisions of DataPhone is that it runs directly on PSTN, and does not required any additional infrastructural support, such as ISP subscription, domain name service, routing gateway, etc., thus avoiding their associated configuration headaches. We have successfully built a fully functional DataPhone prototype and evaluated its usefulness through end user testing. Initial responses are both favorable and encouraging.

Insider attack is one of the most serious cybersecurity threats to corporate America. Among all insider threats, information theft is considered the most damaging in terms of potential financial loss. Moreover, it is also especially difficult to detect and prevent, because in many cases the attacker has the proper authority to access the stolen information. According to the 2003 CSI/FBI Computer Crime and Security Survey, theft of proprietary information was the single largest category of losses in the 2003 survey totaling $70.1 million or 35% of the total financial loss reported in that survey. In this paper, we describe the design, implementation and evaluation of an industrial-strength solution called Display-Only File Server (DOFS), which can transparently and effectively stop information theft by insiders in most cases, even if the insiders have proper authorities to read/write the protected information. The DOFS architecture ensures that bits of a protected file never leave a DOFS server after the file is checked in and users can still interact with the protected files in the same way as if it is stored locally. Essentially, DOFS decouples "display access" from other types of accesses to a protected file by providing users only the "display image" rather than the bits of the files, and applies the thin-client computing model on existing client-server applications.

An intrusion-resilient database management system is the one that is capable of restoring its consistency after being compromised by a malicious attack or a human error. More specifically, an intrusion-resilient mechanism helps to quickly repair a database by nullifying the damage caused by malicious or erroneous transactions, while preserving the effects of unaffected legitimate transactions that take place between intrusions/errors and their detection. The goal of this project is to develop a portable implementation framework that can augment a commercial database management system with intrusion resilience without requiring any modifications to its internals. The intrusion resilience mechanism described in this paper significantly improves the availability of modern DBMSs by facilitating and sometimes even automating the post-intrusion damage repair process. In addition, it can be embodied in a reusable implementation framework, whose portability is demonstrated by its successful application to three different DBMSs: PostgreSQL, Oracle, and Sybase. Performance measurements on the fully operational prototypes under the TPC-C benchmark show that the run-time overhead of the intrusion-resilience mechanism is between 6% and 13%.

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

The growing popularity of consumer broadband connection technology, in particular cable TV and ADSL, has started a quiet revolution that will reshape the Internet connectivity solutions for commercial enterprises. One emerging theme is the replacement of dedicated lines based on frame relay or ISDN technologies with multiple inexpensive ADSL/cable TV links each of which potentially is subscribed from a different ISP. The key enabling technology for this revolution is multihoming load balancing, which spreads an enterprise's Internet traffic among multiple access links to increase the aggregate throughput, and diverts traffic away from non-functional links when they fail. Although there exist several commercial multihoming load balancing products in the marketplace, very little is published about the design tradeoffs and their performance implications. We describe the design space of multihoming load balancing systems, discuss the tradeoffs involved in load balancing and fail-over implementation strategies, and present quantitative performance measurements collected on a commercial multihoming load balancing system.

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

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

One of the most dangerous cybersecurity threats is control hijacking attacks, which hijack the control of a victim application, and execute arbitrary system calls assuming the identity of the victim program’s effective user. System call monitoring has been touted as an effective defense against control hijacking attacks because it could prevent remote attackers from inflicting damage upon a victim system even if they can successfully compromise certain applications running on the system. However, the Achilles’ heel of the system call monitoring approach is the construction of accurate system call behavior model that minimizes false positives and negatives. This paper describes the design, implementation, and evaluation of a Program semantics-Aware Intrusion Detection system called Paid , which automatically derives an application-specific system call behavior model from the application’s source code, and checks the application’s run-time system call pattern against this model to thwart any control hijacking attacks. The per-application behavior model is in the form of the sites and ordering of system calls made in the application, as well as its partial control flow. Experiments on a fully working Paid prototype show that Paid can indeed stop attacks that exploit non-standard security holes, such as format string attacks that modify function pointers, and that the run-time latency and throughput penalty of Paid are under 11.66% and 10.44%, respectively, for a set of production-mode network server applications including Apache, Sendmail, Ftp daemon, etc.

Most state-of-the-art commercial storage virtualization systems focus only on one particular storage attribute, capacity. This paper describes the design, implementation and evaluation of a multi-dimensional storage virtualization system called Stonehenge, which is able to virtualize a cluster-based physical storage system along multiple dimensions, including bandwidth, capacity, and latency. As a result, Stonehenge is able to multiplex multiple virtual disks, each with a distinct bandwidth, capacity, and latency attribute, on a single physical storage system as if they are separate physical disks. A key enabling technology for Stonehenge is an eciencyaware real-time disk scheduling algorithm called dualqueue disk scheduling, which maximizes disk utilization eciency while providing Quality of Service (QoS) guarantees. To optimize disk utilization eciency, Stonehenge exploits run-time measurements extensively, for admission control, computing latency-derived bandwidth requirement, and predicting disk service time.

The increasing popularity of IEEE 802.11-based wireless local area networks (LANs) lends them credibility as a viable alternative to third-generation (3G) wireless technologies. Even though wireless LANs support much higher channel bandwidth than 3G networks, their network-layer handoff latency is still too high to be usable for interactive multimedia applications such as voice over IP or video streaming. Specifically, the peculiarities of commercially available IEEE 802.11b wireless LAN hardware prevent existing mobile Internet protocol (IP) implementations from achieving subsecond Mobile IP handoff latency when the wireless LANs are operating in the infrastructure mode, which is also the prevailing operating mode used in most deployed IEEE 802.11b LANs. In this paper, we propose a low-latency mobile IP handoff scheme that can reduce the handoff latency of infrastructure-mode wireless LANs to less than 100 ms, the fastest known handoff performance for such networks. The proposed scheme overcomes the inability of mobility software to sense the signal strengths of multiple-access points when operating in an infrastructure-mode wireless LAN. It expedites link-layer handoff detection and speeds up network-layer handoff by replaying cached foreign agent advertisements. The proposed scheme strictly adheres to the mobile IP standard specification, and does not require any modifications to existing mobile IP implementations. That is, the proposed mechanism is completely transparent to the existing mobile IP software installed on mobile nodes and wired nodes. As a demonstration of this technology, we show how this low-latency handoff scheme together with a wireless LAN bandwidth guarantee mechanism supports undisrupted playback of remote video streams on mobile stations that are traveling across wireless LAN segments.

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

3D models have become an essential element of multimedia applications because they provide visual effects that permit interactive exploration. As in other media types, efficient compression of 3D models is essential to reduce the associated storage and processing cost. Triangle mesh is the prevailing geometric representation for 3D scene models. Despite significant research on compression algorithms for triangle mesh in recent years, most 3D model editing tools still manipulate triangle meshes in an uncompressed representation. A novel compression-domain mesh editing (CDE) technique, which supports an efficient lossless mesh compression algorithm called BFT that allows 3D models to be directly edited based on the BFT compression form. Experimental results from real-world complex 3D models running on a fully operational CDE prototype demonstrate that compared to the editing of uncompressed triangle mesh, the CDE technique achieves a reduction in run-time memory requirements during the editing process by a factor of 14, while keeping the average edit operation latency under 2 msec regardless of the size of the 3D models.

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

The data contents of an information system may be corrupted due to security breaches or human errors. The financial loss of such corruption is typically proportional to the amount of time required to recover the system's data/service. Recognizing that it is impossible to build absolutely secure computer systems and that human errors are inevitable, this project focuses on intrusion tolerance techniques that speed up the process of repairing a damaged system after an intrusion/error takes place. The proposed system, called Repairable File Service (or RFS), is specifically designed to facilitate the reparation of compromised network file servers. An architectural innovation of RFS is that it is decoupled from and requires no modifications on the shared file server that is being protected. RFS supports fine-grained logging to allow roll-back of any file update operation, and keeps track of inter-process dependencies to quickly determine the extent of system damage after an attack/error. Compared with the current practice of manual post-intrusion damage repair, RFS significantly reduces the mean time to repair and thus improves the overall system availability. Empirical measurements on the fully operational RFS prototype shows that the performance overhead of RFS is less than 6%, and that RFS is able to speed up the repair process by at least two orders of magnitude compared to manual repair.

The prevailing practice for testing protocol implementations is direct code instrumentation to trigger specific states in the code. This leaves very little scope for reuse of the test cases. In this paper, we present the design, implementation, and evaluation of VirtualWire, a network fault injection and analysis system designed to facilitate the process of testing network protocol implementations. VirtualWire injects user-specified network faults and matches network events against anticipated responses based on high-level specifications written in a declarative scripting language. With VirtualWire, testing requires no code instrumentation and fault specifications can be reused across versions of a protocol implementation. We illustrate the effectiveness of VirtualWire with examples drawn from testing Linux's TCP implementation and a real-time Ethernet protocol called Rether. In each case, 10 to 20 lines of script is sufficient to specify the test scenario. VirtualWire is completely transparent to the protocols under test, and additional overhead in protocol processing latency it introduces is below 10% of the normal.

Probabilistic packet marking (PPM) is a technique designed to identify packet traffic sources with low storage and processing overhead on network routers. In most previous PPM approaches, individual path messages carry only partial path information. These methods are susceptible to "path falsification" attacks, which greatly reduce their effectiveness. This work proposes a path-falsification-attack free PPM algorithm called Path Information Caching and Aggregation (PICA) that records paths of packet streams in fix-length path messages, thus eliminating the need of path reconstruction at the receiver end. Besides, by using a router's forwarding table to decompose packet volume, this semi-stateful method is more accurate in traffic volume report. It also supports both a packet rate-based path message generation algorithm and a redundant path message suppression mechanism to further eliminate path messages with the same destination. Finally, PICA protects PICA routers from being attacked by faked path messages. We have performed a trace-driven simulation study on the proposed PICA algorithm and compared its effectiveness with IETF's iTrace scheme by varying the sampling probability, the number of attack sources, and attack traffic rate. Compared to iTrace, the PICA algorithm reduces the total number of path messages required by a factor of more than 2, while reporting traffic volume more accurately.

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

Deployment of asynchronous learning systems is still very limited mainly because of the use of expensive video to record and play back classroom lectures. The key advantage of the Lectern II approach is that all important lecture components can be effectively captured without video. Lectern II employs the touch-sensitive screen technology to build a "digital desk," which is shown to be able to effectively support and transparently capture the standard classroom lecturing activity. Recorded lectures can be edited and automatically uploaded to a Web server, and than viewed by students via a standard streaming player. As the total cost of a complete Lectern II system is under $4,000, Lectern II represents the first course lecture recording system that has the potential to be widely deployed in the classrooms of universities and K-12 schools.

Summary for only given. Conventional digital video playback systems provide only limited user interactivity, mostly in the form of VCR-like controls. In this model, the temporal ordering and the spatial viewpoints of the video streams being viewed are completely determined at authoring time. In contrast, we have defined a form of interactive video called active video (see http://www.ecsl.cs.sunysb.edu//spl sim/anindya/avs/avs.html, 2002), which supports hyper-linking among related video sequences and interpolation of video sequences with neighboring viewpoints, to offer end users the additional flexibility of choosing the sequencing and the viewing angle (even virtual ones) at playback time. However, active video has a substantially higher storage and transmission cost due to multiple time-synchronized video streams capturing the dynamic scene and the pixel-level correspondence maps encoding the spatial association among the frame-pairs of all adjacent streams. The maps are interpolated at run-time to generate virtual views. We describe and evaluate the following three compression techniques that alleviate the storage and network transmission costs of active video: spatial video compression; lossy map compression; lossless map compression.

Disk logging is a fundamental building block for fault tolerance system design because it captures a persistent snapshot of critical system state for subsequent recovery in the occurrence of failures. Logging typically is required to be synchronous to ensure absolute recoverability. Therefore speeding up synchronous disk write is critical to those fault tolerance systems that are based on disk logging. This paper describes a novel track-based disk logging technique that is able to reduce the latency of synchronous disk writes to the minimum without compromising data integrity guarantee. As an application of track-based disk logging, we present the design and implementation of a low-write-latency disk subsystem called Trail. Through a fully operational Trail prototype, we demonstrate that Trail achieves the best known disk. logging performance record, which is close to data transfer delay plus command processing overhead. A 4 KByte disk write takes less than 1.5 msec. Based on the TPC-C benchmark, the transaction throughput of a Trail-based transaction processing system is on an average 62.9% higher-than one based on a standard disk subsystem, and the database logging-related disk I/O overhead is reduced by 42%.

This paper presents an FPGA-based design and implementation of a three dimensional (3D)) triangle mesh decompressor. Triangle mesh is the dominant representation of 3D geometric models. The prototype decompressor is based on a simple and highly efficient triangle mesh compression algorithm, called BFT mesh encoding. To the best of our knowledge, this is the first hardware implementation of triangle mesh decompression. The decompressor can be added at the front-end of a 3D graphics card sitting on the PCI/AGP bus. It can reduce the bandwidth requirement on the bus between the host and the graphics card by up to 80% compared to standard triangle mesh representations. Other mesh decompression algorithms with comparable compression efficiency to BFT mesh encoding are too complex to be implemented in hardware.

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

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

A major challenge in Internet edge router design is to support both high packet forwarding performance and versatile and efficient packet processing capabilities. The thesis of this research project is that a cluster of PCs connected by a high speed system area network provides an effective hardware platform for building routers to be used at the edges of the Internet. This paper describes a scalable and extensible edge router architecture called Panama, which supports a novel aggregate route caching scheme, a real-time link scheduling algorithm whose performance overhead is independent of the number of real-time flows, a highly efficient kernel extension mechanism to safely load networking software extensions dynamically, and an integrated resource scheduler which ensures that real-time flows with additional packet processing requirements still meet their end-to-end performance requirements. This paper describes the implementation and evaluation of the first Panama prototype based on a cluster of PCs and Myrinet.

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

A major challenge in Internet edge router design is to support both high packet forwarding performance and versatile and efficient packet processing capabilities. The thesis of this research project is that a cluster of PCs connected by a high-speed system area network provides an effective hardware platform for building routers to be used at the edges of the Internet. This paper describes a scalable and extensible edge router architecture called Panama, which supports a novel aggregate route caching scheme, a real-time link scheduling algorithm whose performance overhead is independent of the number of real-time flows, a highly efficient kernel extension mechanism to safely load networking software extensions dynamically, and an integrated resource scheduler which ensures that real-time flows with additional packet processing requirements still meet their end-to-end performance requirements. This paper describes the implementation and evaluation of the first Panama prototype based on a cluster of PCs and Myrinet.

The advent of executable contents such as Java applets exposes World Wide Web (WWW) users to a new class of attacks that were not possible before. Despite an array of security checking, detection, and enforcement mechanisms built into the language model, the compiler, and the run-time system of Java, serious security breach incidents due to implementation bugs still arose repeatedly in the past several years. Without a provably correct implementation of Java's security architecture specification, it is difficult to make any conclusive statements about the security characteristic of current Java virtual machines. The Spout project takes an alternative approach to address Java's security problems. Rather than attempt a provable secure implementation, we aim to confine the damages of malicious Java applets to selective machines, thus, preventing the machines behind an organization's firewall from being attacked by malicious or buggy applets. More concretely, Spout is a distributed Java execution engine that transparently decouples the processing of an incoming applet's application logic from that of graphical user interface (GUI), such that the only part of an applet that is actually running on the requesting user's host is the harmless GUI code. A unique feature of the Spout architecture that does not exist in other similar systems, is that it is completely transparent to and does not require any modifications to WWW browsers or class libraries on the end hosts. This paper describes the detailed design, implementation, and performance measurements of the first Spout prototype, which also incorporates run-time resource monitoring mechanisms to counter denial-of-service attacks.

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

Buffer overflow attack can inflict upon almost arbitrary programs and is one of the most common vulnerabilities that can seriously compromise the security of a network-attached computer system. This paper presents a compiler-based solution to the notorious buffer overflow attack problem. Using this solution, users can prevent attackers from compromising their systems by changing the return address to execute injected code, which is the most common method used in buffer overflow attacks. Return address defender (RAD) is a simple compiler patch that automatically creates a safe area to store a copy of return addresses and automatically adds protection code into applications that it compiles to defend programs against buffer overflow attacks. Using it to protect a program does not need to modify the source code of the protected programs. Moreover, RAD does not change the layout of stack frames, so binary code it generated is compatible with existing libraries and other object files. Empirical performance measurements on a fully operational RAD prototype show that programs protected by RAD only experience a factor of between 1.01 to 1.31 slow-down. In this paper we present the principle of buffer overflow attacks, a taxonomy of defense methods, the implementation details of RAD, and the performance analysis of the RAD prototype.

The exponential growth in Internet traffic has motivated the development of a new breed of microprocessors called network processors, which are designed to address the performance problems resulting from the explosion in Internet traffic. The development efforts of these network processors concentrate almost exclusively on streamlining their data paths to speed up network packet processing, which mainly consists of routing and data movement. Rather than blindly pushing the performance of packet processing hardware, an alternative approach is to avoid repeated computation by applying the time-tested architecture idea of caching to network packet processing. Because the data streams presented to network processors and general-purpose CPUs exhibit different characteristics, detailed cache design tradeoffs for the two also differ considerably. This research focuses on cache memory design specifically for network processors. Using a trace-drive simulation methodology, we evaluate a series of three progressively more aggressive routing-table cache designs. Our simulation results demonstrate that the incorporation of hardware caches into network processors, when combined with efficient caching algorithms, can significantly improve the overall packet forwarding performance due to a sufficiently high degree of temporal locality in the network packet streams. Moreover, different cache designs can result in up to a factor of 5 difference in the average routing table lookup time, and thus in the packet forwarding rate.

Suez is a high-performance real-time packet router that supports fast best-effort packet routing and scalable QoS-guaranteed packet scheduling, and is built on a hardware platform consisting of a cluster of commodity PCs connected by a gigabit/sec system area network. The major goal of the Suez project is to demonstrate that the PC cluster architecture can be as cost-effective a platform for high-performance network packet routing as for parallel computing. Suez features a cache-conscious routing-table search algorithm that exploits CPU caching hardware for fast lookup by treating IP addresses directly as virtual addresses. To scale the number of real-time connections supportable with the link speed, Suez implements a fixed-granularity fluid fair queuing (FGFFQ) algorithm that completely eliminates the per-packet sorting overhead associated with conventional weighted fair queuing algorithms. This paper presents the architectural features of Suez, and reports the performance measurements of the Linux-based Suez prototype, which is built on four Pentium-II 400 MHz machines and Myrinet.

The advent of executable contents such as Java applets exposes WWW users to a new class of attacks that were not possible before. Serious security breach incidents due to implementation bugs arose repeatedly in the past several years. Without a provably correct implementation of Java's security architecture specification, it is difficult to make any conclusive statements about the security characteristic of current Java virtual machines. The Spout project takes an alternative approach to address Java's security problems. Rather than attempt a provably secure implementation, we aim to confine the damages of malicious Java applets to selective machines, thus protecting resources behind an organization's firewall from attacks by malicious or buggy applets. Spout is essentially a distributed Java execution engine that transparently decouples the processing of an incoming applet's application logic from that of the graphical user interface (GUI), such that the only part of an applet that is actually running on the requesting user's host is the harmless GUI code. A unique feature of the Spout architecture that does not exist in other similar systems, is that it is completely transparent to and does not require any modifications to WWW browsers or class libraries on the end hosts. This paper describes the design, implementation, and performance measurements of the first Spout prototype, which also incorporates run-time resource monitoring mechanisms to counter denial-of-service attacks.

Extensive research in TCP's congestion control mechanism has resulted in an effective algorithm that gives fairly precise estimates on the available bandwidth on a given network path (J. Postel, 1981; V. Jacobson, 1988). However, most past efforts focused on enhancing the accuracy and robustness of the path bandwidth estimation algorithms for individual TCP connections. Relatively fewer attempts have been made to further improve data transport efficiency by sharing path bandwidth information among concurrent TCP connections with the same sources and destinations. The paper proposes an aggregate TCP-based congestion control algorithm (ATCP) that allows individual TCP connections to reach their fair shares of the available network path bandwidth more quickly, while still observing TCP's congestion control semantics. In addition, the proposed algorithm is guaranteed to perform no worse than current TCP congestion control algorithm in all cases, and is designed to be implemented in a way that is completely transparent to both ends of a TCP connection. ATCP is particularly useful for TCP connections that are short-lived and yet have a long round-trip delay, such as Web page transfers using HTTP 1.0. Our trace-driven simulation study shows that the aggregate congestion control algorithm can reduce the normalized transaction latency by a factor of up to 2, compared to standard TCP.

Very large irregular-grid data sets are represented as tetrahedral meshes and may incur significant disk I/O access overhead in the rendering process. An effective way to alleviate the disk I/O overhead associated with rendering a large tetrahedral mesh is to reduce the I/O bandwidth requirement through compression. Existing tetrahedral mesh compression algorithms focus only on compression efficiency and cannot be readily integrated into the mesh rendering process, and thus demand that a compressed tetrahedral mesh be decompressed before it can be rendered into a 2D image. This paper presents an integrated tetrahedral mesh compression and rendering algorithm called Gatun, which allows compressed tetrahedral meshes to be rendered incrementally as they are being decompressed, thus leading to an efficient irregular grid rendering pipeline. Both compression and rendering algorithms in Gatun exploit the same local connectivity information among adjacent tetrahedra, and thus can be tightly integrated into a unified implementation framework. Our tetrahedral compression algorithm is specifically designed to facilitate the integration with an irregular grid renderer without any compromise in compression efficiency. A unique performance advantage of Gatun is its ability to reduce the runtime memory footprint requirement by releasing memory allocated to tetrahedra as early as possible.

Wire-speed IP (Internet Protocol) routers require very fast routing table lookup for incoming IP packets. The routing table lookup operation is time consuming because the part of an IP address used in the lookup, i.e., the network address portion, is variable in length. This paper describes the routing table lookup algorithm used in a cluster-based parallel IP router project called Suez. The innovative aspect of this algorithm is its ability to use CPU caching hardware to perform routing table caching and lookup directly by carefully mapping IP addresses to virtual addresses. By running a detailed simulation model that incorporates the performance effects of the CPU memory hierarchy against a packet trace collected from a major network router, we show that the overall performance of the proposed algorithm can reach 87.87 million lookups per second for a 500-MHz Alpha processor with a 16-KByte L1 cache and a 1-MByte L2 cache. This result is one to two orders of magnitude faster than previously reported results on software-based routing table lookup implementations. This paper also reports the performance impacts of various architectural parameters in the proposed scheme and its storage costs, together with the measurements of an implementation of the proposed scheme on a Pentium-II machine running Linux.

EtheReal is a real-time fast Ethernet switch architecture that provides bandwidth guarantees to distributed multimedia applications without OS or hardware modifications on the host machines. It implements true link-layer multicast, and offers a natural match to support network-layer QoS protocols such as RSVP. Because real-time performance guarantees fundamentally require state to be installed inside the network, link/switch failures could lead to significant disruption to the QoS promised to the user applications. This paper describes the fault detection and recovery mechanism supported by the EtheReal architecture, and reports on the performance measurements of the initial prototype implementation. The heart of EtheReal's fault detection and recovery mechanism is a fast spanning tree reconfiguration algorithm to reduce the total fault recovery time, and a delayed link inactivation scheme that allows real-time connections which are not affected by the failed links/switches to continue to exist, even though some of the links are marked as "blocked" in the new spanning tree topology. Measurements on the prototype show that the fault detection and recovery time on a network whose diameter is 10 hops are 220 ms and 31 ms, respectively. This combined delay corresponds to a minor jitter in real-time audio/video communication, and is a significant improvement over the standard IEEE 802.1d implementation, which takes on the order of 30 sec.

Although PC-class 3D graphics hardware has made significant strides in the last several years, the underlying architectural design principles are still generally considered as a black art. The quantitative approach prevalent in mainstream computer architecture design is rarely applied, at least as far as publicly available research literature is concerned. One main reason for this deficiency is the absence of a detailed workload characterization of 3D applications. This paper reports the results of a dynamic 3D workload characterization effort, which focuses on interactive 3D applications spanning multiple frames. To the best of our knowledge, this is one of the first such studies that have ever been attempted. In addition, whenever possible, this paper presents the empirical workload characteristics in the light of their architectural implications and detailed design tradeoffs. In particular, the paper discusses quantitatively the extent to which the workload impacts graphics architecture features such as rasterization pipeline, frame buffer design, texture memory management and system bus design.

Phoenix is a real-time network-attached storage device (NASD) that guarantees real-time data delivery to network clients even across single disk failure. The service interfaces that Phoenix provides are best-effort/real-time reads/writes based on unique object identifiers and block offsets. Data retrieval from Phoenix can be serviced in server push or client pull modes. Phoenix's real-time disk subsystem performance results from a standard cycle-based scan-order disk scheduling mechanism. However, the disk I/O cycle of Phoenix is either completely active or completely idle. This on-off disk scheduling model effectively reduces the power consumption of the disk subsystem, without increasing the buffer size requirement. Phoenix also exploits unused disk storage space and maintains additional redundancy beyond the generic RAID5-style parity. This extra redundancy, typically in the form of block replication, reduces the time to reconstruct the data on the failed disk. This paper describes the design, implementation, and evaluation of Phoenix, one of the first, if not the first, NASDs that support fault-tolerant, real-time, and low-power network storage service.

The trend towards extensible software architectures and component-based software development demands safe, efficient, and easy-to-use extension mechanisms to enforce protection boundaries among software modules residing in the same address space. This paper describes the design, implementation, and evaluation of a novel intra-address space protection mechanism called Palladium, which exploits the segmentation and paging hardware in the Intel X86 architecture and efficiently supports safe kernel-level and user-level extensions in a way that is largely transparent to programmers and existing programming tools. Based on the considerations on ease of extension programming and systems implementation complexity, Palladium uses different approaches to support user-level and kernel-level extension mechanisms. To demonstrate the effectiveness of the Palladium architecture, we built a Web server that exploits the user-level extension mechanism to invoke CGI scripts as local function calls in a safe way, and we constructed a compiled network packet filter that exploits the kernel-level extension mechanism to run packet-filtering binaries safely inside the kernel at native speed. The current Palladium prototype implementation demonstrates that a protected procedure call and return costs 142 CPU cycles on a Pentium 200MHz machine running Linux.

1 Introduction Content-based image database retrieval fundamentally consists of two components: feature extraction, which abstracts high-level symbolic representations from pixellevel images, and fast searching, which employs intelligent indices to avoid exhaustive search and reduce the query response time. The Parallel Multimedia Index Server (PAMIS) project aims to build a general parallelizing index engine that can be tailored to specific media data types, such as image, speech, video, etc. Specifically, PAMIS supports an indexing mechanism for nearest-neighbor search for media objects whose distance metrics satisfy the triangular inequality. Almost all the media types we have considered have a representation whose distance metric satisfies the triangular inequality.

Distributed multimedia applications require guaranteed quality of service (QoS) from the underlying networks. This paper describes the design, implementation, and evaluation of a real-time Fast Ethernet switch called EtheReal that provides bandwidth guarantees to real-time applications running on Ethernet without modification to the hardware and operating system on the host machines. At the heart of the EtheReal switch architecture is a novel real-time connection setup protocol that is completely transparent to the host machine's OS, and thus allows the switch to be deployed in a network of heterogeneous machines running different OS platforms. The only dependency of EtheReal on the hosts is their support for TCP/UDP/IP. In addition, the EtheReal switch uses an Ethernet address swapping technique for real-time packets, similar to ATM to avoid the complexity of maintaining a global connection ID space. Because of the inherent CRC support built into Ethernet hardware, this technique significantly reduces the total processing overhead compared to address swapping at higher network layers. The current EtheReal switch prototype is fully operational; and is built with off-the-shelf PC hardware. It is capable of supporting up to 640 Mbits/sec across 4 ports, and has a per-hop connection establishment overhead of 0.1-0.6 msec and a 10 /spl mu/s non-real-time packet latency.

Describes the design, implementation and evaluation of a parallel indexer called PAMIS (PArallel Multimedia Index Server) for a polygonal 2D shape image database. PAMIS is based on a shape representation scheme called the turning function, which exhibits the desirable properties of position, scale and rotation invariance, and has a similarity metric function that satisfies the triangular inequality, which is required for efficient database indexing. Because the goal of the PAMIS project is to support "like-this" image queries, the indexing scheme we chose, the vantage-point tree (VPT), uses relative rather than absolute distance values to organize the database elements for efficient nearest-neighbor searching. We have successfully implemented PAMIS on a network of workstations to exploit the I/O and computation parallelism inherent in the VPT algorithm. We found that it is preferable to make the VPT node size as small as possible in order to have a lean and deep VPT structure, and the best-case scheduling strategy performs the best among the scheduling strategies considered. Overall, the performance of the VPT algorithm scales very well with the number of processors, and the indexing efficiency (defined as the percentage of database elements touched by the search) of PAMIS is 6% and 39% for "good" queries that ask for 1 and 50 nearest neighbors, respectively.

Describes the implementation and performance evaluation of a 3D graphics library that can be readily linked with parallel applications to provide run-time visualization on large-scale message-passing parallel machines, such as the Intel Paragon. The prototype implementation is currently fully operational, and is based on Mesa, a public-domain OpenGL implementation, and on a sort-last parallelization strategy. Through a detailed performance analysis, we show that the scalability of the current prototype is close to the theoretical limit for the given hardware architecture. We have also developed a unified framework to describe parallel compositing algorithms and show that two popular parallel compositing algorithms, binary swapping and parallel pipeline compositing, are just two extreme instances of this framework. Such a framework is important because it allows users to tailor the compositing algorithm according to the computation/communication characteristics of specific parallel machines by tuning the parameters appropriately. The current parallel Mesa library prototype implements such a parameterizable family of compositing algorithms.

A video server guarantees the I/O bandwidth required for the smooth playback of a video access request once it has been admitted into the system. To ensure that new video access requests will not jeopardize the bandwidth guarantees promised to existing streams, an admission control module that decides whether a new request should be granted based on the resource usage is essential in the design of video servers. This paper presents a general framework in which video server admission control algorithms can be described in terms of how I/O delays are estimated. Then five specific admission control algorithms are studied in detail. The performances of these algorithms care analyzed in the context of an operational disk-array-based video server called SBVS. Detailed measurements from actual implementations of these admission control algorithms are used to compare their performances in terms of the maximum numbers of streams that can be admitted without causing overloads. One surprising result from this work is that the performance gap between the statistical and deterministic algorithms is between 10% to 40%, which is much smaller than were reported in earlier work.

Locust is a distributed shared virtual memory system that exploits compile-time data dependency information to address the issues of false sharing, cache coherence overhead, and affinity process scheduling. The paper reports the results and their analysis of a comprehensive performance evaluation study of the first Locust prototype, which is implemented on a 12-node Pentium cluster running FreeBSD and has been fully operational for a year. The results show that for the set of regular programs tested, the performance of Locust is within 1-8% of that of the message passing system implemented on the same hardware/software platform. The main performance gain of Locust as compared to existing weak cache consistency models mainly comes from the elimination of unnecessary synchronizations using the generational cache coherence protocol, and the function-shipping approach of implementing synchronization operations.

streams with other media types such as audio is an es-Fasy-io-use audio[video authoting took play a cmcial Ta2ein moving multimedia pTogTamsfrom TeseaTchcu-Tiosify to main-stTeam applications.This papeT desckbes the design and implementation of an inteTactitre video authoTing system called Zodiac, which employs an innovative edit histoTy abstraction to suppoTt Sevemt unique editing jeafuTes notfoun~in existing commercial and Te-seaTch video editing systems.Zo disc pTOVideSUSeTSa concepti~ally clean and semantically poweTfil bran&ing history model of edit operations to oTganize the authoTingpTocess, and to navigate among the design aL teTnatives.In addition, by analyzing the edit histo~, Zodiac is able to Teiiably detect a composed stTeam5 shot and scene boznda~es, ~hi& faci~itate intemctive ~~ideobTowsiny.Zodiac ako featuTes a video object annotation capability that allows meTs to associate annotations to moving objects in a video sequence.The annotations themselves could be text, image, audio, OT ~'ideo.Zodiac is built on top of hf3fFS, a file system specifica~~ydesigned foT inteTac~~ve mu~~imedia de- velaprnent environments, and implements an internal bufieT manage~that suppoTk transparent lossless com pT~ssion/decompression.Shot/scene detection, video object annotation, and bu~eT management all exploit the edit historr information foT peTfomance optimization.A complete digitd video authoring environment must support two fundamental functions: capturing and generation of raw video cfips, and temporal arrangement of video segments with special inter-segment transition eflects.b addition, the abiity to synchronize video Permissionto make digilzl or hard copies of all or part of thrs \trork for personzl or cl=

Providing network bandwidth guarantees over an Ethernet requires coordination of the network nodes for traffic prioritization such that real-time data can have deterministic access to the network. We have shown previously how RETHER, a software based token passing protocol can efficiently provide real-time support over a single shared Ethernet segment. This work extends the token passing mechanism into a switched, multi-segment Ethernet environment. This paper describes the detailed design issues, their solutions, and a fully operational switch implementation built into the FreeBSD kernel. By testing the protocol independently and as the underlying network protocol of the Stony Brook Video Server, we have verified that the bandwidth guarantees are successfully provided, with relatively low run-time overhead, for real-time connections crossing multiple Ethernet segments. This paper also provides a comprehensive performance evaluation of the prototype.

Beluga is a single-chip switch architecture specifically targeted at local area ATM networks, and it features three architectural innovations. First, an interconnection hierarchy composed of multiple switching fabrics is built into the chip to provide both low-latency cell transfer when the traffic is light and low cell drop rate under heavy load. Secondly, to improve silicon efficiency, Beluga is based on shared memory architecture, and the buffers are implemented using DRAM rather than SRAM technology. Heavy interleaving and selective invalidation are used to address long latency and periodic refreshing problems, respectively. Thirdly, Beluga supports multicast with minimal physical bit replication. It also separates support for unicast and multicast cells to optimize for the common case, where multicast cells occur infrequently. This paper describes the design details of Beluga and the results of a comprehensive simulation study to quantify the performance impact of each of its architectural features. The most important result from this research is that DRAM-based buffer implementation significantly reduces the cell-drop rate during heavy while exhibiting almost identical cell latency to SRAM-based implementation during light load. Therefore, we believe DRAM makes an attractive alternative for switch buffer implementation, especially for single-chip architecture such as Beluga.

Volumetric data sets require enormous storage capacity even at moderate resolution levels. The excessive storage demands not only stress the capacity of the underlying storage and communications systems, but also seriously limit the speed of volume rendering due to data movement and manipulation. A novel volumetric data visualization scheme is proposed and implemented in this work that renders 2D images directly from compressed 3D data sets. The novelty of this algorithm is that rendering is performed on the compressed representation of the volumetric data without pre-decompression. As a result, the overheads associated with both data movement and rendering processing are significantly reduced. The proposed algorithm generalizes previously proposed whole-volume frequency-domain rendering schemes by first dividing the 3D data set into subcubes, transforming each subcube to a frequency-domain representation, and applying the Fourier projection theorem to produce the projected 2D images according to given viewing angles. Compared to the whole-volume approach, the subcube-based scheme not only achieves higher compression efficiency by exploiting local coherency, but also improves the quality of resultant rendering images because it approximates the occlusion effect on a subcube by subcube basis.

The system architecture of the Stony Brook Video Server (SBVS), which guarantees end-to-end real-time video playback in a client-server setting, is presented. SBVS employs a real-time network access protocol, RETHER, to use existing Ethernet hardware as the underlying communications media. The video server tightly integrates the bandwidth guarantee mechanisms for network transport and disk I/O. SBVS's stream-by-stream disk scheduling scheme optimizes the effective disk bandwidth without incurring significant scheduling overhead. To demonstrate the feasibility of the proposed architecture, we have implemented a prototype called SBVS-1, which can support five concurrent MPEG-1 video streams on an Intel 486DX2/EISA PC. To our knowledge, this system is the first video server that provides an end-to-end performance guarantee from the server's disks to the each user's display over standard Ethernet. This paper describes the implementation details of integrating network and I/O bandwidth guarantee mechanisms, and the performance measurements that drive and/or validate our design decisions. © 1997 by John Wiley & Sons, Ltd.

Article Adventures in building the Stony Brook video server Share on Authors: Michael Vernick Computer Science Department, State University of New York at Stony Brook Computer Science Department, State University of New York at Stony BrookView Profile , Chitra Venkatramani Computer Science Department, State University of New York at Stony Brook Computer Science Department, State University of New York at Stony BrookView Profile , Tzi-cker Chiueh Computer Science Department, State University of New York at Stony Brook Computer Science Department, State University of New York at Stony BrookView Profile Authors Info & Claims MULTIMEDIA '96: Proceedings of the fourth ACM international conference on MultimediaFebruary 1997 Pages 287–295https://doi.org/10.1145/244130.244230Online:01 February 1997Publication History 26citation350DownloadsMetricsTotal Citations26Total Downloads350Last 12 Months3Last 6 weeks0 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 SiteGet Access

Withthe advent of high-performance microprocessors and high-speed local area networks, networks of workstations (NOW) are now capable of delivering sustained computational performance comparable to that of a supercomputer.

Distributed multimedia applications require performance guarantees from the underlying network subsystem. Ethernet has been the dominant local area network architecture in the last decade, and we believe that it will remain popular because of its cost-effectiveness and the availability of higherbandwidth Ethernets. We present the design, implementation and evaluation of a software-based timed-token protocol called RETHER that provides real-time performance guarantees to multimedia applications without requiring any modifications to existing Ethernet hardware. RETHER features a hybrid mode of operation to reduce the performance impact on non-real-time network traffic, a race-condition-free distributed admission control mechanism, and an efficient token-passing scheme that protects the network against token loss due to node failures or otherwise. To our knowledge, this is the first software implementation of a real-time protocol over existing Ethernet hardware. Performance measurements f...

This paper describes the design and implementation of a VLSI design process management system called Papyrus, which is built upon a history-based design process model that supports both routine and exploratory VLSI design processes. Emphasis of this paper is put on the descriptions of Papyrus's basic data models, design decisions, and implementation details. The operational prototype features a transparent dynamic load balancing scheme to exploit the computation power of networked workstations, an atomicity-guarantee mechanism to preserve the high-level abstraction of the design task construct, an interactive design-history manipulation facility, and a set of storage management techniques to reduce the storage overhead entailed by the single assignment update semantics, which is crucial to the support of the so-called rework mechanism. This system also embodies an innovative history-based meta-data inference scheme that automates many previously user-responsible design data management functions.>

Ethernet has been the dominant local area network architecture in the last decade, and we believe that it will continue to be so because of its cost-effectiveness and the availability of higher-bandwidth Ethernets. We propose and evaluate a software-based protocol called RETHER (Real-time ETHERnet) that provider real-time performance guarantees to multimedia applications without modifying existing Ethernet hardware. RETHER features a hybrid mode of operation to reduce the performance impact on non-real-time network packets, a race-condition-free distributed admission control mechanism, and an efficient token-passing scheme that protects the network against token loss due to node failures.>

Beyond data caching, data prefetching is by far the most effective way to address the memory access bottleneck associated with high-performance processors. This is particularly true for scientific programs whose working sets cannot be easily fit into the on-chip data cache. This paper proposes a new data prefetching architecture called Sunder, which combines the flexibility and accurateness of software prefetching and the transparency and low-overhead of hardware prefetching. The heart of the design is a dedicated prefetch engine that is programmable at run time by the software. An important design decision is to keep the prefetch engine completely isolated from the normal instruction execution pipeline except a loop counter to keep the two synchronized at the boundaries of loop iterations. A detailed simulation study on the Sunder architecture shows that compared to the cache-only architecture, Sunder achieves an average relative performance advantage over cache-only architectures ranging from 28% to 46%, with smaller cache block sizes leading to greater performance improvement.>

The paper proposes a memory architecture called Wafer-scale Interconnected Memory Array (WIMA), which is intended to replace ultra-high-density monolithic DRAM ICs. This architecture employs the high-performance interconnects provided by multichip module technology, the cache-embedding concept, and prime degree interleaving to expose the DRAM's internal parallelism not exploitable by monolithic DRAMs. Using WIMA modules as the basic building blocks, a high-bandwidth, low latency, and low cost vector memory system is developed that supports parallelism among multiple vector access streams. To mask the long start-up latencies, vector memory accesses are architectured to be split-phased. To alleviate the performance impact of bank conflicts, prime degree memory interleaving is adopted. The major contribution of this work is the development of a novel indexing mechanism for prime degree interleaving, which takes at most two integer divisions for each logical vector memory access.>

A novel disk architecture called Trail is proposed to optimize the disk write latency without sacrificing the disk read performance. This architecture features a track-based logging technique, which essentially reduces a disk write latency to the transfer delay. In addition, this disk architecture allows concurrent read/write, and implicit write scheduling without compromising data integrity. Through a synthetic-trace simulation study, we have shown that for transaction processing workloads, the write latency improvement of Trail over conventional disk devices is at least an order of magnitude. Trail's read latency performance is also better in all cases, sometimes the improvement is also over an order of magnitude. In terms of disk bandwidth utilization, the Trail architecture has a close to 100% write bandwidth efficiency and a read bandwidth efficiency at least as good as a conventional disk.>

In view of the growing gap between processor speeds and net work latency, it becomes increasingly expensive to maintain multi-processor cache consistency via run-time inter processor communication. Software-Controlled cache coher ence schemes have the advantage of simplified hardware and the reduction of inter-processor communication traffic. Among previously proposed software-based schemes, those based on the concept of version/timestamp show the most aggressive performance potential. Unfortunately these methods have several implementation and performance prob lems that prevent them from being practical implementation choices. In this paper, we discuss these problems and describe a generational cache coherence algorithm that elim inates all of these problems. Moreover, the new algorithm can exploit inter-level temporal locality of parallel programs with significantly less hardware support.

In a multimedia storage system video is probably the most demanding data type because of its large data volume and strict timing requirements.Image compression and parallel I/O architecture have been proposed in the literature to address the storage problem associated with digital video.This paper takes a systems approach by integrating video compression with data layout algorithms on parallel disk arrays to support high-quality video rendition.Specifically, we propose to use a multiresolution video representation scheme based on Gaussian and Laplacian Pyramids, which allows the storage system to satisfy video access requests by transferring only the minimum amount of data that is absolutely necessary.We also develope a new array storage layout algorithm for the Laplacian pyramid coding scheme to support jitter-free video rendering at the level of disk subsystems.We report on the results of a simulation study on the effectiveness of the proposed integrated design.The result shows that under the assumed workload the multi-resolution scheme is significantly better than the conventional representation in terms of the I/O rate, average waiting time, and average physical data bandwidth requirement.Specifically, the Laplacian Pyramid representation costs three to four times less data traffic, , reduces the average waiting time to one-eighth of that of the conventional approach, and achieves a five to ten times better average I/O rate.

Article Free Access Share on A novel memory access mechanism for arbitrary-view-projection volume rendering Author: T. Chiueh Computer Science Department, State University of New York at Stony Brook, Stony Brook, NY Computer Science Department, State University of New York at Stony Brook, Stony Brook, NYView Profile Authors Info & Claims Supercomputing '93: Proceedings of the 1993 ACM/IEEE conference on SupercomputingDecember 1993 Pages 690–698https://doi.org/10.1145/169627.169817Published:01 December 1993Publication History 3citation159DownloadsMetricsTotal Citations3Total Downloads159Last 12 Months6Last 6 weeks3 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

A data management paradigm that incrementally and transparently constructs the relationship among VLSI design objects is proposed. This paradigm is based on a design history model and the specifications of CAD-tool execution semantics. Based on this paradigm, algorithms are developed to automatically establish interobject relationships as a side effect of CAD-tool execution. This paradigm represents a vastly different approach in that it exploits history information, as well as domain knowledge, to deduce useful metadata for data management.>

Article Eliminating the address translation bottleneck for physical address cache Share on Authors: Tzi-cker Chiueh View Profile , Randy H. Katz View Profile Authors Info & Claims ASPLOS V: Proceedings of the fifth international conference on Architectural support for programming languages and operating systemsSeptember 1992 Pages 137–148https://doi.org/10.1145/143365.143501Online:01 September 1992Publication History 28citation507DownloadsMetricsTotal Citations28Total Downloads507Last 12 Months10Last 6 weeks2 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 SiteGet Access

The author describes a novel memory architecture, wafer-scale interconnected memory array (WIMA), that is intended to replace ultradensity monolithic DRAM (dynamic random access memory) ICs. This architecture employs the high-performance high-density interconnects provided by the multichip module technology, cache-embedding, and prime-degree interleaving to expose the internal parallelism not exploited by monolithic DRAMs. Using WIMA modules as the basic building blocks, a high-bandwidth, low-latency, and low-cost main memory system is proposed that could support the parallelism among multiple vector access streams. A novel indexing mechanism for prime-degree interleaving is developed which delivers fast and predictable memory access latency with modest hardware requirements.>

A new architectural concept called multithreaded vecrorization is introduced to bmaden the range of “vectorizable” code while keeping the same pipeline efficiency and simplicity as in conventional vector machines. This architecture can be viewed as a compromise between vector and VLIW machines. A compiler algorithm based on the software. pipelining technique is proposed to map loops to multi-threaded architecture. For several conventionally considered nonvectorizable kernels, we show this architecture can deliver as much as 60 percent of performance gain over conventional vector machines.

Article An integrated memory management scheme for dynamic alias resolution Share on Author: Tzi-cker Chiueh Department of Electrical Engineering and Computer Science, University of California, Berkeley, CA Department of Electrical Engineering and Computer Science, University of California, Berkeley, CAView Profile Authors Info & Claims Supercomputing '91: Proceedings of the 1991 ACM/IEEE conference on SupercomputingAugust 1991 Pages 682–691https://doi.org/10.1145/125826.126157Online:01 August 1991Publication History 4citation198DownloadsMetricsTotal Citations4Total Downloads198Last 12 Months1Last 6 weeks0 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 SiteGet Access

There are two aspects of engineering design datz internal data representation and abstract attri-

A history model is proposed to support the dynamic aspects of VLSI design, i.e., the controlled and disciplined sequencing of CAD tool invocations. This model is based on a task specification language, for encapsulating CAD tool invocations, and a novel activity thread, which maintains the history of task invocations and serves as a focus for sharing work results in a cooperative manner. A prototype was built on top of the OCT CAD framework.>