All Computer Science and Engineering Research

Overlay networks are becoming a popular vehicle for deploying advanced network services in the Internet. Overlay networks are implemented by deploying service nodes at suitably chosen sites in the network. Service nodes communicate with users through the commodity Internet, while among themselves, they may use either the commodity Internet or dedicated channels. The number of distinct service nodes has a big influence on the operational cost of an overlay network; meanwhile, the distance between service nodes and end users has a big influence on the quality of the service. In... Read More

Overlay networks are becoming a popular vehicle for deploying advanced services in the Internet. One such service is multicast. Unlike conventional IP multicast, which requires universal deployment of network layer mechanisms, the overlay multicast model leverages the existing unicast mechanism and offers many service flexibilities to applications. Implementing multicast without requiring network support eliminates many deployment complexities that IP multicast has faced. However, it also raises new issues in efficient network design. In an earlier paper, we studied multicast routing algorithms designed to optimize resource usage in overlay networks, when... Read More

Multicast is an efficient transmission scheme for supporting group communication in networks. Contrasted with unicast, where multiple point-to-point connections must be used to support communications among a group of users, multicast is more efficient because each data packet is replicated in the network – at the branching points leading to distinguished destinations, thus reducing the transmission load on the data sources and traffic load on the network links. To implement multicast, networks need to incorporate new routing and forwarding mechanisms in addition to the existing are not adequately supported in... Read More

This thesis describes an unsupervised system to learn natural language morphology, specifically suffix identification from unannotated text. The system is language independent, so that is can learn the morphology of any human language. For English this means identifying “-s”, “-ing”, “-ed”, “-tion” and many other suffixes, in addition to learning which stems they attach to. The system uses no prior knowledge, such as part of speech tags, and learns the morphology by simply reading in a body of unannotated text. The system consists of a generative probabilistic model which is... Read More

In recent years, networked sensors are finding use in a variety of different applications ranging from temperature monitoring to battlefield strategy planning. Advances in fabrication techniques have led to the development of sensor-actuator devices called MEMS. It has now become possible to move software closer to where the “action” is, i.e. the sensors themselves. These sensor devices typically have a micro-controller, instruction and data memory, a radio module for wireless communication and an operating system. These devices are severely resource constrained in terms of memory, processing power and energy, since... Read More

Program visualization has the potential to be an important tool for people who seek to observe and understand the behavior of a running computation. This thesis focuses on alleviating barriers to the realization of this potential that pertain to the design of a visualization system and to insufficient knowledge about how people take advantage of program visualizations. Our major contribution is the design of a visualization approach capable of improving user’s performance through the use of economy of information and tasks. We present evidence from our empirical studies that this... Read More

This is the final report For Washington University's Terabit Burst Switching Project, supported by DARPA and Rome Air Force Laboratory. The primary objective of the project has been to demonstrate the feasibility of Burst Switching, a new data communication service, which seeks to more effectively exploit the large bandwidths becoming available in WDM transmission systems. Burst switching systems dynamically assign data bursts to channels in optical datalinks, using routing information carried in parallel control channels.

The flexibility to adapt to new services and protocols without changes in the underlying hardware is and will increasingly be a key requirement for advanced networks. Introducing a processing component into the data path of routers and implementing packet processing in software provides this ability. In such a programmable router, a powerful processing infrastructure is necessary to achieve to level of performance that is comparable to custom silicon-based routers and to demonstrate the feasibility of this approach. This work aims at the general design of such programmable routers and, specifically,... Read More

In this thesis we have studied the potential of Motion JPEG 2000 for video processing and compared its performance with current widely used video coding standards, Motion JPEG, MPEG-2, and MPEG-4. Four key aspects are compared among them, which are compression efficiency, error resilience, perceptual video quality, and computation complexity. Our experiments show that Motion JPEG 2000 provides high compression performance, strong error resilience, good perceptual video quality, and acceptable computation complexity for real-time video processing. Together with a rich set of features inherited from JPEG 2000, such as resolution... Read More

Tracking or localizing a moving target is a difficult task in a distributed sensor network, due to the lack of knowledge of the target's motion and signal noises. Most existing approaches to the problem use only sensory information and may require accurate target's motion models. In this paper, we present a Markovian approach that combines dynamically estimated target's motion models with received sensory information. Without a given motion model, this approach localizes a target in two steps, a location prediction step using dynamically generated motion models and a location correction... Read More

We study a resource allocation problem, which is a central piece of a real-world crew scheduling problem. We first formulate the problem as a hybrid soft constraint satisfaction and optimization problem and show that its worst-case complexity is NP-complete. We then propose and study a set of decision and optimization modeling schemes for the problem. We consider the expressiveness of these modeling schemes for the problem. We consider the expressiveness of these modeling methods. Specifically, we experimentally investigate how these modeling schemes interplay with the best existing systematic search and... Read More

The ongoing increases of line speed in the Internet backbone combined with the need for increased functionality of network devices presents a major challenge. These demands call for the use of reprogrammable hardware to provide the required flexible, high-speed functionality, at all network layers. The Field Programmable Port Extender (FPX) provides such an environment for development of networking components in reprogrammable hardware. We present a framework to streamline and simplify networking applications that process ATM cells, AAL5 frames, Internet Protocol (IP) packets and UDP datagrams directly in hardware.

