All Computer Science and Engineering Research

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. Fur-thermore, 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

Maximum Boolean satisfiability (max-SAT) is the optimization counterpart of Boolean satisfiability (SAT), in which a variable assignment is sought to satisfy the maximum number of clauses in a logical formula. A branch-and-bound algorithm based on the Davis-Putnam-Logemann-Loveland procedure (DPLL) is one of the most efficient complete algorithms for solving max-SAT. In this paper, We propose and investigate a number of new strategies for max-SAT. Our first strategy is a set of unit propagation rules for max-SAT. As unit propaga-tion is a very efficient strategy for SAT, we show that it... Read More

The goal of this research is to explore techniques for shading 3D computer generated models using scanned images of actual paint samples. The techniques presented emphasize artistic control of brush stroke texture and color. We first demonstrate how the texture of a paint sample can be separated from its color transition. Four methods, three real-time and one off-line, for producing rendered images from the paint samples are then presented. Finally, we develop metrics for evaluating how well each method achieves our goal in terms of texture similarity, shading correctness, and... Read More

We describe a new method for determining when an object can be garbage collected. The method does not require marking live objects. Instead, each object X is dynamically associated with a stack frame M, such that X is collectable when M pops. Because X could have been dead earlier, our method is conservative. Our results demonstrate that the method nonetheless identifies a large percentage of collectable objects. The method has been implemented in Sun's Java Virtual Machine interpreter, and results are presented based on this implementation.

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 building a system in which a significant portion of the data mining task (i.e., the portion that examines the bulk of the raw data) is implemented in fast hardware, close to the... Read More

The goal of packet-switched networks has conventionally been delivering data to users. This concept is changing rapidly as current technologies make it possible to build network processing engines that apply intermediary services to data traffic. This trend introduces an extensive range of ways to develop and operate applications by allowing processing services customized for applications' needs at intermediate network users, as it can relieve individuals from the need to acquire, install, and maintain software in end systems to perform required functions. As such network services become more widely used, it... Read More

The correctness of a real-time system is very much dependent on the time at which a specific task is completed. Hence, satisfying a storage allocation request within bounded time is important. Fragmentation of the heap after repeated allocations and deallocations is a major issue for real-time systems, as most allocators depend on garbage collection for defragmentation of the heap, which might not finish in time to honor deadlines. We present the storage requirement for a defragmentation-free binary-buddy allocator. We also study a localized defragmentation algorithm to satisfy a single allocation... Read More

Chip Multi-Processors(CMPs) are now available in a variety of systems. They provide the opportunity to achieve high computational performance by exploiting application-level parallelism within a single chip form factor. In the communications environment, network processors (NPs) are often designed around CMP architectures and, in this context, the processors may be used in a pipelined manner. This leads to the issue of scheduling tasks on such processor pipelines. A tool and algorithm called Greedy pipe has been developed that determines the nearly optimal schedules for such multiprocessor pipelines. The tool offers... Read More

Chip Multi-Processors (CMPs) are now available in a variety of systems and provide the opportunity for achieving high computational performance by exploiting application-level parallelism. In the communications environment, network processors (NPs) are often designed around CMP architectures and in this context the processors may be used in a pipelined manner. This leads to the issue of scheduling tasks on processor pipelines. This paper considers problems associated with determining optimal application task assignments for such pipelines. A system and algorithm called Greedy Pipe is presented and its performance analyzed. The algorithm... Read More

Typically, when a program executes, it creates objects dynamically and requests storage for its objects from the underlying storage allocator. The patterns of such requests can potentially lead to internal fragmentation as well as external fragmentation. Internal fragmentation occurs when the storage allocator allocates a contiguous block of storage to a program, but the program uses only a fraction of that block to satisfy a request. The unused portion of that block is wasted since the allocator cannot use it to satisfy a subsequent allocation request. External fragmentation, on the... Read More

