David Bruce Johnson - US grants

This research investigates the tradeoff between failure-free overhead and output latency in transparent distributed rollback-recovery. This tradeoff arises because, with rollback-recovery, output to the "outside world" must be delayed until enough recovery information is recorded on stable storage to guarantee that if a failure occurs, the system will never roll back to a state preceding the one from which the output was performed. The resulting latency can be reduced by keeping recovery information on stable storage closely up-to-date during failure-free operation, but at the expense of extra failure- free overhead. The work includes an investigation of how rollback-recovery methods based on logging can be extended to support nondeterministic process execution, occurring, for instance, as a result of multithreading. Nondeterministic events are recorded on stable storage, and are used during failure recovery to replay the same events. For example, by recording the execution of synchronization primitives such as semaphores, one can support multithreading in which all access to shared data is protected by these synchronization primitives. Checkpoints offer an alternative for processes for which recording nondeterministic events is impossible or is too expensive.

NCR-9502725 David B. Johnson The availability of powerful mobile computing devices and wireless networking products and services is increasing dramatically, making it natural for users to expect to be able to access network resources and to utilize the growing global internetwork at any time and from any where. However, existing internetworking protocols such as IP, ISO CLNP, NetWare IPX, and AppleTalk cannot currently support this type of host mobility. Network applications generally must be reconfigured and restarted when connecting to the network at a different point, making host movement difficult, time consuming, and error prone. The objective of this research is to develop scalable and robust protocols for providing seamless support of transparent internetworking for wireless and mobile hosts. This research addresses a number of areas in which new support is needed for this goal, including internetwork routing to mobile hosts; routing among mobile hosts in an ad hoc wireless network; internetwork multicasting to and from mobile hosts; and protocol support to allow higher-layer protocols and applications to adapt their behavior in response to mobility. The work in this project will consist of designing new protocols, implementing each protocol, and evaluating each protocol using performance measurement and simulation studies over a range of environments and alternative design choices.

An ad hoc network is a group of mobile computers (or nodes) using wireless network interfaces, in which individual nodes cooperate by forwarding packets for each other to allow nodes to communicate beyond their direct wireless transmission ranges. This project is attempting to create a routing protocol for ad hoc networks that is highly robust against attacks, yet is able to perform close to the best existing non-secure ad hoc network routing protocols.

The research focuses primarily on on-demand (or reactive) routing protocols, in which a node attempts to discover a route to some destination only when it has a packet to send to that destination, but also considers how the routing security techniques developed apply to other styles of ad hoc network routing protocols such as periodic (or proactive) and hybrid protocols. The research addresses passive and active attackers, including cooperating attacking nodes and compromised nodes. The types of attacks considered range from routing disruption attacks, in which an attacker attempts to cause legitimate data packets to be routed in dysfunctional ways, to resource consumption attacks, in which an attacker injects packets into the network in an attempt to consume valuable network resources such as bandwidth, or to consume node resources such as memory (storage) or computation power.

The PIs driving vision is to provide a high-performance, scalable and widely deployed wireless Internet that facilitates services ranging from radically new and unforeseen applications to true wireless "broadband" to residences and public spaces at rates of 10s of Mb/sec. Unfortunately, today's wireless networks such as cellular and WiFi hot-spots cannot achieve this vision due to problems encountered on multiple fronts: (1) excessive costs of the wired backhaul network, (2) poor performance scaling, and (3) excessive costs of spectral license fees. We will design an architecture that is based on Transit Access Points (TAPs), devices that form a wireless backbone mesh via high-performance directional-antenna wireless links operating in the unlicensed band.

This multihop wireless mesh interconnects wireless TAPs with limited wired Internet entry points and with wireless multihopping mobile users. To achieve the objectives with this architecture, the PIs will use a combination of theory, algorithm and protocol design, simulation, and implementation and testbed experimentation to address the following fundamental research issues: (1) development of scalable distributed opportunistic scheduling and media access protocols, (2) development of coordinated multi-hop resource management algorithms, (3) analysis of system capacity that incorporates the critical effects of protocol overhead, and (4) deployment of a first-of-its-kind neighborhood testbed.

Abstract:

In a battery-powered sensor network, energy and communication bandwidth are both limited. Moreover, processing a sensor measurement locally often requires orders of magnitude less energy than communicating it to a distant node, yielding an interesting communication/computation tradeoff: whenever possible, the network should reduce the need for global communication at the expense of increased local processing and communication. A promising approach for reducing global communication is to perform signal processing to extract key information inside the sensor network in a distributed fashion, thus dramatically reducing global communication requirements without losing fidelity.

This project aims to develop a sensor network architecture whose communications hierarchy is aligned with the information flow of its computations. In particular, the research involves developing (1) a multi-overlay sensor network architecture that supports both multi-scale and proximity communication and computation; (2) new multiscale sensor data representations based on wavelet transforms; and (3) network services for sychronization and localization of network nodes. The research includes analysis, simulation, and a small-scale testbed of sensor nodes on the Rice University campus.

