All Computer Science and Engineering Research

Multi-robot systems require efficient and accurate planning in order to perform mission-critical tasks. This paper introduces a mixed-integer linear programming solution to coordinate multiple heterogenenous robots for detecting and controlling multiple regions of interest in an unknown environment. The objective function contains four basic requirements of a multi-robot system serving this purpose: control regions of interest, provide communication between robots, control maximum area and detect regions of interest. Our solution defines optimum locations of robots in order to maximize the objective function while efficiently satisfying some constraints such as avoiding... Read More

We introduce the concept of perceptually meaningful image editing and present two techniques for manipulating the apparent depth of objects in an image. The user loads an image, selects an object and specifies whether the object should appear closer or further away. The system automatically determines target values for the object and/or background that achieve the desired depth change. These depth editing operations, based on techniques used by traditional artists, manipulate either the luminance or color temperature of different regions of the image. By performing blending in the gradient domain... Read More

The phenomenon of warmer colors appearing nearer in depth to viewers than cooler colors has been studied extensively by psychologists and other vision researchers. The vast majority of these studies have asked human observers to view physically equidistant, colored stimuli and compare them for relative depth. However, in most cases, the stimuli presented were rather simple: straight colored lines, uniform color patches, point light sources, or symmetrical objects with uniform shading. Additionally, the colors used were typically highly saturated. Although such stimuli are useful in isolating and studying depth cues... Read More

This paper demonstrates the use of image-space constraints for key frame interpolation. Interpolating in image-space results in sequences with predictable and controlable image trajectories and projected size for selected objects, particularly in cases where the desired center of rotation is not fixed or when the key frames contain perspective distortion changes. Additionally, we provide the user with direct image-space control over {\em how} the key frames are interpolated by allowing them to directly edit the object's projected size and trajectory. Image-space key frame interpolation requires solving the inverse camera problem... Read More

Given a positive integer k and a complete graph with non-negative edge weights that satisfy the triangle inequality, the remote-clique problem is to find a subset of k vertices having a maximum-weight induced subgraph. A greedy algorithm for the problem has been shown to have an approximation ratio of 4, but this analysis was not shown to be tight. In this thesis, we present an algorithm called d-Greedy Augment that generalizes this greedy algorithm (they are equivalent when d = 1). We use the technique of factor-revealing linear programs to... Read More

Given a complete graph with nonnegative edge weights satisfying the triangle inequality and a positive integer p, the remote-clique problem is to find a subset of p vertices having a maximum-weight induced subgraph. A simple greedy algorithm for the problem has been shown to have an approximation ratio of 4, but a tight example has not been provided. In this paper, we use the technique of factor revealing linear programs to prove that this algorithm actually achieves an approximation ratio of 2, matching the best-known ratio for the problem. The... Read More

As high integrity real-time systems become increasingly large and complex, forcing a static model of memory usage becomes untenable. The challenge is to provide a dynamic memory model that guarantees tight and bounded time and space requirements without overburdening the developer with memory concerns. This paper provides an analysis of memory management approaches in order to characterise the tradeoffs across three semantic domains: space, time and a characterisation of memory usage information such as the lifetime of objects. A unified approach to distinguishing the merits of each memory model highlights... Read More

The goal of this research is to develop new and more intuitive ways for editing a mesh from a static camera angle. I present two ways to edit a mesh via a simple sketching system. The first method is a gray-scale editor which allows the user to specify a fall off function for the region being deformed. The second method is a profile editor in which the user can re-sketch a mesh’s profile. Lastly, the types of edits possible will be discussed and our results will be presented.

With the emergence of high data rate sensor network applications, there is an increasing demand for high-performance query services in such networks. To meet this challenge, we present Dynamic Conflict-free Query Scheduling (DCQS), a novel scheduling technique for queries in wireless sensor networks. In contrast to earlier TDMA protocols designed for general-purpose networks and workloads, DCQS is specifically designed for query services supporting in-network data aggregation. DCQS has several important features. First, it optimizes the query performance and energy efficiency by exploiting the temporal properties and precedence constraints introduced by... Read More

Limit crossing is a methodology in which modified versions of a problem are solved and compared, yielding useful information about the original problem. Pruning rules that are used to exclude portions of search trees are excellent examples of the limit-crossing technique. In our previous work, we examined limit crossing for optimization problems. In this paper, we extend this methodology to decision problems. We demonstrate the use of limit crossing in our design of a tool for identifying K-SAT backbones. This tool is guaranteed to identify all of the backbone variables... Read More

This document provides information for deploying activePDF Toolkit Professional in a development environment. This document is organized into four sections: Getting Started, Tutorials, Technical Reference and the Toolkit Appendices. The Getting Started section covers setup and installation, includes a product overview and information related to operating Toolkit Professional. Tutorials includes examples of many Toolkit features, including PDF generation and form filling. All of the tutorials can be used with activePDF Toolkit. Technical Reference provides detailed information on Toolkit’s objects, subobjects, methods and properties.

The continuous growth in the Internet’s size, the amount of data traffic, and the complexity of processing this traffic gives rise to new challenges in building high-performance network devices. One of the most fundamental tasks performed by these devices is searching the network data for predefined keys. Address lookup, packet classification, and deep packet inspection are some of the operations which involve table lookups and searching. These operations are typically part of the packet forwarding mechanism, and can create a performance bottleneck. Therefore, fast and resource efficient algorithms are required.... Read More

