Technical Reports and MS Project Reports

With recent advances in wireless communication technology, mobile computing is an increasingly important area of research. A mobile system is one where independently executing components may migrate through some space during the course of the computation, and where the pattern of connectivity among the components changes as they move in and out of proximity. Mobile UNITY is a notation and proof logic for specifying and reasoning about mobile systems. In this paper it is argued that Mobile UNITY contributes to the modular development of system specifications because of the declarative ...Read More

The Mediator is a visual configuration tool for use with The Programmers' Playground distributed programming environment. With the Mediator, one can interactively launch distributed application modules, configured communication among the modules, observe communication patterns, interactively control module communication, kill running modules, and receive imported applications from a separate World Wide Web interface. This manual describes how to use the Mediator both as a stand-alone configuration tool and as a visual interface to the Playground Application Management System.

Application management refers to the process of making software applications available to end-users and providing automated mechanisms for launching and joining such applications. The Programmers' Playground is a computing environment for creating distributed applications from modular, reusable components. This paper discusses a set of tools that enable application developers to: (1) design and debug Playground distributed applications from existing "off-the-shelf" components using a visual configuration tool, (2) make new application components available on the Internet through a "launcher" service, and (3) make complete distributed applications available via a World Wide ...Read More

As computing components get smaller and people become accustomed to having computational power at their disposal at any time, mobile computing is developing as an important research area. One of the fundamental problems in mobility is maintaining connectivity through message passing as the user moves through the network. This is usually accomplished in one of two ways: search or tracking. In search, an algorithm hunts the mobile unit through the network each time a message is to be delivered, while in tracking, a specific home keeps up to date information ...Read More

With the advent of wireless technology and laptops, mobility is an important area of research. A fundamental problem in this area is the delivery of messages to a moving mobile. Current solutions work correctly only for slowly moving nodes that stay in one location long enough for tracking to stabilize. In this paper we consider the problem of message delivery to rapidly moving mobile units. With these algorithms, we introduce a new method for designing algorithms based on the paradigm of considering a mobile unit as a message, and adapting ...Read More

LIME is a system designed to assist in the rapid development of dependable mobile applications over both wired and ad hoc networks. Mobile agents reside on mobile hosts and all communication takes place via transiently shared tuple spaces distributed across the mobile hosts. The decoupled style of computing characterizing the Linda model is extended to the mobile environment. At the application level, both agents and hosts perceive movement as a sudden change of context. The set of tuples accessible by a particular agent residing on a given host is altered ...Read More

The JavaBeans component model allows users to plug together software components to create Java applications by specifying simple relationships between component events and properties. This paper describes work on augmenting the simple JavaBeans model with a multi-way constraint mechanism that allows users to graphically specify more complex multi-way contraints, resolve cyclical constraints between bean properties and graphically layout bean components. We also discuss weaknesses in the JavaBeans model and Java Abstract Windowing Toolkit (AWT) that were discovered while integrating a constraint mechanism with JavaBeans.

This paper presents a Real-time Upcall (RTU) [1] based TCP/IP implementation that guarantees throughput for continuous media applications and ensures low latency bounds for interactive applications. RTU is an endsystem rate-based scheduling mechanism that provides quality of service (QoS) in terms of CPU cycles, to applications. We restructured the existing NetBSD TCP/IP implementation to exploit the RTU concurrency model and to provide predictable performance. Our experimental results show that on two 200 MHz NetBSD PCs connected by a 155Mbps ATM link, the RTU based kernel TCP/IP implementation provides excellent throughput ...Read More

This paper describes an algorithm which can roughly halve the size of the current Internet routing tables. This algorithm is based on the radix trie representation of routing tables, which was firstly used in the BSD Unix distributions. The binary tree representation, which is a simplified case of radix tree, does well at showing the relationships among all routing table entries and provides us a way to build a collapse algorithm based on its internal structure. The binary tree collapse algorithm consists of three techniques, with the first two quite ...Read More

This report summarizes progress on the Terabit Burst Switching Project at Washington University for the period from December 15, 1997 through March 15, 1998. Efforts during this period have concentrated on working out details of the burst switch architecture, evaluating a variety of implementation alternatives and developing the physical design of the 160 Gb/s ATM switch to allow demonstration of the burst switch within a realistic network context.

