Technical Reports and MS Project Reports

We reconsider several issues related to fragmentation and reassembly in IP. We first reconsider reassembly. We describe a simple expected case optimization that improves reassembly performance to 38 instructions per fragment if the fragments arrive in FIFO order (the same assumption made in header prediction) which has been implemented in the NetBSD kernel. Next, we introduce the new idea of Graceful Intermediate Reassembly (GIR), which is a generalization of the existing IP mechanisms of destination and hop-by-hop reassembly. In GIR, we coalesce the fragments at an intermediate router in order ...Read More

This report describes the design and implementation of a gigabit ATM switching system supporting link rates from 150 Mb/s to 2.4 Gb/s, with a uniquely efficient multicast switch architecture that enables the construction of systems with essentially constant per port costs for configurations ranging from 8 to 4096 ports and system capacities approaching 1- Tb.s. The system design supports many-to-one and many-to-many forms of multicast, in addition to the usual one-to-many. It also provides multicast virtual paths, constant time configuration of multicast connections and an efficient packet-level discard method, that ...Read More

This paper presents the ARAS simulator with which asynchronous instruction pipelines can be modelled, simulated and displayed. ARAS allows one to construct instruction pipelines by preparing various configuration files. Using these files and a number of benchmark programs, performance of the instruction pipelines can be obtained. The performance of asynchronous instruction pipelines can also be compared to synchronous case. Thus, one can decide the optimal design for instruction pipelines in asynchornous or synchronous cases and explore the deisng space of asynchronous instruction pipeline architectures.

This paper outlines a study of MPEG compressed video sequences and simulation of multiplexed video traffic in the ATM environment. A number of statistical characteristics including autocorrelation and variance of MPEG-1 compressed video sequences are used to characterize the 16 sample traces used in this study. From these measurements, a preliminary model is developed which utilizes basic measurements of the individual component video sequences to predict bandwidth requirements and cell loss of the multiplexed video traffic.

We present the design and implementation of Sensus, a practical, secure and private system for conducting surveys and elections over computer networks. Expanding on the work of Fujioka, Okamoto, and Ohta, Sensus uses blind signatures to ensure that only registered voters can vote and that each registered voter only votes once, while at the same time maintaining voters' privacy. Sensus allows voters to verify independently that their votes were counted correctly, and anonymously challenge the results should their votes be miscounted. We outline seven desirable properties of voting systems and ...Read More

We are building a very high performance 1.2 Gb/s ATM network interface chip called the APIC (ATM Port Interconnect Controller). In addition to borrowing userful ideas from a number of research and commercial prototypes, the APIC design embraces several innovative features, and integrates all of these pieces into a coherent whole. This paper describes some of the novel ideas that have been incorporated in the APIC design with a view to improving the bandwidth and latency seen by end-applications. Among the techniques described, Protected DMA and Protected I/O were designed ...Read More

This paper considers the problem of designing ATM networks that are nonblocking with respect to virtual circuit requests, subject to specified constraints on the traffic. In this paper, we focus on global traffic constraints that simply limit the total entering and exiting traffic at each switching system. After reviewing prior results for linear link costs, we introduce a more realistic link cost model, and develop a number of results using it. We also describe a technique for converting tree-structured networks to nonblocking hierarchical networks satisfying limits on the capacity of ...Read More

This paper addresses the problem of topological design of ATM (and similar) communication networks. We formulate the problem from a worst-case point of view, seeking network desings that, subject to specified traffic constraints, are nonblocking for point-to-point and multicast virtual circuits. Within this model we give various conditions under which star networks are optimal or near-optimal. These conditions are approximately satisfied in many common situations making the results of practical significance. An important consequence of these results is that, where they apply, there is no added cost for nonblocking multicast ...Read More

This paper seeks to bridge the gap between theory and practice of real-time scheduling in the domain of multimedia computer systems. We show that scheduling algorithms that are good in theory, often have practical limitations. However when these algorithms are modified based on practical considerations, existing theoretical results cannot be used as they are. In this paper we motivate the need for new scheduling schemes for multimedia protocol processing, and demonstrate their real-time performance in our prototype implementation. We then explain the observed results by analysis and measurement. More specifically, ...Read More