While the problem of general packet classification has received a great deal of attention from researchers over the last ten years, there is still no really satisfactory solution. Ternary Content Addressable Memory (TCAM), although widely used in practice, is both expensive and consumes a lot of power. Algorithmic solutions, which rely on commodity memory chips, are relatively inexpensive and power-efficient, but have not been able to match the generality and performance of TCAMs. In this paper we propose a new approach to packet classification, which combines architectural and algorithmic techniques.... Read More

Agilla is a mobile agent middleware for sensor networks. Mobile agents are special processes that can migrate across sensors. They increase network flexibility by enabling active in-network reprogramming. Neighbor lists and tuple spaces are used for agent coordination. Agilla was originally implemented on Mica2 motes, but has been ported to other platforms. Its Mica2 implementation consumes 41.6KB of code and 3.59KB of data memory. Agents can move five hops in less than 1.1s with over 92% success. Agilla was used to develop multiple applications related to fire detection and tracking,... Read More

Recent years have seen rapid growth of online services that rely on large-scale server clusters to handle high volume of requests. Such clusters must adaptively control the CPU utilizations of many processors in order to maintain desired soft real-time performance and prevent system overload in face of unpredictable workloads. This paper presents DUC-LB, a novel distributed utilization control algorithm for cluster-based soft real-time applications. Compared to earlier works on utilization control, a distinguishing feature of DUC-LB is its capability to handle system dynamics caused by load balancing, which is a... Read More

Automatic detection of features in three-dimensional objects is a critical part of shape matching tasks such as object registration and recognition. Previous approaches to local surface matching have either focused on man-made objects, where features are generally well-defined, or required some type of user interaction to select features. Manual selection of corresponding features and subjective determination of the difference between objects are time consuming processes requiring a high level of expertise. Curvature is a useful property of a surface, but curvature calculation on a discrete mesh is often noisy and... Read More

Multiplicative Increase (MI), Additive Increase (AI), and Multiplicative Decrease (MD) are linear adjustments used extensively in networking. However, their properties are not fully understood. We analyze responsiveness (time for the total load to reach the target load), smoothness (maximal size of the total load oscillations after reaching the target load), fairing speed (speed of convergence to equal individual loads) and scalabilities of MAIMD algorithms, which generalize AIMD algorithms via optional inclusion of MI. We prove that an MAIMD can provide faster asymptotic fairing than a less smooth AIMD. Furthermore, we... Read More

We present a surface reconstruction technique that constructs a smooth analytic surface from scattered data. The technique is robust to noise and both poorly and non-uniformly sampled data, making it well-suited for use in medical applications. In addition, the surface can be parameterized in multiple ways, making it possible to represent additional data, such as electromagnetic potential, in a different (but related) coordinate system to the geometric one. The parameterization technique also supports consistent parameterizations of multiple data sets.

The Business Process Execution Language (BPEL) has become the dominant means for expressing traditional business processes as workflows. The widespread deployment of mobile devices like PDAs and mobile phones has created a vast computational and communication resource for these workflows to exploit. However, BPEL so far has been deployed only on relatively heavyweight server platforms such as Apache Tomcat, leaving the potential created by these lower-end devices untapped. This paper presents Sliver, a BPEL workflow process execution engine that supports a wide variety of devices ranging from mobile phones to... Read More

The workflow model is well suited for scenarios where many entities work collaboratively towards a common goal, and is used widely today to model complex business processes. However, the fundamental workflow model is very powerful and can be applied to a wider variety of application domains. This paper represents an initial investigation into the possibility of using workflows to model collaboration in an ad hoc mobile environment. Moving to a mobile setting introduces many challenges as the mobility of the participants in a workflow imposes constraints on allocation of workflow... Read More

Protein databases have grown exponentially over the last decade. This exponential growth has made extracting valuable information from these databases increasingly time consuming. This project presents a new method of accelerating a commonly used program for performing similarity searching on protein databases, BLASTP. This project describes the design and implementation of Mercury BLASTP, a customized hardware accelerated variant of BLASTP. This project focuses on the gapped alignment stage of Mercury BLASTP and provides design details and implementation results.

The continuing ossification of the Internet is slowing the pace of network innovation. Network diversification presents one solution to this problem, by virtualizing the network at multiple layers. Diversified networks consist of a shared physical substrate, virtual routers (metarouters), and virtual links (metalinks). Virtualizing routers enables smooth and incremental upgrades to new network services. Our current priority for a diversified router prototype is to enable reserved slices of the network for researchers to perform repeatable, high-speed network experiments. General-purpose processors have well established techniques for virtualization, but do not scale... Read More

NCBI BLASTP is a popular sequence analysis tool used to study the evolutionary relationship between two protein sequences. Protein databases continue to grow exponentially as entire genomes of organisms are sequenced, making sequence analysis a computationally demanding task. For example, a search of the E. coli. k12 proteome against the GenBank Non-Redundant database takes 36 hours on a standard workstation. In this thesis, we look to address the problem by accelerating protein searching using Field Programmable Gate Arrays. We focus our attention on the BLASTP heuristic, building on work done... Read More

Elastic applications are primarily interested in minimal delay achievable for their messages under current network load. In this paper, we investigate how to transmit such messages over a bottleneck link efficiently and fairly.

This thesis examines in detail the Hardware-Accelerated Identification of Languages (HAIL) project. The goal of HAIL is to provide an accurate means to identify the language and encoding used in streaming content, such as documents passed over a high-speed network. HAIL has been implemented on the Field-programmable Port eXtender (FPX), an open hardware platform developed at Washington University in St. Louis. HAIL can accurately identify the primary languages and encodings used in text at rates much higher than what can be achieved by software algorithms running on microprocessors.

