Technical Reports and MS Project Reports

The next generation Internet needs to support multiple diverse application contexts. In this paper, we present Internet 3.0, a diversified, multi-tier architecture for the next generation Internet. Unlike the current Internet, Internet 3.0 defines a new set of primitives that allows diverse applications to compose and optimize their specific contexts over resources belonging to multiple ownerships. The key design philosophy is to enable diversity through explicit representation, negotiation and enforcement of policies at the granularity of network infrastructure, compute resources, data and users. The basis of the Internet 3.0 architecture ...Read More

Recent years have witnessed the adoption of wireless sensor-actuator networks as a communication infrastructure for process control applications. An important enabling technology for industrial process control is WirelessHART, an open wireless sensor-actuator network standard specifically developed for process industries. A key challenge faced byWirelessHART networks is to meet the stringent real-time communication requirements imposed by feedback control systems in process industries. Fixed priority scheduling, a popular scheduling policy in real-time networks, has recently been shown to be an effective real-time transmission scheduling policy in WirelessHART networks. Priority assignment has a ...Read More

WirelessHART is an open wireless sensor-actuator network standard for industrial process monitoring and control that requires real-time data communication between sensor and actuator devices. Salient features of a WirelessHART network include a centralized network management architecture, multi-channel TDMA transmission, redundant routes, and avoidance of spatial reuse of channels for enhanced reliability and real-time performance. This paper makes several key contributions to real-time transmission scheduling in WirelessHART networks: (1) formulation of the end-to-end real-time transmission scheduling problem based on the characteristics of WirelessHART; (2) proof of NP-hardness of the problem; (3) ...Read More

The WirelessHART standard has been specifically designed for real-time communication between sensor and actuator devices for industrial process monitoring and control. End-to-end communication delay analysis for WirelessHART networks is required for acceptance test of real-time data flows from sensors to actuators and for workload adjustment in response to network dynamics. In this paper, we map the scheduling of real-time periodic data flows in a WirelessHART network to real-time multiprocessor scheduling. We, then, exploit the response time analysis for multiprocessor scheduling and propose a novel method for the end-to-end delay analysis ...Read More

Home area networks (HANs) promise to enable sophisticated home automation applications such as smart energy usage and assisted living. However, recent empirical study of HAN reliability in real-world residential environments revealed significant challenges to achieving reliable performance in the face of significant and variable interference from a multitude of coexisting wireless devices. We propose the Adaptive and Robust Channel Hopping (ARCH) protocol: a lightweight receiveroriented protocol which handles the dynamics of residential environments by reactively channel hopping when channel conditions have degraded. ARCH has several key features. First, ARCH is ...Read More

Home area networks (HANs) consisting of wireless sensors have emerged as the enabling technology for important applications such as smart energy and assisted living. A key challenge faced by HANs is maintaining reliable operation in real-world residential environments. This paper presents two in-depth empirical studies on the wireless channels in real homes. The spectrum study analyzes the spectrum usage in the 2.4 GHz band where wireless sensor networks based on the IEEE 802.15.4 standard must coexist with existing wireless devices. We characterize the ambient wireless environment in six apartments through ...Read More

This is a collection of papers presented at the workshop "What Do Collaborations with the Arts Have to Say About HRI", held at the 2010 Human-Robot Interaction Conference, in Osaka, Japan.

Classical scheduling abstractions such as deadlines and priorities do not readily capture the complex timing semantics found in many real-time cyber-physical systems. Time utility functions provide a necessarily richer description of timing semantics, but designing utility-aware scheduling policies using them is an open research problem. In particular, optimal utility accrual scheduling design is needed for real-time cyber-physical domains. In this paper we design optimal utility accrual scheduling policies for cyber-physical systems with periodic, non-preemptable tasks that run with stochastic duration. These policies are derived by solving a Markov Decision Process ...Read More

The ability to build systems of systems is vital to the real-time community as we endeavor to build increasingly sophisticated systems. Subsystems must be modular and isolated to ensure desired real-time performance when assembled by the system integrator. While virtualization has gained broad adoption and success for system integration in non-real-time domains, no existing virtual machine manager is designed to enforce real-time performance. On the other hand, while a rich body of promising theories on hierarchical real-time scheduling algorithms has been proposed in the literature to support composable real-time performance ...Read More