In response to the increasing network speeds, many operations in IP routers and similar devices are being made more efficient. With the advances in other areas of packet processing, the verification and regeneration of cyclic redundancy check (CRC) codes of the data link layer is likely to become a bottleneck in the near future. In this paper, we present a mechanism to defer CRC verification without compromising reliability. This opens the possibility of incremental updates of the CRC. We introduce a new high-speed technique and present efficient implementation, speeding up... Read More

The ongoing exponential increase of line speed in the Internet and combined with the uncountable requests for increased functionality of network devices presents a major challenge. These demands call for the use of reprogrammable hardware to provide the required flexible high-speed functionaltiy. The Field Programmable Port Extender (FPX) provides such an environment for development of networking components in reprogrammable hardware. We present the high-speed IP routing components in reprogrammable hardware. We present the high-speed IP routing module "OBIWAN" (Optimal Binary search IP lookup for Wide Area Networks) built on top... Read More

The provisioning of dynamic forms of services is becoming the main stream of today's network. In this paper, we focus on services assisted by network servers and different forms of associated sessions. We identify two types of services: transparent, where the session is unaware of the server location, and configurable, where the sessions need to be configured to use their closest server. For both types we formalize the problem of optimally placing network servers and introduce approximated solutions. We present simulation result of approximations and heuristics. We also solve the... Read More

Scheduling problems arise each time there is some form of resource contention. The problem addressed by scheduling disciplines is that of ordering the access to contended resources. The ordering is typically based on either (1) properties that are exposed by the entities that compete for the resource (like a deadline), or by (2) external properties (like the arrival order), or (3) a combination of both. In literature there exist many different scheduling algorithms, each of which has certain properties and an associated application domain. All these scheduling disciplines are based... Read More

This paper describes the architecture of the Smart Port Card (SPC) designed for use with the Washington University Gigabit Switch. The SPC uses an embedded Intel Pentium processor running open-source NetBSD to support network management and active networking applications. The SPC physically connects between a switch port and a normal link adapter, allowing cell streams to be processed as they enter or leave the switch. In addition to the hardware architecture, this paper describes current and future applications for the SPC.

Random Access Memory (RAM) is a common resources needed by networking hardware modules. Synchronous Dynamic RAM (SDRAM) provides a cost effective solution for such data storage. As the packet processing speeds in the hardware increase memory throughput can be a bottleneck to achieve overall high performance. Typically there are multiple hardware modules which perform different operations on the packet payload and hence all try to access the common packet buffer simultaneously. This gives rise to a need for a memory controller which arbitrates between the memory requests made by different... Read More

One goal of any genome project is the elucidation of hte primary sequence of DNA contained within a given species. While the availability ot the primary sequence itself is valuable, it does not reach its full potential until i has been annotated. Generally defined, annotation is descriptive information or commentary added to text, in this case genomic sequence. Without a mechanism for collecting, recording, and disseminating community-based annotation, a valuable source of information is severely diminshed. In this report I outline the design and implementation of a Distributed Annotation System... Read More

While hardware plugins are well suited for processing data with high throughput, software plugins are well suited for implementing complex control functions. A plugin module has been implemented for the FPX that executes software on an embedded soft-core processor. By including this module in an FPX design, it is possible to implement active networking functions on the FPX using both hardware and software. The KCPSM, an 8-bit microcontroller developed by Xilinx Corp., has been embedded into an FPX module. The module includes circuits to be reprogrammed over the network and... Read More

The client-server model continues to dominate distributed computing with increasingly more flexible variants being deployed. Many are centered on the notion of discovering services at run time and on allowing any system component to act as a service provider. The result is a growing reliance on the service registration and discovery mechanisms. This paper addresses the issue of facilitating such service provision capabilities in the presence of (logical and physical) mobility exhibited by applications executing over ad hoc networks. The solution being discussed entailes a new kind of service model,... Read More

Field Programmable Gate Arrays (FPGAs) can be partially reconfigured to implement Dynamically loadable Hardware Plugin (DHP) modules. A tool called PARBIT has been developed that transforms FPGA configuration bitfiles to enable DHP modules. With this tool it is possible to define a partial reconfigurable area inside the FPGA and download it into a specified region of the FPGA device. One or more DHPs, with different sizes can be implemented using PARBIT.

The design of ad hoc mobile applications often requires the availability of a consistent view of the application state among the participating hosts. Such views are important because they simplify both the programming and verification tasks. Essential to constructing a consitent view is the ability to know what hosts are within proximity of each other, i.e., form a group in support of the particular application. In this paper we propose a protocol that allows hosts within communication range to maintain a consistent view of the group membership despite movement and... Read More

Packets in the Internet can experience large queueing delays during busy periods. Backbone routers are generally engineered to have large buffers, in which packets may wait as long as half a second (assuming FIFO service, longer otherwise). During congestion periods, these bufferfs may stay close to full, subjecting packets to long delays, even when the intrinsic latency of the path is relatively small. This paper studies the performance improvements that can be obtained by using more sophisticated packet schedulers, than are typical of Internet routers. The results show that the... Read More

This paper describes the design, implementation, and performance of an open, high-performance, dynamically reconfigurable Multi-Service Router (MSR) being developed at Washington University in St. Louis. This router provides an experimentation platform for research on protocols, router software, and hardware design, network management, quality of service and advanced applications. The MSR has been designed to be flexible, without sacrificing performance. It support gigabit links and uses a scalable architecture suitable for supporting hundreds or even thousands of links. The MSR's flexibility makes it an ideal platform for experimental research on dynamically... Read More