We present novel approaches to managing three key resources in an event-driven sensornet OS: memory, energy, and peripherals. We describe the factors that necessitate using these new approaches rather than existing ones. A combination of static allocation and compile-time virtualization isolates resources from one another, while dynamic management provides the flexibility and sharing needed to minimize worst-case overheads. We evaluate the effectiveness and efficiency of these management policies in comparison to those of TinyOS 1.x, SOS, MOS, and Contiki. We show that by making memory, energy, and peripherals first-class abstractions,... Read More

A challenge for many wireless sensor networks is to remain operational for long periods of time on a very limited power supply. While many power management protocols have been proposed, a solution does not yet exist that allows them to be seamlessly integrated into the existing systems. In this paper we study the architectural support required to resolve this issue. We propose a framework that separates sleep scheduling from the basic MAC layer functionality and provide a set of unified interfaces between them. This framework enables different sleep scheduling policies... Read More

Radio power management is of paramount concern in wireless sensor networks that must achieve long lifetimes on scarce amounts of energy. While a multitude of power management protocols have been proposed in the past, the lack of system support for flexibly integrating them with a diverse set of applications and network platforms has made them difficult to use. Instead of proposing yet another power management protocol, this paper focuses on providing link layer support towards realizing a Unified Power Management Architecture (UPMA) for flexible radio power management in wireless sensor... Read More

In many wireless sensor networks, energy is an extremely limited resource. While many different power management strategies have been proposed to help reduce the amount of energy wasted, application developers still face two fundamental challenges when developing systems with stringent power constraints. First, existing power management strategies are usually tightly coupled with network protocols and other system functionality. This monolithic approach has led to standalone solutions that cannot easily be reused or extended to other applications or platforms. Second, different power management strategies make different and sometimes even conflicting assumptions... Read More

The amount of biosequence data being produced each year is growing exponentially. Extracting useful information from this massive amount of data is becoming an increasingly difficult task. This thesis focuses on accelerating the most widely-used software tool for analyzing genomic data, BLAST. This thesis presents Mercury BLAST, a novel method for accelerating searches through massive DNA databases. Mercury BLAST takes a streaming approach to the BLAST computation by offloading the performance-critical sections onto reconfigurable hardware. This hardware is then used in combination with the processor of the host system to... Read More

Heuristic optimization methods are adaptive when they sample problem solutions based on knowledge of the search space gathered from past sampling. Recently, competent evolutionary optimization methods have been developed that adapt via probabilistic modeling of the search space. However, their effectiveness requires the existence of a compact problem decomposition in terms of prespecified solution parameters. How can we use these techniques to effectively and reliably solve program learning problems, given that program spaces will rarely have compact decompositions? One method is to manually build a problem-specific representation that is more... Read More

Virtualization has been proposed as a vehicle for overcoming the growing problem of internet ossification [1]. This paper studies the problem of mapping diverse virtual networks onto a common physical substrate. In particular, we develop a method for mapping a virtual network onto a substrate network in a cost-efficient way, while allocating sufficient capacity to virtual network links to ensure that the virtual network can handle any traffic pattern allowed by a general set of traffic constraints. Our approach attempts to find the best topology in a family of backbone-star... Read More

Profile Hidden Markov models are highly expressive representations of functional units, or motifs, conserved across protein sequences. Profile-HMM search is a powerful computational technique that is used to annotate new sequences by identifying occurrences of known motifs in them. With the exponential growth of protein databases, there is an increasing demand for acceleration of such techniques. We describe an accelerator for the Viterbi algorithm using a two-stage pipelined design in which the first stage is implemented in parallel reconfigurable hardware for greater speedup. To this end, we identify algorithmic modifications... Read More

Applications for constrained embedded systems are subject to strict runtime and resource utilization bounds. With soft core processors, application developers can customize the processor for their application, constrained by available hardware resources but aimed at high application performance. The more reconfigurable the processor is, the more options the application developers will have for customization and hence increased potential for improving application performance. However, such customization entails developing in-depth familiarity with all the parameters, in order to configure them effectively. This is typically infeasible, given the tight time-to-market pressure on the... Read More

The Castro and Liskov Byzantine Fault Tolerance protocol for replicated state machines (CLBFT) provides a practical means of tolerating arbitrary replica failures in replicated passive data servers. For better performance, CLBFT uses Message Authentication Codes (MAC) instead of public Key cryptography to authenticate messages and preserves replica consistency even in the presence of malicious clients. However, CLBFT is susceptible to potential attacks by malicious clients using corrupted MACs to force replica groups into expensive configuration changes repeatedly. While not affecting correctness, this vulnerability can seriously impair the performance of the... Read More

The wide-spread use of mobile computing devices has led to an increased demand for applications that operate dependably in opportunistically formed networks. A promising approach to supporting software development for such dynamic settings is to rely on the context-aware computing paradigm, in which an application views the state of the surrounding ad hoc network as a valuable source of contextual information that can be used to adapt its behavior. Collecting context information distributed across a constantly changing network remains a significant technical challenge. This dissertation presents a query-centered approach to... Read More

