Computer Engineering Commons^™

Provisioning On-Line Games: A Traffic Analysis Of A Busy Counter-Strike Server, Wu-Chang Feng, Francis Chang, Wu-Chi Feng, Jonathan Walpole

Computer Science Faculty Publications and Presentations

This paper describes the results of a 500 million packet trace of a popular on-line, multi-player, game server. The results show that the traffic behavior of this heavily loaded game server is highly predictable and can be attributed to the fact that current game designs target the saturation of the narrowest, last-mile link. Specifically, in order to maximize the interactivity of the game itself and to provide relatively uniform experiences between players playing over different network speeds, on-line games typically fix their usage requirements in such a way as to saturate the network link of their lowest speed players. While …

Poster: Provisioning On-Line Games: A Traffic Analysis Of A Busy Counter-Strike Server, Francis Chang, Wu-Chang Feng, Wu-Chi Feng, Jonathan Walpole

Computer Science Faculty Publications and Presentations

A poster that illustrates the client/server model employed by an multiplayer online game, focusing on bandwidth usage.

Supporting Low-Latency Tcp-Based Media Streams, Ashvin Goel, Charles Krasic, Kang Li, Jonathan Walpole

Computer Science Faculty Publications and Presentations

The dominance of the TCP protocol on the Internet and its success in maintaining Internet stability has led to several TCP-based stored media-streaming approaches. The success of these approaches raises the question whether TCP can be used for low-latency streaming. Low latency streaming allows responsive control operations for media streaming and can make interactive applications feasible. We examined adapting the TCP send buffer size based on TCP's congestion window to reduce application perceived network latency. Our results show that this simple idea significantly improves the number of packets that can be delivered within 200 ms and 500 ms thresholds.

Infopipes: An Abstraction For Multimedia Streaming, Andrew P. Black, Huang Jie, Rainer Koster, Jonathan Walpole, Calton Pu

Computer Science Faculty Publications and Presentations

To simplify the task of building distributed streaming applications, we propose a new abstraction for information flow – Infopipes. Infopipes make information flow primary, not an auxiliary mechanism that is hidden away. Systems are built by connecting predefined component Infopipes such as sources, sinks, buffers, filters, broadcasting pipes, and multiplexing pipes. The goal of Infopipes is not to hide communication, like an RPC system, but to reify it: to represent communication explicitly as objects that the program can interrogate and manipulate. Moreover, these objects represent communication in application-level terms, not in terms of network or process implementation.

Thread Transparency In Information Flow Middleware, Rainer Koster, Andrew P. Black, Jie Huang, Jonathan Walpole, Calton Pu

Computer Science Faculty Publications and Presentations

Existing middleware is based on control-flow centric interaction models such as remote method invocations, poorly matching the structure of applications that process continuous information flows. Difficulties cultiesin building this kind of application on conventional platforms include flow-specific concurrency and timing requirements, necessitating explicit management of threads, synchronization, and timing by the application programmer. We propose Infopipes as a high-level abstraction for information flows, and we are developing a middleware framework that supports this abstraction. Infopipes transparently handle complexities associated with control flow and multi-threading. From high-level configuration descriptions the platform determines what parts of a pipeline require separate threads or …

Reifying Communication At The Application Level, Andrew P. Black, Jie Huang, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Middleware, from the earliest RPC systems to recent Object-Oriented Remote Message Sending (RMS) systems such as Java RMI and CORBA, claims transparency as one of its main attributes. Coulouris et al. define transparency as “the concealment from the … application programmer of the separation of components in a distributed system.” They go on to identify eight different kinds of transparency.

We considered titling this paper “Transparency Considered Harmful”, but that title is misleading because it implies that all kinds of transparency are bad. This is not our view. Rather, we believe that the choice of which transparencies should be offered …

Infopipes—An Abstraction For Information Flow, Jie Huang, Andrew P. Black, Jonathan Walpole, Calton Pu

Computer Science Faculty Publications and Presentations

