WINGs for the Internet

WINGS FOR THE INTERNET

The WINGs 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 was completed in 2000. Several technologies developed in WINGS served 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 is part of the UCSC School of Engineering.

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

Objective

Today’s internetwork technology has been extremely successful in linking huge numbers of computers and users; however, this technology is oriented toward computer interconnection in relatively stable operational environments, which cannot adequately support many of the emerging civilian and military uses and interconnection of networks. A multihop packet-radio network is an ideal technology to establish an “instant communication infrastructure” in disaster areas resulting from flood, earthquake, hurricane, or fire, support U.S. military doctrine, and extend the global communication infrastructure to the wireless mobile environment.

Achieving multimedia communication on the move and instant information infrastructures presents a challenge, because of the many differences between wireline and wireless networks, the characteristics of portable devices (e.g., power levels, size), and the dynamics of large mobile environments in the battlefield and urban areas.

To meet this challenge, UCSC and Rooftop designed, analyzed, implemented, and tested wireless internet gateways (WINGs) needed to enable the seamless marriage of distributed, dynamic, self-organizing, multihop wireless networks with the emerging multimedia Internet.

WINGs enables fundamentally new wireless network architectures in which not all network nodes must have the same capabilities but any network node can move with minimal detriment to network performance. To effectively tradeoff the small size and low-power requirements of hand-helds with the higher-power, long-range needs of the overall network, we targeted our development and demonstration efforts on a two-tier, mobile wireless architecture. Long-range WINGs, which are transportable and reside in vehicles, tents, or on roof tops, to be used to establish dynamic backbones, and short-range WINGs, which are low power and can be hand held, serve as the access points for mobile users.

Approach

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

  • Innovative packet-radio networking protocols and architectures designed top to bottom to guarantee service for multimedia traffic and to provide a seamless extension of the Internet.
  • A unique protocol development environment that provides a seamless transition of new network algorithms and protocols from simulations to the actual embedded radio platform.
  • Modular, high-speed, low-cost, commercial, spread-spectrum radio hardware.

WING protocols permit seamless interfacing between a WING-based network and the rest of the global communication infrastructure. The innovative WING protocols developed in this project include channel access protocols, link control protocols, and routing protocols.

Our development and demonstration tools and methodology of WINGs was based on:

  • A commercial spread-spectrum radio
  • Rooftop’s unique protocol development toolkit, which permits the same code used in simulations to be used as embedded software controlling the operation of the transceiver hardware.

Accomplishments

The WING prototypes were used and adopted by several other DARPA research groups in the GloMo program, including BBN.

The research work in this project resulted in 25 refereed papers published in journals and conferences, four Ph.D. theses, and two M.S. theses. All of these works are available on line at
http://www.soe.ucsc.edu/research/ccrg/publications.html The theses completed with support from this project are the following:

  1. Shree Murthy, “Routing in Packet-Switched Networks Using Path-Finding Algorithms,” Ph.D. thesis, Computer Engineering, University of California, Santa Cruz, CA 95064, Sept. 1996.
  2. Jyoti Raju, “Distributed Assignment of Codes in Multihop Radio Networks,” M.S. Thesis, Computer Science, University of California, Santa Cruz, CA 95064, June 1998.
  3. Christina Parsa, “Improving TCP Performance over Wireless Networks at the Link Layer,” M.S. Thesis, Computer Engineering, University of California, Santa Cruz, June 1998.
  4. Andrew Muir, “Channel Access Protocols based on Transmission Groups,” PhD Thesis, Computer Engineering, University of California, Santa Cruz, CA 95064, June 1998.
  5. Chane L. Fullmer, “Collision Avoidance Techniques for Packet-Radio Networks,” PhD Thesis, Computer Engineering, University of California, Santa Cruz, CA 95064, June 1998.
  6. Rodrigo Garces, “Collision Avoidance and Resolution Multiple Access,” PhD Thesis, Computer Engineering, University of California, Santa Cruz, CA 95064, March 1999.

