All Computer Science and Engineering Research

The wide-spread use of mobile computing devices has ledto an increased demand for applications that operate de-pendably in opportunistically formed networks. A promis-ing approach to supporting software development for suchdynamic settings is to rely on the context-aware computingparadigm, in which an application views the state of the sur-rounding ad hoc network as a valuable source of contextualinformation that can be used to adapt its behavior. Col-lecting context information distributed across a constantlychanging network remains a significant technical challenge.With this in mind, we propose a query-centered approach tosimplifying context interactions in... Read More

Context-aware computing refers to a paradigm in which applications sense aspects of the environment and use this information to adjust their behavior in response to changing circumstances. In this paper, we present a formal model and notation (Context UNITY) for expressing quintessential aspects of context-aware computations; existential quantification, for instance, proves to be highly effective in capturing the notion of discovery in open systems. Furthermore, Context UNITY treats context in a manner that is relative to the specific needs of an individual application and promotes an approach to context maintenance... Read More

Manifold learning has become a vital tool in data driven methods for interpretation of video, motion capture, and handwritten character data when they lie on a low dimen-sional, non-linear manifold. This work extends manifold learning to classify and parameterize unlabeled data which lie on multiple, intersecting manifolds. This approach sig-nificantly increases the domain to which manifold learn-ing methods can be applied, allowing parameterization of example manifolds such as figure eights and intersecting paths which are quite common in natural data sets. This approach introduces several technical contributions which may be... Read More

Middleware for distributed real-time embedded (DRE) systems has grown increasingly complex, to address functional and temporal requirements of diverse applications. While current approaches to modeling middleware have eased the task of assembling, deploying and configuring middleware and the applications that use it, a lower-level set of formal models is needed to uncover subtle timing and liveness hazards introduced by interference between and within distributed computations, particularly in the face of alternative middleware concurrency strategies. In this paper, we propose timed automata as a formal model of low-level middleware building blocks... Read More

Middleware for distributed real-time embedded (DRE) systems has grown more and more complex in recent years, to address functional and temporal requirements of complex real-time applications. While current approaches for modeling middleware have eased the task of assembling, deploying and configuring middleware and applications, a more formal, fundamental and lower-level set of models is needed to be able to uncover subtle safety and timing errors introduced by interference between computations, particularly in the face of alternative concurrency strategies in the middleware layer. In this paper, we examine how formal models... Read More

As the number of transistors on a single integrated circuit approach a billion, the problems of clock distribution, power consumption, multiple clock domains, meeting timing requirements, and reuse of subsystem designs grow ever more difficult. Coordinating a billion transistors with the present design methodologies will require hundreds of years of engineering time. A new design methodology is needed. The GALS (Globally Asynchronous Locally Synchronous) approach, that blends clockless and clocked subsystems is a strong contender.

Packet switched networks such as the Internet require packet classification at every hop in order to ap-ply services and security policies to traffic flows. The relentless increase in link speeds and traffic volume imposes astringent constraints on packet classification solutions. Ternary Content Addressable Memory (TCAM) devices are favored by most network component and equipment vendors due to the fast and de-terministic lookup performance afforded by their use of massive parallelism. While able to keep up with high speed links, TCAMs suffer from exorbitant power consumption, poor scalability to longer search... Read More

We present a novel architecture and execution model for an infrastructure supporting fault-tolerant, long-running distributed applications spanning multiple administrative domains. Components for both transaction processing and persistent state are replicated across multiple servers, en-suring that applications continue to function correctly de-spite arbitrary (Byzantine) failure of a bounded number of servers. We give a formal model of application execution, based on atomic execution steps, linearizability and a sep-aration between data objects and transactions that act on them. The architecture is designed for robust interoperability across domains, in an open and shared... Read More

Crossbar-based switches are commonly used to implement routers with throughputs up to about 1 Tb/s. The advent of work-conserving crossbar scheduling algorithms now makes it possible to engineer sys-tems that perform well, even under extreme traffic conditions. Unfortunately, all the published work-conservation results for crossbar scheduling apply only to systems that switch fixed-length cells, not variable length packets. Routers that use a cell-based crossbar with a nominally work-conserving scheduler to switch variable length packets can fail to be work-conserving at the external links, since the router cannot forward a packet... Read More

Language X provides a formal and intuitive way to describe a series of interconnected processing fiblocks.fl Users of Language X may enter in a logical arrangement of blocks that describes the interconnection of their inputs and outputs. Language X also provides syntax for specifying implementation details for processing blocks and for targeting the entire architecture onto arbitrary sets of devices. Formally, Language X is a structure-only dataflow programming language (DFPL) that is heavily dependent on its library of functions.

Steganography, or information hiding, is to conceal the existence of messages so as to protect their confidentiality. We consider de-ciphering a stegoscript, a text with secret messages embedded within a covertext, and identifying the vocabularies used in the mes-sages, with no knowledge of the vocabularies and grammar in which the script was writ-ten. Our research was motivated by the prob-lem of identifying conserved non-coding func-tional elements (motifs) in regulatory regions of genome sequences, which we view as stego-scripts constructed by nature with a statis-tical model consisting of a dictionary and... Read More