This report summarizes progress on the Terabit Burst Switching Project at Washington University for the period from June 15, 1998 through September 15, 1998.

This paper presents a new communication service for ATM networks that provides one-way, adjustable rate, on-demand communication channels. The proposed dynamic flow service is designed to operate within a multi-service cell switched network that supports both conventional switched virtual circuits and IP packet routing and is designed to complement those services. It is particularly well suited to applications that transmit substantial amounts of data (a few tens of kilobytes or more) in fairly short time periods (up to a few seconds). Much of the current world-wide web traffic falls within ...Read More

We introduce a model for learning from examples and membership queries in situations where the boundary between positive and negative examples is somewhat ill-defined. In our model, queries near the boundary of a target concept may receive incorrect or "don't care" responses, and the distribution of examples has zero probability mass on the boundary region. The motivation behind our model is that in many cases the boundary between positive and negative examples is complicated or "fuzzy." However, one may still hope to learn successfully, because the typical examples that one ...Read More

We first present an algorithm that uses membership and equivalence queries to exactly identify a discretized geometric concept defined by the unioin of m axis-parallel boxes in d-dimensional discretized Euclidean space where each coordinate can have n discrete values. This algorithm receives at most md counterexamples and uses time and membership queries polynomial in m and log(n) for any constant d. Furthermore, all equivalence queries can be formulated as the union of O(mdlog(m)) axis-parallel boxes. Next, we show how to extend our algorithm to efficiently learn, from only equivalence queries, ...Read More

We present several efficient parallel algorithms for PAC-learning geometric concepts in a constant-dimensional space. The algorithms are robust even against malicious classification noise of any rate less than 1/2. We first give an efficient noise-tolerant parallel algorithm to PAC-learn the class of geometric concepts defined by a polynomial number of (d-1)-dimensional hyperplanes against an arbitrary distribution where each hyperplane has a slope from a set of known slopes. We then describe how boosting techniques can be used so that our algorithms' dependence on {GREEK LETTER} and {DELTA} does not depend ...Read More

We present an efficient algorithm for PAC-learning a very general class of geometric concepts over Rd for fixed d. More specifically, let T be any set of s halfspaces. Let x = (x1,...,xd) be an arbitrary point in Rd. With each t Є T we associate a boolean indicator function It(x) which is 1 if and only if x is in the halfspace t. The concept class Cds that we study consists of all concepts formed by any boolean function over It1, ...Its for ti Є T. This class is ...Read More

Cluster based architectures that employ high performance inexpensive Personal Computers (PCs) interconnected by high speed commodity interconnect have been recognized as a cost-effective way of building high performance scalable Multimedia-On-Demand (MOD) storage servers [4, 5, 7, 9]. Typically, the PCs in these architectures run operating systems such as UNIX that have traditionally been optimized for interactive computing. They do not provide fast disk-to-network data paths and guaranteed CPU and storage access. This paper reports enhancements to the 4.4 BSD UNIX system carried out to rectify these limitations in the context ...Read More

Current network technology is bandwidth-rich but latency-poor; thus round-trip delays will dominate access latency for web traffic. We describe four new techniques that reduce the round-trips needed for web accesses. The techniques are based on the paradigm of preprocessing a web page to collect information about links and inline data in the page. Stored Address Binding almost always eliminates the DNS lookup (which can cost seconds) at the start of a transaction. In Informed Server Proxying, a server tells its client that it has cached pages referenced in a page ...Read More

This report develops a practical method for connection admission control in ATM networks. The method is based on a virtual cell loss probability criterion, is designed to handle heterogeneous traffic types and allows each traffic source to be described by an individual finite-state model with as many states as are needed to describe the source traffic. To make connection admission decisions with respect to individual links, an aggregate finite state model is computed from the individual models and used to estimate the virtual cell loss probabilities. To reduce the computational ...Read More

We describe new mechanisms to deal with asymmetries that arise in routing protocols. We show how to avoid route asymmetries (due to non-unique shortest paths) by adding random integer link costs. We show in detail how RIP can be modified to avoid route asymmetry with high probability, without affecting either its efficiency or performance metrics such as convergence time. Symmetrical intra-domain routing also makes possible a new form of congestion control that we call Reverse Path Congestion Control (RPCC). We show, using simulations, that RPCC can augment existing TCP congestion ...Read More