Soft constraint minimization problems (SCMPs) contain hard constraints that cannot be violated and soft constraints that may be violated but carry penalties if not satisfied. In this paper, we first extend local search, WalkSAT in particular, to SCMPs and study the existing SAT encoding schemes for SCMPs. We propose a general encoding method called k-encoding. We then investigate the effects of local search neiborhood structures introduced by encoding schemes and analyze the anytime performance of extended WalkSAT using different encoding methods. Our experimental results on various graph coloring problems show... Read More

In this proposal, we consider the problem of resource reservation for Integrated Services (IntServ) and Differentiated Services (DiffServ) networks. Current approaches for resource reservation in INtegrated Service Networks adopt an all-or-nothing approach, where partially acquired resources must be released if resources are not available at all routers on the chosen path. Furthermore, under high load, end-systems must retry requests repeatedly leading to inefficient allocation and increased traffic. We propose a new approach called Deferred REServation (DERS) that substantially improves performance (reduces the overall cell rejection probability and increases link utilization)... Read More

This paper studies the performance of deferred resource reservation in data networks. Conventional resource reservation protocols, such as PNNI and RSVP adopt an all-or-nothing approach, where partially acquired resources must be released if resources are not available at all links on the chosen path. During periods of high network load, this leads users to retry requests repeatedly, adding control traffic at exactly the time when the network's capacity to process that control traffic is exhausted. Deferred REServation (DRES) can significantly improve performance by reducing the overall call rejection probability, allowing... Read More

To provide flexibility in deploying new protocols and services, general-purpose processing engines are being placed in the datapath of routers. Such network processors are typically simple RISC multiprocessors that perform forwarding and custom application processing of packets. The inherent unpredictability of execution time of arbitrary instruction code poses a significant challenge in providing QoS guarantees for data flows that compete for such processing resources in the network. However, we show that network processing workloads are highly regular and predictable. Using estimates of execution times of various applications on packets of... Read More

Multi-dimensional scaling is an analysis tool which transforms pairwise distances between points to an embedding of points in space which are consistent with those distances. Two recent techniques in statistical patter recognition, locally linear embedding (LLE) and Isomap, give a mechanism for finding the structure underlying point sets for which comparisons or distances are only meaningful between nearby points. We give a direct method to extend the embedding algorithm to new topologies, finding the optimal embedding of points whose geodesic distance on a surface mathes the given pairwise distance measurements.... Read More

The recent popularity of catadioptic and multi-camera imaging systems indicates a need to create formal models for general, non-perspective camera geometries. Development of algorithmic tools for interpreting images from a generalized camera model will lead to a better understanding of how to design camera systems for particular tasks. Here we define the corollary to epi-polar constraints for standard cameras - the relationship between two images of a scene taken by generalized cameras from viewpoints related by discrete or differential motions.

Video application over the Internet are getting increasingly popular because of the explosive growth of the Internet. However, video packets loss due to network congestions can degrade the video quality substantially. In this paper, we propose a transmission scheme for Motion-JPEG2000. It can be implemented in an active network environment efficiently. Our simulation shows that our scheme gracefully adapts to network congestion and improves the quality of video transmission in congested IP networks.

Optical Burst Switching (OBS) is an experimental network technology that enables the construction of very high capacity routers, using optical data paths and electronic control. In this paper, we study two designs for wavelength converting switches that are suitable for use in optical burst switching systems and evaluate their performance. Both designs use tunable lasers to implement wavelength conversion. One is strictly nonblocking design, that also requires optical crossbars. The second substitutes Wavelength Grating Routers (WGR) for the optical crossbars, reducing cost, but introducing some potential for blocking. We show... Read More

Termination detection, a classical problem in distributed computing, is revisited in the new setting provided by the emerging mobile computing technology. A simple solution tailored for use in ad hoc networks is employed as a vehicle for demonstrating the applicability of formal requirements and design strategies to the new field of mobile computing. The approach is based on well understood techniquest in specification refinement, but the methodology is tailored to mobile applications and helps designers address novel concerns such as the mobility of hosts, transient interactions, and specific coordination constructs.... Read More

Context-Aware computing is characterized by the ability of a software system to continuously adapt its behavior to a changing environment over which it has little or no control. Previous work along these lines presumed a rather narrow definition of context, one that was centered on resources immediately available to the component in question, e.g., communication bandwidth, physical location, etc. This paper explores context-aware computing in the setting of ad hoc networks consisting of numerous mobile hosts that interact with each other opportunistically via transient wireless interconnections. We extend the context... Read More

As computing devices become smaller and wireless networking technologies improve, the popularity of mobile computing continues to rise. In today's business world, many consider devices such as cell phones, PDAs, and laptops as essential tools. As these and other devices become increasingly independent of the wired infrastructure, new kinds of applications that assume an ad hoc network infrastructure will need to be deployed. Such a setting poses new challenges for the software developer, e.g., the lack of an established network topology, bandwidth limitations, and frequent disconnections. In this paper, we... Read More

We propose a new network and system architecture for multicast in the Internet. Our main objectives are to find a cost-effective way to scale to a large number of multicast groups whose members are geographically dispersed, and to enable small and less capable devices to participate in group communications. In order to preserve the efficiency of data distribution gained by multicast, while avoiding the control complexity previously exhibited by IP multicast, we propose the use of an overlay network for multicast services. We construct "virtual" multicast trees, which consist of... Read More