The efficient deployment and robust operation of many sensor network applications depend on deploying relays to ensure wireless coverage. Radio mapping aims to predict network coverage based on a small number of link measurements from sampled locations. Radio mapping is particularly challenging in complex indoor environments where walls significantly affect radio signal propagation. This paper makes the following key contributions to indoor radio mapping. First, our empirical study in an office building identifies a wall-classification model as the most effective model for indoor environments due to its balance between model ...Read More

This paper presents the design, deployment, and empirical study of a wireless clinical monitoring system that collects pulse and oxygen saturation readings from patients. The primary contribution of this paper is an in-depth clinical trial that assesses the feasibility of wireless sensor networks for patient monitoring in general (non-ICU) hospital units. The trial involved 32 patients monitored in a step-down cardiology unit at Barnes-Jewish Hospital, St. Louis. During a total of 31 days of monitoring, the network achieved high reliability (median 99.92%, range 95.21% - 100%). The overall reliability of ...Read More

Service provisioning has gained significant attention as a promising programming model for heterogeneous wireless sensor networks. Its key idea is to exploit the decoupling of service providers and consumers to enable platform-independent applications that are dynamically bound to platform-specific services. We explore novel adaptive service binding strategies that are able to cope with network dynamics and to promote energy conservation. To achieve this goal, we developed policies and algorithms that automatically switch providers in response to network topology changes and adapt application behavior when opportunities for energy savings surface. The ...Read More

Heterogeneous wireless sensor networks represent a challenging programming environment. Servilla addresses this by offering a new middleware framework that provides service provisioning. Using Servilla, developers can construct platform-independent applications over a dynamic set of devices with diverse computational resources and sensors. A salient feature of Servilla is its support for dynamic discovery and binding to local and remote services, which enables flexible and energy-efficient in-network collaboration among heterogeneous devices. Furthermore, Servilla provides a modular middleware architecture that can be easily tailored for devices with a wide range of resources, allowing ...Read More

Thermal control is crucial to real-time systems as excessive processor temperature can cause system failure or unacceptable performance degradation due to hardware throttling. Real-time systems face significant challenges in thermal management as they must avoid processor overheating while still delivering desired real-time performance. Furthermore, many real-time systems must handle a broad range of uncertainties in system and environmental conditions. To address these challenges, this paper presents Thermal Control under Utilization Bound (TCUB), a novel thermal control algorithm specifically designed for real-time systems. TCUB employs a feedback control loop that dynamically ...Read More

Open soft real-time systems, such as mobile robots, must respond adaptively to varying operating conditions, while balancing the need to perform multiple mission specific tasks against the requirement that those tasks complete in a timely manner. Setting and enforcing a utilization target for shared resources is a key mechanism for achieving this behavior. However, because of the uncertainty and non-preemptability of some tasks, key assumptions of classical scheduling approaches do not hold. In previous work we presented foundational methods for generating task scheduling policies to enforce proportional resource utilization for ...Read More

Open soft real-time systems, such as mobile robots, experience unpredictable interactions with their environments and yet must respond both adaptively and with reasonable temporal predictability. Because of the uncertainty inherent in such interactions, many of the assumptions of the real-time scheduling techniques traditionally used to ensure predictable timing of system actions do not hold in those environments. In previous work we have developed novel techniques for scheduling policy design where up-front knowledge of execution time distributions can be used to produce both compact representations of resource utilization state spaces and ...Read More

Source code on the web is a widely available and potentially rich learning resource for non-programmers. However, unfamiliar code can be daunting to end-users without programming experience. This paper describes the results of an exploratory study in which we asked non-programmers to find and modify the code responsible for specific functionality within unfamiliar programs. We present two interacting models of how non-programmers approach this problem: the Task Process Model and the Landmark-Mapping model. Using these models, we describe code search strategies non-programmers employed and the difficulties they encountered. Finally, we ...Read More

Overlay hosting systems such as PlanetLab, and cloud computing environments such as Amazon’s EC2, provide shared infrastructures within which new applications can be developed and deployed on a global scale. This paper ex-plores how systems of this sort can be used to enable ad-vanced network services and sophisticated applications that use those services to enhance performance and provide a high quality user experience. Specifically, we investigate how advanced overlay hosting environments can be used to provide network services that enable scalable virtual world applications and other large-scale distributed applications requiring ...Read More

Magnetic spin valve devices enable the design of logic and memory elements that are suitable for use when constructing digital systems. A master-slave flip-flop design is proposed that can be clocked using an externally applied global magnetic field. With an external global clock, the digital system no longer needs to deliver the clock on-chip, thereby eliminating the need for a clock distribution network. We assess the power, area, and speed implications associated with the ability to eliminate the clock distribution network on a hybrid CMOS-magnetologic digital system.

