Technical Reports and MS Project Reports

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

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