Real-time upcalls (RTUs) are an operating systems mechanism to provide quality-of-service (QoS) guarantees to network applications, and to efficiently implement protocols in user space with (QoS) guarantees. Traditionally, threads (and real-time extensions to threads) have been used to structure concurrent activities in user space protocol implementations. However, preemptive scheduling required for real-time threads leads to excessive context switching, and introduces the need for expensive concurrency control mechanisms such as locking. The RTU mechanism exploits the iterative nature of protocol processing to eliminate the need for locking, and reduce asynchronous preemption, ...Read More

We report a number of new results in generalized caching. This problem arises in modern computer networks in which data objects of various sizes are transmitted frequently. First it is shown that its optimal solution is NP-complete. Then we explore two methods of obtaining nearly optimal answers based on the dynamic programming algorithm that we provided in [5]. These methods enable a trade-off between optimality and speed. It is also shown that LFD (the longest forward distance algorithm which is the optimal policy in the classical case), is no longer ...Read More

Network traffic can be reduced significantly if caching is utilized effectively. As an effort in this direction we study the replacement problem that arises in caching of multimedia objects. The size of objects and the cost of cache misses are assumed non-uniform. The non-uniformity of size is inherent in multimedia objects, and the non-uniformity of cost is due to the non-uniformity of size and the fact that the objects are scattered throughout the network. Although a special case of this problem, i.e. the case of uniform size and cost, has ...Read More

This report describes an ATM Multipoint Connection Caching strategy (AMCC) to control the explosive growth of traffic within the network and at an endpoint in a large Distributed Interactive Simulation (DIS) application such as a battlefield simulation. For very large DIS applications with 100,000 entities, the current method of broadcasting information among entities will no longer be feasible due to computational and network bandwidth limitations. Our scheme divides the simulation space into grids and each grid square or a set of grid squares forms a multicast group. Entities join the ...Read More

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 language and logic for specifying and reasoning about mobile systems, the components of which must operate in a highly decoupled way. In this paper it is argued that Mobile UNITY contributes to ...Read More

Distributed multimedia applications supported by a global electronic infrastructure have tremendous potential for providing users with customized communication and computation environments. Since communication and computation requirements vary by context and change dynamically, it is unlikely that off-the-shelf applications will anticipate the needs of all users. Therefore, empowering end-users to create their own customized applications for both communication and computation is an important challenge. This dissertation presents several mechanisms that enable end-users to create and configure distributed multimedia applications, including end-users construction direct manipulation graphical users interface (GUIs) and application management ...Read More

This paper describes an empirical study of end-users that tested the usability of The Programmers' Playground graphical environment. The Programmers' Playground is a software library and run-time system for constructing distributed multimedia applications. Playground's graphical environment enables end-users to create direct manipulation graphical user interfaces (GUIs) and to dynamically configure communication among distributed application components. In this study, 28 end-users with no prior experience in distributed computing or user interface construction were timed and evaluated on several tasks using our graphical environment. Tasks included the use of direct and indirect ...Read More

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 used in Mobile IP and cellular phones for the unicast problem rely on tracking the mobile unit. Tracking solutions scale badly when mobile nodes move frequently, and do not generalize well to multicast delivery. Our paper proposes a new ...Read More

We present a voice-activated, hands-off, ATM-based video conferencing application. The application, called Vaudeville, features high quality NTSC video, voice-activated audio transmission, audio bridging of two audio streams, and voice-activated video switching. It supports multiple simultaneous multi-party conferences using a scalable multicast mechanism. We describe how Vaudeville was built using a component-based distributed programming environment. We also describe the algorithms used to contorl the audio and video of the applciation. Audio and video are encoded in hardware using an ATM hardware multimedia interface.

Software developers typically must choose between interpreted and compiled environments for their programming activities. However, the current trends toward mobile computing and platform independence suggest moving to a new continuous compilation paradigm that integrates the advantages of each environment. Movement in this direction can already be seen in the development of Sun Microsystems' Java environment. The resulting continuous compiler operates not as a prelude to, but rather in tandem with, program execution. In this thesis we present the results of experiments that compare the performance of the continuous compilation model ...Read More