Advances in middleware, operating systems, and popular, general-purpose languages have brought the ideal of reasonably-bound execution time closer to developers who need such assurances for real-time and embedded systems applications. Extensions to the Java libraries and virtual machine have been proposed in a real-time Java standard, which provides for specification of release times, execution costs, and deadlines for a restricted class of threads. To use such features, the programmer is required to use unwieldy code constructs to create region-like areas of storage, associate them with execution scopes, and allocate objects... Read More

We explain how to use simple composition rules to drive an automated, mobile photography system. The composition rules are used to determine both the location for a good photograph, and how to frame that photograph. We describe the composition component in the context of a larger application, a robotic photographer. The robot moves around an area with people in it, opportunistically looking for faces and taking photographs. We describe both how to find faces in the world and how to create “good” photographs of those faces.

With the advent of operating systems and programming languages that can evaluate and guarantee real-time specifications, applications with real-time requirements can be authored in higher-level languages. For example, a version of Java suitable for real-time (RTSJ) has recently reached the status of a reference implementation, and it is likely that other implementations will follow. Analysis to show the feasibility of a given set of tasks must take into account their worst-case execution time, including any storage allocation or deallocation associated with those tasks. In this thesis, we present a hardware-based... Read More

A complete mapping from genome to proteome would constitute a foundation for genome-based biology and provide targets for pharmaceutical and therapeutic intervention. This is one reason gene structure prediction has been a major subfield of computational biology for over 20 years. Many of the widely used gene prediction systems were developed in the 1990s and are unable to take advantage of the revolution in comparative genomics brought on by the sequencing of the entire genomes of an increasing numbers of vertebrates. Twinscan is a new system for high-throughput gene-structure prediction... Read More

Limone is a new coordination model and middleware that enables rapid application development for wireless ad hoc networks entailing logical mobility of agents and physical mobility of hosts. Designed to function in open environments, Limone performs automatic agent discovery but filters the results to define for each agent an individualized acquaintance list in accordance with run-time policies that are customizable by the application. This asymmetry among participants represents a new direction in coordination research and is dictated by the need to accommodate settings involving large numbers of agents and hosts... Read More

This paper presents Limone, a new coordination model that facilitates rapid application development over ad hoc networks consisting of logically mobile agents and physically mobile hosts. Limone assumes an agent-centric perspective on coordination by allowing each agent to define its own acquaintance policy and by limiting all agent-initiated interactions to agents that satisfy the policy. Agents that satisfy this acquaintance policy are stored in an acquaintance list, which is automat-ically maintained by the system. This asymmetric style of coordination allows each agent to focus only on relevant peers. Coordination activi-ties... Read More

We identify common storage-referencing gestures in Java bytecode and machine-level code, so that a gesture comprising a sequence of storage dereferences can be condensed into a single instruction. Because these gestures access memory in a recognizable pattern, the pattern can be preloaded into and executed by a “smart” memory. This approach can improve program execution time by making memory accesses more efficient, by saving CPU cycles, bus cycles, and power. We introduce a language of valid gesture types and conduct a series of experiments to analyze the characteristics of gestures... Read More

We describe techniques for identifying and optimizing memory-accessing instruction sequences. We capture a sequence of such instructions, with the goal of sending the sequence as a single instruction from the CPU to a smart memory subsystem (IRAM or PIM). With a software/hardware codesign, the memory-accessing gestures can be rewritten as succinct superoperator instructions, and the gestures themselves could vary at runtime. As a result, the CPU executes fewer instructions and the CPU-memory bus is charged less often, resulting in lower power consumption. Reduction in power can be crucial for constrained,... Read More

Chip Multi-Processors (CMPs) are now available in a variety of systems and provide the opportunity for achieving high computational performance by exploiting application-level parallelism. In the communications environment, network processors (NPs), designed around CMP architectures, are generally usable in a pipelined manner. This leads to the issue of scheduling tasks on processor pipelines. This paper considers problems associated with determining optimal schedules for such pipelines. A system and algorithm called Greedy Pipe is presented. The algorithm employs a greedy heuristic to schedule tasks derived from multiple application flows on pipelines... Read More