To discover an efficient fair sending rate for a flow, Transmission Control Protocol (TCP) saturates the bottleneck link and its buffer until the router discards a packet. Such TCP-caused queuing is detrimental for interactive and other delay-sensitive applications. In this paper, we present Multimodal Control Protocol (MCP) which strives to maintain low queues and avoid congestion losses at network links. The multimodal MCP engages routers and hosts in limited explicit communication. A distinguishing property of MCP is stable transmission after converging to efficient fair states. To ensure convergence to fairness,... Read More

The lack of per-flow bandwidth reservation in today's Internet limits the quality of service that an information service provider can provide. This dissertation introduces the reserved delivery subnetwork (RDS), a mechanism that provides consistent quality of service by implementing aggregate bandwidth reservation. A number of design and deployment issues of RDSs are studied. First, the configuration problem of a single-server RDS is formulated as a minimum concave cost network flow problem, which properly reflects the economy of bandwidth aggregation, but is also an NP-hard problem. To make the RDS configuration... Read More

Cardiac high spatio-temporal optical mapping provides a unique opportunity to investigate the dynamics of propagating waves of excitation during ventricular arrhythmia and defibrillation. However, studies using single camera imaging systems are hampered by the inability to monitor electrical activity from the entire surface of the heart. We have developed a three dimensional panoramic imaging system which allows high-resolution and high-dynamic-range optical mapping from the entire surface of the heart. Rabbit hearts (n=4) were Langendorff perfused and imaged by the system during sinus rhythm, epicardial pacing, and arrhythmias. The reconstructed 3D... Read More

Background: Microarray data preprocessing, such as differentially expressed (DE) genes selection, is performed prior to higher level statistical analysis in order to account for technical variability. Preprocessing for the Affymetrix GeneChip includes background correction, normalisation and summarisation. Numerous preprocessing methods have been proposed with little consensus as to which is the most suitable. Furthermore, due to poor concordance among results from cross-platform analyses, protocols are being developed to enable cross-platform reproducibility. However, the effect of data analysis on a single platform is still unknown. The objective of our study is... Read More

CAST is a coordination model designed to support interactions among agents executing on hosts that make up a mobile ad hoc network (MANET). From an application programmer’s point of view, CAST makes it possible for operations to be executed at arbitrary locations in space, at prescribed times which may be in the future, and on remote hosts even when no end-to-end connected route exists between the initiator and target(s) of the operation. To accomplish this, CAST assumes that each host moves in space in accordance with a motion profile which... Read More

Identification of groups of functionally related genes from high throughput gene expression data is an important step towards elucidating gene functions at a global scale. Most existing approaches treat gene expression data as points in a metric space, and apply conventional clustering algorithms to identify sets of genes that are close to each other in the metric space. However, they usually ignore the topology of the underlying biological networks. In this paper, we propose a network-based clustering method that is biologically more realistic. Given a gene expression data set, we... Read More

Identifying intrinsic structures in large networks is a fundamental problem in many fields, such as biology, engineering and social sciences. Motivated by biology applications, in this paper we are concerned with identifying community structures, which are densely connected sub-graphs, in large biological networks. We address several critical issues for finding community structures. First, biological networks directly constructed from experimental data often contain spurious edges and may also miss genuine connections. As a result, community structures in biological networks are often weak. We introduce simple operations to capture local neighborhood structures... Read More

Groupware activities provide a powerful representation for many collaborative tasks. Today, the technologies that support typical groupware applications often assume a stable wired network infrastructure. The potential for collaboration in scenarios that lack this fixed infrastructure remains largely untapped. Such scenarios include activities on construction sites, wilderness exploration, disaster recovery, and rapid intervention teams. Communication in these scenarios can be supported using wireless ad hoc networks, an emerging technology whose full potential is yet to be understood and realized. In this paper, we consider the fundamental technical issues that need... Read More

Designing software that supports collaboration among multiple users in mobile ad hoc networks is challenging due to the dynamic network topology and inherent unpredictability of the environment. However, as we increasingly migrate to using mobile computing platforms, there is a pertinent need for software that can support a wide range of collaborative activities anywhere and at any time without relying on any external infrastructure. In this paper, we adopt the workflow model to represent the structure of an activity that involves multiple tasks being performed in a structured, collaborative fashion... Read More

Although many algorithms and architectures have been proposed, the design of efficient packet classification systems remains a challenging problem. The diversity of filter specifications, the scale of filter sets, and the throughput requirements of high speed networks all contribute to the difficulty. We need to review the algorithms from a high-level point-of-view in order to advance the study. This level of understanding can lead to significant performance improvements. In this dissertation, we evaluate several existing algorithms and present several new algorithms as well. The previous evaluation results for existing algorithms... Read More

The field of manifold learning provides powerful tools for parameterizing high-dimensional data points with a small number of parameters when this data lies on or near some manifold. Images can be thought of as points in some high-dimensional image space where each coordinate represents the intensity value of a single pixel. These manifold learning techniques have been successfully applied to simple image sets, such as handwriting data and a statue in a tightly controlled environment. However, they fail in the case of natural image sets, even those that only vary... Read More

Middleware for Distributed Real-time and Embedded (DRE) systems has grown more and more complex in recent years due to the varying functional and temporal requirements of complex real-time applications. To enable DRE middleware to be configured and customized to meet the demands of different applications, a body of ongoing research has focused on applying model-driven development techniques to developing QoS-enabled middleware. While current approaches for modeling middleware focus on easing the task of as-assembling, deploying and configuring middleware and middleware-based applications, a more formal basis for correct middleware composition and... Read More