Many real-time systems must control their CPU utiliza-tions in order to meet end-to-end deadlines and prevent over-load. Utilization control is particularly challenging in dis-tributed real-time systems with highly unpredictable work-loads and a large number of end-to-end tasks and processors. This paper presents the Decentralized End-to-end Utilization CONtrol (DEUCON) algorithm that can dynamically enforce desired utilizations on multiple processors in such systems. In contrast to centralized control schemes adopted in earlier work, DEUCON features a novel decentralized control struc-ture that only requires localized coordination among neigh-bor processors. DEUCON is systematically designed... Read More

A key challenge for distributed real-time and embedded (DRE) middleware is maintaining both system reliability and desired real-time performance in unpredictable envi-ronments where system workload and resources may fluc-tuate significantly. This paper presents FC-ORB, a real-time Object Request Broker (ORB) middleware that em-ploys end-to-end utilization control to handle fluctuations in application workload and system resources. The contribu-tions of this paper are three-fold. First, we present a novel utilization control service that enforces desired CPU utiliza-tion bounds on multiple processors by adapting the rates of end-to-end tasks within user-specified ranges. Second,... Read More

Linear perspective is a good approximation to the format in which the human visual system conveys 3D scene information to the brain. Artists expressing 3D scenes, however, create nonlinear projections that balance their linear perspective view of a scene with elements of aesthetic style, layout and relative importance of scene objects. Manipulating the many parameters of a linear perspective camera to achieve a desired view is not easy. Controlling and combining mul-tiple such cameras to specify a nonlinear projection is an even more cumbersome task. This paper presents a direct... Read More

In this paper a language-based approach to functionally correct imperative programming is proposed. The approach is based on a programming language called RSP1, which combines dependent types, general recursion, and imperative features in a type-safe way, while preserving decidability of type checking. The methodology used is that of internal verification, where programs manipulate programmer-supplied proofs explicitly as data. The fundamental technical idea of RSP1 is to identify problematic operations as impure, and keep them out of dependent types. The resulting language is powerful enough to verify statically non-trivial properties of... Read More

This paper presents MobiQuery, a spatiotemporal query service that allows mobile users to periodically collect sensor data from the physical environment through wireless sensor networks. A salient feature of \MQ is that it can meet stringent spatiotemporal performance constraints, including query latency, data freshness, and changing areas of interest due to user mobility. We present three just-in-time prefetching protocols that enable MobiQuery to achieve desired spatiotemporal performance despite low node duty cycles, while significantly reducing communication overhead. We validate our approach through both theoretical analysis and extensive simulations under realistic... Read More

Recent empirical studies revealed that multi-hop wireless networks like wireless sensor networks and 802.11 mesh networks are inherently lossy. This finding introduces important new challenges for topology control. Existing topology control schemes often aim at maintaining network connectivity that cannot guarantee satisfactory path quality and communication performance when underlying links are lossy. In this paper, we present a localized algorithm, called Configurable Topology Control (CTC), that can configure a network topology to different provable quality levels (quantified by worst-case dilation bounds in terms of expected total number of transmisssions) required... Read More

This paper proposes the Minimum Power Configuration (MPC) approach to power management in wireless sensor networks. In contrast to earlier research that treats different radio states (transmission/reception/idle) in isolation, MPC integrates them in a joint optimization problem that depends on both the set of active nodes and the transmission power. We propose four approximation algorithms with provable performance bounds and two practical routing protocols. Simulations based on realistic radio models show that the MPC approach can conserve more energy than existing minimum power routing and topology control protocols. Furthermore, it... Read More

Many mission-critical distributed real-time applicationsmust handle aperiodic tasks with hard end-to-end dead-lines. Existing middleware such as RT-CORBA lacksschedulability analysis and run-time scheduling mecha-nisms that can provide real-time guarantees to aperiodictasks. This paper makes the following contributions to thestate of the art for end-to-end aperiodic scheduling in mid-dleware. First, we compare two approaches to aperiodicscheduling, the deferrable server and the aperiodic utiliza-tion bound, using representative workloads. Numerical re-sults show that the deferrable server analysis is less pes-simistic than the aperiodic utilization bounds when appliedoffline. Second, we propose a practical approach to... Read More

In this paper, we present a technique to automati-cally synthesize dancing moves for arbitrary songs. Our current implementation is for virtual characters, but it is easy to use the same algorithms for entertainer robots, such as robotic dancers, which fits very well to this year’s conference theme. Our technique is based on analyzing a musical tune (can be a song or melody) and synthesizing a motion for the virtual character where the character’s movement synchronizes to the musical beats. In order to analyze beats of the tune, we developed a... Read More

This paper describes a scheduling abstraction, called group scheduling, that emphasizes fine grain configurability of scheduling system semantics. The group scheduling approach described and evaluated in this paper is an extremely flexible framework within which a wide range of scheduling semantics can be expressed. The paper describes both the OS and middleware based implementations of the framework, and shows through evaluation that they produce the same behavior from a non-trivial set of application computations. Further, the evaluation shows that the framework can easily support application-aware scheduling algorithms to improve performance.