Multicast servises can be provided either as a basic network service or as an application-layer service. Higher level multicast implementations often provide more sophisticated features, and since they don't require network supoprt for multicast, they can provide multicast services, where no network layer support is available. Overlay multicast networks offer an intermediate option, potentially combining the flexibility and advanced features of application layer multicast with the greater efficiency of network layer multicast. Overlay multicast networks play an important role in the Internet. Indeed, since Internet Service Providers have been slow... Read More

The Field-programmable Port eXtender (FPX) provides dynamic, fast, and flexible mechanisms to process data streams at the ports of the Washington University Gigabit Switch (WUGS-20). By performing all computations in FPGA hardware, cells and packets can be processed at the full line speed of the transmission interface, currently 2.4 Gbits/sec. In order to design and implement portable hardware modules for the Reprogrammable Application Devide (RAD) on the FPX board, all modules should conform to a standard interface. This standard interface specifies how modules receive and transmit ATM cells of data... Read More

The Field-programmable Port eXtender (FPX) provides dynamic, fast, and flexible mechanisms to process data streams at the ports of the Washington University Gigabit Switch (WUGS-20). In order to facilitate the design and implementation of portable hardware modules for the Reprogrammable Application Device (RAD) on the FPX board, infrastructure components have been developed. These components abstract application module designers from device-specific timing specifications of off-chip memory devices, as well as processing system-level control cells. This document describes the design and internal functionality of the infrastructure components and is intended as a... Read More

Continuing growth in optical link speeds places increasing demands on the performance of Internet routers, while deployment of embedded and distributed network services imposes new demands for flexibility and programmability. IP adress lookup has become a significant performance bottleneck for the highest performance routers. New commercial products utilize dedicated Content Addressable Memory (CAM) devides to achieve high lookup speeds. This paper describes an efficient, scalable lookup engine design, able to achieve high-performance with the use of a small portion of a reconfigurable logic device and a commodity Random Access Memory... Read More

Users and developers of visualization tools must deal with the problem of specifying what information to show and how to represent it. Typically, the user's focus of interest will change over time, and the specifications must change with the user's interests. Techniques for the simple, direct, and intuitive creation and refinement of these specifications can be useful. In this paper we show how legends, a natural element of graphical displays, may be used as a direct and unobstrusive interaction device through which users may interactively specify new visualizations and animations.

This report summarizes progress on Washington University's Terabit Burst Switching Project, supported by DARPA and Rome Air Force Laboratory. This project seeks to demonstrate the feasibility of Burst Switching, a new data communication service which can more effectively exploit the large bandwidths becoming available in WDM transmission systems, than conventional communication technologies like ATM and IP-based packet switching. Burst switching systems dynamically assign data bursts to channels in optical data links, using routing information carried in parallel control channels. The project will lead to the construction of a demonstration switch... Read More

This report summarizes progress on Washington University’s Terabit Burst Switching Project, supported by DARPA and Rome Air Force Laboratory. This project seeks to demonstrate the feasibility of Burst Switching, a new data communication service which can more effectively exploit the large bandwidths becoming available in WDM transmission systems, than conventional communication technologies like ATM and IP-based packet switching. Burst switching systems dynamically assign data bursts to channels in optical data link, using routing information carried in parallel control channels. The project will lead to the construction of a demonstration switch... Read More

When using an on-demand media streaming system on top of a network with Multicast support, it is sometimes more efficient to use broadcast to distribute popular content. There has been a lot of research in broadcasting on-demand content to multiple, asynchronous receivers. In this paper, we propose a family of novel, practical techniques for broadcasting on-demand media, which achieve lowest known server/network bandwidth usage and I/O efficient client buffer management, while retaining the simplicity of a frame-based single channel scheme.

The growing deployment of wireless local area networks (WLANs) in corporate environments, the increasing number of wireless Internet service providers and demand for quality of service support create a need for controlled sharing of wireless bandwidth. In this technical report a method for using long-term channel-state information in order to control the sharing of wireless bandwidth is studied. The algorithm enables an opera-tor of a WLAN to equalize the revenue/cost for each customer in the network and to control the link-sharing based on a combination of user-centric and operator-centric fact-tors.... Read More

Active Networking is the basis for a range of new and innovative applications that make use of computational resources inside network routers. One such application is Aggregated Hierarchical Multicast, which aims at implementing efficient many-to-many communication. In certain scenarios it is possible to transmit less accurate, aggregated data and thus achieve better scalability. Using Active Networks, this aggregation computation can be done transparently by network routers without end system support. We present how aggregated data streams can be structured in a hierarchical fashion to allow easy access of data at... Read More

The new ISO/ITU-T standard for still image coding, JPEG2000, has been shown to provide superior coding efficiency to the previous standard, JPEG. Because of the superb performance of JPEG2000, it is reasonable to argue that Motion-JPEG2000, the corresponding moving picture coding standard of JPEG2000, has equally outstanding performance. However, there has not been a sufficient performance evaluation of Motion-JPEG2000. To this end, we have studied the potential of Motion-JPEG2000 for video processing. Our experiments show that Motion-JPEG2000 provides high compression performance, strong error resilience, and good perceptual image quality. Together... Read More

While advances in computer and communications technology have made the network ubiquitous, they ahve also rendered networked systems vulnerable to malicious attacks orchestrated from a distance. These attacks, usually called cracker attacks or intrusions, start with crackers infiltrating a network through a vulnerable host and then going on to launch further attacks. Crackers depend on increasingly sophisticated techniques like using distributed attack sources. On the other hand, software that guards against them remains rooted in traditional centralized techniques, presenting an easily-targetable single point of failure. Scalable, distributed network intrusion prevention... Read More