Distributed real-time and embedded (DRE) systems have stringent constraints on timeliness and other properties whose assurance is crucial to correct system behavior. Formal tools and techniques play a key role in verifying and validating system properties. However, many DRE systems are built using middleware frameworks that have grown increasingly complex to address the diverse requirements of a wide range of applications. How to apply formal tools and techniques effectively to these systems, given the range of middleware configuration options available, is therefore an important research problem. This paper makes three... Read More

Camera manipulation is a hard problem since a graphics camera is defined by specifying 11 independent parameters. Manipulating such a high-dimensional space to accomplish specific tasks is difficult and requires a certain amount of expertise. We present an intuitive interface that allows novice users to perform camera operations in terms of the change they want see in the image. In addition to developing a natural means for camera interaction, our system also includes a novel interface for viewing and organizing previously saved views. When exploring complex 3D data-sets a single... Read More

The notion of a proof is central to all of mathematics. In the language of formal logic, a proof is a finite sequence of inferences from a set of axioms, and any statement one yields from such a finitistic procedure is called a theorem. For better or for worse, this is far from the form a traditional mathematical proof takes. Mathematicians write proofs that omit routine logical steps, and details deemed tangential to the central result are often elided. These proofs are fuzzy and human-centric, and a great amount of... Read More

To isolate computations from denial of service (DoS) attacks and other forms of adversarial interference, it is necessary to constrain the effects of interactions among computations. This paper makes four contributions to research on isolation of computations from adversarial interference: (1) it describes the design and implementation of a kernel level scheduling policy to control the effects of adversarial attacks on computations’ execution; (2) it presents formal models of the system components that are involved in a representative DoS attack scenario; (3) it shows how model checking can be used... Read More

The GENI Project (Global Environment for Network Innovation) is a major NSF-sponsored initiative that seeks to create a national research facility to enable experimental deployment of innovative new network architectures on a sufficient scale to enable realistic evaluation. One key component of the GENI system will be the GENI Backbone Platform (GBP) that provides the resources needed to allow multiple experimental networks to co-exist within the shared GENI infrastructure. This report reviews the objectives for the GBP, reviews the key issues that affect its design and develops a detailed reference... Read More

A diversified network substrate enables multiple end-to-end metanetworks to co-exist within a shared physical infrastructure. Metanetworks are implemented by metarouters, hosted by substrate routers, and metarouters are connected by metalinks. The substrate allocates resources (both link bandwidth and processing resources) to metarouters based on advance reservations received from metanetwork planning systems. It also enables dynamic creation of access metalinks, connecting end systems to metarouters, and supports mobility of end systems under the control of their metanetworks. This report defines a model for a diversified internet and presents a detailed design... Read More

Pipelining an algorithmis a popularmethod of increasing the performance of many computation-intensive applications. Often, one wants to form pipelines composed mostly of commonly used simple building blocks such as DSP components, simple math operations, encryption, or pattern matching stages. Additionally, one may desire to map these processing tasks to different computational resources based on their relative performance attributes (e.g., DSP operations on an FPGA). Auto-Pipe is composed of the X Language, a flexible interface language that aids the description of complex dataflow topologies (including pipelines); X-Com, a compiler for the... Read More

An increasing number of distributed real-time embedded systems face the critical challenge of providing Quality of Service (QoS) guarantees in open and unpredictable environments. For example, such systems often need to enforce CPU utilization bounds on multiple processors in order to avoid overload and meet end-to-end dead-lines, even when task execution times deviate significantly from their estimated values or change dynamically at run-time. This dissertation presents an adaptive QoS control framework which includes a set of control design methodologies to provide robust QoS assurance for systems at different scales. To... Read More

Knuth-Bendix completion is a technique for equational automated theorem proving based on term rewriting. This classic procedure is parametrized by an equational theory and a (well-founded) reduction order used at runtime to ensure termination of intermediate rewriting systems. Any reduction order can be used in principle, but modern completion tools typically implement only a few classes of such orders (e.g., recursive path orders and polynomial orders). Consequently, the theories for which completion can possibly succeed are limited to those compatible with an instance of an implemented class of orders. Finding... Read More

Byzantine agreement protocols for replicated deterministic state machines guarantee that externally requested operations continue to execute correctly even if a bounded number of replicas fail in arbitrary ways. The state machines are passive, with clients responsible for any active ongoing application behavior. However, the clients are unreplicated and outside the fault-tolerance boundary. Consequently, agreement protocols for replicated state machines do not guarantee continued correct execution of long-running client applications. Building on the Castro and Liskov Byzantine Fault Tolerance protocol for unreplicated clients (CLBFT), we present a practical algorithm for Byzantine... Read More

Finding all gene structures is a crucial step in obtaining valuable information from genomic sequences. It is still a challenging problem, especially for vertebrate genomes, such as the human genome. Expressed Sequence Tags (ESTs) provide a tremendous resource for determining intron-exon structures. However, they are short and error prone, which prevents existing methods from exploiting EST information efficiently. This dissertation addresses three aspects of using ESTs for gene structure annotation. The first aspect is using ESTs to improve de novo gene prediction. Probability models are introduced for EST alignments to... Read More

This paper considers the problem of virtualizing the resources of a network processor (NP) in order to allow multiple third-parties to execute their own virtual router software on a single physical router at the same time. Our broad interest is in designing such a router capable of supporting virtual networking. We discuss the issues and challenges involved in this virtualization, and then describe specific techniques for virtualizing both the control and data-plane processors on NPs. For Intel IXP NPs in particular, we present a dynamic, macro-based technique for virtualization that... Read More

