Ramesh Govindan - US grants

9321043 USC Postel The major project elements for the routing arbiter include advancement of Internet routing algorithms with respect to scaling and stability issues, routing information registration and dissemination for the network service providers serving the Internet, deployment of route servers to aid in the dissemination and real time maintenance of the global Internet routing system, and coordination and sharing of technical information in support of the Internet operations community. A key task for the routing arbiter will be to enhance the use of new switched services offered by the telecommunications carriers, sucy as ATM, in place of dedicated point to point technology that is widely deployed in wide area internets. This proposal is a part of a collaborative effort with Merit. Although both Merit and USC teams will collaborate in all areas, USC will take the lead with the route servers, advanced routing development, provision of a testbed and routing engineering and Merit will take the lead for management and coordination, transition, and operations. While Merit will take the lead in overall coordination, USC will see that apprpriate collaboration is accomplished in research and development.

The Multihop wireless capabilities will enable communication and coordination among autonomous nodes in unplanned environments and configurations. At the same time wireless channels present challenges of dynamic operating conditions, power constraints for autonomously-powered nodes, and complicating interactions between high level behavior and lower level channel characteristics (e.g. , increased synchronized communication will significantly degrade channel characteristics). The major goal of the research is the development, testing and characterization of algorithms for scalable, application driven, wireless network services using a heterogeneous collection of communicating mobile nodes. Some of these nodes will be autonomous (robots) in that their movements will not be human controlled. The others will be portable thus, making them dependent on humans for transportation. While the focus of the work is on the mobile nodes, include immobile computers on the network as well. It emphasize that most (though not all)
of the mobile nodes will have modest sensing, computational and communication resources. The collection as a whole is an example of a sensor network. The chief scientific motivation behind the work is the design of robust, efficient and scalable algorithms. The researchers hypothesize that distributed algorithms that rely on local interactions have many compelling characteristics, resulting in these properties. There is significant overlap between the problems of coordinating the autonomous mobile nodes that carry some of the sensors and the algorithms that direct the f ow of information from source(s) to sink(s) in the network. Both setsof algorithms will be carefully designed to improve robustness, effciency and scalability.

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.

Sensornets will provide detailed measurements at fine spatial granularities over large geographic areas. Providing access to the data is a formidable challenge because the measured data are distributed across the entire sensornet and communication between sensornet nodes requires substantial expenditures of scarce energy. Data-centric abstractions are now seen as a fundamental aspect of sensornet systems that provide efficient access to sensor measurements. In prior work, we have suggested that sensornet applications would benefit from data-centric storage. Such systems enable efficient querying and search in large-scale sensornets. However, data-centric storage makes exacting demands on its routing infrastructure. In particular, data-centric storage is predicated on a robust and efficient routing primitive that allows storing data by name at a node in the sensornet.

This proposal seeks to investigate the design and development of geographic hash tables (GHTs), a routing primitive for data-centric storage. GHTs bring together two technologies, distributed hash tables (DHTs) and geographic ad-hoc routing, that were developed in two completely unrelated contexts, peer-to-peer systems and ad hoc wireless networks. Each technology has been extensively explored in its respective domain, but the combination of these technologies in the new, and more challenging, context of sensor networks raises many new design challenges.

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.

The purpose of the informational meeting is to share with the community the goals and scope of the focus area. By including presentations from researchers, vendors, and applications experts, this meeting will enable attendees to get a sense of the state of the art in sensor networks, and the key challenges facing the focus area and sub-areas thereof. It will help the community better target proposals; PIs will be able to conserve efforts by understanding which proposals would be completely out of scope. Finally, it will start to build a community for the focus area, perhaps encouraging early collaboration and potentially strengthening the pool of submissions.

The Tenet project is developing an alternative architecture for tiered wireless sensor networks that contain both small-form-factor motes and high-powered nodes called masters. The Tenet project's guiding architectural principle asserts that multi-node data fusion functionality and complex application logic should be implemented only on the masters, since the cost and complexity of implementing this in motes outweighs the performance benefits of doing so.

Tenet thus simplifies and standardizes the design and construction of the most difficult-to-handle software on a sensor network. It restricts mote communication to trees rooted at masters. Tree communication is well understood, leads to more predictable communication patterns and improves the manageability of the mote tier. Direct inter-mote communication would destroy much of this predictability and manageability.

The project is designing and prototyping the Tenet stack. This stack embodies the Tenet architectural principle and can be reused by several applications. The development of such a stack for large-scale sensor networks will greatly accelerate the development of a variety of applications ranging from habitat monitoring to structural monitoring. Without a Tenet-like architecture, sensor network deployments will never truly impact the world.

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.

Proposal Number: Collaborative Research: 0626954, 0626151, and 0627155
PI: Ramesh Govindan, Leonidas Guibas, Subhash Suri
Institution: USC, Stanford, UCSB
Title: NeTS-NOSS: Lightweight Monitoring Tools for Sensor Networks

Abstract:

Networks of tiny and inexpensive smart sensors have ushered a new generation of low-cost, large-scale, high-resolution, real-time sensing and actuation. As their economic importance grows along with their size and complexity, it becomes critical to ensure their operational health and robustness through continuous monitoring. With that motivation, this project develops lightweight monitoring algorithms and tools for sensor networks that allow the network operators to observe the large-scale behavior of the network and detect significant anomalies in network attributes or performance. The tools themselves are generic and can be composed to provide tailored solutions to meet various application-specific needs.

The design of these monitoring tools requires inferring global aspects of the network through local information available at individual nodes. In order to synthesize a global summary from local views in a lightweight, energy-efficient manner, the project employs three methods: (1) intelligent sampling, (2) information aggregation, and (3) sparse representation of the signal landscape. These methods utilize mathematical techniques from geometry, topology, statistics, and distributed signal processing.

The network monitoring tools enable better designed, more robust, trustworthy, and longer-lived sensor networks in operation. That, in turn lowers costs and enlarges the community of users as well as the set of potential commercial applications for networked sensing.

The research output of this project includes novel algorithms, software tools, and their empirical evaluation using testbeds.

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

Contention-Awareness in Mesh Transport: Theory and Practice

Multi-hop wireless mesh networks are becoming increasingly important elements of edge networks in the Internet. These networks of static nodes provide community networking, distributed sensing, and Internet access. In each case, the primary advantage of a mesh is its easy deployability and upgradability.

Despite these advantages, mesh networks have not seen widespread adoption. The primary reason for this is a lack of attention to the transport performance of such networks, which leads to poor end-user experience. The central challenge to improving transport performance in mesh networks is to make the transport protocol aware of the complex interference that exists in multi-hop wireless networks.

Intellectual Merit. This work will explore the design space of transport protocols for mesh networks. It will focus on two classes of designs: a) easy to implement, fair and efficient schemes that ensure that competing traffic is correctly throttled when congestion is detected inside the network, and b) near-optimal schemes estimate available network capacity and apportion it to flows in a fair and efficient manner.

Broad Impact. The proposed work can spur the adoption of mesh networks in a future Internet, and influence architectural choices in its design. Mesh networks are already becoming the networking technology of choice in a variety of locations including airports, hotels, convention centers, shopping malls, education facilities, and hospitals. With their increasing economic importance, this project is poised to make impact, seeking as it does to improve the performance of mesh networks.

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.

This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5).

This project focuses on understanding the principles and methods for the design of green networks at the edge of the Internet. The total power consumption of edge networks is estimated to be quite significant, so even moderate improvements in energy-usage in an individual device can result in non-trivial savings overall. Obtaining these moderate improvements in the energy-efficiency of edge networks is challenging for two reasons: the diversity of edge networks and the dynamics in their workload.

Intellectual Merit. Leveraging the researchers' combined expertise in low-power electronics, link-layer technologies, and energy-efficient network subsystem design and architecture, the project will: a) devise a deep energy-inspection architecture that encompasses a broad range of edge devices and networking technologies, and incorporates innovative hardware designs for subsystem-level monitoring and control of energy usage; b) explore run-time energy adaptation at various levels of the network, enabled by this inspection architecture; c) examine coordination mechanisms for controlling edge network energy usage which will allow coordinated energy management across components and devices, enabling more aggressive energy savings.

Broad Impacts. The project can have significant societal benefit, targeted as it is on sustainable technologies. Moreover, the techniques it develops for energy efficiency can be broadly applied to other areas of computing: large server systems, mobile devices, and consumer appliances. Beyond its impact on technology, the project will also contribute to workforce development by training EE and CS students in sustainability.

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.

Networked systems have always been designed to operate even in the presence of failures, especially in communication links and storage. Until recently other components of such systems had relatively low probabilities of failures and for most networked systems, desired levels of resilience could be achieved using minimal redundancy added in an ad hoc manner. Two opposing trends are likely to make the task of achieving resilience significantly more difficult in the coming years: (a) increasing hardware failure probabilities: with the move towards finer nano-scale fabrication, chips are increasingly vulnerable to soft errors caused by external noise and are increasingly likely to fail early due to fatigue; (b) higher resilience requirements: as critical services continue to migrate to clouds, service providers are compelled into more stringent service-level agreements (SLAs), including higher reliability, higher availability, and tighter guarantees on service times. The above combination can dramatically increase the overhead of existing approaches for achieving desired levels of resilience.

Intellectual merit: The first outcome of this project will be a holistic roadmap for resilience of networked systems. This resilience roadmap will take the roadmaps from the nano-scale CMOS (trends in chip cost, functionality, performance, power, and resilience that can be attained at chip level) and attempt to realistically project the future cost of currently-used networking and systems techniques for achieving desired level of resilience. The second outcome of this project is to develop resilience methods that scale gracefully in the face of increasing hardware failures. Such techniques will use novel partitioned redundancy strategies that achieve reliability at different levels across hardware and software layers.
Broader Impacts. The resilience roadmap will provide unprecedented understanding of the trends in resilience and a uniquely realistic assessment of challenges and opportunities. This will significantly influence the research in the hardware as well as networking communities. A systematic design of scalable resilience methods will lead to significantly higher levels of resilience, lower costs - capital (equipment) as well recurring (especially, energy), and/or higher levels of performance. The utilitarian gains to society by the proposed project are likely to be substantial, since networked systems now constitute one of our most critical infrastructures and consume an increasingly large proportion of our resources.

