Technical Reports and MS Project Reports

As computer networks increase in speed, it becomes difficult to monitor and manage the transmitted digital content. To alleviate these problems, hardware-based search (FPgrep) and search-and-replace (FPsed) modules have been developed. FP-grep has the ability to scan packet payloads for a given set of regular expressions and pass or drop packets based on the payload contents. FPsed also scans packet payloads for a set of regular expressions and adds the ability to modify the payload if desired. The hardware circuits that implement the FPgrep and FPsed modules can be generated, ...Read More

LIME (Linda in a Mobile Environment) 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 refined in LIME to transient sharing of identically-named tuple spaces carried by individual mobile units. Tuple spaces are also extended with a notion of location and programs are given the ability to react to specified states. The ...Read More

Context-aware computing, an emerging paradigm in which applications sense and adapt their behavior to changes in their operational environment, is key to developing dependable software for use in the often unpredictable settings of ad hoc networks. However, designing an application which gathers, maintains, and adapts to context can be a difficult undertaking, even for a seasoned programmer. Our goal is to simplify the programming task by hiding such issues from the programmer, allowing one to quickly and reliably produce a context-aware application for use in ad hoc networks. With this ...Read More

This paper describes theoretical and experimental results for the auto-calibration of sensor platform consisting of a camera and a laser range finder. Real-world use of autonomous sensor platforms often requires the recalibration of sensors without an explicit calibration object. The constraints are based upon data captured simultaneously from the camera and the laser range finder while the sensor plat-form undergoes an arbitrary motion. The rigid motions of both sensors are related, so these data constrain the relative position and orientation of the camera and laser range finder. We introduce the ...Read More

We describes theoretical and experimental results for the extrinsic calibration of sensor platform consisting of a camera and a laser range finder. The proposed technique requires the system to observe a planar pattern in several poses, and the constraints are based upon data captured simultaneously from the camera and the laser range finder. The planar pattern surface and the laser scanline on the planar pattern are related, so these data constrain the relative position and orientation of the camera and laser range finder. The calibration procedure starts with a closed-from ...Read More

Traditionally, network communication entailed the delivery of messages to specific network addresses. As computers acquired multimedia capabilities, new applications such as video broadcasting dictated the need for real-time quality of service guarantees and delivery to multiple recipients. In light of this, a subtle transition took place as a subset of IP addresses evolved into a group-naming scheme and best-effort delivery became subjugated to temporal constraints. With recent developments in mobile and sensor networks new applications are being considered in which physical locations and even temporal coordinates play a role in ...Read More

Motivation: Pseudoknots have generally been excluded from the prediction of RNA secondary structures due to the difficulty in modeling and complexity in computing. Although several dynamic programming algorithms exist for the prediction of pseudoknots using thermodynamic approaches, they are neither reliable nor efficient. On the other hand, comparative methods are more reliable, but are often done in an ad hoc manner and require expert intervention. Maximum weighted matching (Tabaska et. al, Bioinformatics, 14:691-9, 1998), an algorithm for pseudoknot prediction with comparative analysis, suffers from low prediction accuracy in many cases. ...Read More

The goal of this project is to develop a 3D input device using a stiff piece of paper and a camera. The camera tracks the piece of paper in 3D space. The user orients the paper in 3D space and then draws on the paper using a pen-like device. The camera tracks the movement of the pen on the piece of paper. The location of the pen in 3D space can then be calculated from the orientation of the paper. A drawing application that uses this 3D input device was ...Read More

TCP-Splitter is a hardware circuit which facilitates the monitoring of TCP/IP data streams. When located within high-speed networking equipment, this circuit provides ordered TCP byte streams for all TCP flows at line rates. This document provides and in-depth look at the design and implementation of the TCP-Splitter circuit. The operation of the TCP-Splitter with three sample client applications is also described.

Context-aware computing is a new paradigm whose emergence has been fostered by a growing reliance on light and mobile computing devices, which adapt their behavior to changing environmental conditions. The dynamic nature of the environment is a direct result of the mobility of people and devices. Because the development of applications that entail a significant level of dynamic adaptation is a difficult and error-prone task, new design methods and constructs are needed. Precise and flexible specification of the resources needed to operate in specific contexts combined with transparent context management ...Read More