Radio power management is of paramount concern in wireless sensor networks (WSNs) that must achieve long lifetimes on scarce amount of energy. Previous work has treated communication and sensing separately, which is insufficient for a common class of sensor networks that must satisfy both sensing and communication requirements. Furthermore, previous approaches focused on reducing energy consumption in individual radio states resulting in suboptimal solutions. Finally, existing power management protocols often assume simplistic models that cannot accurately reflect the sensing and communication properties of real-world WSNs. We develop a unified power... Read More

Autonomous mobile agent navigation is crucial to many mis-sion-critical applications (e.g., search and rescue missions in a disaster area). In this paper, we present how sensor net-works may assist probabilistic roadmap methods (PRMs), a class of efficient navigation algorithms particularly suit-able for dynamic environments. A key challenge of apply-ing PRM algorithms in dynamic environment is that they re-quire the spatiotemporal sensing of the environment to solve a given navigation problem. To facilitate navigation, we propose a set of query strategies that allow a mobile agent to periodically collect real-time information... Read More

Motion planning algorithms enable us to find feasible paths for moving objects. These algorithms utilize feasibility checks to differentiate valid paths from invalid ones. Unfortunately, the computationally expensive nature of such checks reduces the effectiveness of motion planning algorithms. However, by using hardware acceleration to speed up the feasibility checks, we can greatly enhance the performance of the motion planning algorithms. Of course, such acceleration is not limited to feasibility checks; other components of motion planning algorithms can also be accelerated using specially designed hardware. A Field Programmable Gate Array... Read More

Collision detection algorithms check the intersection between two given surfaces or volumes. They are computationally-intensive and the capabilities of conventional processors limit their performance. Hardware acceleration of these algorithms can greatly benefit the systems that need collision detection to be performed in real-time. A Field Programmable Gate Array (FPGA) is a great platform to achieve such acceleration. An FPGA is a collection of digital gates which can be reprogrammed at run time, i.e., it can be used as a CPU that reconfigures itself for a given task. In this paper,... Read More

High-performance intrusion detection and prevention systems are needed by network administrators in order to protect Internet systems from attack. Researchers have been working to implement components of intrusion detection and prevention systems for the highly popular Snort system in reconfigurable hardware. While considerable progress has been made in the areas of string matching and header processing, complete systems have not yet been demonstrated that effectively combine all of the functionality necessary to perform intrusion detection and prevention for real network systems. In this thesis, three architectures to perform rule processing,... Read More

Autonomous mobile entity navigation through dynamic and unknown environments is an essential part of many mission critical applications like search and rescue and fire fighting. The dynamism of the environment necessitates the mobile entity to constantly maintain a high degree of awareness of the changing environment. This criteria makes it difficult to achieve good navigation performance by using just on-board sensors and existing navigation methods and motivates the use of wireless sensor networks (WSNs) to aid navigation. In this paper, we present a novel approach that integrates a roadmap based... Read More

Structured program editors can lower the entry barrier for beginning computer science students by preventing syntax errors. However, when editors force programs to be executable after every edit, a rigid development process results. We explore the use of a separate edit-time grammar that is more permissive than the runtime grammar. This helps achieve a balance between structured editing and flexibility, particularly in live development environments. JPie is a graphical programming environment that applies this separation to the live development of Java applications. We present the design goals for JPie’s edit-time... Read More

We present smartacking, a technique that improves performance of Transmission Control Protocol (TCP) via adaptive generation of acknowledgments (ACKs) at the receiver. When the bottleneck link is underutilized, the receiver transmits an ACK for each delivered data segment and thereby allows the connection to acquire the available capacity promptly. When the bottleneck link is at its capacity, the smartacking receiver sends ACKs with a lower frequency reducing the control traffic overhead and slowing down the congestion window growth to utilize the network capacity more effectively. To promote quick deployment of... Read More

The Edinburgh Logical Framework (LF) has been proposed as a system for expressing inductively defined sets. I will present an inductive definition of the set of manifold meshes in LF. This definition takes into account the topological characteri-zation of meshes, namely their Euler Characteristic. I will then present a set of dependent data types based on this inductive def-inition. These data types are defined in a programming language based on LF. The language’s type checking guarantees that any typeable expression represents a correct manifold mesh. Furthermore, any mesh can be... Read More

Active Queue Management (AQM) is an important problem in networking. In this paper, we propose a general functional optimiza-tion model for designing AQM schemes. Unlike the previous static func-tion optimization models based on the artificial notion of utility function, the proposed dynamic functional optimization formulation allows us to directly characterize the desirable system behavior of AQM and design AQM schemes to optimally control the dynamic behavior of the system. Such a formulation also allows adaptive control which enables the AQM scheme to continuously adapt to dynamic changes of networking con-ditions.... Read More

Many mission-critical wireless sensor network applications must resolve the inherent conflict between the tight resource constraints on each sensor node, particularly in terms of energy, with the need to achieve desired quality of service such as end-to-end real-time performance. To address this challenge we propose the Real-time Power-Aware Routing (RPAR) protocol. RPAR achieves required communication delays at minimum energy cost by dynamically adapting the transmission power and routing decisions based on packet deadlines. RPAR integrates a geographic forwarding policy cognizant of deadlines, power, and link quality with new algorithms for... Read More

Given a matrix of values, rearrangement clustering involves rearranging the rows of the matrix and identifying cluster boundaries within the linear ordering of the rows. The TSP+k algorithm for rear-rangement clustering was presented in [3] and its implementation is described in this note. Using this code, we solve a 2,467-gene expression data clustering problem and identify “good” clusters that con-tain close to eight times the number of genes that were clustered by Eisen et al. (1998). Furthermore, we identify 106 functional groups that were overlooked in that paper. We make... Read More