Common collection objects such as hash tables are included in modern runtime libraries because of their widespread use and efficient implementation. While operating systems and programming languages continue to improve their real-time features, common implementations of hash tables and other collection objects are not necessarily suitable for real-time or embedded-systems. In this paper, we present an algorithm for managing hash tables that is suitable for such systems. The algorithm has been implemented and deployed in place of Java’s Hashtable class. We present evidence of the algorithm’s performance, experimental results documenting... Read More

We present a system for painting how the appearance of an object changes under different lighting and viewing conditions. The user paints what the object should look like under different lighting conditions (dark, partially dark, fully lit, etc.) and (optionally) different viewing angles. The system renders the object under new lighting conditions and a new viewing angle by combining these paintings. We also provide a technique for constructing texture maps directly from the user’s paintings.

Language support of dynamic storage management simplifies the application programming task immensely. As a result, dynamic storage allocation and garbage collection have become common in general purpose computing. Garbage collection research has led to the development of algorithms for locating program memory that is no longer in use and returning the unused memory to the run-time system for late use by the program. While many programming languages have adopted automatic memory reclamation features, this has not been the trend in Real-Time systems. Many garbage collection methods involve some form of... Read More

This paper addresses the design and implementation of thin coordination veneers for use in the development of applications over ad hoc wireless networks. A coordination veneer is defined as an adaptation layer that customizes a general-purpose coordination middleware to a particular domain with minimal development effort. This technique allows developers to build highly-tailored coordination models while leveraging 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 based coordination in the... Read More

Ad hoc networks are formed opportunistically as mobile devices come within wireless communication range of each other. Since individual devices are typically subject to severe resource limitations, it is both possible and desirable for a device to enhance its functionality by taking advantage (in a cooperative manner) of capabilities available on other devices. Service provision refers to the process by which devices advertise their willingness to offer specific services and discover other of services. This paper describes a service provision model designed specifically for use in ad hoc settings. Security... 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

This thesis examines the effects of changing the numerical representation of audio signals in digital hearing aids to minimize power consumption. Within the hearing aid design a majority of the power used is consumed in the many finite impulse response filters. The main processing involved in these filters is a multiply-accumulate function. We examine the power consumption of 12 different multiply-accumulate units that use the following numerical representations: a 16-bit linear representation, a 9-bit logarithmic representation, and 10 different floating-point rep-representations ranging from 9 to 13 bits. A selection of... Read More

Rate control, in conjunction with congestion control, is important and necessary to maintain both stability of overall network and high quality of individual data transfer flows. In this paper, we study stable rate control algorithms for streaming data, based on control theory. We introduce various control rules to maintain both sending rate and receiver buffer stable. We also propose an adaptive two-state control mechanism to ensure the rate control algorithms are compatible to TCP traffics. Extensive experimental results are shown to demonstrate the effectiveness of the rate control algorithms.

Sensor network presents us many new challenging practical and theoretical problems. This paper is concerned with minimal exposure problem in sensor networks. Exposure, proposed by Megerian and others [3] as a useful metric to describe the sensor coverage of a path in a sensor field, exhibits interesting properties and induces related open problems. In this paper, we present a solution to an open one-sensor exposure problem [2, 3] using variational calculus as our first step in further understanding of the exposure problem in multiple sensor scenarios.

The recent advent of wireless mobile ad hoc networks and sensor networks creates many opportunities and challenges. This thesis explores some of them. In light of new application requirements in such environments, it proposes a new multicast paradigm called spatiotemporal multicast for supporting ad hoc network applications which require both spatial and temporal coordination. With a focus on a special case of spatiotemporal multicast, called mobicast, this work proposes several novel protocols and analyzes their performances. This dissertation also investigates implications of mobility on the classical group membership problem in... Read More

We propose a new multicast communication paradigm called “spatiotemporal multicast” for supporting applications which require spatiotemporal coordination in wireless sensor networks. In this paper we focus on a special class of spatiotemporal multicast called “mobicast” featuring a message delivery zone that moves at a constant velocity v. The key contributions of this work are: (1) the specification of mobicast and its performance metrics, (2) the introduction of four different mobicast protocols along with the analysis of their performance, (3) the introduction of two topological network compactness metrics for facilitating the... Read More