This project will draw upon two different disciplines, hardware architecture and networked systems, and involve detailed case studies and development of completely new theory and techniques, and will therefore provide unique educational and training opportunities for students and working professionals in these fields.

Budget Impact Statement: The item numbers in this paragraph refer to those in Figure 9 and Section 3.2 (entitled 'Proposed Research Tasks and Plan') of our original proposal. We will undertake all tasks and sub-tasks proposed in item-1 (and all its sub-items). In item-2, we will undertake the development of a general framework to consider all basic redundancy schemes and alternative ways of deploying them (sub-item-2.1). We will also characterize the associated tradeoffs (sub-item-2.2) and the consequences of realistic constraints (sub-item-2.3). However, we will pursue the development of prototype tools (as outlined in sub-item-2.4), to the extent necessary to demonstrate the benefits of our approach and to conduct case studies (described in item-3). Finally, we will undertake the case studies as originally proposed in item-3.

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.

Until now, the cyber component of automobiles has consisted of control algorithms and associated software for vehicular subsystems designed to achieve one or more performance, efficiency, reliability, comfort, or safety goals, primarily based on short-term intrinsic vehicle sensor data. However, there exist many extrinsic factors that can affect the degree to which these goals can be achieved. These factors can be determined from: longer-term traces of in-built sensor data that can be abstracted as triplines, socialized versions of these that are shared amongst vehicle users, and online databases. These three sources of information collectively constitute the automotive infoverse.

This project harnesses this automotive infoverse to achieve these goals through high-confidence vehicle tuning and driver feedback decisions. Specifically, the project develops software called Headlight that permits the rapid development of apps that use the infoverse to achieve one or more goals. Advisory apps can provide feedback to the driver in order to ensure better fuel efficiency, while auto-tuning goals can set car parameters to promote safety. Allowing vehicles and such apps to share vehicle data with others and to use extrinsic information results in novel information processing, assurance, and privacy challenges. The project develops methods, algorithms and models to address these challenges.

Broader Impact - This project can have significant societal impact by reducing carbon emissions and improving vehicular safety, can spur innovation in tuning methods and encourage researchers to experiment with this class of cyber-physical systems. The active participation of General Motors will strongly facilitate technology transfer. The program has outreach through internships, course material, high school and undergraduate involvement, and through creating an open infrastructure usable by diverse developers.

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.

Management of today's networks usually requires an army of operators who devote tremendous time and energy. Software-defined networking (SDN) has been shown to be a promising paradigm for simplifying network management. However, management tasks in SDNs require the use of constrained network resources: switch memory and CPU, and the switch-controller network bandwidth. Given these resource constraints, network operators may have to reason about resource usage when initiating network management tasks.

This project seeks to explore the space of resource management for software-defined network management. Specifically, it will examine the design of virtualized resource pools that provide the abstraction of (nearly) infinite resources (memory, CPU and switch), while dynamically adapting to the resource needs of these network management tasks. This approach has the advantage that network operators do not have to reason about resource usage when instantiating network management tasks. The research will yield resource management algorithms, improved resource usage designs, and systems implementations for virtualized resource pools.

Network operators make billion-dollar investments in network infrastructures, but put little thought into visibility and control of these infrastructures. This project can lead to better-managed, more reliable, and more resource-efficient network infrastructures in ISPs, enterprises and clouds. These efforts eventually will have broader societal impact by enabling commercial, social, and scientific advances. The proposal will give underrepresented groups and undergraduates opportunities to participate in research and will likely result in technology transfer to major cloud providers and ISPs.

Global Internet services, such as web search, social networking, video dissemination, and cloud computing are built on data centers that are large warehouses full of computers. The computers in the data centers are connected together, and to the Internet, by a network. If that network goes down then the computers it connects and the Internet services they support also go down. This project aims to decrease, by one to two orders of magnitude, how long those networks are down each month.

The project will explore the design of two components that can contribute significantly towards decreasing network downtime. One component will be a new highly-available control plane that will include a new replication protocol that provides strong consistency and resilience to the failure of an external failure detector while retaining as many of the desirable properties of current less-available designs (e.g., small resource footprint) as possible. The other component will be an automated management plane that will raise the level of abstraction of specifying a management operation (MOp) on the network, thereby allowing automated software to synthesize and manage the sequence of steps necessary to achieve a complex network MOp such as upgrading software on a large network.

Global Internet services are an integral part of modern life and increasing their availability will benefit society. The project plans include developing software prototypes and working closely with large Internet services to increase the likelihood of technology transfer. The research in the project will be conducted by graduate students and undergraduate students that will learn how networks work, how to build and improve them, and how to build and improve the computer systems that control them. Each of these skills is likely to be increasingly important in the coming years.

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.