Real-time hybrid testing of civil structures, in which computational models and physical components must be integrated with high fidelity at run-time represents a grand challenge in the emerging area of cyber-physical systems. Actuator dynamics, complex interactions among computers and physical components, and computation and communication delays all must be managed carefully to achieve accurate tests. To address these challenges, we have developed a novel middleware for integrating cyber and physical components flexibly and with suitable timing behavior within a Cyber-physical Instrument for Real-time hybrid Structural Testing (CIRST). This paper makes ...Read More

Many compute-bound software kernels have seen order-of-magnitude speedups on special-purpose accelerators built on specialized architectures such as field-programmable gate arrays (FPGAs). These architectures are particularly good at implementing dynamic programming algorithms that can be expressed as systems of recurrence equations, which in turn can be realized as systolic array designs. To efficiently find good realizations of an algorithm for a given hardware platform, we pursue software tools that can search the space of possible parallel array designs to optimize various design criteria. Most existing design tools in this area produce ...Read More

We consider the special case of tracking objects in highly structured scenes. In the context of vehicle tracking in urban environments, we offer a fully automatic, end-to-end system that discovers and parametrizes the lanes along which vehicles drive, then uses just these pixels to simultaneously track dozens of objects. This system includes a novel active contour energy function used to parametrize the lanes of travel based only on the accumulation of spatio-temporal image derivatives, and a tracking algorithm that exploits longer temporal constraints made possible by our compact data representation; ...Read More

We introduce the integral-pixel camera model, where measurements integrate over large and potentially overlapping parts of the visual field. This models a wide variety of novel camera designs, including omnidirectional cameras, compressive sensing cameras, and novel programmable-pixel imaging chips. We explore the relationship of integral-pixel measurements with image motion and find (a) that direct motion estimation using integral-pixels is possible and in some cases quite good, (b) standard compressive-sensing reconstructions are not good for estimating motion, and (c) when we design image reconstruction algorithms that explicitly reason about image motion, ...Read More

Skeleton descriptors are commonly used to represent, understand and process shapes. While existing methods produce skeletons at a fixed dimension, such as surface or curve skeletons for a 3D object, often times objects are better described using skeleton geometry at a mixture of dimensions. In this paper we present a novel algorithm for computing mixed-dimensional skeletons. Our method is guided by a continuous analogue that extends the classical grassfire erosion. This analogue allows us to identify medial geometry at multiple dimensions, and to formulate a measure that captures how well ...Read More

Networking research funding agencies in the USA, Europe, Japan, and other countries are encouraging research on revolutionary networking architectures that may or may not be bound by the restrictions of the current TCP/IP based Internet. We present a comprehensive survey of such research projects and activities. The topics covered include various testbeds for experimentations for new architectures, new security mechanisms, content delivery mechanisms, management and control frameworks, service architectures, and routing mechanisms. Delay/Disruption tolerant networks, which allow communications even when complete end-to-end path is not available, are also discussed.

The single best-effort service of the Internet struggles to accommodate divergent needs of different distributed applications. Numerous alternative network architectures have been proposed to offer diversified network services. These innovative solutions failed to gain wide deployment primarily due to economic and legacy issues rather than technical shortcomings. Our paper presents a new simple paradigm for network service differentiation that accounts explicitly for the multiplicity of Internet service providers and users as well as their economic interests in environments with partly deployed new services. Our key idea is to base the ...Read More

A high profile internet server is always a target of denial-of-service attacks. In this paper, we propose a novel technique for protecting an internet server from distributed denial-of-service attacks. The defense mechanism is based on a distributed algorithm that performs weight-fair throttling at the upstream routers. The throttling is weight-fair because the traffics destined for the server are controlled increased or decreased ) by the leaky-buckets at the routers based on the number of users connected, directly or through other routers, to each router. To the best of our knowledge, ...Read More

Vertex-connectivity and edge-connectivity represent the extent to which a graph is connected. Study of these key properties of graphs plays an important role in varieties of computer science applications. Recent years have witnessed a number of linear time 3-edge-connectivity algorithms - with increasing simplicity. In contrast, the state-of-the-art algorithm for 3-vertex-connectivity due to Hopcroft and Tarjan lacks the simplicity in the sense of ease of implementation as well as the number of passes over the graph although its time and space complexity is theoretically linear. In this paper, we propose ...Read More