Networking devices must be capable of processing traffic flows from multiple sources. In order to verify that such devices operates properly, a network testbench can be used to inject traffic into the device. The specification of the traffic flows can be difficult. At the low level, there are header fields, data checksums, and packet length fields that all must be formatted correctly. Further, there can be multiple flows of traffic that will arrive simultaneously. It is desirable to specify traffic at a high level of abstraction. A software program can ...Read More

Because of its flexibility and high performance, reconfigurable logic functions implemented on the Field-programmable Port Extender (FPX ) are well suited for implementing network processing such as packet classification, filtering and intrusion detection functions. This project focuses on two key aspects of the FPX system. One is providing a Gigabit Ethernet interface by designing logic for a FPGA which is located on a line card. Address Resolution Protocol (ARP) packets are handled in hardware and Ethernet frames are processed and transformed into cells suitable for standard FPX application. The other ...Read More

Single Nucleotide Polymorphism (SNP) Genotyping is an important molecular genetics process in the early stages of producing results that will be useful in the medical field. Due to inherent complexities in DNA manipulation and analysis, many different methods have been proposed for a standard assay. One of the proposed techniques for performing SNP Genotyping requires amplifying regions of DNA surrounding a large number of SNP loci. In order to automate a portion of this particular method, it is necessary to select a set of primers for the experiment. Selecting these ...Read More

High-speed packet classification is crucial to the implementation of several advanced network services and protocols; many QoS implementations, active networking platforms, and security devices (such as firewalls and intrusion-detection systems) require it. But performing classification on multiple fields, at the speed of modern networks, is known to be a difficult problem. The Recursive Flow Classification (RFC) algorithm described by Gupta and McKeown performs classification very quickly, but can require excessive storage when using thousands of rules. This paper studies a compressed representation for the tables used in RFC, trading some ...Read More

Historically, many distributed real-time and embedded (DRE) systems were developed manually from scratch, leading to stove-piped solutions that while correct in both functional and QoS properties were very expensive to develop and difficult to maintain and extend. First-generation middleware technologies such as CORBA 2.x [1], XML [2], and SOAP [3], served to shield application developers from low-level platform details, thus raising the level of abstraction at which distributed systems are developed and supporting reuse of infrastructure to amortize development costs over the lifetime of a system. However, interdependencies between services ...Read More

General purpose middleware has been shown to be effective in meeting diverse functional requirements for a wide range of distributed systems. Advanced middleware projects have also supported a single quality-of-service dimension such as real-time, fault tolerance, or small memory footprint. However, there is limited experience supporting multiple quality-of-service dimensions in mid-dleware to meet the needs of special purpose applications. Even though general purpose middleware can cover an entire spectrum of applications by supporting the union of all features required by each application, this approach breaks down for distributed real-time and ...Read More

General purpose middleware has been shown effective in meeting diverse functional requirements for a wide range of distributed systems. Advanced middleware projects have also supported single quality-of-service dimensions such as real-time, fault tolerance, or small memory foot-print. However, there is limited experience supporting multiple quality-of-service dimensions in middleware to meet the needs of special purpose applications. Even though general purpose middleware can cover an entire spectrum of functionality by supporting the union of all features required by each application, this approach breaks down for distributed real-time and embedded sys-tems. For ...Read More

As the focus of networking research shifts from raw performance to the delivery of advanced network services, there is a growing need for open-platform systems for extensible networking research. The Applied Research Laboratory at Washington University in Saint Louis has developed a flexible Network Services Platform (NSP) to meet this need. The NSP provides an extensible platform for prototyping next-generation network services and applications. This paper describes the design of a system-on-chip Packet Processor for the NSP which performs all core packet processing functions including segmentation and reassembly, packet classification, ...Read More

Packet classification is the enabling technology for next generation network services and often the primary bottleneck in high-performance routers. Due to the importance and complexity of the problem, a myriad of algorithms and resulting implementations exist. The performance and capacity of many algorithms and classification devices, including TCAMs, depend upon properties of the filter set and query patterns. Unlike microprocessors in the field of computer architecture, there are no standard performance evaluation tools or techniques available to evaluate packet classification algorithms and products. Network service providers are reluctant to distribute ...Read More

Multistage interconnection networks with internal cell buffering and dynamic routing are among the most cost-effective architectures for multi-terabit internet routers. One of the key design issues for such systems is maintaining cell ordering, since cells are subject to varying delays as they pass through the interconnection network. The most flexible and scalable approach to cell resequencing uses timestamps and a time-ordered resequencing buffer at each router output port. Conventional, fixed-threshold resequencers can perform poorly in the presence of extreme traffic conditions. This paper explores alternative resequencer designs that are more ...Read More