The Internet Inter-ORB Protocol (IIOP) enables heterogeneous CORBA-compliant Object Request Brokers (ORBs) to interoperate over TCP/IP networks. The IIOP uses the Common Data Representation (CDR) transfer syntax to map CORBA Interface Definition Langauge (IDL) data types into a bi-canonical wire format. Due to the excessive marshaling/demarshaling overhead, data copying, and high-levels of function call overhead, conventional implementation of IIOP protocols yield poor performance over high-speed networks. To meet the demands of emerging distributed multimedia applications, CORBA-compliant ORBs must support both interoperable and highly efficient IIOP implementations. This paper provides two ...Read More

The objective of The Programmers' Playground, described in this manual, is to provide a development environment and underlying support for end-user construction of distributed multimedia applications from reusable self-describing software components. Playground provides a set of software tools and a methodology for simplifying the design and construction of applications that interact with each other and with people in a distributed computer system. This manual explains how to write interactive distributed applications using Playground. The only background necessary to get started is an understanding of basic data structures and control constructs ...Read More

Developing the ability to recognize a landmark from a visual image of a robot's current location is a fundamental problem in robotics. We describe a way in which the landmark matching problem can be mapped to that of learning a one-dimensional geometric pattern. The first contribution of our work is an efficient noise-tolerant algorithm (designed using the statistical query model) to PAC-learn the class of one-dimensional geometric patterns. The second contribution of our work is an empirical study of our algorithm that provides at least some evidence that statistical query ...Read More

The CORBA Event Service provides a flexible model for asynchronous communication among objects.However, the standard CORBA Event Service specification lacks important features required by real-time applications. For instance, operational flight programs for fighter aircraft have complex real-time processing requirements. This paper describes the design and performance of an object-oriented, real-time implementation of the CORBA Event Service that is designed to meet these requirements. This paper makes three contributions to the design and performance measurement of object-oriented real-time systems. First, it illustrates how to extend the CORBA Event Service so that ...Read More

The non-determinism, complexity, and size of distributed software systems present significant difficulties for designers and maintainers. Visualization can help alleviate these difficulties through interactive exploratory tools that allow both novice and experienced users to investigate a distributed computation using a common tool set. Essential to the success of a visual exploration tool is the ability to provide accurate representations of global states. This paper is concerned with the use of snapshots in support of interactive visual exploration of distributed computations. The nature of the visualization process requires snapshots that (1) ...Read More

High-performance Web servers are essential to meet the growing demands of the Internet. Satisfying these demands requires a thorough understanding of the key factors that affect Web server performance. This paper provides three contributions to the design, implementation, and evaluation of high-performance Web servers. First, we report the results of a comprehensive empirical study of popular high-performance Web servers (such as Apache, Netscape Enterprise, PHTTPD, and Zeus) over high-speed ATM networks. This study illustrates their relative performance and identifies their performance bottlenecks. To measure performance accurately, we developed a new ...Read More

Computational steering, the interactive adjustment of application parameters and allocation of resources, is a promising technique for higher-productivity simulation, finer-grained optimization of dynamically varying algorithms, and greater understanding of program behavior and the characteristics of data sets and solution spaces. Tools for computational steering must provide monitoring, visualization, and interaction facilities. In addition, these tools must address issues related to the consistency, latency, and scalability at each of these phases, and must consider the perturbation that results. In this paper we describe transaction-based components for a computational steering system and ...Read More

Formal accounts of negotiation tend to invoke the strategic models of conflict which have been impressively developed by game theorists in this half-century. For two decades, however, research on artificial intelligence (AI) has produced a different formal picture of the agent and of the rational deliberations of agents. AI's models are not based simply on intensities of preference and quantities of probability. AI's models consider that agents use language in various ways, that agents use and convey knowledge, that agents plan, search, focus, and argue. Agents can choose their language, ...Read More

This paper estimates the link costs of constraint based nonblocking ATM networks on a sphere. Analytical results are obtained when switches are uniformly distributed on the surface of a unit sphere and every switch has source and sink capacity of one, and the results are compared with simulations.