The primary goal of this research is to develop a perception based image editing system. The input to this system will be either a rendered image, a photograph, or a high dynamic range image. We are currently developing techniques that allow the user to edit these images in a perceptually intuitive manner. Specifically we are considering the following image editing features: (1) warm - cool image adjustment, (2) intensity adjustment, (3) contrast adjustment, and (4) detail adjustment. The algorithms we are developing can be used either in an interactive editing... Read More

Class hierarchy design is central to object-oriented software development. How-ever, it is sometimes difficult for developers to anticipate all the implications of a design until implementation is underway. To support experimentation with different designs, we extend prior work on live development environments to allow run-time modification of the class hierarchy. The result is a more fluid object-oriented development process, in which immediate feedback from the executing program can be used to guide hierarchy design. This thesis presents a framework and developer support for run-time modification of class inheritance relations in... Read More

Class hierarchy design is central to object-oriented software development. However, it is sometimes difficult for developers to anticipate all the implications of a design until implementation is underway. To support experimentation with different designs, we extend prior work on live development environments to allow run-time modification of the class hierarchy. The result is a more fluid object-oriented development process, in which immediate feedback from the executing program can be used to guide hierarchy design. This paper presents a framework and developer support for run-time modification of class inheritance relations in... Read More

Beginning programmers are best served by integrateddevelopment environments that adapt to their growingsophistication as programmers. To this end, we propose fourdesign goals for learning curve management in educationalprogramming environments. We provide pedagogicaljustification for each goal, describe possible supporting featuresets, and discuss the extent to which these goals have beenachieved in some current environments, particularly JPie, ourinteractive environment for live construction of Java applications.

This paper proposes Efficient Sleep Scheduling based on Application Timing (ESSAT), a novel power manage-ment scheme that aggressively exploits the timing seman-tics of wireless sensor network applications. We present three ESSAT protocols each of which integrates (1) a light-weight traffic shaper that actively shapes the workload inside the network to achieve predictable timing proper-ties over multiple hops, and (2) a local scheduling algorithm that wakes up nodes just-in-time based on the tim-ing properties of shaped workloads. Our ESSAT protocols have several distinguishing features. First, they can save significant energy with... Read More

Knuth’s buddy system is an attractive algorithm for managing storage allocation, and it can be made to operate in real time. However, the is-sue of defragmentation for heaps that are managed by the buddy system has not been studied. In this paper, we present strong bounds on the amount of storage necessary to avoid defragmentation. We then present an algorithm for defragmenting buddy heaps and present experiments from applying that algorithm to real and syn-thetic benchmarks. Our algorithm is within a factor of two of optimal in terms of the... Read More

Over 90 percent of all microprocessors are now used for real-time and embedded applications. The behavior of these applications is often constrained by the physical world. It is therefore important to devise higher-level languages and middleware that meet conventional functional requirements, as well as dependably and productively enforce real-time constraints. Real-Time Java is emerging as a safe, real-time environment. In this thesis we use it as our experimentation platform; however, our findings are easily adapted to other similar platforms. This thesis provides the following contributions to the study of safe... 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 need for static scheduling of tasks on processor pipelines. This thesis considers problems associated with determining optimal schedules for such pipelines. A collection of algorithms is presented with their utility determined by the size and other characteristics of the system. The algorithms employ heuristics,... Read More

Modern Network Intrusion Detection Systems (NIDS) inspect the network packet payload to check if it conforms to the security policies of the given network. This process, of-ten referred to as deep packet inspection, involves detection of predefined signature strings or keywords starting at an arbitrary location in the payload. String matching is a computationally intensive task and can become a potential bottleneck without high-speed processing. Since the conventional software-implemented string matching algorithms have not kept pace with the increasing network speeds, special purpose hardware solutions have been introduced. In this... Read More

Agilla is a mobile agent middleware that facilitates the rapid deployment of adaptive applications in wireless sensor networks (WSNs). Agilla allows users to create and inject special programs called mobile agents that coordinate through local tuple spaces, and migrate across the WSN performing application-specific tasks. This fluidity of code and state has the potential to transform a WSN into a shared, general-purpose computing platform capable of running several autonomous applications at a time, allowing us to harness its full potential. We have implemented and evaluated a fire tracking application to... Read More

Wireless sensor networks (WSNs) are difficult to pro-gram and usually run statically-installed software limiting its flexibility. To address this, we developed Agilla, a new middleware that increases network flexibility while simplifying application development. An Agilla network is deployed with no pre-installed application. Instead, users inject mobile agents that spread across nodes performing application-specific tasks. Each agent is autonomous, allowing multiple applications to share a network. Programming is simplified by allowing programmers to create agents using a high-level language. Linda-like tuple spaces are used for inter-agent communication and context discovery. This... Read More

This paper promotes a probabilistic approach for building models of local video statistics for use in background subtraction schemes. By shifting into a probabilistic framework, additional analytical tools become available for the creation and evaluation of these models. This paper continues to suggest the use of nonparametric statistical methods for measuring the quality of efficient local spatio-temporal models of video background distributions. Beginning with the familiar relative entropy distance between probability distributions, we create a new distance measure that can be used to quantitatively measure the quality of a probabilistic... Read More