Branch-and-bound and branch-and-cut use search trees to identify optimal solutions. In this paper, we introduce a linear search strategy which we refer to as cut-and-solve and prove optimality and completeness for this method. This search is different from traditional tree searching as there is no branching. At each node in the search path, a relaxed problem and a sparse problem are solved and a constraint is added to the relaxed problem. The sparse problems provide incumbent solutions. When the constraining of the relaxed problem becomes tight enough, its solution value... Read More

Combinatorial optimization problems are ubiquitous in scientific research, engineering, and even our daily lives. A major research focus in developing combinatorial search algorithms has been on the attainment of efficient methods for deriving tight lower and upper bounds. These bounds restrict the search space of combinatorial optimization problems and facilitate the computa-tion of what might otherwise be intractable problems. In this paper, we survey the history of the use of bounds in both AI and OR. While research has been extensive in both domains, until very recently it has been... Read More

Given a matrix of values in which the rows correspond to objects and the columns correspond to features of the objects, rearrangementclustering is the problem of rearranging the rows of the matrix such that the sum of the similarities between adjacent rows is maximized. Referred to by various names and reinvented several times, this clustering technique has been extensively used in many fields over the last three decades. In this paper, we point out two critical pitfalls that have been previously overlooked. The first pitfall is deleterious when rearrangement clustering... Read More

Methods are presented for synthesizing delay-insensitive circuits whose behavior is specified by Petri net models of macromodular control elements. These control elements implement five natural functions used in asynchronous system design. Particular attention is paid to modules requiring mutual exclusion where metastability must be carefully controlled.

The Open Network Laboratory (ONL) is a remotely accessible network testbed designed to enable network researchers to conduct experiments using high performance routers and applications. ONL™s Remote Laboratory Interface (RLI) allows users to easily configure a network topology, initialize and modify the routers™ routing tables, packet classification tables and queuing parameters. It also enables users to add software plugins to the embedded processors available at each of the routers™ ports, enabling the introduction of new functionality. The routers provide a large number of built-in counters to track various aspects of... Read More

This work presents a novel rendering technique inspired by artistic approaches. Instead of trying to recreate the appearance of a traditional medium, such as charcoal or watercolor, this approach is a mixture of both photo-realism and abstraction. Artists use a process of abstraction to provide structural information about subjects that do not have clearly defined shapes, such as groups of leaves in a tree. For example, an artist will first use a color wash to approximate a group of leaves, then add detail on top of parts of this wash... Read More

Auto-Pipe is a tool that aids in the design, evaluation, and implementation of pipelined applications that are distributed across a set of heterogeneous devices including multiple processors and FPGAs. It has been developed to meet the needs arising in the domains of communications, computation on large datasets, and real time streaming data applications. In this paper, the Auto-Pipe design flow is introduced and two sample applications, developed for compatibility with the Auto-Pipe system, are presented. The sample applications are the Triple-DES encryption standard and a subset of the signal-processing pipeline... Read More

Reference counting is a garbage-collection technique that maintains a per-object count of the number of pointers to that object. When the count reaches zero, the object must be dead and can be collected. Although it is not an exact method, it is well suited for real-time systems and is widely implemented, sometimes in conjunction with other methods to increase the overall precision. A disadvantage of reference counting is the extra storage trac that is introduced. In this paper, we describe a new cache write-back policy that can substantially decrease the... Read More

Reinforcement learning (RL) has shown itself to be an effective paradigm for solving optimal control problems with a finite number of states. Generalizing RL techniques to problems with a continuous state space has proven a difficult task. We present an approach to modeling the RL value function using a manifold representation. By explicitly modeling the topology of the value function domain, traditional problems with discontinuities and resolution can be addressed without resorting to complex function approximators. We describe how manifold techniques can be applied to value-function approximation, and present methods... Read More

An ultrasound imaging system includes transmitting ultrasound waves into a human body, collecting the reflections, manipulating the reflections, and then displaying them on computer screen as a grayscale image. The standard approach for ultrasound imaging is to use the fundamental frequency from the reflected signal to form images. However, it has been shown that images generated using the harmonic content have improved resolution as well as reduced noise, resulting in clearer images. Although harmonic imaging has been shown to return improved images, this has never been shown with a B-mode,... Read More

Recent advances in DNA sequencing have resulted in several terabytes of DNA sequences. These sequences themselves are not informative. Biologists usually perform comparative analysis of DNA queries against these large terabyte databases for the purpose of developing hypotheses pertaining to function and relation. This is typically done using software on a general multiprocessor. However, these data sets far exceed the capabilities of the modern processor and performing sequence similarity analysis is increasingly becoming less efficient. There is an urgent need for more efficient ways of querying large DNA sequences for... Read More

The scope of wireless sensor network (WSN) applications has traditionally been restricted by physical sensor coverage and limited computational power. Meanwhile, IP networks like the Internet offer tremendous connectivity and computing resources. This paper presents Agimone, a middleware layer that integrates sensor and IP networks as a uniform platform for flexible application deployment. This layer allows applications to be deployed on the WSN in the form of mobile agents which can autonomously discover and migrate to other WSNs, using a common IP backbone as a bridge. It facilitates data sharing... Read More