Recent advances in wireless networking technology and the increasing demand for ubiquitous, mobile connectivity demonstrate the importance of providing reliable systems for managing reconfiguration and disconnection of components. Design of such systems requires tools and techniques appropriate to the task. Many formal models of computation, including UNITY, are not adequate for expressing reconfiguration and disconnection and are therefore inappropriate vehicles for investigating the impact of mobility on the construction of modular and composable systems. Algebraic formalisms such as the pi-calculus have been proposed for modeling mobility. This paper addresses the ...Read More

Traditionally, a distributed system has been viewed as a collection of fixed computational elements connected by a static network. Prompted by recent advances in wireless communications rechnology, the emerging field of mobile computing is challenging these assumptions by providing mobile hosts with connectivity that may change over time, raising the possibility that hosts may be called upon to operate while only weakly connected to or while completely disconnected from other hosts. We define a concurrent mobile system as one where independently executing coponents may migrate through some space during the ...Read More

Aggregate visualization and manipulation enables the viewing and interaction of dynamically changing data sets in a graphically meaningful way. However, off-the-shelf applications generally provide only limited ways to view aggregates. To be truly effective to the end-user, an aggregate visualization should be customizable to suit the individual's needs. This paper describes a software system that empowers end-users to create interactive aggregate visualizations through direct manipulation. Included are mechanisms for specifying how aggregate data is processed from multiple sources, providing functionality similar to project, select, join, and cross product of relational ...Read More

Aggregate visualization and manipulation enables the viewing and interaction of dynamically changing data sets in a graphically meaningful way. However, off-the-shelf applications typically provide only limited ways to view static aggregates and generally to not support manipulation of aggregate data through the resulting visualization. To be fully dynamic, an aggregate visualization should be customizable to suit the individual's needs and should allow end-users to modify the data through direct manipulation. This paper describes a software system that empowers end-users to create interactive aggregate visualizations through a visual language interface. Included ...Read More

EUPHORIA is a user interface management system that enables end-users to create direct manipulation graphical user interfaces (GUIs) through interactive drawing. Used in conjunction with The Programmers' Playground, a distributed programming environment, end-users can dynamically create and associate GUI components with an underlying application without programming, This document describes EUPHORIA's functionality.

With recent advances in wireless communication and the ubiquity of laptops, mobile computing has become an important research area. An essential problem in mobile computing is the delivery of a message from a source to either a single mobile node, unicast, or to a group of mobile nodes, multicast. Standard solutions proposed for macromobility (Mobile IP) and micromobility (cellular phones) for the unicast problem rely on tracking the mobile node. Tracking solutions scale badly when mobile nodes move frequently, and do not generalize well to multicast delivery. Our paper proposes ...Read More