Home area networks (HANs) consisting of wireless sensors have emerged as the enabling technology for important applications such as smart energy and assisted living. A key challenge faced in deploying robust wireless sensor networks (WSNs) for home automation applications is the need to provide long-term, reliable operation in the face of the varied sources of interference found in typical residential settings. To better understand the channel dynamics in these environments, we performed an in-depth empirical study of the performance of HANs in ten real-life apartments. Our empirical study leads to ...Read More

Recent advances in surface reconstruction algorithms allow surfaces to be built from contours lying on non-parallel planes. Such algorithms allow users to construct surfaces of similar quality more efficiently by using a small set of oblique contours, rather than many parallel contours. However, current medical imaging systems do not provide tools for sketching contours on oblique planes. In this paper, we take the first steps towards bridging the gap between the new surface reconstruction technologies and putting those methods to use in practice. We develop a novel interface for modeling ...Read More

Workflows, widely used on the Internet today, typically consist of a graph-like structure that defines the orchestration rules for executing a set of tasks, each of which is matched at run-rime to a corresponding service. The graph is static, specialized directories enable the discovery of services, and the wired infrastructure supports routing of results among tasks. In this paper we introduce a radically new paradigm for workflow construction and execution called open workflow. It is motivated by the growing reliance on wireless ad hoc networks in settings such as emergency ...Read More

Workflow middleware executes tasks orchestrated by rules defined in a carefully handcrafted static graph. Workflow management systems have proved effective for service-oriented business automation in stable, wired infrastructures. We introduce a radically new paradigm for workflow construction and execution called open workflow to support goal-directed coordination among physically mobile people and devices that form a transient community over an ad hoc wireless network. The quintessential feature of the open workflow paradigm is dynamic construction of custom, context-specific workflows in response to unpredictable and evolving circumstances by exploiting the knowledge and ...Read More

Existing workflow middleware executes tasks orchestrated by rules defined in a carefully handcrafted static graph. Workflow management systems have proved effective for service-oriented business automation in stable, wired infrastructures. We introduce a radically new paradigm for workflow construction and execution called open workflow to support goal-directed coordination among physically mobile people and devices that form a transient community over an ad hoc wireless network. The quintessential feature of the open workflow paradigm is dynamic construction and execution of custom, context-specific workflows in response to unpredictable and evolving circumstances by exploiting ...Read More

The Least Occupied Output First (LOOFA) scheduler is one of several unbuffered crossbar schedulers that provides strong performance guarantees when operated with a speedup of 2 or more. Because LOOFA requires the computation of a maximal matching, it has been considered too slow for use in systems with link rates of 10 Gb/s or more. This paper studies an approximate variant of LOOFA described briefly in [16]. We introduce a general family of schedulers that allows for partial sorting and that includes the LOOFA scheduler as a special case. We ...Read More

This report describes the Supercharged Planetlab Platform (SPP), a system designed as a prototype of an internet-scale overlay hosting platform. Overlay networks have become an important vehicle for delivering Internet applications. Overlay network nodes are typically implemented using general purpose servers or clusters. The SPP offers a more integrated architecture, combining general-purpose servers with high performance Network Processor (NP) subsystems. SPP nodes have recently been deployed as part of the Global Environment for Network Innovation (GENI) and are available for use by research users.

Real-time systems on non-preemptive platforms require a means of bounding the execution time of programs for admission purposes. Worst-Case Execution Time (WCET) is most commonly used to bound program execution time. While bounding a program’s WCET statically is possible, computing its true WCET is difficult.We present a new technique we call partial program admission, a means of statically enforcing an otherwise untrusted assertion of WCET without adding runtime overhead, by means of code duplication. We apply this technique to real programs from the virtual networking arena and present the results.

Virtualized network infrastructures are currently deployed in both research and commercial contexts. The complexity of the virtualization layer varies greatly in different deployments, ranging from cloud computing environments, to carrier Ethernet applications using stacked VLANs, to networking testbeds. In all of these cases, there are many users sharing the resources of one provider, where each user expects their resources to be isolated from all other users. Our work in this area is focused on network testbeds. In particular, we present the design of the latest version of the Open Network ...Read More

