Ramesh Govindan - US grants

This award is made under the high performance connections portion of ANIR's "Internet Technologies " announcement, NSF 98-104. It provides support for two years to address tools and methodologies for network protocol interoperability testing, with special emphasis on multicast protocols. Collaborators include but are not limited to Cisco Systems, 3COM, and Nortel Networks.

Recent work has pointed out the existence of power-laws in the degree distribution of real-world
networks. In retrospect, these findings while widely publicized are perhaps not surprising; power-laws
for various notions of size in real-world phenomena have been known for several decades.
Nevertheless, these findings have sparked extensive interest in the structure and macroscopic properties
of the Internet. Such interest is timely; recent work has also revealed that network topology properties
may impact protocol performance
Generating realistic topologies is a prerequisite for understanding the impact of topology on pro-tocol
performance. Our recent work on topology generation motivates the proposed research and is
driven by the perceived dichotomy between structural generators those that explicity embody some
notion of hierarchy in constructing topologies and connectivity-based generators those that at-tempt
to generate topologies with power-law degree distributions.
Our preliminary research on this larger question reveals several interesting results: that real net-works
are well-modeled by connectivity-based generators, and that these generators result in graphs
with a continuum of levels of hierarchy. Continuing on from this work, our proposed research will at-tempt
to increase our fundamental understanding of the structure of real networks, and their impact on
protocol performance. Conceptually, our proposed research has three interrelated parts: understand-ing
hierarchy in real networks, devising structural models for topology construction based on Highly
Optimized Tolerance, and examining more closely the impact of topology on protocol performance.
The structure of networks, and their impact on protocols, has received little attention until recently.
In terms of broader impact, this work has the potential for making fundamental progress in the areas
of topology modeling. In a larger sense, it may develop methods that can be used to understand the
physical processes that lead to the development of other real-world networks, such as the Web topology
and social networks.

Structural Health Monitoring (SHM) is a highly interdisciplinary area of research focused on developing techniques to detect damage in structures such as buildings, bridges, aircraft, ships and spacecraft. Most SHM research to date has focused either on global damage assessment techniques using low-resolution measurements of a structure's response to ambient excitation, or on limited local independent damage detection mechanisms.

This proposal advocates a paradigm shift in SHM, using decentralized local excitation and high-resolution measurements of response to these excitations, detected and collaboratively analyzed through a spatially
dense wireless network of devices. This shift promises simpler and more accurate techniques to identify and even localize damage within the structure.

The goal of the proposed research is the design of a networked computer system, with distributed actuation and sensing, for SHM. The term "networked SHM" denotes the class of monitoring systems that will
be enabled by this research. By combining local excitation with high-resolution sensing, networked SHM is quite distinct from other sensor network applications being examined today. Networked SHM promises a future where, for example, buildings are constructed using concrete mixed with several tens of thousands of embedded sensor devices as well as low-power local exciters. The network of sensors will be able to continuously monitor the structure, trigger alarms that identify the onset of damage, precisely pinpoint the location of damage and also provide a long-term history of ambient stresses imposed on the building.

This project is focused on understanding the abstractions and mechanisms necessary to develop a macroprogramming system, called Kairos, which enables a developer to specify the global behavior of a distributed computation in sensor networks. Kairos translates this single centralized program into programs that execute on individual nodes, then instantiates and executes these programs automatically with additional runtime support. Kairos can result in rapid turn-around of robust code, since programmers and systems designers are often able to clearly describe (and reason about the correctness of) a centralized version of a distributed computation, but often find it difficult to implement (or understand the correctness of) a node-local program that realizes the same desired global behavior.

Kairos presents an abstraction of a sensor network as a collection of nodes that can all be tasked together simultaneously within a single program. The programmer is presented with three constructs: reading and writing variables at nodes, iterating through the one-hop neighbors of a node, and naming and addressing arbitrary nodes. Kairos leverages the observation that most distributed computations in sensor networks will rely on eventual consistency of shared node state both for robustness and for energy efficiency.

Kairos will advance the programmability of sensor networking subsystems and applications. It is possible to implement fairly sophisticated distributed algorithms (like localization and object tracking) in the Kairos framework without significant loss of efficiency. We intend to develop a prototype Kairos system and hope to use it in CENS applications as well as educational activities.