Building Object-Oriented Distributed Systems has been facilitated by Remote Message Sending (RMS) systems like Java RMI and implementations of CORBA. However, RMS systems are designed to support request/response interactions. Streaming applications, in contrast, are characterized by high-bandwidth, long-duration communication with stringent performance requirements. Examples of streaming applications include video-on-demand, teleconferencing, on-line education, and environmental observation. These applications transfer huge amounts of data and focus on distributed information flow rather than request/response.

To simplify the task of building distributed streaming applications, we propose a new abstraction for information flow—Infopipes. Using Infopipes, information flow becomes the heart of the system, not an …

Moving Towards Massively Scalable Video-Based Sensor Networks, Wu-Chi Feng, Jonathan Walpole, Calton Pu, Wu-Chang Feng

Computer Science Faculty Publications and Presentations

Networking and computing technologies are becoming advanced enough to enable a wealth of diverse applications that will drastically change our everyday lives. Some past examples of these developments include the World Wide Web and wireless data networking infrastructures. As is quite obvious, the World Wide Web has enabled a fundamental change in the way many people deal with day-to-day tasks. Through the web, one can now make on-line reservations for travel, pay bills through on-line banking services, and view personalized on-line newscasts. More recently, developments in wireless technologies have enabled anywhere, anytime access to information over wireless medium. As wireless …

Modeling The Transient Rate Behavior Of Bandwidth Sharing As A Hybrid Control System, Kang Li, Molly H. Shor, Jonathan Walpole, Calton Pu

Computer Science Faculty Publications and Presentations

This paper uses hybrid control to model a problem of computer network systems, the dynamic behavior of bandwidth sharing among competing TCP traffic. It has been well known in the computer network community that well-behaved (TCP-friendly) congestion control mechanisms are crucial to the robustness of the Internet. Congestion control determines the transmission rate for each flow. Right now, most TCP-friendly research focuses only on the average throughput behavior without considering how the data is sent out in the short-term (e.g. bursty or smooth). However, recent experimental results show that short-term rate adjustments can change the bandwidth sharing result. Therefore, it …

Infosphere Project: An Overview, Calton Pu, Jonathan Walpole

Computer Science Faculty Publications and Presentations

We describe the Infosphere project, which is building the systems software support for information-driven applications such as digital libraries and electronic commerce. The main technical contribution is the Infopipe abstraction to support information flow with quality of service. Using building blocks such as program specialization, software feedback, domain-specific languages, and personalized information filtering, the Infopipe software generates code and manage resources to provide the specified quality of service with support for composition and restructuring.

Rate-Matching Packet Scheduler For Real-Rate Applications, Kang Li, Jonathan Walpole, Dylan Mcnamee, Calton Pu, David Steere

Computer Science Faculty Publications and Presentations

A packet scheduler is an operating system component that controls the allocation of network interface bandwidth to outgoing network flows. By deciding which packet to send next, packet schedulers not only determine how bandwidth is shared among flows, but also play a key role in determining the rate and timing behavior of individual flows. The recent explosion of rate and timing-sensitive flows, particularly in the context of multimedia applications, has focused new interest on packet schedulers. Next generation packet schedulers must not only ensure separation among flows and meet real-time performance constraints, they must also support dynamic fine-grain reallocation of …

Aspects Of Information Flow, Andrew P. Black, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Along with our colleagues at the Oregon Graduate Institute and Georgia Institute of Technology, we have recently been experimenting with real-rate systems, that is, systems that are required to move data from one place to another at defined rates, such as 30 items per second. Audio conferencing or streaming video systems are typical: they are required to deliver video or audio frames from a source (a server or file system) in one place to a sink (a display or a sound generator) in another; the frames must arrive periodically, with constrained latency and jitter. We have successfully built such systems …

Work In Progress: Automating Proportion/Period Scheduling, David Steere, Jonathan Walpole, Calton Pu

Computer Science Faculty Publications and Presentations