Many real-world problems involve constraints that cannot be all satisfied. The goal toward an overconstrained problem is to find solutions minimizing the total number of constraints violated. We call such a problem constraint minimization problem (CMP). We study the behavior of the phase transitions and backbones of CMP. We first investigate the relationship between the phase transitions of Boolean satisfiability, or precisely 3-SAT (a well-studied NP-complete decision problem), and the phase transitions of MAX 3-SAT (an NP-hard optimization problem). To bridge the gap between the easy-hard-easy phase transitions of 3-SAT,... Read More

The provision of advanced computational services within networks is rapidly becoming both feasible and economical. We present a general approach to the problem of configuring application sessions that require intermediate processing by showing how the session configuration problem can be transformed to a conventional shortest path problem. We show, through a series of examples, that the method can be applied to a wide variety of different situations.

The purpose of this document is to present the overview of tte plugin management architecture and the description of the software developed for the scalable, high performance active network node project in Washington University, St. Louis. The plugin management is a user space daemon program that runs at the code(plugin) server and at the active network component of a router or a switch port processor. The running programs cooperate to load plugins from the code server to the active network component. This software is intended to be used among multiple... Read More

Synthesizer is a pattern language for designing digital synthesizers using modular synthesis in software to generate sound. Software developed according to this pattern language emulates the abilities of an analog synthesizer. Modular synthesis is one of the oldest sound synthesis techniques. It was used in the earliest analog synthesizers, like the Moog [1] and ARP [2]. These machines introduced the oscillator-filter-amplifier paradigm, where sound generated by an oscillator is passed through a series of filters and amplifers before being sent to a speaker. These first machines had physical modules through... Read More

Active networks allow customized processing of data traffic within the network which can be used by applications to improve the quality of their sessions. To simplify development of active applications in a heterogeneous environment, we propose active network pipes as a programming abstraction to specify transmission and processing requirements. We describe a routing algorithm that maps application session requirements onto network resources and determines an optimal route through the network transiting all required processing sites. Additionally, we propose a network software architecture to implement the functionality required to support active... Read More

The FPX provides simple and fast mechanisms to process cells or packets. By performing all computations in FPGA hardware, cells and packets can be processing at the full line speed of the card [currently 2.4 Gbits/sec]. A sample application, called 'Hello World' has been developed that illustrates how easily an application can be implemented on the FPX. This application uses the FPGA hardware to search for a string on a particular flow and selectively replace contents of the payload. The resulting circuit operates at 119 MHz on a Xilinx XCV... Read More

For systems with a large number of FPGAs, where a design is instantiated across multiple FPGAs in a chassis, an efficient mechanism of programming the FPGA devices is needed. The mechanism described herein allows multiple FPGAs to be programmed across a backplane. Only a single configuration PROM is required to store the configuration for the multiple instances of the design. When the system boots, all FPGAs are programmed in parallel. This design is applicable to any system which contains a multiple board system which has instances of identical FPGA implementations... Read More

This paper explores the range of constructs and issues facing the designer of mobile code systems which allow for the unit of mobility to be finer-grained than that of execution. Mobile UNITY, a notation and proof logic for mobile computing, provides for this research a clean abstract setting, i.e., unconstrained by compilation and performance considerations traditionally associated with programming language design. Within the context of Mobile UNITY, we take the extreme view that every line of code and every variable declaration is potentially mobile, i.e., it may be duplicated and/or... Read More

The IP multicast model allows scalable and efficient multi-party communication, particularly for groups of large size. However, deployment of IP multicast requires substantial infrastructure modifications and is hampered by a host of unresolved open problems such as reliability, flow and congestion control, security and access control. Motivated by these problems, we have designed and implemented ALMI, an application level group communication middleware, which does not rely on network infrastructure support and thus, allows accelerated deployment and simplified configuration at the cost of a relatively small increase in traffic load. ALMI... Read More

LIME is a middleware supporting the development of applications that exhibit physical mobility of hosts, logical mobility of agents, or both. LIME adopts a coordination perspective inspired by work on the Linda model. The context for computation, represented in Linda by a globally accessible, persistent tuple space, is represented in LIME by transient sharing of the tuple spaces carried by each individual mobile unit. Linda tuple spaces are also extended with a notion of location and with the ability to react to a given state. The hypothesis underlying our work... Read More

In this paper we consider the automatic discovery of design (programming) patterns. While patterns have surfaced as an effective mechanism for authoring and understanding compelx software, popular languages lack facilities for direct specification of patterns or verification of pattern usage in program specifications. Static analysis for patterns is provably undecidable; we focus on discovery and verification of patterns by analyzing dynamic sequences of method calls on object. We show a proof-of-concept of our approach by presenting the results of analyzing a Java program for Iterator patterns.

The design of ad hoc mobile applications often requires the availability of a consistent view of the application state among the participating hosts. Essential to constructing a consistent view is the ability to know what hosts are within proximity of each other, i.e., form a group in support of the particular application. In this paper we propose an algorithm that allows hosts within communication range to maintain a consistent view of the group membership despite movement and frequent disconnections. The novel features of this algorithm are its reliance on location... Read More

Mobility entails the study of systems in which components change location, in a voluntary or involuntary manner, and move across a space that may be defined to be either logical or physical. Coordination is concerned with what happens when two or more components come in contact with each other. In this paper we put forth a working definition of coordinatoin, we construct argumetns that demonstrate that coordination is central to understanding mobility, we explore the intellectual richness of the notion of coordination, and we consider the practical implications of coordination-centered... Read More

