ARPA PROPOSAL ABSTRACT - submitted 11-24-97 I. COVER SHEET 1. BAA NUMBER: 98-03 2. TECHNICAL TOPIC AREA: 3) Demonstration of Enhanced Applications 6) Active Network Management Technologies that are Capable of Adapting the Network to Meet Quality of Service Guarantees 3. PROPOSAL TITLE: Active Sensor Networks 4. TECHNICAL POINT OF CONTACT: Prof. Henning G. Schulzrinne (PI) Dr. Danilo Florissi (co-PI) Email: hgs@cs.columbia.edu Email: df@cs.columbia.edu Phone: 212 939-7042 Phone: 212 939-7095 Fax: 212 666-0140 Fax: 212 666-0140 Mailing Address: Mailing Address: Computer Science Department Computer Science Department Columbia University Columbia University 500 West 120th Street 500 West 120th Street Room 450 Computer Science Bldg Room 450 Computer Science Bldg New York, NY 10027 New York, NY 10027 Prof. Yechiam Yemini (co-PI) Prof. William Menke (co-PI) Email: yemini@cs.columbia.edu Email: menke@ldeo.columbia.edu Phone: 212 939-7123 Phone: 914 365-8438 Fax: 212 666-0140 Fax: 914 365-8150 Mailing Address: Mailing Address: Computer Science Department Lamont-Doherty Columbia University Earth Observatory 500 West 120th Street Columbia University Room 450 Computer Science Bldg Palisades, NY 10964 New York, NY 10027 Prof. Yair Amir (co-PI) Prof. Baruch Awerbuch (co-PI) Email: yairamir@cs.jhu.edu Email: baruch@cs.jhu.edu Phone: 410 516-4803 Phone: 410 516-8038 Fax: 410 510-6134 Fax: 410 510-6134 Mailing Address: Mailing Address: Department of Computer Department of Computer Science, NEB 224 Science, NEB 224 The Johns Hopkins University The Johns Hopkins University Baltimore, MD 21218 Baltimore, MD 21218 5. ADMINISTRATIVE CONTACT: Name: Patricia Welch Phone Number: 212 854-6851 Email: phw1@cunix.cc.columbia.edu Mailing Address: Office of Projects & Grants 500 West 120th Street Room 351 Engineering Terrace New York, NY 10027 6. COSTS FY1 FY2 FY3 Total $650,000 $650,000 $650,000 $1,950,000 7. TYPE OF BUSINESS: OTHER EDUCATIONAL (university). II. TECHNICAL SECTION A. INNOVATIVE CLAIMS We propose to develop technologies for Active Sensor Network (ASN) that can dynamically adapt their functionality, protocols, and operations to dynamic changes in the targets monitored, foci of interest and network resource availability as described below. ASN technologies will add significant flexibility to the current state of the art of sensor network engineering. Specifically, they will contribute three novel dimensions of dynamic adaptability: (1) adaptation to changes in external scenarios monitored by the network; for example, upon discovering certain types of aircraft a sensor can deploy tracking algorithms specifically optimized for this aircraft; (2) adaptation to dynamic changes in users interest; for example, a user monitoring seismic sensors may wish to allocate greater ASN resources to execute more detailed samples of certain frequency bands; (3) adaptation to dynamic resource availability; for example, a sensor failure may trigger dynamic redeployment of functions among neighboring sensors. ASN will also enable time-sharing of resources among multiple sensing tasks. Sensor networks typically involve limited resources that constrain their ability to execute simultaneous sensing tasks. ASN will enable dynamic sharing of resources among concurrent sensing tasks. For example, a sound-based aircraft monitoring ASN may be shared among tasks to detect arrival of new aircraft, track motion of aircraft that were previously detected, and collect and process signatures to classify the aircrafts. Many sensor applications require timely delivery for early warning of potential dangerous events. ASN can deploy dynamic application-specific resource configuration protocols to guarantee real-time response. We propose to use active networks technologies to program new protocols based on economic principles that can adapt the Quality of Service (QoS) seen by the sensor applications. Finally ASN can use special application-specific protocols to multicast data among sensors and more powerful processing units. We will use programmable multicast as opposed to current hardwired (IP Multicast) or middle-ware techniques (Horus, Transis, Totem). In contrast, application-specific multicast enables the application to create and dynamically tailor multicast services inside the network, thus allowing both flexibility and efficiency. The project deliverables include a fully functional prototype of a real ASN software components and in-field tests, a programming platform to develop ASN, and novel active protocols for adaptive QoS management and multicasting. B. TECHNICAL RATIONALE The goal of the project is to demonstrate use of active network technology to improve the performance and functionality of a real sensor network. Active network technology allows programming of networks much the same way that one can program the end machine. Programmability is especially useful in systems like sensor networks that have scarce resources, complex functionality, and are prone to frequent failures. For example, one may need to deploy during operation a specialized routing protocol to extract and disseminate accurate information from critical sensors. Or one may decide to change the code that is running at particular sensors in order to cope with system failures or special events. The project will integrate multiple supporting technologies to accomplish its goal. The first technology is the Netscript system for programming network. Netscript is a dataflow-based language that abstracts packet stream processing functions. The system also includes the VAN architecture for abstracting network connectivity structures (nodes and links). Finally, Netscript enables automatic generation of management instrumentation. The second technology are protocols for multicasting and resource allocation that use economic principles. ASN have limited resources and need sophisticate resource allocation and multicasting capabilities. We will develop protocols based on economic principles that can be customized to specific ASN situations and can be dynamically deployed on-demand. The target testbed is a sensor network to study seismic activities (described later). The project will develop a new generation of sensor networks that can accomplish multiple novel tasks. At the end of the contract, we will deliver: * A fully functional prototype of a real ASN software components and in-field tests. We will upgrade an existing sensor network that detects seismic events with active components to create an ASN. The target testbed sensor networks are described in the next section. * A programming platform to develop ASN. We will use and extend the Netscript system for active networks and include special libraries suitable for sensor network applications and operations. * Novel active protocols. New protocols based on economic principles for will be used to experiment and enhance the functionality of ASN. We will develop protocols for adjustable QoS reservation and for new multicasting algorithms that can efficiently disseminate collected sensor data. * Investigation of use of Netscript for automatic management of ASN. We plan to integrate the design of the system and its management by using Netscript. Management is a core component of any in-field sensor network. The proposed research will benefit from significant prior work by the PIs. Prof. Schulzrinne is one of the co-developers of RTP and his work on Internet telephony signaling is current under consideration by the IETF as the Internet telephony media server control protocols. Dr. Danilo Florissi has worked on new protocol architectures for high-speed networks to provide guaranteed QoS. Prof. Yemini and his students have pursued preliminary studies of the Netscript language in recent years, as part of the project to develop decentralized network management technologies. Prof. Amir has been working with distributed systems, network protocols, and replicated systems for more than 10 years. Prof. Awerbuch's research is focused on theory online and distributed decisions making and application of this theory to networks, and distributed systems. His work has been recognized with the Outstanding Innovation Award of IBM's Research Division and has been adopted as standard for IBM's wide-area and metropolitan-area networks. Prof. Menke is with Lamont-Dohert Earth Observatory (which is scientifically renowned throughout the world) and has been working with seismic sensor networks for many years. Three of the ones he has participated in are described in the next section. This is a three year project. During the first year we will design the Netscript extensions and the new protocols. The second year is devoted to implement the extensions and protocols possibly using testbed. Finally, during the third year we will deploy the algorithms in the real sensor network and use it for field tests. The remaining of this abstract is devoted to explain the components in more details and how they can accomplished the stated goals. B.1. THE TARGET APPLICATION: Earthquake Detection Network Test Bed We propose to test the active network techniques on an Earthquake Detection Network (EDN). An earthquake detection network is a system of geographically-distributed stations that measures the ground motion associated with earthquakes and other seismic phenomena, characterizes the earthquake's size and location, alerts personnel to its occurrence, and archives data for future study. Most current implementations of EDN's are based on a star topology: stations on the rays perform mainly data-collection and transmission, and some simple data processing (e.g., parameter extraction, data compression); a single site at the star's center receives data from all stations, correlates them, prepares a detailed description of the earthquake, notifies civil defense personnel, and archives the data in a database. Realtime broadcasts of warning of impending strong ground motion - which can allow safe shutdown of industrial processes - are also possible, though not currently implemented in existing systems. EDN's perform several levels of data processing. Raw ground motion data is typically a continuous multi-component time series, that is created by digitizing an analog ground motion sensor (e.g., seismolemeter or accelerometer), and which must be timestamped, compressed, telemetered and archived. Earthquakes are recognized though their distinctive signature in the ground motion data. Their identification is complicated because a large distant earthquake can produce shaking levels similar to very small, nearby events (e.g., footsteps). Event detection and recognition is typically carried out in a multi-stage process, with a simple level of processing being performed on the data stream from a single station (often by the station processor itself), and a more complicated stage, involving correlation between stations, being conducted later. Our techniques have the potential of enhancing the functionality - and improving performance - of EDN's in several ways: We have identified three EDN's that are potential testbeds: 1. IRIS BroadBand Array, a portable, 32-station, spread-spectrum radio telemetered network operated by the Incorporated Research Institutions for Seismology (a US non-profit organization) for seismological research. It can be borrowed by any university. It had been successfully operated in for several months during a seismological experiment in Wyoming. Station processors are specialized hardware with which Menke has several years of experience. 2. SIL Array, a permanent, 20-station, X.25 telemetered civil-defense network operated by the Iceland Meterological Office (Reykjavik, Iceland). Menke has worked with this group for about ten years, and has excellent contacts with the staff. The SIL array has the reputation of being one of the more advanced, in terms of the sophistication of its software and its functionality. Its use of UNIX operating systems on both station and central processors make software development easier. 3. Lamont Cooperative Seismic Network, a permanent, 25 station, internet-telemetered, academic research network operated by the Lamont-Doherty Earth Observatory (Columbia University) in conjunction with various other academic institutions and government agencies. The system has only four station processors (with 5-10 sensors telemetered to each station via old analog radio links), so it is the most primitive of the three testbed systems. Its accessibility (with one station processor physically at Columbia) and high network bandwidth may make it useful for preliminary testing. B.2. THE NETSCRIPT SYSTEM FOR ACTIVE NETWORKS The core idea of the NetScript approach to active networks is that of creating unifying abstractions. It is useful to draw on the analogy to PostScript to explain this. PostScript abstracted the functions of a printing engine in terms of universal language primitives. PostScript programs can be viewed as active elements that abstract page processing by a printer. They are dynamically dispatched to printing engines that interpret and execute them. These abstractions of PostScript created a unifying logical separation between printing engines and the page descriptions that they execute. This enabled printer vendors to introduce innovative engines that are universally programmable by applications vendors to accomplish richer functionality than was possible before. NetScript pursues a similar paradigm to create active network engines. It views a network node as a collection of engines that process packet streams. The language abstracts packet stream processing functions in terms of universal abstracted primitives. Scripts in the language are used to construct dataflow engines -- the active elements -- that operate on packet streams. The NetScript language creates unifying abstractions of packet stream processing that enable programming arbitrary stream processing functions. Like PostScript, these abstractions create unifying logical separation between node processing engines and the stream-processing functions that they execute. Once an active element has been coded as a NetScript program it is dynamically dispatched and executed at nodes using an agent delegation mechanism. Delegation-servers, embedded in nodes, support a secure delegation protocol to dynamically deploy, execute, and control NetScript programs. Programs arriving at a node are dynamically compiled, optimized, and bound by the NetScript runtime environment to other active elements at the node. Thus, the first unifying abstraction pursued by NetScript is that of capturing language-level universal primitives to create packet- processing engines. The second unifying abstraction pursued by NetScript is that of network connectivity structure. This abstraction is implemented by the NetScript Virtual Active Network (VAN) mechanisms. A VAN is formed by connecting active nodes using virtual links. A virtual link abstracts underlying network link and node resources that provision it. Furthermore, the VAN manages this binding of virtual links to link provisioning resources dynamically to admit changes in resource availability and VAN needs. VAN abstractions thus accomplish two major goals. They organize active elements into units of coordinated end-end functions. They separate and abstract active network processing from the underlying resources that they use. A third unifying abstraction used by NetScript is that of manageability. The NetScript compiler can analyze the structure of stream processing engines and automatically generates instrumentation to monitor their behaviors. This unifies and automates the creation of management information bases (MIBs) for active elements. This should be contrasted with the current explosive growth in ad hoc, manually coded MIB instrumentation of network elements. NetScript would replace these thousands of MIBs with a single unifying instrumentation. It would replace the ad hoc labor-intensive processes of committees and vendors to create these MIBs with automated compile-time processing, akin to the generation of debugging support. B.3. ACTIVE PROTOCOLS We plan to experiment with the ASN to implement novel active protocols for adjustable QoS guarantees and multicasting. In the following, we provide an overview of the techniques that we plan to use in developing the protocols. ADJUSTABLE QOS. We use economic principles to allocate resources in a network. In our model, each application provides a QoS-reward function, indicating how important it is to achieve a certain level of QoS, measured in some currency. Money is not the objective, rather, it is a tool for achieving efficiency and capturing priorities. For example, real time sensor data may need a hard bound on latency, which means that if latency exceeds this value, then the reward is zero. Non critical sensor samples can be flexible and offer rewards based on diminishing returns curve. In general, the QoS-reward function may be represented by a multi-dimensional matrix, specifying the amount of reward for different values of important parameters such as bandwidth, latency and jitter. Additionally, some sensors may need different levels of service at different times, yielding time variable QoS-reward function. For example, at a time that an earthquake is detected, the appropriate warning sub-system receives top priority. It offers an extremely high reward and no tolerance for QoS degradation. Our aim is to allocate the limited resources in the presence of conflicting and time-variable demands and priorities of different applications. When we decide to allocate resources, we use a concept of opportunity cost, which measures the amount of deterioration in the service level for other applications that may want to use this resource in the future. The opportunity cost reflects the relationship between future demand of the resource and its current supply. It can be estimated in an online manner by exponential function of the current resource utilization. Surprisingly, using this simple online estimate enables us to allocate resources in a way that the total reward paid by all of the applications is close to the one achieved by optimal prescient strategy that has full information about the future. Our algorithm does not know or use any information about the future inputs and priorities, and does not assume any correlation between past and future. MULTICASTING. We strive to approximately optimize the costs of the overall multicast tree by using online Steiner Tree algorithms for joining members or merging subgroups. Instead of finding the shortest path to the sender, the new member connects via a shortest path to a previously connected member. This algorithm provably yields near- optimal overall cost. We will modify this algorithm in order to meet the sensor application requirements for end-to-end latency. This modification will appropriately restrict the shortest path selection, without significantly compromising total bandwidth cost optimality. *** added 12-17-97 Your abstract entitled "Active Sensor Networks", with control number 9803061, has completed the evaluation process and was found to fit within the program goals of this BAA. We encourage you to develop a full proposal based on your submitted abstract and remind you that the BAA stresses innovative, revolutionary advances in the state of the art. Please understand that all full proposals will again be evaluated carefully by a quality review panel, must stand on their own merits, and must fit program goals to be considered for funding. The deadline for submission of proposals under BAA 98-03 is 4:00 pm ET, Monday, Jan 12 1998. Thank you for your participation in DARPA programs.