This paper presents a novel protocol for a spatiotemporal variant of multicast called mobicast, designed to support message delivery in sensor and mobile ad hoc networks. The spatiotemporal character of mobicast relates to the obligation to deliver a message to all the nodes that will be present at time t in some geographic zone Z, where both the location and shape of the delivery zone are a function of time over some interval (tstart, tend). The protocol, called Face-Aware Routing (FAR), exploits ideas adapted from existing applications of face routing... Read More

Sensor networks often involve the monitoring of mobile phenomena, which can be facilitated by a spatiotemporal multicast protocol we call “mobicast”. Mobicast is a novel spatiotemporal multicast protocol featuring a delivery zone that evolves over time. Mobicast can in theory provide absolute spatiotemporal delivery guarantees by limiting communication to a mobile forwarding zone whose size is determined by the global worst-case value associated with a compactness metric defined over the geometry of the network. In this work, we first studied the compactness properties of sensor networks with uniform distribution. The... Read More

SimplePipe is a simulation framework/tool for analyzing performance effects of alternative task allocations in network processors having multiple pipelines where pipeline stages are either processors or dedicated hardware functions. Tasks are defined in terms of sequence of separate C program executions with each sequence representing the functional requirements of a flow, where a flow is defined as the set of packets having the same processing requirements. The assignment of tasks to pipeline stages, selection of number of stages, and determination of processor cache sizes are important designing decisions impacting performance.

Context-awareness is emerging as an important computing paradigm designed to address the special needs of applications that must accommodate or exploit the highly dynamic environments that occur in the presence of physical or logical mobility. A number of formal models are available for reasoning about concurrency. Models designed to capture the specifics of mobility are fewer but still well represented (e.g., Mobile Ambients, π-Calculus, and Mobile UNITY). These models do not, however, provide constructs necessary for explicit modeling of context-aware interactions. This paper builds upon earlier efforts on state-based formal... Read More

The increasing ubiquity of communicating mobile devices and vastly different mobile application needs have led to the emergence of middleware models for ad hoc networks that simplify application programming. One such system, EgoSpaces, addresses specific needs of individual applications, allowing them to define what data is included in their operating context using declarative specifications constraining properties of data, agents that own the data, hosts on which those agents are running, and attributes of the ad hoc network. In the resulting coordination model, application agents interact with a dynamically changing environment... 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

The increasing ubiquity of mobile computing devices has made ad hoc networks everyday occurrences. In these highly dynamic environments, the multitude of devices provides a varied and rapidly changing environment in which applications must learn to operate. Successful end-user applications will not only learn to function in this environment but will take advantage of the variety of information available. Protocols for gathering an application’s contextual information must be built into the network to function in a timely and adaptive fashion. This paper presents a protocol for providing context information to... 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 that 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 interacting with each other opportunistically via transient wireless interconnections. We extend a component’s context to encompass... Read More

Context-aware mobile applications require constant adaptation to their changing environments. Technological advancements have increased the pervasiveness of mobile computing devices such as laptops, handhelds, cellular phones, and embedded sensors. The sheer amount of context information necessary for adaptation places a heightened burden on application developers as they must manage and utilize vast amounts of data from diverse sources. Facilitating programming in this data-rich environment requires an infrastructure for sensing, collecting, and providing context information to applications. In this paper, we demonstrate the feasibility of providing such an infrastructure. It allows... Read More

The increased pervasiveness of wireless mobile computing devices draws new attention to the need for coordination among small, networked components. The very nature of the environment requires devices to interact even when they meet unpredictably. Because these networks are often decoupled from a fixed infrastructure, reliance on centralized servers for authentication and access policies is impractical. Access control is crucial in such systems, and applications must directly manipulate and examine access policies because they require full control of their data. In this paper, we explore the essential features of general... Read More