Current reliable multicast protocols do not have scalable congestion control mechanisms and this deficiency leads to concerns that multicast deployment may endanger stability of the network. In this paper, we present a sender-based approach for multicast congestion control targeted towards reliable bulk data transfer. We assume that there are a few bottleneck links in a large scale multicast group at any time period and these bottlenecks persist long enough to be identified and adapted to. Our work focus on dynamically identifying the worst congested path in the multicast tree and... Read More

We present a new algorithm and framework for dynamic routing of bandwidth guaranteed flows. The problem is motivated by the need to dynamically set up bandwidth guaranteed paths in carrier and ISP networks. Traditional routing algorithms such as minimum hop routing or widest path routing do not take advantage of any knowledge about the traffic distribution or ingress-egress pairs, and therefore can often lead to severe network underutilization. Our work is inspired by the recently proposed "minimum interference routing" algorithm (MIRA) of Kodialam and Lakshman, but it improves on their... Read More

Distributed object computing (DOC) middleware shields developers from many tedious and error-prone aspects of programming distribued applications. Without proper support from the middleware, however, it can be hard to evolve distributed applications after they are deployed. Therefore, DOC middleware should support meta-programming mechanisms, such as smart proxies and interceptors, that improve the adaptability of distributed applications by allowing their behavior to be modified without drastically changing existing software. This paper presents three contributions to the study of metaprogramming mechanisms for DOC middleware. First, it illustrates, compares, and contrasts several meta-programming... Read More

Demands for flexible processing has moved general-purpose processing into the data path of networks. With the development of System-On-a-Chip technology, it is possible to put several processors with memory and I/O components on a single ASIC. We present a model of such a system with a simple performance metric and show how the number of processors and cache sizes can be optimized for a given workload. Based on a telecommunications benchmark we show the results of such an optimization and discuss how specialied hardware and appropriate scheduling can further improve... Read More

We use the SRB (Storage Request Broker) middleware to design and implement a storage archival system which will be used to archive Neuroscience data. As part of the design process, we developed and used an experimenter's workbench to measure SRB performance. These experiments improved our understanding of both the functionality and the performance of the SRB. This technical report describes the scripts in the experimenter's workbench, the archiving scripts, and performance measurements.

This paper proves that the revenue equivalence theorem ceases to hold for auctions without common knowledge about the agents' prior beliefs. That is, different auction forms yield different expected revenue. To prove this, an auction game is converted to a Bayesian decision problem with an infinite hierarchy of beliefs. A general solution for such Bayesian decision problems is proposed. The solution is a generalization of the standard Bayesian solution and coincides with it for finite belief trees and for trees representing common knowledge. It is shown how the solution generalizes... Read More

To be an effective platform for performance-sensitive real-time and embedded applications, off-the-shelf OO middleware like CORBA, DCOM, and Java RMI must preserve communication-layer quality of service (QoS) properties to applications end-to-end. However, conventional OO middleware interoperability protocols, such as CORBA's GIOP/IIOP or DCOM's MS-RPC, are not well suited for applications that cannot tolerate the message footprint size, latency, and jitter associated with general-purpose messaging and transport protocols. It is essential, therefore, to develop standard plugable protocols frameworks that allow custom messaging and transport protocols to be configured flexibly and used... Read More

In this paper, we take the extreme view that every line of code is potentially mobile, i.e., may be duplicated and/or moved from one program context to another on the same host or across the network. Our motivation is to gain a better understanding of the range of constructs and issues facing the designer of a mobile code system, in a setting that is abstract and unconstrained by compilation and performance considerations traditionally associated with programming language design. Incidental to our study is an evaluatoin of the expressive power of... Read More

Advances in wireless communication and network computing technologies make possible new kinds of applications involving transient interactions among physical components that move across a wide range of spaces, from the confines of a room to the airspace across an ocean, and require no fixed networking infrastructure to communicate with one another. Such components may come together to form ad hoc networks for the purpose of exchanging information or in order to engage in cooperative task-oriented behaviors. Ad hoc networks are assembled, reshaped and taken apart as components move in and... Read More

The provision of a reliable communication infrastructure for mobile agents is still an open research issue. The challenge to reliability we address in this work does not come from the possibility of faults, but rather from the mere presence of mobility, which slightly complicates the problem of ensuring the delivery of information even in a fault-free network. For instance, the asynchronous nature of message passing and agent migration may cause situations where messages forever chase a mobile agent that moves frequently from one host to another. Current solutions rely on... 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. An approach to this is to have a single home node constantly track the current location of the mobile unit and forward messages to this location. One problem with this approach is that during the update to the home agent after movement,... Read More

In this paper, we propose a new framework called Active Network Management and Control (ANMAC) for the management and control of high speed networks. The software architecture in ANMAC allows routers to execute dynamically loadable kernel plug-in modules which perform diagnostic functions for network management. ANMAC uses mobile probe packets to perform efficient resource reservation (using our novel reservation scheme), facilitate feedback-based congestion control, and to provide "distributed debugging" of complex anomalous network behavior. ANMAC also provides security measures against IP spoofing, and other security attacks. The network manager has... Read More

With wide deployment of high-speed networks such as vBNS today, video-conference applications over WANs have become increasingly feasible. MMX has proven to be a good desktop video-conference devide for local ATM networks. Now, ALX has been designed to extend MMX's video conferencing capability to IP-over-ATM WANs such as vBNS. In this report, we discuss a floor control protocol for ALX video-conference applications. We first show how an "ideal" protocol should behave to meet our requirements. Then we compare three protocols based on distributed algorithms, and a protocol based on a... Read More

