SPARROW

SPARROW: SECURE PROTOCOLS FOR ADAPTIVE, ROBUST, RELIABLE, and OPPORTUNISTIC WINGs

The SPARROW project was funded by DARPA / ITO at the University of California, Santa Cruz (UCSC) and Rooftop Communications Corporation (Rooftop) of Mountain View, California. The project completed in 2002. Technologies developed in SPARROW helped the development of the NOKIA Wireless Routers after NOKIA acquired Rooftop in 1999.

This project was part of the DARPA Global Mobile (GloMo) program.

At UCSC, this project was part of the research carried out at the Computer Communication Research Group (CCRG) of the Computer Engineering Department, which was part of the UCSC Baskin School of Engineering.

The principal investigators of this project were J.J. Garcia-Luna-Aceves (UCSC) and David Beyer (Rooftop).

Objective

The Wireless Internet Gateways for Internets ( WINGS) project introduced and demonstrated dramatic improvements in both the core network technology needed for Global Mobile Information systems, as well as in the way that this technology is developed, fielded, and then further advanced. SPARROW built on the WINGS results to provide novel secure protocols for adaptive, robust, reliable, and opportunistic WINGs supporting integrated mobile information systems.

Approach

Our approach consisted of advancing the state of the art in the following thre areas:

  • The method of approach in SPARROW extended the state of the art in the following three areas:
  • Secure Protocols for Adaptive, Robust, Reliable, and Opportunistic WINGs (SPARROW): New protocols were developed for multihop packet-radio networks and integrated end-to-end networking. Secure protocols were designed for exchanging control information (e.g., routing) that can protect nodes even against compromised WINGs and aid in the detection of intrusions. Protocols were designed to provide “the best-match of quality for user and system applications at any time” given their service requirements and the potential capacity of the network, which may affected by nodes moving at high speeds, large numbers of nodes and users involved in many-to-many dialogues, and the varying accuracy and latency of control information. Protocols were designed for opportunistic environmental awareness and multimodal operation that (a) use knowledge of the location of WINGs, time, channel characteristics, and threats, to predict and to react to network conditions to support QoS requirements dynamically; and (b) use multiple codes, frequencies, power levels, antenna directionality, and switching modalities, to effect adaption to detected or predicted network changes and threats more effectively than existing packet-radio protocols can.
  • The capabilities of the C++ Protocol Toolkit (CPT) was augmented to permit geographically dispersed users to control and visualize hybrid simulations involving real and simulated WINGs. This tool set allowed the testing of WING hardware prototypes as part of simulated large-scale networks. The tool set facilitated remote monitoring and troubleshooting of WINGs, and allow the GloMo community to use WING testbeds remotely.
  • Configurable, location-aware WING prototypes were developed, whose exact configuration can be tailored for the rapid prototyping of different protocols, capabilities, and applications. The new WING platforms include a “metanet WING” running on FreeBSD for interconnection with DARTNET and other wireless and wired networks. The Metanet WINGs were based on an open routing architecture built on gated running under FreeBSD, a new link API that was developed to facilitate interoperability between protocols and radios already equipped with link and MAC protocols implemented in firmware, and new drivers for commercial radios as neededemacs .

Recent Accomplishments

The RIMA (Receiver Initiated Multiple Access) protocol was designed. Most prior medium access control (MAC) protocols aimed at avoiding collisions of data packets in networks with hidden terminals are sender-initiated, in that the sender transmits a short request to send (RTS) asking the receiver for permission to transmit. In contrast, in RIMA, the receiver polls its neighbors with a short ready-to-receive (RTR) packet; neighbors then send a short RTS to allow the receiver to jam the channel if there are RTS collisions, and a successful sender transmits a data packet if there is no receiver jamming. The primary objective of a receiver-initiated MAC protocol is to account for the on-off operation of untethered nodes that need to preserve battery life. An analytical model has been used to prove that RIMA provides similar or better throughput than prior MAC protocols for ad-hoc networks in the presence of hidden terminals.

A new multichannel MAC protocol called Hop Reservation Multiple Access (HRMA) for wireless ad-hoc networks was designed and analyzed. HRMA is based on very-slow frequency-hopping spread spectrum (FHSS) and takes advantage of the time synchronization necessary for frequency hopping. HRMA allows a pair of communicating nodes to reserve a frequency hop (channel) using a reservation and handshake mechanism on every frequency hop that guarantee collision-free data transmission in the presence of hidden terminals. HRMA provides a baseline to offer QoS in ad-hoc networks based on simple half-duplex slow FHSS radios. The throughput achieved in HRMA was analyzed for the case of a hypercube network topology assuming variable-length packets, and compare it against the multichannel slotted ALOHA protocol generalized from those used as part of some previous commercial ad-hoc networks based on spread spectrum radios, such as Metricom’s Ricochet system. The numerical results show that HRMA can achieve much higher throughput than multichannel slotted ALOHA within the traffic-load ranges of interest, especially when the average packet length is large compared to the duration of a dwell time in the frequency hopping sequence, in which case the maximum throughput of HRMA is close to the maximum possible value.