The technical papers published describing the results of our research in this project are the following:

  1. D. Beyer, M.D. Vestrich, and J.J. Garcia-Luna-Aceves, “The Rooftop Community Network: Free, High-Speed Network Access for Communities,” The First One Hundred Feet: New Options for Internet and Broadband Access, Harvard Information Infrastructure Project, Arlington VA, October 1996.
  2. A. Muir and J.J. Garcia-Luna-Aceves, “Group Allocation Multiple Access in Single-Channel Wireless LANs,” Proc. Communication Networks and Distributed Systems Modeling and Simulation Conference, Phoenix, Arizona, 12–15 January 1997.
  3. A. Muir and J.J. Garcia-Luna-Aceves, “Supporting Real-Time Multimedia Traffic in a Wireless LAN,” Proc. SPIE Multimedia Computing and Networking 1997, San Jose, California, February 1997.
  4. R. Garces and J.J. Garcia-Luna-Aceves, “Collision Avoidance and Resolution Multiple Access with Transmission Groups,” Proc. IEEE INFOCOM ’97, Kobe, Japan, April 7–11, 1997.
    ( Selected for ACM WINET Issue on Best Papers from Infocom 97)
  5. A. Muir and J.J. Garcia-Luna-Aceves, “Group Allocation Multiple Access with Collision Detection,” Proc. IEEE INFOCOM ’97, Kobe, Japan, April 7–11, 1997.
  6. S. Murthy and J.J. Garcia-Luna-Aceves, “Loop-Free Internet Routing Using Hierarchical Routing Trees,” Proc. IEEE INFOCOM ’97, Kobe, Japan, April 7–11, 1997.
  7. C. Fullmer and J.J. Garcia-Luna-Aceves, “Complete Single-Channel Solutions to Hidden-Terminal Problems,” Proc. IEEE ICC ’97, Montreal, Canada, June 1997.
  8. R. Garces and J.J. Garcia-Luna-Aceves, “Collision Avoidance and Resolution Multiple Access: First-Success Protocols,” Proc. IEEE ICC ’97, Montreal, Canada, June 1997.
  9. C. Fullmer and J.J. Garcia-Luna-Aceves, “Solutions to Hidden-Terminal Problems in Wireless Networks,” Proc. ACM SIGCOMM ’97, Cannes, France, 14–18 September 1997.
  10. J.J. Garcia-Luna-Aceves, C. Fullmer, E. Madruga, D. Beyer, and T. Frivold, “Wireless Internet Gateways (WINGs),” Proc. IEEE MILCOM ’97, Monterey, California, November 1997.
  11. J.J. Garcia-Luna-Aceves and J. Raju, “Distributed Assignment of Codes for Multihop Packet-Radio Networks,” Proc. IEEE MILCOM ’97, Monterey, California, November 1997.
  12. R. Garces and J.J. Garcia-Luna-Aceves, “A Near-Optimum Channel Access Protocol Based on Incremental Collision Resolution and Distributed Transmission Queues,” Proc. IEEE INFOCOM ’98, San Francisco, California, March 29–April 2, 1998.
  13. A. Muir and J.J. Garcia-Luna-Aceves, “A Channel Access Protocol for Multihop Wireless Networks with Multiple Channels,” Proc. IEEE ICC ’98, Atlanta, Georgia, June 7–11, 1998.
  14. J.J. Garcia-Luna-Aceves and C. Fullmer, “Performance of Floor Acquisition Multiple Access in Ad-Hoc Networks,” Proc. IEEE ISCC’98: Third IEEE Symposium on Computers and Communications, Athens, Greece, June 30–July 2, 1998.
  15. R. Garces, J.J. Garcia-Luna-Aceves, and R. Rom, “ An Access Etiquette for Very-Wide Wireless Bands,” Proc. IEEE IC3N ’98: Seventh International Conference on Computer Communications and Networks, Lafayette, Louisiana, October 12–15, 1998.
  16. A. Muir and J.J. Garcia-Luna-Aceves, “An Efficient Packet-Sensing MAC Protocol for Wireless Networks,” ACM Journal on Mobile Networks and Applications, Vol.~3, No.~2, pp.~221–234, 1998.
  17. R. Garces and J.J. Garcia-Luna-Aceves, “Collision Avoidance and Resolution Multiple Access,” Cluster Computing (Baltzer Sci. Pub.), Vol.~1, pp.~197–212, 1998.
  18. S. Murthy and J.J. Garcia-Luna-Aceves, “A Routing Architecture for Mobile Integrated Services Networks,” ACM Mobile Networks and Applications Journal, Special Issue on Mobile Networking in The Internet, Vol.~3, No.~4, pp.~391–407, 1998.
  19. S. Murthy and J.J. Garcia-Luna-Aceves, “A “A Loop-Free Routing Protocol for Large-Scale Internets Using Distance Vectors,” Computer Communications, Vol.~21, No.~2, 1998, pp.~147–161.
  20. R. Garces and J.J. Garcia-Luna-Aceves, “Collision Avoidance and Resolution Multiple Access with Transmission Queues,” ACM Wireless Networks Journal, Special Issue on Selected Papers from INFOCOM 97, Vol.~5, No.~2, pp.~95–109, March 1999.
  21. C. Parsa and J.J. Garcia-Luna-Aceves, “TULIP: A Link-Level Protocol for Improving TCP over Wireless Links,” Proc. IEEE Wireless Communications and Networking Conference 1999 (WCNC 99), New Orleans, Louisiana, September 21–24, 1999.
  22. J.J. Garcia-Luna-Aceves and C. Fullmer, “Floor Acquisition Multiple Access (FAMA) in Single-Channel Wireless Networks,” ACM Mobile Networks and Applications Journal, special issue on Ad-Hoc Networks, Vol. 4, 1999, pp. 157-174.
  23. R. Garces and J.J. Garcia-Luna-Aceves, “Collision Avoidance and Resolution Multiple Access for Multichannel Wireless Networks,” Proc. Infocom 2000, Tel-Aviv, Israel, March 26–30, 2000.
  24. R. Garces, J.J. Garcia-Luna-Aceves, and R. Rom, “An Access Etiquette for Very-Wide Wireless Bands,” Computer Communications, Elsevier, 2000.
  25. C. Parsa and J.J. Garcia-Luna-Aceves, “Improving TCP Performance over Wireless Networks at The Link Layer,” ACM Mobile Networks and Applications Journal, Special Issue on Mobile Data Networks: Advanced Technologies and Services, Vol. 5, No. 1, 2000, pp. 57-71.