Network testbeds such as Emulab and the Open Network Laboratory use virtualization to enable users to define end user virtual networks within a shared substrate. This involves mapping users' virtual network nodes onto distinct substrate components and mapping virtual network links onto substrate paths. The mappings guarantee that different users' activities can not interfere with one another. The problem of mapping virtual networks onto a shared substrate is a variant of the general graph embedding problem, long known to be NP-hard. In this paper, we focus on a more general ...Read More

In the last few years, there has been active research on aggregating advanced statistical measures in multidimensional data cubes from partitioned subsets of data. In this paper, we propose an online compression and aggregation scheme to support Bayesian estimations in data cubes based on the asymptotic properties of Bayesian statistics. In the proposed approach, we compress each data segment by retaining only the model parameters and a small amount of auxiliary measures. We then develop an aggregation formula that allows us to reconstruct the Bayesian estimation from partitioned segments with ...Read More

Partial order based reduction (POR) has recently attracted research in planning. POR algorithms reduce search space by recognizing interchangable orders between actions and expanding only a subset of all possible orders during the search. POR has been extensively studied in model checking and proved to be an enabling technique for reducing the search space and costs. Recently, two POR algorithms, including the expansion core (EC) and stratified planning (SP) algorithms, have been proposed. Being orthogonal to the development of accurate heuristic functions, these reduction methods show great potential to improve ...Read More

We present a novel constraint-partitioning approach for solving continuous nonlinear optimization based on augmented Lagrange method. In contrast to previous work, our approach is based on a new constraint partitioning theory and can handle global constraints. We employ a hyper-graph partitioning method to recognize the problem structure. We prove global convergence under assumptions that are much more relaxed than previous work and solve problems as large as 40,000 variables that other solvers such as IPOPT [11] cannot solve.

With the fast development of wireless sensor network (WSN) technologies, WSNs have widely shifted from a specialized platform for a single application to an integrated infrastructure supporting multiple applications. It is hence a critical problem to allocate multiple applications to multiple sensors in order to maximize user utility subject to various resource constraints. The resulting constrained optimization problem is difficult since it is discrete, nonlinear, and not in closed-form. In this report, we develop an efficient optimization algorithm with rigorous approximation bounds for submodular monotonic optimization with multiple knapsack constraints. ...Read More

Traditional AI search methods, such as BFS, DFS, and A*, look for a path from a starting state to the goal in a state space most typically modelled as a directed graph. Prohibitively large sizes of the state space graphs make optimal search difficult. A key observation, as manifested by the SAS+ formalism for planning, is that most commonly a state-space graph is well structured as the Cartesian product of several small subgraphs. This paper proposes novel search algorithms that exploit such structure. The results reveal that standard search algorithms ...Read More

Real-time patient monitoring is critical to early detection of clinical patient deterioration in general hospital wards. A key challenge in such applications is to reliably deliver sensor data from mobile patients. We present an empirical analysis on the reliability of data collection from wireless pulse oximeters attached to users. We observe that most packet loss occur from mobile users to their first-hop relays. Based on this insight we developed the Dynamic Relay Association Protocol (DRAP), a simple and effective mechanism for dynamically discovering the right relays for wireless sensors attached ...Read More

This paper presents Servilla, a highly flexible service provisioning framework for heterogeneous wireless sensor networks. Its service-oriented programming model and middleware enable developers to construct platform-independent applications over a dynamic set of devices with diverse computational resources and sensors. A salient feature of Servilla is its support for dynamic discovery and binding to local and remote services, which enables flexible and energy-efficient in-network collaboration among heterogeneous devices. Furthermore, Servilla provides a modular middleware architecture that can be easily tailored for devices with a wide range of resources, allowing even resource-limited ...Read More

Open soft real-time systems, such as mobile robots, experience unpredictable interactions with their environments and yet must respond both adaptively and with reasonable temporal predictability. New scheduling approaches are needed to address the demands of such systems, in which many of the assumptions made by traditional real-time scheduling theory do not hold. In previous work we established foundations for a scheduling policy design and verification approach for open soft real-time systems, that can use different decision models, e.g., a Markov Decision Process (MDP), to capture the nuances of their scheduling ...Read More

We introduce the concept of local neighborhoods, a generalization of the one-ring on a mesh to unlabeled 3D data points arising from sampling a 2D surface embedded in 3D. The local neighborhood supports both local shape classification and robust normal estimation. In particular, local neighborhoods out-perform traditional approaches in unevenly sampled, curved regions. We show that the local neighborhood can be used in place of a full mesh structure for applications such as smoothing, moving least-squares reconstruction, and parameterization. Longer version of paper submitted to CAGD