This paper takes a systematic look at calculating the curvature of surfaces represented by triangular meshes. We have developed a suite of test cases for assessing the sensitivity of curvature calculations, to noise, mesh resolution, and mesh regularity. These tests are applied to existing discrete curvature approximation techniques and three common surface fitting methods (polynomials, radial basis functions and conics). We also introducea modification to the standard parameterization technique. Finally, we examine the behaviour of the curvature calculation techniques in the context of segmentation.

Software modification at run-time can facilitate rapid prototyping, streamline development and debugging, and enable interactive educational programming environments. However, sup-porting live fine-grain program modification while reaping the benefits of a compiled type-safe language is a challenging problem. This paper presents fine-grain dynamic classes that support live object-oriented software development in which a program can be modified during execution. We present an implementation of dynamic classes in Java that does not require modification of the Java Virtual Machine. Our implementation supports full interoperability between instances of dynamic classes and compiled classes,... Read More

JPie is a visual programming environment supporting live construction of Java applications. Class modifications, such as declaring instance variables and overriding methods, take effect immediately on existing instances of the class to encourage experimentation in an educational setting. Because programs are edited live, editing gestures must transform the program from one well-formed state to another, without intermediate ambiguous states. To accomplish this, JPie’s visual representation provides capsules, which represent logical code units, and semantic regions, which represent different aspects of a program. A capsule’s meaning depends upon its containing semantic... Read More

In this paper, we revisit the question of how much buffer an IP router should allocate for its output link. For a long time, the intuitive answer of setting the buffer size to the bitrate-delay product has been widely regarded as reasonable. Recent studies of interaction between queueing at IP routers and TCP congestion control proposed alternative answers. First, we expose and explain contradictions between existing guidelines for link buffer sizing. Then, we argue that the problem of link buffer sizing needs a different formulation. In particular, the chosen buffer... Read More

In this paper, we revisit the problem of selecting the buffer size for an IP network link. After a comprehensive overview of issues relevant to the link buffer sizing, we examine usefulness of existing guidelines for choosing the buffer size. Our analysis shows that the existing recommendations not only are difficult to implement in the context of IP networks but also can severely hurt interactive distributed applications. Then, we argue that the networking research community should change its way of thinking about the link buffer sizing problem: the focus should... Read More

We present a new widget, the IBar, for controlling all as-pects of a perspective camera. This widget provides an in-tuitive interface for controlling the perspective distortion in the scene by providing single handles that manipulate one or more projection parameters simultaneously (e.g., distance-to-object and lens aperture) in order to create a single per-ceived projection change (increasing the perspective distor-tion without changing the scene size). We demonstrate that novice users more easily learn how to manipulate the camera using the IBar.

Context-awareness refers to a computing model where ap-plication behavior is driven by a continually-changing environment. Mobile computing poses unique challenges to context-sensitive applications and middleware, including the ability to run on resource-poor devices like PDAs and the necessity to limit assumptions about the underlying network. Though middleware exists to provide context-awareness to applications, they have not been designed with the limitations inherent in dynamic mobile environments in mind. This paper discusses a lightweight approach to context-sensitivity that takes into account these considera-tions. We explore the use of modularization to tailor... Read More

Much of the work on networking and communications is based on thepremise that components interact in one of two ways: either they are connected viaa stable wired or wireless network, or they make use of persistent storage repositoriesaccessible to the communicating parties. A new generation of networks raises seri-ous questions about the validity of these fundamental assumptions. In mobile ad hocwireless networks connections are transient and availability of persistent storage is rare.This paper is concerned with achieving communication among mobile devices that maynever find themselves in direct or indirect contact... Read More

Ad hoc networks are dynamic, open environments that exhibit decoupled computing due to frequent disconnections and transient interactions. Reliable deploy-ment of components in such demanding settings requires a different design approach for the mechanisms that perform these functions. Not only do the deployment mechanisms have to perform the traditional tasks of deploying, installing, integrating and activat-ing components, they must also be robust enough to handle the nuances of an ad hoc network. This paper proposes a mechanism for component deployment that is adapted for use in ad hoc networks, and,... Read More

Ad hoc networks are dynamic environments where fre-quent disconnections and transient interactions lead to de-coupled computing. Typically, participants in an ad hoc network are small mobile devices such as PDAs or cellu-lar phones that have a limited amount of resources avail-able locally, and must leverage the resources on other co-located devices to provide the user with a richer set of func-tionalities. Service-oriented computing (SOC), an emerging paradigm that seeks to establish a standard way of mak-ing resources and capabilities available for use by others in the form of services, is... Read More

The increasing ubiquity of wireless mobile devices is promoting unprecedented levels of electronic collaboration among devices interoperating to achieve a common goal. Issues related to host interoperability are addressed partially by the service-oriented computing paradigm. However, certain technical concerns relating to reliable interactions among hosts in ad hoc networks have not yet received much attention. We introduce ”follow-me sessions”, where interaction occur between a client and a service, rather than a specific provider or server. We allow the client to switch service providers if needed. The redundancy offers scope for... Read More