An effective approach for energy conservation in wireless sensor networks is scheduling sleep intervals for extraneous nodes, while the remaining nodes stay active to provide continuous service. For the sensor network to operate successfully, the active nodes must maintain both sensing coverage and network connectivity. Furthermore, the network must be able to configure itself to any feasible degrees of coverage and connectivity in order to support different applications and environments with diverse requirements. This paper presents the design and analysis of novel protocols that can dynamically configure a network to ...Read More

This thesis presents a Field Programmable Gate Array (FPGA) based, high-speed search system that is intended to perform simple data mining operations on the data streaming from an off-the-shelf hard drive. This system includes the search engine itself and a device that snoops the traffic on an ATAPI/IDE peripheral bus, capturing data transmitted by a hard drive attached to the bus and forwarding that data to the search engine. The search engine, which is an adaption of the Smith-Waterman local sequence alignment algorithm, can process search data at a rate ...Read More

Modern day digital integrated circuit designs can be designed without choosing a target programmable device or fabrication process until near the very end of the design flow. Current analog design tools and processes, however, require that the fabrication process be chosen very early on in the design process. This paper describes a vision of analog design that can be used to make more of the analog design process independent of which fabrication process is going to be used by designing at a higher, process independent level. An integrated circuit for ...Read More

A Distributed Constraint Satisfaction Problem (DCSP) aims to find consistent assignments of values to a set of variables distributed on multiple nodes. Despite its simple definition, DCSPs can model a broad variety of traditional artificial intelligence problems. Furthermore, many problems found in emerging sensor-actuator networks can be formalized to DCSPs. However, due to the platform limitations of networked embedded systems such as sensor-actuators networks, building real-world applications for solving DCSPs not only requires the improved DCSP algorithms but also novel system approaches. This thesis first develops a performance-driven middleware framework ...Read More

Greedy geographic routing is attractive in wireless sensor networks due to its efficiency and scalability. However, greedy geographic routing may incur long routing paths or even fail due to routing voids on random network topologies. We study greedy geographic routing in an important class of wireless sensor networks (e.g., surveillance or object tracking systems) that provide sensing coverage over a geographic area. Our geometric analysis and simulation results demonstrate that existing greedy geographic routing algorithms can successfully find short routing paths based on local states in sensing-covered networks. In particular, ...Read More

A fast control cell processor (CCP) has been designed and implemented in order to process control cells as they enter the module. This fast CCP is capable of receiving back-to-back control cells, processing them, and sending them out in back-to-back fashion. The fast CCP comes equipped with a SRAM interface and a statistics interface. Currently, the fast CCP uses the Statistics Counter Plus to count the number of control cells on each VCI, the number of SRAM reads on each VCI, the number of SRAM writes on each VCI, and ...Read More

Hundreds of types of events can occur in a complex networking device, and millions of these events occur every second. In order to debug and manage a complex networking device, it is necessary to count events and track statistics. A device has been implemented that counts 256 events from three independent sources. The module provides a simple interface to read back the number of occurrences of each event. To most efficiently utilize the area on the chip, the counting module stores the counter values in block memory on a FPGA ...Read More

The Statistics Counter Plus is a more generalized version of the Statistics Counter circuit developed earlier this year. When an event occurs multiple times, the user may hold the increment event signal asserted while the event occurs. As before, 256 separate events can be tracked.

In many data mining applications, the size of the database is not only extremely large, it is also growing rapidly. Even for relatively simple searches, the time required to move the data off magnetic media, cross the system bus into main memory, copy into processor cache, and then execute code to perform a search is prohibitive. We are proposing that a significant portion of the data mining task (i.e., the portion that examines the bulk of the raw data) be implemented in fast hardware, close to the magnetic media on ...Read More

This proposal addresses two problems in programmable networks. Specifically, we are interested in networks that can dynamically deploy applications and session-specific plugins within network routers, to provide advanced commination services. In the first half of the proposal, we present a general approach to the problem of configuring application sessions that require intermediate processing in programmable networks. In the second half, we discuss how to provision a programmable network for such session by placing and dimensioning link bandwidth and processing resources in an efficient way.