Observing systems facilitate scientific studies by instrumenting the real world and collecting corresponding measurements, with the aim of detecting and tracking phenomena of interest. In this proposal, we focus on a class of observing systems which are (1) embedded into the environment, (2) consist of stationary and mobile sensors, and (3) react to collected observations by reconfiguring the system and adapting which observations are collected next, these are referred to as Reactive Observing Systems (ROS). The goal of ROS is to help scientists verify or falsify hypotheses with useful samples taken by the stationary and mobile units, as well as to analyze data autonomously to discover interesting trends or alarming conditions.
A wide range of critical environmental monitoring objectives in resource management, environmental protection, and public health all require distributed observing systems. This project will explore ROS in the context of a marine biology application, where the system monitors, e.g., water temperature and light as well as concentrations of micro-organisms and algae in a body of water. Using a hybrid network of stationary and mobile sensors, communicating both via wired and wireless links, the system collects fine-grained measurements of interesting information in near real-time. An example of the use of such a system is the rapid identification of micro-organisms to predict the onset of algal blooms. Such blooms can have devastating economic consequences.

Current technology precludes sampling all possibly relevant data. Therefore there is need to develop approaches for optimizing and controlling the set of samples to be taken at any given time, taking into consideration the application's objectives and system resource constraints. To support such an optimization and control process, a significant part of the framework must be dedicated to the development of models of data, and their automatic validation or adaptation. As part of the validation and adaptation process, the framework must also include a distributed support mechanism for locating data of interest. The methods to be pursued in the project include a multi-scale modeling framework for ROS, that allows applications to construct inter-related models of varying spatio-temporal scope based on collected data. Guided by the models, the reactive elements of the system predict where interesting data and phenomena are likely to be found. In the process of constructing models, the system actively seeks most useful data to improve both, the models and phenomenon detection and tracking. In a feedback cycle, this data acquisition is guided by previous, perhaps less precise, models. Thus, the system to be developed (AMBROsia) enables optimal collection of measurements in a manner that respects system resource constraints, yet improves the overall fidelity of phenomenon detection and tracking. Such a system will aid scientific research by facilitating the testing of scientific hypothesis. It will provide timely predictions of sampling needs, and tracking information for dynamic phenomena. Overall, AMBROSia will facilitate observation, detection, and tracking of scientific phenomena that were previous only partially (or not at all) observable and/or understood.

ABSTRACT

Directorate for Computer and Information Science and Engineering (CISE)
Division Computer and Network Systems (CNS)
Science of Design (SoD) Program

Proposal Number: 0725354
P/I: Todd Millstein
PI Department: Computer Science
Institution: University of California - Los Angeles
Award: $ 800,000

Title: ""SoD: An Electronic Design Automation Approach to Embedded Networked Software""

This project adapts design approaches from the Electronic Design Automation (EDA) domain to improve the reliability and flexibility of software-intensive systems. In particular, the project develops methodologies, languages, and tools for designing embedded networked (EN) systems software. This project (based in UCLA with a sub-award to USC) is motivated by the EDA top-down design methodologies employed for hardware; the project develops languages and tools that adapt the EDA approach to the design and implementation of software systems. EN systems (which consist of a distributed collection of computing resources embedded in the physical world) are becoming increasingly important in both scientific and social applications (for example, earthquake prediction, contaminant tracking in ground water, soil erosion detection, traffic monitoring, etc.). The EDA design methodology is a logical foundation for designing software intensive systems because it articulates a design flow that contains a number of stages, which successively lower a high-level design until a fully specified hardware system is produced. Developers of EN systems need to describe the global behavior of their designs independent of the nonfunctional constraints, to make important domain knowledge and constraints from the physical world explicit, and to incorporate these properties into the development process in a staged manner. As EN systems move into the mainstream and software engineers outside of research laboratories take on the challenge of building of such systems, the need for sound software design methodologies and tools grows. The approach pursued with this project can greatly simplify the design of software for this important class of systems and thereby accelerate adoption.


Program Manager: Anita J. La Salle
Date: June 6, 2007

Proposal Number: 0820061/0820034/0820230

TITLE: Design and Run-time Techniques for Physically Coupled Software

PIs: Ramesh Govindan (USC), Rajesh Gupta (UCSD), Mani Srivastava (UCLA), and Paulo Tabuada (UCLA)

ABSTRACT:

Many real-world systems are deeply embedded in the physical world and their operational behavior is determined in large part by a tight coupling between the system components and the physical environment. This project seeks to establish the scientific principles governing software for such physically-coupled systems by focusing on four challenges in the context of distributed sensing and control applications: 1) Support for physical context in the form of programming structures that enable application software to explicitly capture the state of the physical world as an observable in an embedded computation; 2) Formal methods for composing software modules that indirectly interact with each other through the physical world, and a run-time safety supervisor that provably enforces correctness of composition; 3) Programming structures to enable design and verification of applications with resource provisioning that is driven by and adapts to physical-world dynamics; 4) System software support for sharing physically-coupled sensor and actuator resources in distributed settings. In addition, educational techniques targeting the teaching of topics in physically-coupled computational systems are being explored by creating shared educational content in the form of self-contained reusable modules.

Smartphones are fast becoming a full-fledged computing platform that
our society depends upon. Smartphone applications that access data
and computing resources in the "cloud" are inevitable given the
processing and storage limitations on the phones. Today the burden of
partitioning smartphone applications between the phone and the cloud
lies squarely with the programmer. This manual approach to
partitioning applications is fundamentally limited and will not scale
up to allow smartphones to become a truly rich and robust computing
platform. Manual partitioning is tedious and error prone. Moreover,
manual partitioning requires the programmer to make important
decisions that cannot be properly made until run time.

This project explores the requirements, design, and implementation of
a programming system for cloud-enabled smartphone applications that is
inherently adaptive, partitioning applications transparently in order
to cope with a diverse set of dynamic constraints. The project is
studying cloud-enabled smartphone applications from a variety of
domains in order to understand application requirements, constraints,
and tradeoffs in practice. The project is also pursuing programming
models that allow developers to flexibly and declaratively express an
application's components along with their dependencies and
constraints. Finally, the project is developing a prototype system
architecture that collaboratively executes an application on the phone
and the cloud subject to the application's requirements. Within a
decade, smartphones will transform the way health and lifestyle
choices are delivered to much of the population. This project is
helping to enable this transformation by making a rich class of
smartphone applications much easier to create, adapt, and understand.

Systematic Analysis of Protocol Implementations

Internet protocol development and standardization has long been driven by the philosophy of 'rough consensus and running code.' The downside to this approach is that protocol specifications are rarely rigorously verified, even for properties that fall within the capabilities of protocol verification techniques. Further, the 'rough' nature of the approach means that some important design decisions are inevitably omitted from the specification or are defined ambiguously. Therefore, in practice the correctness, performance, and resilience of network protocols are implicitly defined by vendor and open-source implementations of the protocol specification, and these implementations are based upon the developers' varying interpretations of the standards document. This leaves developers in a bind: they are unsure of the properties of the protocol specification, and do not have tools to reason about the properties of complex protocol implementations.

Intellectual Merit. This project will develop a general approach and an associated tool that will enable developers and expert users to systematically analyze a variety of properties on a range of protocol implementations. The approach builds upon recent advances in program analysis techniques in novel ways that are tailored towards the special properties and requirements of protocol implementations. Moreover, the project will instantiate the general approach with new analyses for important tasks that are largely manual and highly error-prone today, including interoperability testing and precise tracking of state changes over time (e.g., to identify anomalous state sequences or characterize protocol complexity).

The project is based on the observation that protocol implementations have an implicit internal structure, in the form of a state machine that embodies the key behavioral properties of the implementation. Due to the complexity of protocol implementations, this state machine will typically not be completely inferable by program analysis. To address this problem, the project will develop operators on a protocol implementation that allow developers to specify scalable and precise views of the underlying state machine. Developers can additionally use these views to perform a targeted concrete execution of the protocol on a real topology in order to investigate the particular property under consideration.

The outcome of the project will be a software system called Spa. Developers will provide protocol implementations and use their expertise about the protocol and its properties of interest to specify appropriate operators and guide targeted concrete execution. The project will evolve Spa operators using experiences gained from applying Spa to several protocol analyses that have not been previously considered, and will start with a set of operators that have been informed by the PIs' preliminary research.