We propose the notion of Java-program gestures that are composed of a series of memory-accessing instructions. By finding patterns in gestures whose execution can be atomic, we can load them in an intelligent memory controller. This process can improve performance of the Java Virtual Machine, decrease code footprint, and reduce power consumption in hardware. In this thesis we formally define a language of gestures and introduce a method of detecting them statically at compile-time. We introduce a simple heuristic for reducing the number of gestures that must be loaded into... Read More

This paper presents FAR, a Face-Aware Routing protocol for mobicast, a spatiotemporal variant of multicast tailored for sensor networks with environmental mobility. FAR features face-routing and timed-forwarding for delivering a message to a mobile delivery zone. Both analytical and statistical results show that, FAR achieves reliable and just-in-time mes-sage delivery with only moderate communication and memory overhead. This paper also presents a novel distributed algorithm for spatial neighborhood discovery for FAR boot-strapping. The spatiotemporal performance and reliability of FAR are demonstrated via ns-2 simulations.

The increased pervasiveness of wireless mobile com-puting devices draws new attention to the need for coor-dination among small networked components. The very nature of the environment requires devices to interact opportunistically when resources are available. Such interactions occur unpredictably as mobile agents gen-erally have no advance knowledge of other agents they will encounter over the lifetime of the application. In addition, as the ubiquity of communicating mobile de-vices increases, the number of application agents sup-ported by the network grows drastically. Managing ac-cess control is crucial to such systems, and applica-tion... 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. Applications with these capabilities are referred to as context-aware. 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,... 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. This style of interaction is imperative in ad hoc mobile networks that consist of numerous mobile hosts coordinating with each other opportunistically via transient wireless interconnections. In this paper, we provide a formal abstract characterization of a host’s context that extends to encompass a neighborhood within the ad hoc network. We provide an application in an ad hoc network a specification mechanism... Read More

Context-aware mobile applications require constant adapta-tion 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 a middleware infrastructure for sensing, collect-ing, and providing context information to applications. In this paper, we demonstrate the feasibility of providing such a middleware that... Read More

This thesis motivates a fully automatic approach for locating roads in aerial video by using active contours in conjunction with motion cues. Directed active contours provide ideal parametric representations of roads due to their ability to fit the variety seen in road shapes. Motion in stabilized aerial video can be represented as a distribution of spatio-temporal derivatives. These motion cues can then be incorporated into the energy function, which yields active contours that better model the active roads in a scene. We present results using this approach on typical models... 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, since QSDRR needs to maintain a separate queue for each active flow, there is a legitimate concern that it may be too costly for... Read More

Minimax is a recently proposed procedure for electing committees, but it cannot be applied without an understanding of its computational complexity and its susceptibility to manipulate. We examine two compelling variations of minimax and prove both to be NP-complete. We derive upper and lower bounds on the size of minimax winner set for a given election. We present a heuristic for calculating a minimax winner set and present experiments based on its use. Finally, we present a general strategy for manipulating a minimax election.

An increasing number of distributed real-time systems face the critical challenge of provid-ing quality of service guarantees in open and unpredictable environments. In particular, such systems often need to enforce utilization bounds on multiple processors in order to avoid over-load and meet end-to-end deadlines even when task execution times are unpredictable. While recent feedback control real-time scheduling algorithms have shown promise, they cannot han-dle the common end-to-end task model where each task is comprised of a chain of subtasks dis-tributed on multiple processors. This paper presents the End-to-end Utilization CONtrol... Read More

This paper presents MobiQuery, a spatiotemporal query service that allows mobile users to periodically gather information from their surrounding areas through a wireless sensor network. A key advantage of MobiQuery lies in its capability to meet stringent spatiotemporal performance constraints crucial to many applications. These constraints include query latency, data freshness and fidelity, and changing query areas due to user mobility. A novel just-in-time prefetching algorithm enables MobiQuery to main-tain robust spatiotemporal guarantees even when nodes op-erate under extremely low duty cycles. Furthermore, it sig-nificantly reduces the storage cost and... Read More

Several approaches to hard, real-time garbage collection have been recently proposed. All of these approaches require knowing certain statistical properties about a program's execution, such as the maximum extent of live storage, the rate of storage allocation, and the number of non-null object references. While these new approaches offer the possibility of guaranteed, reasonably bounded behavior for garbage collection, the determination of the required information may not be straight forward for the application programmer. In this paper we present evidence suggesting that the necessary factors can vary widely over the... Read More

In this thesis, we describe the use of Genetic Programming (GP) to learn obstacle detectors to be used for obstacle avoidance on a mobile robot. The first group of experiments focus on learning visual feature detectors for this task. We provide experimental results across a number of different environments, each with different characteristics, and draw conclusions about the performance of the learned feature detector and the training data used to learn such detectors. We also explore the utility of seeding the initial population with previously evolved individuals and subtrees, and... Read More

We describe middleware and programming environment tools (JPie/qt) that allow programmers to access relational databases in an object-oriented way. Building on top of the JDBC API and leveraging live dynamic class creation and modification in JPie, the JPie/qt middleware presents the user with a simple interactive mechanism for creating object-oriented applications that access databases. Classes are generated mirroring the database schema and programmers deal directly with these classes. Objects of these classes can be database-bound, so reads and writes to their fields are reflected in the relational database immediately. Database... Read More