The recent effort to define middleware capable of supporting real-time applications creates the opportunity to raise the level of abstraction presented to the programmer. We propose that proportion/period is a better abstraction for specifying resource needs and allocation than priorities. We are currently investigating techniques to address some issues that are restricting use of proportion/period scheduling to research real-time prototypes. In particular, we are investigating techniques to automate the task of selecting proportion and period, and that allow proportion/period to incorporate job importance under overload conditions.

Investigation Of Image Feature Extraction By A Genetic Algorithm, Steven P. Brumby, James P. Theiler, Simon J. Perkins, Neal R. Harvey, John J. Szymanski, Jeffrey J. Bloch, Melanie Mitchell

Computer Science Faculty Publications and Presentations

We describe the implementation and performance of a genetic algorithm which generates image feature extraction algorithms for remote sensing applications. We describe our basis set of primitive image operators and present our chromosomal representation of a complete algorithm. Our initial application has been geospatial feature extraction using publicly available multi-spectral aerial-photography data sets. We present the preliminary results of our analysis of the efficiency of the classic genetic operations of crossover and mutation for our application, and discuss our choice of evolutionary control parameters. We exhibit some of our evolved algorithms, and discuss possible avenues for future progress.

Fine-Grain Period Adaptation In Soft Real-Time Environments, David Steere, Joshua Gruenberg, Dylan Mcnamee, Calton Pu, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Reservation-based scheduling delivers a proportion of the CPU to jobs over a period of time. In this paper we argue that automatically determining and assigning this period is both possible and useful in general purpose soft real-time environments such as personal computers and information appliances. The goal of period adaptation is to select the period over which a job is guaranteed to receive its portion of the CPU dynamically and automatically. The choice of period represents a trade-off between the amount of jitter observed by the job and the overall efficiency of the system. Secondary effects of period include quantization …

Qos Scalability For Streamed Media Delivery, Charles Krasic, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Applications with real-rate progress requirements, such as mediastreaming systems, are difficult to deploy in shared heterogenous environments such as the Internet. On the Internet, mediastreaming systems must be capable of trading off resource requirements against the quality of the media streams they deliver, in order to match wide-ranging dynamic variations in bandwidth between servers and clients. Since quality requirements tend to be user- and task-specific, mechanisms for capturing quality of service requirements and mapping them to appropriate resource-level adaptation policies are required. In this paper, we describe a general approach for automatically mapping user-level quality of service specifications onto resource …

Feedback Based Dynamic Proportion Allocation For Disk I/O, Dan Revel, Dylan Mcnamee, Calton Pu, David Steere, Jonathan Walpole

Computer Science Faculty Publications and Presentations

In this paper we propose to use feedback control to automatically allocate disk bandwidth in order to match the rate of disk I/O to the real-rate needs of applications. We describe a model for adaptive resource management based on measuring the relative progress of stages in a producer-consumer pipeline. We show how to use prefetching to transform a passive disk into an active data producer whose progress can be controlled via feedback. Our progress-based framework allows the integrated control of multiple resources. The resulting system automatically adapts to varying application rates as well as to varying device latencies.

Adaptive Resource Management Via Modular Feedback Control, Ashvin Goel, David Steere, Calton Pu, Jonathan Walpole

Computer Science Faculty Publications and Presentations

A key feature of tomorrow’s operating systems and runtime environments is their ability to adapt. Current state of the art uses an ad-hoc approach to building adaptive software, resulting in systems that can be complex, unpredictable and brittle. We advocate a modular and methodical approach for building adaptive system software based on feedback control. The use of feedback allows a system to automatically adapt to dynamically varying environments and loads, and allows the system designer to utilize the substantial body of knowledge in other engineering disciplines for building adaptive systems. We have developed a toolkit called SWiFT that embodies this …

A Feedback-Driven Proportion Allocator For Real-Rate Scheduling, David Steere, Ashvin Goel, Joshua Gruenberg, Dylan Mcnamee, Calton Pu, Jonathan Walpole

Computer Science Faculty Publications and Presentations