The term distributed computing conjures the image of a fixed network structure whose nodes support the execution of processes that communicate with each other via messages traveling along links. Peer-to-peer communication is feasible but client-server relationships dominate. More recently, servers have been augmented with brokerage capabilities to facilitate discovery of available services. Stability is the ideal mode of operation; changes are relatively slow; even in the case of failure, nodes and links are expected eventually to come back up. By contrast, mobility represents a total meltdown of all the stability... Read More

Pattern matching techniques have been useful in solving many problems associated with computer science, including data compression (Chrochemore and Lecroq, 1996), data encryption (RSA Laboratories, 1993), and computer vision (Grimson and Huttenlocher, 1990). In recent years, developments in molecular biology have led to large scale sequencing of genomic DNA. Since this data is being produced in such rapid fasion, tools to analyze DNA segments are desired. The goal here is to discuss various techniques and tools for solving various pattern matching questions in computational biology, including optimal sequence alignment, multiple... Read More

The Human Genome Project (HGP) has led to the deposit of human genomic sequence in the form of sequenced clones into various databases such as the DNA Data Bank of Japan (DDBJ) (Tateno and Gojobori, 1997), the European Molecular Biology Laboratory (EMBL) Nucleotide Sequence Database (Stoesser, et. al., 1999), and GenBank (Benson, et. al., 1998). Many of these sequenced clones occur in regions where sequencing has taken place either within the same sequencing center or other centers throughout the world. The assembly of extended segments of genomic sequence by looking... Read More

In automated negotiation systems consisting of self-interested agents, contracts have traditionally been binding. Leveled commitment contracts - i.e. contracts where each party can decommit by paying a predetermined penalty - were recently shown to improve Pareto efficiency even if agents rationally decommit in Nash equilibrium using inflated thresholds on how good their outside offers must be before they decommit. This paper operationalizes the four leveled commitment contracting protocols by presenting algorithms for using them. Algorithms are presented for computing the Nash equilibrium decomitting thresholds and decommitting probabilities given the contract... Read More

Combinatorial auctions, i.e. auctions where bidders can bid on combinations of items, tend to lead to more efficient allocations than traditional auctions in multi-item auctions where the agents' valuations of the items are not additive. However, determining the winners so as to maximize revenue is NP-complete. First, existing approaches for tackling this problem are reviewed: exhaustive enumeration, dynamic programming, approximation algorithms, and restricting the alloable combinations. Then we present our search algorithm for optimal winner determination. Experiments are shown on several bid distributions. The algorithm allows combinatorial auctions to scale... Read More

This paper presents eMediator, a next generation electronic commerce server that demonstrates some ways in which AI, algorithmic support, and game theoretic incentive engineering can jointly improve the efficiency of ecommerce. First, its configurable auction house includes a variety of generalized combinatorial auctions, price setting mechanism, novel bid types, mobile agents, and user support for choosing an auction type. Second, its leveled commitment contract optimizer determines the optimal contract price and decommitting penalties for a variety of leveled commitment contracting protocols, taking into account that rational agents will decommit insincerely... Read More

This paper analyzes automated distributive negotiation where agents have firm deadlines that are private information. The agents are allowed to make and accept offers in any order in continuous time. We show that the only sequential equilibrum outcome is the one where the agents wait until the first deadline, at which point that agent concedes everything to the other. This holds for pure and mixed strategies. So, interestingly, rational agents can never agree to a nontrivial split because offers signal enough weakness of bargaining power (early deadline) so that the... Read More

In computational markets utilizing algorithms that establish a general equilibrium, competitive behavior is usually assumed: each agent makes its demand (supply) decisions so as to maximize its utility (profit) assuming that it has no impact on market prices. However, there is a potential gain from strategic behavior via speculating about others because an agent does affect the market prices, which affect the supply/demand decisions of others, which again affect the market prices that the agent faces. Determining the optimal strategy when the speculator has perfect knowledge about the other agents... Read More

In automated negotiation systems consisting of self-interested agents, contracts have traditionally been binding. Leveled commitment contracts - i.e. contracts where each party can decommit by paying a predetermined penalty - were recently shown to improve expected social welfare even if agents decommit insincerely in Nash equilibrium. Such contracts differ based on whether agents have to declare their decommitting decisions sequentially or simultaneously, and whether or not agents have to pay the penalties if both decommit. For a given contract, these protocols lead to different decommitting thresholds and probabilities. However, this... Read More

Current IP routers are stateless: they forward individual packets based on the destination address contained in the packet header, but maintain no information about the application or flow to which a packet belongs. This stateless service model works well for best effort datagram delivery, but is grossly inadequate for applications that require quality of service guarantees, such as audio, video, or IP telephony. Maintaining state for each flow is expensive because the number of concurrent flows at a router can be in the hundreds of thousands. Thus, stateful solutions such... Read More

Internet routers forward packets based on the destination address of a packet. A packet's address is matched against the destination prefixes stored in the router's forwarding table, and the packet is sent to the output interface determined by the longest matching prefix. While some existing schemes work well for IPv4 addresses, we believe that none of the current schemes scales well to IPv6, especially when fast updates are required. As the Internet evolves into a global communication medium, requiring multiple addresses per user, the switch to longer addresses (e.g. IPv6)... Read More