We describe middleware and programming environment tools (JPie/qt) that allow programmers to access relational databases in an object-oriented way. Building on top of the JDBC API and leveraging live dynamic class creation and modification in JPie, the JPie/qt middleware presents the user with a simple interactive mechanism for creating object-oriented applications that access databases. Classes are generated mirroring the database schema and programmers deal directly with these classes. Objects of these classes can be database-bound, so reads and writes to their fields are reflected in the relational database immediately. Database... Read More

A network of adaptive processing elements has been developed that transforms and fuses video captured from multiple sensors. Unlike systems that rely on end-systems to process data, this system distributes the computation throughout the network in order to reduce overall network bandwidth. The network architecture is scalable because it uses a hierarchy of processing engines to perform signal processing. Nodes within the network can be dynamically reprogrammed in order to compose video from multiple sources, digitally transform camera perspectives, and adapt the video format to meet the needs of specific... Read More

We present middleware for a Server Development Environment that facilitates live development of SOAP and CORBA servers. As the underlying implementation platform, we use JPie, a tightly integrated programming environment for live software construction of Java applications. JPie provides dynamic classes whose signature and implementation can be modified at run time, with changes taking effect immediately upon existing instances of the class. We extend this model by automating the server deployment process, allowing developers to devote their full attention to the implementation of server logic. Moreover, the live development model... Read More

We present middleware for a Client Development Environment that facilitates live development of client applications for SOAP or CORBA servers. We use JPie, a tightly integrated programming environment for live software construction in Java, as the target platform for our design. JPie provides dynamic classes whose signature and implementation can be modified at run time, with changes taking effect immediately upon existing instances of the class. We extend this model to automate addition, mutation, and deletion of dynamic server methods within dynamic clients. Our implementation simplifies distributed application development by... Read More

Most scalable switches are required to buffer packets at both their inputs and outputs to overcome the slow memory speeds of packet queues. This thesis deals with the design of scheduling algorithms for such Combined Input and Output Queued (CIOQ) switches. For crossbar based CIOQ switches, we demonstrate the underperformance of commercially used scheduling algorithms under overload traffic conditions using targeted stress tests and present ideas to develop robust, stress resistant versions of these algorithms that are still simple enough to be implemented in high speed switches. To regulate the... Read More

Buffered multistage interconnection networks offer one of the most scalable and cost-effective approaches to building high capacity routers and switches. Unfortunately, the performance of such systems has been difficult to predict in the presence of the extreme traffic conditions that can arise in Internet routers. Recent work introduced the idea of distributed scheduling, to regulate the flow of traffic in such systems. This work demonstrated (using simulation and experimental measurements) that distributed scheduling can en-able robust performance, even in the presence of adversarial traffic patterns. In this paper, we show... 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 de-veloping dependable agent-based software systems for use in the often unpredictable settings of ad hoc net-works. However, designing an application agent which gathers, maintains, and adapts to context can be a diffi-cult undertaking in an open and continuously changing environment, 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... 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 agent-based soft-ware systems for use in the often unpredictable settings of ad hoc net-works. However, designing an application agent which interacts with other agents to gather, maintain, and adapt to context can be a difficult undertaking in an open and continuously changing environment, even for a seasoned programmer. Our goal is to simplify the programming task by hiding the details of agent coordination from the programmer,... Read More

Aerial video provides strong cues for automatic road extraction that are not available in static aerial images. Using stabilized (or geo-referenced) video data, capturing the distribution of spatio-temporal image derivatives gives a powerful, local representation of scene variation and motion typical at each pixel. This allows a functional attribution of the scene; a “road” is defined as paths of consistent motion --- a definition which is valid in a large and diverse set of environments. Using a classical relationship between image motion and spatio-temporal image derivatives, road features can be... Read More

In this proposal, we introduce the reserved delivery subnetwork (RDS), a mechanism that can al-low information service providers to deliver more consistent service to their customers without perflow resource reservation. In addition to service performance improvements, reserved delivery sub-networks can also provide protection against network resource attacks. Many applications such asweb content delivery services and virtual private networks can benefit from reserved delivery sub-networks. We address a number of issues with the deployment of RDSs. First, we formulate theconfiguration problem of an RDS as a minimum concave cost network flow... Read More

The minimum concave cost network flow problem (MCCNFP) has many applications in areas such as telecommunication network design, facility location, production and inventory planning, and traffic scheduling and control. However, it is a well known NP-hard problem, and all existing search based exact algorithms are not practical for networks with even moderate numbers of vertices. Therefore, the research community also focuses on approximation algorithms to tackle the problems in practice. In this paper, we present an improved local search algorithm for the minimum concave cost network flow problem based on... Read More

Optical Burst Switching (OBS) is an experimental network technology that enables the construction of very high capacity routers using optical data paths and electronic control. In this dissertation, we study the design of network components that are needed to build an OBS network. Specifically, we study the design of the switches that form the optical data path through the network. An OBS network that switches data across wavelength channels requires wave-length converting switches to construct an OBS router. We study one particular design of wavelength converting switches that uses tunable... Read More