Within little more than a decade, digital information and the Internet have assumed a critical role in virtually all sectors of society, including education, commerce, science, government, and entertainment. However, today's Internet is dependent on wired or cellular wireless infrastructure. This dependence limits the reach of digital communication to regions of the world where the required infrastructure is technically and economically feasible; at the same time, it renders the network vulnerable to disasters and attacks that threaten this fixed infrastructure. This proposal aims to develop technologies to reduce the dependence of digital communication on wired and cellular wireless infrastructure, thus extending its reach into underdeveloped parts of the world and economically disadvantaged part of society and increasing its resilience to natural disasters, acts of war, or terror attacks on its physical infrastructure.
The work exploits synergies between two areas of research that have enjoyed dramatic advances in recent years, but have to date mostly worked independently: (1) ad hoc networking, and (2) decentralized, self-organizing distributed systems. They have assembled a team of experts in each of these areas that will jointly tackle the major technical challenges towards a network architecture that exploits infrastructure when it is available but does not depend on it:
Self-organizing network hierarchy: Will develop a novel, self-organizing buoy protocol that recursively subdivides the network into an adaptive, proximity-based hierarchy of cells. The cell hierarchy provides the foundation for scalable routing and provides a low-overhead, proximity-based overlay structure that can be used to support network services. Periodic broadcasts from buoy nodes in each cell efficiently disseminate aggregated location, addressing, and routing information. Scalable ad hoc network routing: Based on the buoy protocol, they will develop an ad hoc network routing architecture for mobile and stationary devices that scales to at least tens of thousands of nodes. Nodes maintain only a small amount of routing state that is logarithmic in the size of the network, in exchange for a slightly longer route length. Nodes maintain their routing state passively by listening to buoy broadcasts, which results in very low routing overhead. The per-node space and message requirements of the protocol grow at most logarithmically with the size of the network.
Self-organizing network services: The proposers plan to develop self-organizing, robust, and secure network services that exploit the hierarchical overlay structure of the buoy protocol. Basic naming, host configuration and network time services will ensure the operation of the network in the absence of fixed infrastructure servers that provide conventional DNS, DHCP and NTP services. Other self-organizing services will provide email, instant messaging, storage, and content distribution in the absence of a server infrastructure, manual administration, high-capacity backbones or trusted entities. Our approach builds on foundations from p2p systems, but takes advantage of the hierarchical, proximity-based low overhead overlay structure provided by the buoy protocol to provide a solution suitable for ad hoc wireless environments.
Integrated ad hoc network architecture: The proposers plan to develop a network architecture that will integrate wired and wire-less networks, infrastructure-based, and self-organizing services. The architecture takes advantage of existing infrastructure when and where available, without depending on its presence. In the wake of a disaster, the architecture will allow remaining islands of surviving infrastructure to self-organize jointly with wireless, mobile components to recover and resume connectivity and emergency network services. Similarly, the architecture will allow the integration of islands of wired infrastructure via wireless ad hoc communication in developing countries.
The intellectual merits of this work include the development of the science and technology to meet these challenges; they will evaluate theoretical results, algorithms and protocols through analysis, simulation, and experimental evaluation of prototype implementations; disseminate the results via publications, industrial collaborations, and student training; and to distribute software artifacts for evaluation and use by industry and the research community.
The broader impacts of this work include the development of technologies that will substantially increase the
resilience of digital networks to physical disasters or attacks and that will extend its reach into economically disadvantaged parts of society and underdeveloped parts of the world. Educational impacts include the training of students and research personnel and outreach to educational institutions not historically involved in research.

This project aims to develop an adaptive sensor network architecture that enables the efficient, large-scale, long-term, low-cost, on-demand monitoring of a variety of physical phenomena with high fidelity. The core theme is that distributed signal processing and data assimilation of sensor data, as well as network management and monitoring, should be performed inside the sensor network in order to reduce energy consumption and global communication needs, leading to dramatically increased sensor lifetimes and much higher fidelity in the tracking of the physical phenomena of interest. The goal is to develop a flexible, self-monitoring architecture for this type of in-network processing and sensor networking that exploits adaptivity to significantly improve the network's efficiency, robustness, and usefulness. Two kinds of adaptivity are considered: (1) data adaptivity, where the network topology is adapted to align communications with the natural data flows; and (2) resource adaptivity, where the network topology is adapted based on computational, battery, or bandwidth resources. The expected results include the development of adaptive communication protocols and routing topology, the development of network management tools for sensor communication performance monitoring and inference, and for sensor distribution monitoring, as well as the experimental deployment of the adaptive sensor network architecture in a small-scale testbed of sensor nodes on the Rice University campus. Results will be disseminated through technical reports posted on the project web page, through papers presented at professional meetings, as well as through journal publications.