The accomplishments in this project were:

  • WING software, prototypes and demonstrations.
  • Novel protocols for channel access in multihop packet-radio networks.
  • Link-level control techniques to improve the performance of unmodified transport-level protocols across wireless networks.
  • Routing protocols for multihop packet-radio networks.

Within nine months of the start of the project, the initial WINGs prototype systems (the WING I) were completed and demonstrated at the GloMo Conference at Lake Tahoe in July, 1996.

Since then, the WING I’s were used in a number of other demonstrations around the country. The WING I used the 900MHz, 258-kbps, 4-Msps, direct-sequence spreading LongRanger digital radio modem by Utilicom Inc., and a 25 MHz, 68360-based microcontroller board by Atlas Computer Inc. with 4 MBytes of RAM and 1 MByte of Flash ROM. An embedded, CPT platform wrapper and a set of device drivers were written for the WING I so that all WING protocol software, and CPT libraries above the wrapper, could be seamlessly transitioned between the CPT simulation environment and the WING I.

The Open Internet Radio API’s developed in the WINGS project included:

  1. D.Beyer, T.Frivold, and D.Lancaster of Rooftop Communications, and M.Lewis of SRI International, “Radio Device API.” Evolving GloMo Radio API specification, September 1, 1997.
  2. D.Beyer, “Physical Radio Interface.”  Evolving GloMo Radio API specification, July 1, 1997.
  3. T.Frivold, D.Beyer, B.Nguyen, “Generic Device Driver Programmer’s Guide.”  Rooftop Communications Technical Note.  September 1, 1997.
  4. D.Beyer and M. Lewis, “Simple Example Code for Radio Device API.”
  5. D.Beyer, T.Frivold, “Wireless Internet Gateway (WING) I: Advanced User’s Manual.” Rooftop Technical Report,  October, 1996.

Our final report summarizes key results in the WINGS project.