Design patterns are a topic of great current interest within the object-oriented programming community. The motivation is both economical and intellectual. On one hand, there is the hope of establishing a common culture and language that fosters communicatino and growth in the software engineering field. While a community dominated by empiricism is seeking to achieve higher levels of formality by capturing its experiences in the form of catalogs of design patterns, another community, deeply rooted in formal thinking, is seeking to make its mark on the every day workings of ...Read More

Mobile computing represents a major point of departure from the traditional distributed computing paradigm. The potentially very large number of independent computing units, a decoupled computing style, frequent disconnections, continuous position changes, and the location-dependent nature of the behavior and communication patterns present designers with unprecedented challenges in the areas of modularity and dependability. So far, the literature on mobile computing is dominated by concerns having to do with the development of protocols and services. This paper complements this perspective by considering the nature of the underlying formal models that ...Read More

As computer size continues to decrease and new user interface technologies become more ubiquitous, the conventional keyboard and mouse input interfaces are becoming harder to design into newer machines and less practical for use in some applications. The pen is one input technology more suited for the upcoming generation of smaller computers using direct manipulation interfaces. However, a pen-only user interface relies on continuous gesture and handwriting tecognizers that are often slow, inaccurate, and error prone for command and text entry. Speech recognition is an input modality that can input ...Read More

Distributed stream filtering is a mechanism for implementing a new class of real-time applications with distributed processing requirements. These applications require scalable architectures to support the efficient processing and multiplexing of large volumes of continuously generated data. This paper provides an overview of a stream-oriented model for database query processing and presents a supporting implementation. To facilitate distributed stream filtering, we introduce several new query processing operations, including pipelined filtering that efficiently joins and eliminates duplicates from database streams and a new join method, the progressive join, that joins streams ...Read More

We describe an efficient fair queuing scheme, Leap Forward Virtual Clock, that provides end-to-end delay bounds almost identical to that of PGPS fair queuing, along with throughput fairness. Our scheme can be implemented with a worst-case time O(loglogN) per packet guaranteed delay and throughput fairness. As its name suggests, our scheme is based on Zhang's virtual clock. While the original virtual clock scheme does not achieve throughput fairness, we can modify it with a simple leap forward mechanism that keeps the server clock from lagging too far behind the packet ...Read More

The main economic-theoretic approcahes to the problem of resource allocation make little if any reference to negotiation processes. These processes are fundamentally linguistic, based on the exchange of messages among agents. Communication being so fundamental in the characterization of negotiation processes, the analysis of negotiation must emphasize on the structure of the language in which the negotiations take place. Computer science and particularly Artificial Intelligence have provided interesting insights about that linguistic structure. In the first part of this work we present a brief survey of the literature on resource ...Read More

One of the important features of ATM networks is their ability to support multicast communications. This facilitates the efficient distribution of multimedia information streams (such as audio and video) to large groups of receivers (potentially millions). Because ATM networks do not provide reliable delivery mechanisms, it is up to end systems to provide end-to-end reliability where it is needed. While this is straightforward for point-to-point virtual circuits, it is more difficult for one-to many and many-to-mamy virtual circuits. In this report, we propose some minimal extensions to the hardware of ...Read More

Link striping algorithms are often used to overcome transmission bottlenecks in computer networks. However, traidtional striping algorithms suffer from two major disadvantages. They provide inadequate load sharing in the presence of variable length packets, and may result in non-FIFO delivery of data. We describe a new family of link striping algorithms that solve both problems. Our scheme applies to packets at any layer (physical, data, link, network, and transport) that work over multiple FIFO channels. We deal with variable sized packets by showing how a class of fair queueing algorithms ...Read More