Context-aware computing refers to a computing paradigm in which the behavior of individual components is determined by the circumstances in which they find themselves to an extent that greatly exceeds the typical system/environment interaction pattern common to most modern computing. The environment has an exceedingly powerful impact on a particular application component either because the lat-ter needs to adapt in response to changing external conditions or be-cause it relies on resources whose availability is subject to continuous change. In this paper we seek to develop a systematic understanding of the... Read More

Coordination is a style of interaction in which information exchange among independent system components is accomplished by means of high-level constructs designed to enhance the degree of decoupling among participants. A de-coupled mode of computation is particularly important in the design of mobile systems which emerge dynamically through the composition of independently developed components meeting under unpredictable circumstances and thrust into achieving purposeful cooperative behaviors. This paper examines a range of coordination models tailored for use in mobile computing and shows that the constructs they provide are reducible to simple... Read More

Background: One of the most promising but challenging task in the post-genomic era is to reconstruct the transcriptional regulatory networks. The goal is to reveal, for each gene that responds to a certain biological event, which transcription factors affect its transcription, and how several transcription factors coordinate to accomplish specific regulations. Results: Here we propose a supervised machine learning approach to address these questions. We build decision trees to associate the expression level of a gene with the transcription factor binding data of its promoter. From the decision trees, we... Read More

There is a critical need to perform advanced data processing on network traffic. In order to accom-plish this, protocol processing must first be performed to reassemble individual network packets into consistent data streams representing the exact dataset being transferred between end systems. This task is currently performed by protocol stacks running on end systems. Similar protocol processing opera-tions are needed to process the data on the interior of the network. Given millions of network connections operating on multi-gigabit per second network links, this task is extremely difficult. The TCP-Processor addresses... Read More

The growth of the Internet has enabled it to become a critical component used by businesses, governments and individuals. While most of the traffic on the Internet is legitimate, a proportion of the traffic includes worms, computer viruses, network intrusions, computer espionage, security breaches and illegal behavior. This rogue traffic causes computer and network outages, reduces network throughput, and costs governments and companies billions of dollars each year. This dissertation investigates the problems associated with TCP stream processing in high-speed networks. It describes an architecture that simplifies the processing of... Read More

This paper considers the technical challenges associated with the development of applications designed to work over mobile ad hoc net-works (MANETs). The setting is one in which a miniature application core residing on a mobile host with limited resources is able to support a complex application in a changing open environment by exploiting ser-vices made available by other hosts it encounters. The proposed solution extends in a novel way the applicability of the service provision paradigm to the ad hoc wireless setting. The novelty of the approach rests with the... Read More

In the proxy approach to Service Oriented Comput-ing, a service advertises a proxy, which is searched for, retrievedand used by interested clients as a local handle to the serviceprocess that runs on a remote host. Due to software evolution,it becomes necessary at times to upgrade the service. Some ofthese upgrades may require an upgrade of the proxy software,in addition to the server itself. This paper addresses the issue ofupgrading both the server and its proxy in a manner transparentto the client, and ensures only momentary interruption duringthe switching process. The... Read More

Service oriented computing is a new paradigm that is gaining popularity in dis-tributed computing environments due to its emphasis on highly specialized, modular and platform-agnostic code facilitating interoperability of systems. It borrows concepts from more mature paradigms such as object-oriented and component computing. This results in a progression from object-oriented computing to component computing and finally to service oriented computing, a new paradigm for designing and delivering software. Just as an object encapsulates state and behavior at a fine level of granularity, a service offers similar encapsulation at a larger... Read More

Service oriented computing, with its aim of unhindered in-teroperability, is an appropriate paradigm for ad hoc net-works, which are characterized by physical mobility of het-erogenous hosts and by the absence of standardized application level protocols. The decoupled nature of computing in ad hoc networks can result in disconnections at inoppor-tune times during the client-service interaction process. We introduce the notion of a priori selection of services to reduce the likelihood of disconnection during service usage. A client may specify the times when it requires certain ser-vices. A knowledge base of... Read More

TCAMs are the most popular practical approach to high performance packet classifica-tion, but they suffer from inefficient handling of range matches; the standard approach of rule replication can result in a 2-6x increase in TCAM words needed, for typical firewall databases. We describe three CMOS implementations of a range check circuit to address this problem; the most efficient of these designs allows classification on the standard IPv4 5-tuple with only a 46% increase in transistor count, rather than relying on rule replication. By avoiding replication, the overall transistor count required... Read More

In this proposal, we seek to develop methods for packet classification that can deliver high performance (e.g. wire speed processing at 10 Gb/s) while being reasonably cost-effective (e.g. memory-efficient and having low hardware complexity). In particular, we discuss a new approach involving extended TCAMs. This new approach eliminates the problems that preclude TCAMs from being considered viable solutions to the packet classification problem.