This report summarizes progress on Washington University's Terabit Burst Switching Project, supported by DARPA and Rome Air Force Laboratory. This project seeks to demonstrate the feasibility of Burst Switching, a new data communication service which can more effectively exploit the large bandwidths becoming available in WDM transmission systems, than conventional communication technologies like ATM and IP-based packet switching. Burst switching systems dynamically assign data bursts to channels in optical data links, using routing information carried in parallel control channels. The project will lead to the construction of a demonstration switch... Read More

Current research in Active Networking is focused on developing software architectures and defining funtionality of Execution Environments. While active network systems show superior functionality compared to traditional networks, they only operate at substantially lower link speeds. To increase the acceptance of Active Network in environments where link speeds of several Gb/s are common, we propose a hardware architecture that performs high-speed packet handling while providing the same flexibility as a common software system. The design exploits the independence between data streams for parallel processing. To measure the impact of different... Read More

This paper presents a benchmark, CommBench, for use in evaluating and designing telecommunications network processors. The benchmark applications focus on small, computationally intense program kernels typical of the network processor environment. The benchmark is composed of eight programs, four of them oriented towards packet header processing and four oriented towards data stream procesing. The benchmark is defined and various characteristics of the benchmark are presented. These include instruction frequencies, computational complexity, and cache performance. These measured characteristics are compared to the SPEC benchmark which has traditionally been used in evaluating... Read More

Active networking is a general approach to incorporating general-purpose computational capabilities within the communications infrastructure of data networks. This paper proposes a design of a scalable, high performance active router. This is used as a vehicle for studying the key design issues that must be resolved to allow active networking to become a mainstream technology.

The last few years have seen the development of a model for Integrated Services Internet, which extends the traditional Internet by adding multiple service classes in addition to the traditional best effort service class, and a signaling protocol called RSVP for applications to reserve resources. While this framework has been standardized in the IETF WGs and the RSVP protocol has been defined, there has been no movement towards a commercial implementation of this framework, principally due to its perceived complexity and lack of scalability. This paper analyzes RSVP, discusses some... Read More

Present day routers typically employ monolithic operating systems which are not easily upgraded and extensible. WIth the rapid rate of protocol development it is becoming increasingly important to dynamically upgrade router software in an incremental fashion. We have designed and implemented a high performance, modular, extended integrated services router software architecture in the NetBSD operating system kernel. This architecture allows code modules, called plugins, to be dynamically added and configured at run time. One of the novel features of our design is the ability to bind different plugins to individual... Read More

We study an on-line problem that is motivated by the networking problem of dynamically adjusting delays of acknowledgments in the Transmission Control Protocol (TCP). The theoretical problem we study is the following. There is a sequence of n packet arrival times A = and a look-ahead coefficient L. The goal is to partition A into k subsequences sigma1, sigma2, ...,sigmak (where a subsequence end is defined by an acknowledgment) that minimizes a linear combination of the cost for the number of acknowledgments sent and the cost for the additional latency... Read More

We discuss congestion control mechanisms in multicast transport protocols and we propose TCP-M - a TCP-friendly Multicast transport protocol. TCP-M uses IP multicast to deliver data packets and acknowledgements to provide reliability. Ack implosion at the source is prevented by fusing acknowledgements at some intermediate routers. TCP-M reacts to network congestion exactly like TCP by having the sender emulate a TCP sender.

We describe mechanisms to enhance the reliability and performance of Mobile IP. In Mobile IP today home agents and foreign agents are single points of failure and potential performance bottlenecks. For example, a home agent crash can lead to communication failure if the mobile is away from home. In this paper we describe new mechanisms to allow redundant home and foreign agents. Redundant agents can take over from each other in case of failure, and also split load amongst themselves. Our mechanisms are simple, transparent to existing mobile nodes, and... Read More

Goldberg, Goldman, and Scott demonstrated how the problem of recognizing a landmark from a one-dimensional visual image can be mapped to that of learning a one-dimensional geometric pattern and gave a PAC algorithm to learn that class. In this paper, we present an efficient on-line agnostic learning algorithm for learning the class of constant-dimension geometric patterns. Our algorithm can tolerate both classification and attribute noise. By working in higher dimensional spaces we can represent more features from the visual image in the geometric pattern. Our mapping of the data to... Read More

We introduce the UAV learning model in which some of the attributes in the examples are unspecified. In our model, an example x is classified positive (resp., negative) if all possible assignments for the unspecified attributes result in a positive (resp., negative) classification. Otherwise the classificatoin given to x is "?" (for unknown). Given an example x in which some attributes are unspecified, the oracle UAV-MQ responds with the classification of x. Given a hypothesis h, the oracle UAV-EQ returns an example x (that could have unspecified attributes) for which... Read More

We study non-preemptive, online admission control in the hard deadline model: each job must be either serviced prior to its deadline, or be rejected. Our setting consists of a single resource that services an online sequence of jobs; each job has a length indicating the length of time for which it needs the resource, and a delay indicating the maximum time it can wait for the service to be started. The goal is to maximize total resource utilization. The jobs are non-preemptive and exclusive, meaning once a job begins, it... Read More

As the primary tool for detecting breast carcinoma, mammography provides visual images from which a trained radiologist can identify suspicious areas that suggest the presence of cancer. We describe an approach to image processing that reduces an image to a small number of values based on its structural characteristics using wavelets and neural networks. To illustrate its utility, we apply this methodology to the automatic screening of mammograms for mass lesions. Our results approach performance levels of trained human mammographers.

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