Broader Impact. The protocols that underlie access to our networked world must be reliable, robust to attacks, and must perform well over a range of conditions and in dynamic environments. This project will equip developers and experts to systematically analyze the behavior of their protocols, and will result in an overall improvement in the reliability, robustness, and performance of deployed protocols. The project will accelerate the adoption of the research by making Spa available to researchers and developers, publishing its research results in top networking and programming language conferences, and educating students on the developed research methods by incorporating them in curricula. It will also engage underrepresented groups and undergraduates in research.

The capabilities of mobile devices have increased dramatically and end-users are able to perform a wide range of useful tasks on their smartphones. However, the usability of these devices is strongly influenced by their energy consumption. Despite advances in hardware and battery design, a poorly coded application can drain a smartphone's battery with numerous energy-expensive operations. Developers lack the tools and techniques to identify when and where the energy consumption profiles of their applications can be improved. This research aims to help developers understand how energy is consumed within their applications, and to help them change their applications in ways that will lead to reduced energy consumption. Given the widespread use of mobile applications and the prevalence of energy consumption-related problems, this work will impact both end users and developers by improving applications? energy efficiency and enabling further research in this area. The results of this research will also have marked educational impact through the training of future software engineers in predicting, estimating, measuring, and managing the effects of their system designs and implementations on energy consumption.

This project includes three inter-related thrusts. The first thrust develops program analysis techniques for online measurement and visualization that provides energy consumption information to developers at the level of individual lines of an application?s source code. Using this capability, the second thrust identifies a set of energy-aware development best practices via an empirical study of the relationship between energy consumption and implementation structure at the application's architecture, design, and code levels. The third thrust uses the best practices to propose a set of energy-reducing refactorings to the developers and help them to identify the changes that will lead to the most energy efficient applications.

The Internet is an essential part of modern society, playing a vital role in a wide range of educational, commercial, military, and social activities. However, network operators today have a limited ability to observe and control the paths used to carry traffic across the Internet. For example, although it is often beneficial for several networks to cooperate?e.g., a content provider and cellular network jointly picking the best paths from content to customers?existing Internet routing protocols make it difficult to share information or collaborate to select routes. These limitations contribute to a host of problems, including decreased path stability, degraded performance, and service outages.

This project will develop a system called IN-CONTROL that aggregates information from participating networks and active measurements into an inter-domain network information base (iNIB). The iNIB presents operators with a unified interface for making observations about global forwarding paths and a rich control interface for issuing requests to steer traffic along preferred paths. To build the iNIB, the project is focusing on the following tasks: (i) developing provenance-based techniques to obtain reliable results from computations performed over potentially-untrustworthy data (ii) designing deployable mechanisms for observing and controlling Internet forwarding paths, and (iii) building a scalable implementation that incorporates optimizations to reduce resource demands for answering iNIB queries. The intellectual merit of this research lies in developing reliable abstractions for observing and controlling Internet forwarding paths and a scalable implementation that can be readily deployed on the current Internet.

The broader impacts include reducing the fragility of the Internet, and broadening the interdisciplinary community of researchers working on problems related to inter-domain networking. This project also provides research experiences for undergraduate students and members of under-represented groups.

When we use Office365, Amazon, or Facebook, we access a world of rich services via a network. Network reliability is paramount for business, science, and government because downtime affects productivity, economic output, and social communication. However, reliability is difficult to achieve in the face of component failure, manual configuration, and the stringent economics of the IT industry. This project will take first steps towards creating a new field of inquiry, Network Design Automation (NDA). NDA seeks to create computer-aided design (CAD) tools that reduce design effort and increase reliability based on a scientific understanding of network structure. NDA is inspired by Electronic Design Automation (EDA), a $7B industry that underpins the $100B chip industry, and is a vibrant intellectual discipline in its own right.

NDA will verify networks using formal methods but also broaden the agenda to debugging networked systems and to other specialized networks such as rural networks and CDNs. Specific new tasks include tying application performance to network problems using machine learning, understanding failure logs using Natural Language Processing, creating more controllable routers inspired by hardware boundary scan ideas, rural network design using constraint satisfaction, network scripting to lower the barriers for operators, and data mining to find configuration bugs without a specification. Networks have unique challenges including heterogeneity, management complexity, rate of evolution (new data centers and service rollouts), and high availability needs. Besides a consistent focus on using algorithm search, we will leverage data mining, machine learning, Natural Language Processing, and hardware test approaches. NDA will not merely reuse existing mechanisms but exploit domain-specific insights about the structure of modern networks to invent new and scalable approaches.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.