For various reasons, a dedicated cluster is not always fully utilized even when all of its processors are allocated to jobs. This occurs any time that a running job does not use 100% of each of the processors allocated to it. Keeping in mind the needs of both the cluster’s system administrators and its users, we would like to increase the throughput and efficiency of the cluster while maintaining or improving the average turnaround time of the jobs and the quality of service of the “primary” jobs originally scheduled on... Read More

We present an image-space camera manipulation widget that sup-ports visualization of the relationship of the camera with respect tothe scene. The form of the widget presents the user with naturalaffordances for camera manipulation. Visual aids such as ghostingof the scene and preview animations are used to acquaint noviceusers with the functions of different parts of the widget. Mousegestures are used to transition between different perspective viewsof the scene in an intuitive way. Finally, we provide a novel methodfor visualizing camera bookmarks.

Packet classification is an enabling function for a variety of Internet applications including Quality of Ser-vice, security, monitoring, and multimedia communications. In order to classify a packet as belonging to a particular flow or set of flows, network nodes must perform a search over a set of filters using multiple fields of the packet as the search key. In general, there have been two major threads of research addressing packet classification: algorithmic and architectural. A few pioneering groups of researchers posed the problem, provided complexity bounds, and offered a collection... Read More

The growth and diversification of the Internet imposes increasing demands on the performance and functionality of network infrastructure. Routers, the devices responsible for the switch-ing and directing of traffic in the Internet, are being called upon to not only handle increased volumes of traffic at higher speeds, but also impose tighter security policies and provide support for a richer set of network services. This dissertation addresses the searching tasks performed by Internet routers in order to forward packets and apply network services to packets belonging to defined traffic flows. As... Read More

Robust Header Compression (ROHC) provides for more efficient use of radio links for wireless communication in a packet switched network. Due to its potential advantages in the wireless access area andthe proliferation of network processors in access infrastructure, there exists a need to understand the resource requirements and architectural implications of implementing ROHC in this environment. We presentan analysis of the primary functional blocks of ROHC and extract the architectural implications on next-generation network processor design for wireless access. The discussion focuses on memory space andbandwidth dimensioning as well as... Read More

Due to the importance and complexity of the packet classification problem, a myriad of algorithms and re-sulting 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 avail-able to evaluate packet classification algorithms and products. Network service providers are reluctant to distribute copies of real filter sets for security and confidentiality reasons, hence realistic test vectors are a scarce... Read More

Packet classification is a multi-field searching task performed by Internet routers in order to apply security policies and network services to packets belonging to defined traffic flows. As this searching task must be performed for every packet traversing a router, fast and scalable solutions are required in order to prevent packet classification from becoming a performance bottleneck. A wide variety of packet classification al-gorithms and devices exist in the research literature and commercial market. The existing solutions exploit various design tradeoffs to provide high search rates, power and space efficiency,... Read More

Three methods for analyzing sequencing traces derived from sequencing reactions containing two DNA templates are presented. All rely on alignment to a segment of assembled genomic sequence containing the original template sequence. Spliced alignment algorithms are used so that traces derived from processed mRNA can be analyzed. The main application of these techniques is the elucidation of alternately spliced transcripts. Several experimental verification of one of the techniques is presented including testing on a set of 48 alternately spliced targets from the human genome and 47 negative controls.

The advent and maturation of component-based middleware frameworks have sim-plified the development of large-scale distributed applications by separating system devel-opment and configuration concerns into different aspects that can be specified and com-posed at various stages of the application development lifecycle. Conventional component middleware technologies, such as J2EE [73] and .NET [34], were designed to meet the quality of service (QoS) requirements of enterprise applications, which focus largely on scalability and reliability. Therefore, conventional component middleware specifications and implementations are not well suited for distributed real-time and embedded (DRE) ap-plications with... Read More

Real-time image transmission is crucial to an emerging class of distributed embedded systems operating in open network environments. Examples include avionics mission re-planning over Link-16, security systems based on wireless camera networks, and online collaboration using camera phones. Meeting image transmission deadlines is a key chal-lenge in such systems due to unpredictable network condi-tions. In this paper, we present the design, modeling, and analysis of CAMRIT, a Control-based Adaptive Middleware framework for Real-time Image Transmission in distributed real-time embedded systems. CAMRIT features a distributed feedback control loop that meets image... Read More

This paper presents the Distributed End-to-end Utiization CONtrol (DEUCON) algorithm. DEUCON can dynamically enforce desired CPU utilizations on all processors in a dis-tributed real-time system despite uncertainties in the system workload. In contrast to earlier centralized control schemes, DEUCON is a distributed control algorithm that is system-atically designed based on the Distributed Model Predictive Control theory. We decompose the global multi-processor utilization control problem into a set of localized subprob-lems, and design a peer-to-peer control structure where each local controller only needs to coordinate with a small number of neighbor... Read More

This paper proposes the minimum power configuration (MPC) approach to energy conservation in wireless sensor networks. In sharp contrast to earlier research that treats topology control, power-aware routing, and sleep management in isolation, MPC integrates them as a joint optimization prob-lem in which the power configurationof a network consists of a set of active nodes and the transmission powers of the nodes. We show through analysis that the minimum power configu-ration of a network is inherently dependent on the data rates of sources. We propose several approximation algorithms with provable... 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. 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