Distributed rate-based real-time systems, such as process control and avionics mission computing systems, have traditionally been scheduled statically. Static scheduling provides assurance of schedulability prior to run-time overhead. However, static scheduling is brittle in the face of unanticipated overload, and treats invocation-to-invocation variations in resource requirements inflexibly. As a consequence, processing resources are often under-utilized in the average case, and the resulting systems are hard to adapt to meet new real-time processing requirements. Dynamic scheduling offers relief from the limitations of static scheduling. However, dynamic scheduling offers relief from the ...Read More

We present a technique for blending multiple images of an object into a single, view-dependent texture map for that object. This technique can be used for image-based rendering, when the object is known, or for “painting” a view-dependent texture map of an object. The technique provides a structured mechanism for combing images at different resolutions, producing a mip-map like structure with the different levels constructed from different images. The user controls the camera angles for which a given image is valid. The technique is also suitable for use on an ...Read More

Context awareness is important for many cooperation and coordination scenarios in ad hoc mobile environments. Developing context-aware applications in a dynamic and volatile ad hoc mobile setting is a complex task. The goal of this proposal is to investigate implications of ad hoc mobility on application design and development, to explore design principles and general design frameworks, and to deliver a middleware to facilitate application development for ad hoc mobile systems. The middleware aims to provide a set of toolkits and services for efficient and reliable information discovery and dissemination ...Read More

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. We argue that preventing the occurrence of unannounced disconnection is essential to constructing and maintaining a consistent view in the ad hoc mobile environment. In this light, we provide the specification for a partitionable group membership service supporting ad hoc mobile applications and propose a protocol for implementing the service. A unique property of ...Read More

This paper is concerned with coordinated delivery of messages in sensor networks. The notion of multicast is re-examined in light of a new set of requirements that are specific to such networks. The result of this investigation is a new concept called mobicast. Mobicast entails the delivery of messages to large sets of nodes in a manner that satisfies a potentially dynamic set of spatiotemporal constraints. In order to demonstrate the feasibility of mobicast, we present a novel topology-aware protocol for sensor networks. Worst-case analysis shows that the protocol provides ...Read More

Electronic traffic signal has the advantage of being easily visible to machines. It is expected to augment the traditional traffic light system in future intelligent transportation environments, where intelligent vehicles interact with each other and with traffic systems and give informed advisories to drivers. One problem with wireless signals is that they are essentially omnidirectional. Even if one uses directional wireless signaling source, it is not clear how any recipient of a signal can reliably determine whether the signal is meant for him or her, in the presence of signal ...Read More

In order to support a wide range of applications, Distributed Object Computing (DOC) middleware frameworks such as ACE and TAO have grown to include a vast number of features. For any one application, though, unused functionality either contributes to code bloat, degrades performance or both. When applied to embedded and realtime systems, these issues can preclude the use of middleware altogether. Currently, to address these concerns, middleware developers continually refactor code to relegate functionality to separate libraries. This process is tedious, time-consuming, and adds complexity for both users and developers. ...Read More

Some of the most dynamic systems being built today consist of physically mobile hosts and logically mobile agents. Such systems exhibit frequent configuration changes and a great deal of resource variability. Applications executing under these circumstances need to react continuously and rapidly to changes in operating conditions and must adapt their behavior accordingly. The development of such applications demands a reexamination of the very notion of context and of the mechanisms used to manage the application response to contextual changes. This paper introduces EgoSpaces, a coordination model and middleware for ...Read More

The advent of optical technology that can feasibly support extremely high bandwidth chip-to-chip communication raises a host of architectural questions in the design of digital systems. Terabit per second (and higher) bandwidths have not been previously available at the chip level. In this thesis, we examine the use of this technology in two different scenarios, viz., as the interconnection network in a multiprocessor system and as a switch fabric in network routers. Specifically, we examine the performance gains associated with utilizing the bandwidth reconfiguration capabilities of a system based on ...Read More

Reconfigurable hardware platforms are the key to extensible high speed networks. They provide flexibility without hindering performance through the internet. Current development of the Field-programmable Port Extender (FPX), a reconfigurable hardware platform allows reconfiguration through an ATM network. However, majority of the internet today is based on the highly popular TCP/IP protocol. The contribution of this work will allow modular components to be reprogrammed via TCP/IP