In this paper we propose changing the decades-old practice of allocating CPU to threads based on priority to a scheme based on proportion and period. Our scheme allocates to each thread a percentage of CPU cycles over a period of time, and uses a feedback-based adaptive scheduler to assign automatically both proportion and period. Applications with known requirements, such as isochronous software devices, can bypass the adaptive scheduler by specifying their desired proportion and/or period. As a result, our scheme provides reservations to applications that need them, and the benefits of proportion and period to those that do not. Adaptive …

Synthetic Files: Enabling Low-Latency File I/O For Qos-Adaptive Applications, Dylan Mcnamee, Dan Revel, Calton Pu, David Steere, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Files are a tried and true operating system abstraction. They present a simple byte-stream model of I/O that has proven intuitive for application programmers and efficient for operating system builders. However, current file systems do not provide good support for adaptive continuous media (CM) applications - an increasingly important class of applications that exhibit complex access patterns and are particularly sensitive to variations in I/O performance. To address these problems we propose synthetic files. Synthetic files are specialized views of underlying regular files, and convert complex file access patterns into simple sequential synthetic file access patterns. Synthetic file construction can …

Quality Of Service Semantics For Multimedia Database Systems, Jonathan Walpole, Charles Krasic, Ling Liu, David Maier, Calton Pu, Dylan Mcnamee, David Steere

Computer Science Faculty Publications and Presentations

Quality of service (QoS) support has been a hot research topic in multimedia databases, and multimedia systems in general, for the past several years. However, there remains little consensus on how QoS support should be provided. At the resource-management level, systems designers are still debating the suitability of reservation- based versus adaptive QoS management. The design of higher system layers is less clearly understood, and the specification of QoS requirements in domain-specific terms is still an open research topic. To address these issues, we propose a QoS model for multimedia databases. The model covers the specification of user-level QoS preferences …

Location Independent Names For Nomadic Computers, David Steere, Mark Morrissey, Peter Geib, Calton Pu, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Recent advances in the Domain Name System (DNS) and the Dynamic Host Configuration Protocol (DHCP) have enabled a new approach to supporting mobile users: location independent naming. In this approach, machines use the same hostname from any internet location, but use an IP address that corresponds to their current location. We describe a protocol that implements location independent naming for nomadic computers, i.e., machines that do not need transparent mobility. Our protocol allows hosts to move across security domains, uses existing protocols, and preserves existing trust relationships. Therefore, it preserves the performance and security of normal IP for nomadic computers …

Adaptation Space: Surviving Non-Maskable Failures, Crispin Cowan, Lois Delcambre, Anne-Francoise Le Meur, Ling Liu, David Maier, Dylan Mcnamee, Michael Miller, Calton Pu, Perry Wagle, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Some failures cannot be masked by redundancies, because an unanticipated situation occurred, because fault-tolerance measures were not adequate, or because there was a security breach (which is not amenable to replication). Applications that wish to continue to offer some service despite nonmaskable failure must adapt to the loss of resources. When numerous combinations of non-maskable failure modes are considered, the set of possible adaptations becomes complex. This paper presents adaptation spaces, a formalism for navigating among combinations of adaptations. An adaptation space describes a collection of possible adaptations of a software component or system, and provides a uniform way of …

Stackguard: Automatic Adaptive Detection And Prevention Of Buffer-Overflow Attacks, Crispin Cowan, Calton Pu, David Maier, Heather Hinton, Jonathan Walpole, Peat Bakke, Steve Beattie, Aaron Grier, Perry Wagle, Qian Zhang

Computer Science Faculty Publications and Presentations

This paper presents a systematic solution to the persistent problem of buffer overflow attacks. Buffer overflow attacks gained notoriety in 1988 as part of the Morris Worm incident on the Internet. While it is fairly simple to fix individual buffer overflow vulnerabilities, buffer overflow attacks continue to this day. Hundreds of attacks have been discovered, and while most of the obvious vulnerabilities have now been patched, more sophisticated buffer overflow attacks continue to emerge.

We describe StackGuard: a simple compiler technique that virtually eliminates buffer overflow vulnerabilities with only modest performance penalties. Privileged programs that are recompiled with the StackGuard …