The adaptive link-state protocol (ALP) was designed, implemented, and demonstrated at the GloMo PI meeting in February 98. ALP was implemented in gated and was demonstrated using PCs running FreeBSD as the operating system. A gated-to-CPT wrapper was completed to allow the exact same code to run in CPT simulations and the WING prototypes. ALP is the first link-state protocol that is well suited for ad-hoc networks with dynamic topologies, because it does not require the state of each link to be flooded to the entire network, or to entire areas if hierarchical routing is used. A router in ALP disseminates link-state updates incrementally to its neighbors for only those links along paths used to reach destinations. Link-state updates are validated using time stamps and contain the same information used in traditional link-state protocols. Simulation experiments were carried out and the results indicate that ALP is as efficient as the Distributed-Bellman Ford algorithm when distances to destinations do not increase and resources do not fail, and more efficient than traditional link-state protocols after distances increase or resources fail. This indicates that ALP performs as well as any prior routing algorithm reported to date.

The design of the Core-Assisted Mesh Protocol (CAMP) was completed. CAMP supports multicast routing in dynamic ad-hoc networks. CAMP generalizes the notion of core-based trees introduced for internet multicasting into multicast meshes that have much richer connectivity than trees. A shared multicast mesh is defined for each multicast group; the main goal of using such meshes is to maintain the connectivity of multicast groups even while network routers move frequently. CAMP consists of the maintenance of multicast meshes and loop-free packet forwarding over such meshes. CAMP guarantees that, within a finite time, every receiver of a multicast group is connected to every source of the group. Multicast packets for a group are forwarded along the shortest paths from sources to receivers defined within the group’s mesh. CAMP uses cores only to limit the traffic needed for a router to join a multicast group; the failure of cores does not stop packet forwarding or the process of maintaining the multicast meshes. Simulation experiments were carried out to compare CAMP’s performance against the performance of tree-based multicast routing protocols; the results indicate that CAMP always provide shorter average delays than tree-based multicast routing protocols. CAMP is more survivable than tree-based protocols, because CAMP can use multiple cores and the failure of a given link does not stop the flow of multicast packets.

The specification of a Slave MAC and Master MAC protocols was provided to USC-ISI and a couple of iterations on the specification were made in collaboration with ISI and SRI. This architecture allows the most time-critical operations to be done as close to the RF section as possible, while still supporting sophisticated, random-access-style channel scheduling protocols to be performed in software or firmware on a flexible CPU. The GloMo Radio API has been extended to handle the new primitives needed for MAC-on-MAC-capable radios.

Voice encoding/decoding boards were integrated into the WING prototypes. Real-time voice has been demonstrated successfully over a multihop WINGs network. These enhanced WING prototypes were used as an applications driver for improved QoS protocols to be developed in SPARROW, as well as to permit real-time voice demonstrations, such as at the upcoming July 98 GloMo PI meeting.

Technology Transition

We collaborated with Raytheon to transition SPARROW technology to the ASPEN project and a SUO system integration project.

Publications

  1. J.J. Garcia-Luna-Aceves and A. Tzamaloukas, “Reversing The Collision-Avoidance Handshake in Wireless Networks “, Proc. IEEE/ACM Mobicom 99, Seattle, Washington, August 15–20, 1999.
  2. A. Tzamaloukas and J.J.~Garcia-Luna-Aceves, “Poll-before-Data Multiple Access”, Proc. IEEE ICC ’99, Vancouver, Canada, June 6–10, 1999.
  3. Z. Tang and J.J. Garcia-Luna-Aceves, “Hop-Reservation Multiple Access (HRMA) for Ad-Hoc Networks”, Proc. IEEE INFOCOM ’99, New York, New York, March 21–25, 1999.
  4. Z. Tang and J.J. Garcia-Luna-Aceves, “Hop-Reservation Multiple Access (HRMA) for Multichannel Packet Radio Networks”, Proc. IEEE IC3N ’98: Seventh International Conference on Computer Communications and Networks, Lafayette, Louisiana, October 12-15, 1998.
  5. J.J. Garcia-Luna-Aceves and M. Spohn, “Scalable Link-State Internet Routing”, Proc. IEEE International Conference on Network Protocols (ICNP 98), Austin, Texas, October 14-16, 1998.
  6. J.J. Garcia-Luna-Aceves and E.L. Madruga, “The Core Assisted Mesh Protocol”, accepted for publication in IEEE Journal on Selected Areas in Communications, Special Issue on Ad-Hoc Networks, 1999.
  7. E.L. Madruga and J.J. Garcia-Luna-Aceves, “Multicasting along Meshes in Ad-Hoc Networks”, Proc. IEEE ICC ’99, Vancouver, Canada, June 6–10, 1999.
  8. J.J. Garcia-Luna-Aceves and E.L. Madruga, “A Multicast Routing Protocol for Ad-Hoc Networks”, Proc. IEEE INFOCOM ’99, New York, New York, March 21–25, 1999.