This manual summarizes how to insert the Field Programmable Port Extender (FPX) into the Washington University Gigabit Switch (WUGS), how to install the NCHARGE control software, how to initialize the system, and how to reprogram a user-defined module into the FPX over the network using the included web-based tools.

The advent of open and widely adopted standards such as Common Object Request Broker Architecture (CORBA) [47] has simplified and standardized the development of distributed applications. For applications with real-time constraints, including avionics, manufacturing, and defense systems, these standards are evolving to include Quality-of-Service (QoS) specifications. Operating systems such as Real-time Linux [60] have responded with interfaces and algorithms to guarantee real-time response; similarly, languages such as Real-time Java [59] include mechanisms for specifying real-time properties for threads. However, the middleware upon which large distributed applications are based has not ...Read More

LimeLite is a new coordination model and middleware designed to support rapid development of applications entailing logical mobility of agents and physical mobility of hosts. Designed to function in open environments, LimeLite performs automatic agent discovery but filters the results to define for each agent an individualized acquaintance list in accordance with run-time policies specified at the application level. This asymmetry among participants in the coordination process is dictated by the need to accommodate settings involving large numbers of agents and hosts that come and go freely. It represents an ...Read More

Practical applications of coordination models demand appropriate security guarantees. In ad hoc settings this must be achieved without reliance on any central point of control. \lime is one of the few coordination models and middleware to provide support for ad hoc networking and mobility. This paper shows how security can be added to \lime by simple extensions to the original model. The extensions include password protected tuple spaces, per tuple access controls and encrypted communication between parts of application running on different hosts. Furthermore, these new capabilities are accommodated with ...Read More

Security is emerging as a growing concern throughout the distributed computing community. Typical solutions entail specialized infrastructure support for authentication, encryption and access control. Mobile applications executing over ad hoc wireless networks present designers with a rather distinct set of security requirements. A totally open setting and limited resources call for lightweight and highly decentralized security solutions. In this paper we propose an approach that relies on extending an existing coordination middleware for mobility (Lime). The need to continue to offer a very simple model of coordination that assures rapid ...Read More

The increasing ubiquity of mobile devices has led to an explosion in the development of applications tailored to the particular needs of individual users. As the research community gains experience in the development of these applications, the need for middleware to simplify such software development is rapidly expanding. Vastly different needs of these various applications, however, have led to the emergence of many different middleware models, each of which approaches the dissemination of contextual information in a distinct way. The EgoSpaces model consists of logically mobile agents that operate over ...Read More

Much of the current work on context-aware computing relies on information directly available to an application via context sensors on its local host, e.g., user profile, host location, time of day, resource availability, and quality of service measurements. We propose a new notion of context which includes in principle any information available in the ad hoc network infrastructure but is restricted in practice to specific views of the overall context. The context of each view is define in terms of data, objects, or events exhibiting certain propertied, associated with particular ...Read More

Mobile UNITY refers to a notation system and proof logic initially designed to accommodate the special needs of the emerging field of mobile computing. The model allows one to define units of computation and mobility and the formal rules for coordination among them in a highly decoupled manner. In this paper, we reexamine the expressive power of the Mobile UNITY coordination constructs from a new perspective rooted in the notion that disciplined usage of a powerful formal model must rely on formally defined schemas. Several coordination schemas are introduced and ...Read More

This paper is concerned with the design and implementation of think coordination veneers for use in the development of applications over ad hoc wireless networks. A coordination veneer is defined as an adaption layer that customizes a general-purpose coordination middleware to a particular application domain with minimal development effort. This technique allows developers to build highly-tailored coordination models while leveraging off established models and middleware. We present three such veneers, the coordination models they embody, and the manner in which they were implemented. The \lime middleware, which supplies tuple space ...Read More

In 1990, the United States Human Genome Project was initiated as a fifteen-year endeavor to sequence the approximately three billion bases making up the human genome (Vaughan, 1996).As of December 31, 2001, the public sequencing efforts have sequenced a total of 2.01 billion finished bases representing 63.0% of the human genome (http://www.ncbi.nlm.nih.gov/genome/seq/page.cgi?F=HsProgress.shtml&&ORG=Hs) to a Bermuda quality error rate of 1/10000 (Smith and Carrano, 1996). In addition, 1.11 billion bases representing 34.8% of the human genome has been sequenced to a rough-draft level. Efforts such as UCSC's GoldenPath (Kent and Haussler, ...Read More