Flow And Congestion Control For Internet Streaming Applications, Shanwei Cen, Calton Pu, Jonathan Walpole

Computer Science Faculty Publications and Presentations

The emergence of streaming multimedia players provides users with low latency audio and video content over the Internet. Providing high-quality, best-effort, real-time multimedia content requires adaptive delivery schemes that fairly share the available network bandwidth with reliable data protocols such as TCP. This paper proposes a new flow and congestion control scheme, SCP (Streaming Control Protocol) , for real-time streaming of continuous multimedia data across the Internet. The design of SCP arose from several years of experience in building and using adaptive real-time streaming video players. SCP addresses two issues associated with real-time streaming. First, it uses a congestion control …

Dynamic Load Distribution In Mist, K. Al-Saqabi, R. M. Prouty, Dylan Mcnamee, Steve Otto, Jonathan Walpole

Computer Science Faculty Publications and Presentations

This paper presents an algorithm for scheduling parallel applications in large-scale, multiuser, heterogeneous distributed systems. The approach is primarily targeted at systems that harvest idle cycles in general-purpose workstation networks, but is also applicable to clustered computer systems and massively parallel processors. The algorithm handles unequal processor capacities, multiple architecture types and dynamic variations in the number of processes and available processors. Scheduling decisions are driven by the desire to minimize turnaround time while maintaining fairness among competing applications. For efficiency, the virtual processors (VPs) of each application are gang scheduled on some subset of the available physical processors.

A Toolkit For Specializing Production Operating System Code, Crispin Cowan, Dylan Mcnamee, Andrew P. Black, Calton Pu, Jonathan Walpole, Charles Krasic, Perry Wagle, Qian Zhang

Computer Science Faculty Publications and Presentations

Specialization has been recognized as a powerful technique for optimizing operating systems. However, specialization has not been broadly applied beyond the research community because the current techniques, based on manual specialization, are time-consuming and error-prone. This paper describes a specialization toolkit that should help broaden the applicability of specializing operating systems by assisting in the automatic generation of specialized code, and {\em guarding} the specialized code to ensure the specialized system continues to be correct. We demonstrate the effectiveness of the toolkit by describing experiences we have had applying it in real, production environments. We report on our experiences with …

Predictable File Access Latency For Multimedia, Dan Revel, Crispin Cowan, Dylan Mcnamee, Calton Pu, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Multimedia applications are sensitive to I/O latency and jitter when accessing data in secondary storage. Transparent adaptive prefetching (TAP) uses software feedback to provide multimedia applications with file system quality of service (QoS) guarantees. We are investigating how QoS requirements can be communicated and how they can be met by adaptive resource management. A preliminary test of adaptive prefetching is presented.

Physical Media Independence: System Support For Dynamically Available Network Interfaces, Jon Inouye, Jim Binkley, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Advances in hardware technology has fueled the proliferation of dynamically configurable network interface cards. This empowers mobile laptop users to select the most appropriate interface for their current environment. Unfortunately, the majority of system software remains "customized" for a particular network configuration, and assumes many network characteristics remain invariant over the runtime of the software. Physical Media Independence (PMI) is the concept of making assumptions about a particular device explicit, detecting events which invalidate these assumptions, and recovering once events are detected. This paper presents a model supporting PMI. Based on device availablilty, the model identifies implicit device-related assumptions made …

A Specialization Toolkit To Increase The Diversity Of Operating Systems, Calton Pu, Andrew P. Black, Crispin Cowan, Jonathan Walpole, Charles Consel

Computer Science Faculty Publications and Presentations

Virus and worm attacks that exploit system implementation details can be countered with a diversified set of implementations. Furthermore, immune systems show that attacks from previously unknown organisms require effective dynamic response. In the Synthetix project, we have been developing a specialization toolkit to improve the performance of operating system kernels. The toolkit helps programmers generate and manage diverse specialized implementations of software modules. The Tempo-C specializer tool generates different versions for both compile-time and run-time specialization. We are now adapting the toolkit to improve operating system survivability against implementations attacks.