Retransmission based error control for large scale multicast applications is difficult because of two main problems: request implosion and lack of local recovery. Existing schemes (SRM, RMTP, TMTP, LBRRM) have good solutions to request implosion, but only approximate solutions (e.g., based on scoped multicast) for the local recovery problem. Our scheme achieves finer grain fault recovery by exploiting new forwarding services that allow us to create a dynamic hierarchy of receivers. We use a new paradigm, where routers provide a more refined form of multicasting (that may be useful to ...Read More

We propose a network monitoring, visualization and control system (NMVC) that ensures adequate quality of service to network users while maintaining high network resource utilization. The main components of our system are a network probe, an endsystem probe, software network management agents that provide extensible multi-attribute event filtering for highly scalable data/event collection, network operation centers (NOCs) which can remotely install and (re)configure these agents, efficient online event ordering algorithms that can help synthesize and display a consistent view of network health, status and performance and a View Choreographer that ...Read More

Advancements in network technology have led to the emergence of new computing paradigms that challenge established programming practices by employing weak forms of consistency and dynamic forms of binding. Code mobility, for instance, allows for invocation-time binding between a code fragment and the location where it executes. Similarly, mobile computing allows hosts (and the software they execute) to alter their physical location. Despite apparent similarities, the two paradigms are distinct in their treatment of location and movement. This paper seeks to uncover a common foundation for the two paradigms by ...Read More

Advancements in network technology have led to the emergence of new computing paradigms that challenge established programming practices by employing weak forms of consistency and dynamic forms of binding. Code mobility, for instance, allows for invocation-time binding between a code fragment and the location where it executes. Similarly, mobile computing allows hosts (and the software they execute) to alter their physical location. Despite apparent similarities, the two paradigms are distinct in their treatment of location and movement. This paper seeks to uncover a common foundation for the two paradigms by ...Read More

Advocates of software design patterns claim that using design patterns improves communication between software developers. The controled experiment that we describe in this report tests the hypothesis that software maintainers of well-structured, well-documented software containing design patterns can make changes (1) faster and (2) with less errors if the use of patterns is explicitly documented in the software. The experiment was performed with 22 participants of a university course on C++ and design patterns; it is similar to a previous experiment performed in Karlsruhe. For one of the two experiment ...Read More

Traditionally, a distributed system has been viewed as a collection of fixed computational elements connected by a static network. Prompted by recent advances in wireless communications rechnology, the emerging field of mobile computing is challenging these assumptions by providing mobile hosts with connectivity that may change over time, raising the possibility that hosts may be called upon to operate while only weakly connected to or while completely disconnected from other hosts. We define a concurrent mobile system as one where independently executing coponents may migrate through some space during the ...Read More

Regions of DNA rich in CpG dinucleotides, also known as CpG islands, are often located upstream of the transcription start side in both tissue specific and housekeeping genes. Overall, CPG dinucleotides are observed at a density of 25% the expected level from base composition alone, partially due to 5-methylcytosine decay (Bird, 1993). Since CpG dinucleotides typically occur with low frequency, CpG islands can be distinguished statistically in the genome. Our method of detecting CpG islands involves a heuristic algorithm employing classic changepoint methods and log-likelihood statistics. A Java applet has ...Read More

DNA sequence analysis depends on the accurate assembly of fragment reads for the determination of a consensus sequence. Genomic sequences frequently contain repeat elements that may confound the fragment assembly process, and errors in fragment assembly, and errors in fragment assembly may seriously impact the biological interpretation of the sequence data. Validating the fidelity of sequence assembly by experimental means is desirable. This report examines the use of restriction digest analysis as a method for testing the fidelity of sequence assembly. Restriction digest fingerprint matching is an established technology for ...Read More

Application Management permits the advertising, launching, and configuring of distributed applications created using the Programmers' Playground. Applications can be documented and made available to end-users through the use of application pages on the World Wide Web. The launching and configuring of applications is performed by a brokerage system consisting of an applicatoin broker and one or more hierarchies of module launchers. This document describes how to setup and use the components of the Application Management system.

Cappuccino is a planning tool for topological design of ATM networks. It uses a novel constraint-based approach to ATM network design. Extensibility of the tool is a basic design goal and the tool provides an open interface to incorporate new algorithms.

This report summarizes the results of an architectural study on Terabit Burst Switching. The purpose of this study was to explore alternative architectures for very high performance switching for data communication, using a combination of optical and electronic technologies. We explore two alternative implementations of the burst switching concept in detail, one using a hybrid architecture with an electronic core, and an integrated architecture using an all optical data path. We also briefly discuss an approach using optical TDM. Our results show that using the hybrid architecture, it is feasible ...Read More

The rapid development of Asynchronous Transfer Mode technology in the last 10-15 years has stimulated renewed interest in the design and analysis of switching systems, leading to new ideas for system designs and new insights into the performance and evaluation of such systems. As ATM moves closer to realizing the vision of ubiquitous broadband ISDN services, the design of switching systems takes on growing importance. This paper seeks to clarify the key architectural issues for ATM switching system design and provides a survey of the current state-of-the-art.

In a previous paper [3], one of the authors, gave a worst-case analysis for the Early Packet Discard (EPD) technique for maintaining packet integrity during overload in ATM switches. This analysis showed that to ensure 100% goodput during overload under worst-case conditions, requires a buffer with enough storage for one maximum length packet from every active virtual circuit. This paper refines that analysis, using assumptions that are closer to what we expect to see in practice and examines how EPD performs when the buffer is not large enough to achieve ...Read More