Distributed Radiological Multimedia Conference (DRMC) is a collaborative imaging/multimedia conferencing tool which allows geographically separated physicians to confer over a shared projection radiograph. DRMC utilizes the advantages of high bandwidth and scalability offered by the new Asynchronous Transfer Mode (ATM) network technology. This application is customized for the high quality of displayed images and rapid response to user requests. It allows conferees to: share a common radiograph; each possess an independently controlled globally visible cursor; be able to point to and outline areas on the image to bring it to ...Read More

Synchronized Data Objects (SDOs) are presented as a method of encapsulating, in the datatype definition, synchronization protocols that are used to control information exchange. SDOs are presented in the context of I/O abstraction, a programming model that seeks to separate communication from computation in order to support dynamic end-user configuration of distrivuted applications. SDOs can be used to implement a variety of synchronization paradigms, including remote invalidation, demand-driven data streams, remote procedure call, and promises. An implementation of SDOs is described in the context of The Programmers' Playground, a distributed ...Read More

Large scale storage servers that provide location transparent, interactive access to hundreds or thousands of concurrent, independent clients will be important components of hte furture information super-highway infrastructure. Two key requirements of such servers are as follows: support high parallelism and concurrency in data access to allow large number of access to the same or different data. Second, support independent interactive playout control operations such as fast-forward, rewind, slow-play, pause, resume, random access etc. with minimal latency. This paper assumes a distributed storage server architecture consisting of several high performance ...Read More

In this paper, an asynchronous pipeline instruction simulator, ARAS is presented. With this simulator, one can design selected instruction pipelines and check their performance. Performance measurements of the pipeline configuration are obtained by simulating the execution of benchmark programs on the machine architectures developed. Depending on the simulation results obtained by using ARAS, the pipeline configuration can be altered to improve its performance. Thus, one can explore the design space of aynchronous pipeline architectures.

We describe a new implementation of the BSD callout and timer facilities. Current BSD kernels take time proportional to the number of outstanding timers to set or cancel timers. Our implementation takes constant time to start, stop, and maintain timers; this leads to a highly scalable design that can support thousands of outstanding timers without much overhead. Unlike the existing implementation, our routines are guaranteed to lock out interrupts only for a small, bounded amount of time. We also extend the setitimer() interface to allow a process to have multiple ...Read More

A useful way to design simple and robust protocols is to make them self-stabilitizing. We describe a new general technique for self-stabilization called window washing. We apply this technique to generalized sliding window protocols that work on a number of topologies. This results in simple, efficient, and self-stabilizing protocols. As far as we know, both window washing and generalized sliding window protocols are new ideas. Our protocols can be used for data links, reliable broadcast, and flow control.

The goal of this research is to determine whether declared strategy voting can be an effective tool for group decision-making. Declared strategy voting is a novel group decision-making procedure in which preference is specified using voting strategies - first-order mathematical functions that specify a choice in terms of zero or more parameters. This research will focus on refining the declared strategy voting concept, developing an accessible implementation of declared strategy voting that can be used for mock elections, assessing the potential impacts of declared strategy voting, and evaluating the effectiveness ...Read More

Effective load balancing algorithms are crucial in fully realizing the performance potential of parallel computer systems. This paper proposes a general matrix iterative model to represent a range of dynamic load balancing algorithms. The model and associated performance measures are used to evaluate and compare vairous load balancing algorithms and derive optimal algorithms and associated parameters for a given application and multiprocessor system. The model is parameterized to represent three load balancing algorithms - the random strategy, diffusion and complete redistribution algorithms. The model is validated by comparing the results ...Read More

We present a new tool for automatically generating prototypes of communication protocols on a wide variety of platforms. Our goal is to reduce design time, enhance portability, and accommodate optimizations automatically. Users of the tool are required to provide an abstract implementation of the protocol in C++ without worrying about the underlying operating system specific system calls. Instead, the user employs high-level interface functions provided by the tool to interact with the underlying operating system. Users also need not worry about complex packet formats that involve fields of various bit ...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 consider the problem of PAC-learning the concept class of geometric patterns where the target geometric pattern is a configuration of k points on the real line. Each instance is a configuration of n points on the real line, where it is labeled according to whether or not it visually resembles the target pattern. To capture the notion of visual resemblance we use the Hausdorff metric. Informally, two ...Read More