These days we witness a major shift towards small, mobile devices, capable of wireless communication. Their communication capabilities enable them to form mobile ad hoc networks and share resources and capabilities. Service Oriented Computing (SOC) is a new emerging paradigm for distributed computing that has evolved from object-oriented and component-oriented computing to enable applications distributed within and across organizational boundaries. Services are autonomous computational elements that can be described, published, discovered, and orchestrated for the purpose of developing applications. The application of the SOC model to mobile devices provides a... Read More

The increasing ubiquity of wireless mobile computing platforms has opened up the potential for unprecedented levels of communication, coordination and collaboration among mobile computing devices, most of which will occur in an ad hoc, on-demand manner. This paper describes SPAWN, a middleware supporting service provision in ad-hoc wireless networks. The aim of SPAWN is to provide the software resources on mobile devices that facilitate electronic collaboration. This is achieved by applying the principles of service oriented computing (SOC), an emerging paradigm that has seen success in wired settings. SPAWN is... Read More

The rapid expansion of the Internet and the increasingly wide deployment of wireless networks provide opportunities to deliver streaming media content to users at anywhere, anytime. To ensure good user experience, it is important to battle adversary effects, such as delay, loss and jitter. In this thesis, we first study efficient loss recovery schemes, which require pure XOR operations. In particular, we propose a novel scheme capable of recovering up to 3 packet losses, and it has the lowest complexity among all known schemes. We also propose an efficient algorithm... Read More

Developing distributed real-time and embedded (DRE)systems in which multiple quality-of-service (QoS) dimen-sions must be managed is an important and challenging R&D problem. This paper makes three contributions to re-search on multi-dimensional QoS for DRE systems. First, itdescribes the design and implementation of a fault-tolerantreal-time CORBA event service for The ACE ORB (TAO).Second, it describes our enhancements and extensions tofeatures in TAO, to integrate real-time and fault toleranceproperties. Third, it presents an empirical evaluation ofour approach. Our results show that with some refinements,real-time and fault-tolerance features can be integrated ef-fectively and... Read More

With the explosion of the World Wide Web, the Internet infrastructure faces new challenges in providing high performance for data traffic. First, it must be able to pro-vide a fair-share of congested link bandwidth to every flow. Second, since web traffic is inherently interactive, it must minimize the delay for data transfer. Recent studies have shown that queue management algorithms such as Tail Drop, RED and Blue are deficient in providing high throughput, low delay paths for a data flow. Two major shortcomings of the current algorithms are: they allow... Read More

This project presents a novel automated framework for microprocessor instruction set exploration that allows users to extend a basic MIPS ISA with new multimedia instructions (including custom vector instructions, a la AltiVec and MMX/SSE). The infrastructure provides users with an extension language that automatically incorporates extensions into a synthesizable processor pipeline model and an executable instruction set simulator. We implement popular AltiVec and MMX extensions using this framework and present experimental results that show significant performance gains of customized microprocessor.

Modern routers and switch fabrics can have hundreds of input and output ports running at up to 10 Gb/s; 40 Gb/s systems are starting to appear. At these rates, the performance of the buffering and queuing subsystem becomes a significant bottleneck. In high performance routers with more than a few queues, packet buffering is typically implemented using DRAM for data storage and a combination of off-chip and on-chip SRAM for storing the linked-list nodes and packet length, and the queue headers, respectively. This paper focuses on the performance bottlenecks associated... Read More

In this paper, we will present a framework for the statistical analysis of the execution time of program units. We will show alternative methods for computing the distribution of the execution times and provide justification for the use of each of the methods presented. We will estimate the worst-case execution time (WCET) of the program units using several methods and compare the results of these methods. We will also present a new method for estimating the WCET, based on the theory of extreme value distributions.

The hierarchical Bayesian Optimization Algorithm (hBOA) [24, 25] learns bit-strings by constructing explicit centralized models of a population and using them to generate new instances. This thesis is concerned with extending hBOA to learning open-ended program trees. The new system, BOA programming (BOAP), improves on previous probabilistic model building GP systems (PMBGPs) in terms of the expressiveness and open-ended flexibility of the models learned, and hence control over the distribution of individuals generated. BOAP is studied empirically on a toy problem (learning linear functions) in various configurations, and further experimental... Read More

While it is generally accepted that garbage-collected languages offer advantages over languages in which objects must be explicitly deallocated, real-time developers are leery of the adverse effects a garbage collector might have on real-time performance. Semiautomatic approaches based on regions have been proposed, but incorrect usage could cause unbounded storage leaks or program failure. Moreover, correct usage cannot be guaranteed at compile-time. Recently, real-time garbage collectors have been developed that provide a guaranteed fraction of the CPU to the application, and the correct operation of those collectors has been proven,... Read More

Programming robots to perform tasks autonomously is difficult. The environment or even the task may change at any moment. The main drawback is that this programming requires a team of highly skilled roboticists to monitor the robot and change its programming to accomplish the task. The system presented here allows robot controllers to be constructed by a non-specialist, using the included restricted natural language parser. The controller can further be refined by a non-specialist using keywords which represent the changes that each parameter makes to the behavior. To show that... Read More

Popular security techniques such as public-private key encryption, firewalls, and role-based access control offer significant protec-tion of system data, but offer only limited protection of the computations using that data from significant interference due to accident or adversarial attack. However, in an increasing number of modern systems, ensuring the reliable execution of system activities is every bit as important as ensuring data security. This paper makes three contributions to the state of the art in protection of the execution of system activities from accidental or adversarial interference. First, we consider... Read More