The emerging mobile computing environment draws new attention to the need for co-ordination among networked components. The very nature of this environment requires parties to interact even when they have never met before, and subsequent encounters are totally unpredictable. Because mobile networks are often decoupled from any fixed network infrastructure, reliance on centralized servers to authenticate agents and to establish data access policies is impractical. Access control is a key component of security in such systems, and application agents must be able to directly manipulate and examine policies because they... Read More

Recent studies have shown that suitably-designed packet discard policies can dramatically improve the performance of fair queueing mechanisms in internet routers. The Queue State Deficit Round Robin algorithm (QSDRR) preferentially discards from long queues, but in-troduces hysteresis into the discard policy to minimize synchronization among TCP flows. QSDRR provides higher throughput and much better fairness than simpler queueing mech-anisms, such as Tail-Drop, RED and Blue. However, because QSDRR discards packets that have previously been queued, it can signficantly increase the memory bandwidth require-ments of high performance routers. In this paper,... Read More

Real-time are beginning to appear in advanced, high-level programming languages such as Java. When complemented by a real-time operating system, the Real-Time Specification for Java (RTSJ) offers strong execution constraints for applications developed in Java. While the RTSJ make the basic services of Java such as storage and thread management ready for many real-time applications, the collection objects, and the rest of the application run-time library, cannot be used by RTSJ applications until their run-time properties are examined and modified as necessary to make them suitable for use by real-time... Read More

This paper presents several methods for shading meshes from scanned paint samples that represent dark to light transitions. Our techniques emphasize artistic control of brush stroke texture and color. We first demonstrate how the texture of the paint sample can be separated from its color gradient. We demonstrate three methods, two real-time and one off-line for producing rendered, shaded images from the texture samples. All three techniques use texture synthesis to generate additional paint samples. Finally, we develop metrics for evaluating how well each method achieves our goal in terms... Read More

Most modern application programs depend on dynamic storage management to handle allocation and deallocation of memory. Unfortunately conventional software-based storage managers are relatively low performance due to the latency associated with accessing DRAM memory. Consequently, developers of programs with very specialized memory requirements, such a real-time systems, often choose to manage memory manually at the application-code level. This practice can greatly increase performance but it can also significantly complicate the development process. In this thesis we present the design, VHDL implementation and performance evaluation of hardware-based storage manager called the... Read More

This thesis reports on experience with PCESjava, a collection of tools which we have developed for the purpose of aiding programmers. Particular applications optimize and instrument JAVA bytecode programs. Using these tools, we have successfully identified impediments to real-time performance in a popular JAVA collections object. Our approach here is based on automatic instruction to obtain traces that show paths whose execution time is not reasonably bounded. We also report on the application of our tool to reduce program footprint in JAVA programs by rewriting the bytecodes to occupy less... Read More

We investigate the impact of numerical representation on the power consumption of digital hearing aids. A fundamental building block, a non-linear amplifier, is implemented using traditional 16-bit linear or customized 9-bit logarithmic and 10-bit floating point numerical representations. An individual channel of a multi-channel hearing aid is constructed, targeting both FPGA and ASIC deployment options. Using signal transition counts in the post-synthesis simulation to model power consumption, we compare the relative power consumption of the non-linear amplifiers, a full hearing aid channel, and the complete hearing aid signal processing for... Read More

The rather large feature set of current Distributed Object Computing (DOC) middleware can be a liability for certain applications which have a need for only a certain subset of these features but have to suffer performance degradation and code bloat due to all the present features. To address this concern, a unique approach to building fully customizable middleware was undertaken in FACET, a CORBA event channel written using AspectJ. FACET consists of a small, essential core that represents the basic structure and functionality of an event channel into which additional... Read More

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

Due to increased production of human DNA sequence, it is now possible to explore and understand human genomic organization at the sequence level. In particular, we have studied one of the major organizational components of vertebrate genome organization previously described as isochores (Bernardi, 1993), which are compositionally homogeneous DNA segments based on G+C content. We have examined sequence data for the existence of compositionally differing regions and report that while compositionally homogeneous regions are present in the human genome, current isochore classification schemes are too brad for sequence-level data.

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