Real-time upcalls (RTUs) are an operating systems mechanism that can be used by applications to efficiently schedule code segments (or handlers) that must execute periodically. While the mechanism was conceibed to support protocol processing with quality-of-service guarantees for networked multimedia applicatoins it is general enough to be applicable in other domains like real-time image processing. Until now real-time threads have been the only mechanism for implementing protocols in user space with QoS guarantees. The RTU mechanism avoids the implementation complexity of the thread based approach while retaining its ability to ...Read More

Packet filters are a mechanism for efficiently demultiplexing network packets to application endpoints. There is currently no general, formal specification method for packet filters that allows for easy or efficient composition of specifications. In this paper we present an automatic approach that achieves all of these goals. We approach packet filter specification as a language recognition problem: each filter is represented by a context-free grammar, whose language is the set of packets the filter should accept. Thus, packet filters can be formulated through a general, well defined specification; further, the ...Read More

This thesis presents a simple, yet powerful, set of mechanisms for testing and debugging distributed applications consisting of modules that communicate through well-defined data interfaces. The tools allow default or programmer-defined functions to be attached to various communication events so that particular data values at interesting points in the program are made available for testing and debugging. The debugging status of each component of the communication interface can be controlled separately so that various debugging information can be turned on and off during program execution. By attaching breakpoints to programmer-defined ...Read More

Hart's "Ascription of Responsibility and Rights" is where we find perhaps the first clear pronouncement of defeasibility and the technical introduction of the term. The paper has been criticised, disavowed, and never quite fully redeemed. Its lurid history is now being used as an excuse for dismissing the importance of defeasibility. Quite to the contrary, Hart's introduction of defeasibility has uniformly been regarded as the most agreeable part of the paper. The critics' wish that defeasibility could be better expounded along the lines of a Wittgensteinian game-theoretic semantics has largely ...Read More

Previous teaching models in the learning theory community have been batch models. That is, in these models the teacher has generated a single set of helpful examples to present to the learner. In this paper we present an interactive model in which the learner has the ability to ask queries as in the query learning model of Angluin [1]. We show that this model is at least as powerful as previous teaching models. We also show that anything learnable with queries, even by a randomized learner, is teachable in our ...Read More

Constraints are widely recognized as a useful tool for user interface constructino. Through constraints, relationships among user interface components can be defined declaratively, leaving the task of relationship management to a constraint solver. Multi-way constraint solvers supporting constraint hierarchies provide a means to specify preferential constraint relationships with a dynamically changing computation flow, making them especially well suited to interactive user interfaces. However, previous such constraint solvers lack the ability to enforce inequalities or to effectively handle cyclic constraint relationships. These deficiencies limit the problems that could be solved using ...Read More

The Programmers' Playground is a software library and run-time system for creating distributed multimedia applications from collections of reusable software moduels. This paper presents the design and implementation of EUPHORIA, Playground's user interface management system. Implemented as a Playground module, EUPHORIA allows end-users to create direct manipulation graphical user interfaces (GUIs) exclusively through the use of a graphics editor. No programming is required. At run-time, attributes of the GUI state can be exposed and connected to external Playground modules, allowing the user to vosualize and directly manipulate state information in ...Read More

High-bandwidth multimedia applications pose new challenges to error control. These include the support of error control for Continuous Media (CM) streams and the scalable support of error control in multipoint applications where the number of participants is large. Current error control mechanisms provide no support for the above applications. In this report we present new error control mechanisms that provide the required support. Continuous media applications have strict timing requirements which greatly affect recovery. To support continuous media applications we have designed and implemented a point-to-point error control mechanism which ...Read More

Mobile computing represents a major point of departure from the traditional distributed computing paradigm. The potentially very large number of independent computing units, a decoupled computing style, frequent disconnections, continuous position changes, and the location-dependent nature of the behavior and communication patterns present designers with unprecedented challenges in the areas of modularity and dependability. This paper describes a modular approach to specifying and reasoning about of mobile computing. Its novelty rests with the notion of allowing transient (location-dependent) data sharing among programs which move in space. The notation is a ...Read More