Design and implementation of a single system image operating system for ad hoc networks

ABSTRACT

In this paper, we describe the design and implementation of a distributed operating system for ad hoc networks. Our system simplifies the programming of ad hoc networks and extends total system lifetime by making the entire network appear as a single virtual machine. It automatically and transparently partitions applications into components and dynamically finds them a placement on nodes within the network to reduce energy consumption and to increase system longevity. This paper describes our programming model, outlines the design and implementation of our system and examines the energy efficiency of our approach through extensive simulations as well as validation of a deployment on a physical testbed. We evaluate practical, power-aware, general-purpose algorithms for component placement and migration, and demonstrate that they can significantly increase system longevity by effectively distributing energy consumption and avoiding hotspots.

REFERENCES

• 1: K. Amiri, D. Petrou, G. Ganger, and G. Gibson. Dynamic Function Placement in Active Storage Clusters. In Proc. of the USENIX Technical Conference, San Diego, CA, June 2000.
• 2: Manish Anand , Edmund B. Nightingale , Jason Flinn, Ghosts in the machine: interfaces for better power management, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990070]
• 3: O. Angin, A. Campbell, M. Kounavis, and R.-F. Liao. The Mobiware Toolkit: Programmable Support for Adaptive Mobile Networking. IEEE Personal Communications Magazine, Special Issue on Adapting to Network and Client Variability, August 1998.
• 4: Yariv Aridor , Michael Factor , Avi Teperman, cJVM: A Single System Image of a JVM on a Cluster, Proceedings of the 1999 International Conference on Parallel Processing, p.4, September 21-24, 1999
• 5: Rajesh Krishna Balan , Mahadev Satyanarayanan , So Young Park , Tadashi Okoshi, Tactics-based remote execution for mobile computing, Proceedings of the 1st international conference on Mobile systems, applications and services, p.273-286, May 05-08, 2003, San Francisco, California [doi>10.1145/1066116.1066125]
• 6: Athanassios Boulis , Chih-Chieh Han , Mani B. Srivastava, Design and implementation of a framework for efficient and programmable sensor networks, Proceedings of the 1st international conference on Mobile systems, applications and services, p.187-200, May 05-08, 2003, San Francisco, California [doi>10.1145/1066116.1066121]
• 7: Lawrence S. Brakmo , Deborah A. Wallach , Marc A. Viredaz, Sleep: a technique for reducing energy consumption in handheld devices, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990069]
• 8: Srijan Chakraborty , David K. Y. Yau , John C. S. Lui, On the effectiveness of movement prediction to reduce energy consumption in wireless communication, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 9: David Cheriton, The V distributed system, Communications of the ACM, v.31 n.3, p.314-333, March 1988 [doi>10.1145/42392.42400]
• 10: Michael D. Dahlin , Clifford J. Mather , Randolph Y. Wang , Thomas E. Anderson , David A. Patterson, A quantitative analysis of cache policies for scalable network file systems, Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.150-160, May 16-20, 1994, Nashville, Tennessee, United States
• 11: Fred Douglis , P. Krishnan , Brian N. Bershad, Adaptive Disk Spin-down Policies for Mobile Computers, Proceedings of the 2nd Symposium on Mobile and Location-Independent Computing, p.121-137, April 10-11, 1995
• 12: L. M. Feeney and M. Nilsson. Investigating the Energy Consumption of a Wireless Network Interface in an Ad Hoc Networking Environment. In Proc. of InfoCom, Anchorage, AK, April 2001.
• 13: Jason Flinn , Dushyanth Narayanan , M. Satyanarayanan, Self-Tuned Remote Execution for Pervasive Computing, Proceedings of the Eighth Workshop on Hot Topics in Operating Systems, p.61, May 20-22, 2001
• 14: Douglas P. Ghormley , David Petrou , Steven H. Rodrigues , Amin M. Vahdat , Thomas E. Anderson, GLUnix: a global layer Unix for a network of workstations, Software—Practice & Experience, v.28 n.9, p.929-961, July 25, 1998 [doi>10.1002/(SICI)1097-024X(19980725)28:9<929::AID-SPE183>3.0.CO;2-C]
• 15: David Kiyoshi Goldenberg , Jie Lin , A. Stephen Morse , Brad E. Rosen , Y. Richard Yang, Towards mobility as a network control primitive, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989481]
• 16: Conserving Transmission Power in Wireless Ad Hoc Networks, Proceedings of the Ninth International Conference on Network Protocols, p.24, November 11-14, 2001
• 17: D. Grunwald, P. Levis, K. I. Farkas, C. B. M. III, and M. Neufeld. Policies for Dynamic Clock Scheduling. In Proc. of OSDI, San Diego, CA, October 2000.
• 18: Selim Gurun , Chandra Krintz , Rich Wolski, NWSLite: a light-weight prediction utility for mobile devices, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990068]
• 19: John Heidemann , Fabio Silva , Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin , Deepak Ganesan, Building efficient wireless sensor networks with low-level naming, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 20: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.93-104, November 2000, Cambridge, Massachusetts, United States
• 21: B. Hinden and C. Partridge. Reliable Data Protocol (RDP), Version 2. In RFC 1151, IETF, April 1990.
• 22: Galen C. Hunt , Michael L. Scott, The Coign automatic distributed partitioning system, Proceedings of the third symposium on Operating systems design and implementation, p.187-200, February 1999, New Orleans, Louisiana, United States
• 23: A. D. Joseph , A. F. de Lespinasse , J. A. Tauber , D. K. Gifford , M. F. Kaashoek, Rover: a toolkit for mobile information access, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.156-171, December 03-06, 1995, Copper Mountain, Colorado, United States
• 24: Eric Jul , Henry Levy , Norman Hutchinson , Andrew Black, Fine-grained mobility in the Emerald system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.109-133, Feb. 1988 [doi>10.1145/35037.42182]
• 25: U. Kremer, J. Hicks, and J. Rehg. Compiler-directed Remote Task Execution for Power Management: A Case Study. In Proc. of COLP, Philadelphia, PA, October 2000.
• 26: T. Kunz , S. Omar, A mobile code toolkit for adaptive mobile applications, Proceedings of the Third IEEE Workshop on Mobile Computing Systems and Applications (WMCSA'00), p.60, December 07-08, 2000
• 27: Philip Levis , David Culler, Maté: a tiny virtual machine for sensor networks, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 28: Zhiyuan Li , Cheng Wang , Rong Xu, Computation offloading to save energy on handheld devices: a partition scheme, Proceedings of the 2001 international conference on Compilers, architecture, and synthesis for embedded systems, November 16-17, 2001, Atlanta, Georgia, USA [doi>10.1145/502217.502257]
• 29: B. Liskov, M. Day, and L. Shrira. Distributed Object Management in Thor. In Proc. of the Workshop on Distributed Object Management, pages 79--91, Edmonton, Canada, August 1992.
• 30: M. Litzkow, T. Tannenbaum, J. Basney, and M. Livny. Checkpoint and Migration of UNIX Processes in the Condor Distributed Processing System. Technical Report 1346, University of Wisconsin-Madison, April 1997.
• 31: Ting Liu , Christopher M. Sadler , Pei Zhang , Margaret Martonosi, Implementing software on resource-constrained mobile sensors: experiences with Impala and ZebraNet, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990095]
• 32: M. J. M. Ma, C.-L. Wang, F. C. M. Lau, and Z. Xu. JESSICA: Java-Enabled Single System Image Computing Architecture. In Proc. of PDPTA, Las Vegas, NV, June 1999.
• 33: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for Ad-Hoc sensor networks, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060303]
• 34: L. Norskog. Sox - Sound eXchange. http://sox.sourceforge.net/.
• 35: John K. Ousterhout , Andrew R. Cherenson , Frederick Douglis , Michael N. Nelson , Brent B. Welch, The Sprite Network Operating System, Computer, v.21 n.2, p.23-36, February 1988 [doi>10.1109/2.16]
• 36: Padmanabhan Pillai , Kang G. Shin, Real-time dynamic voltage scaling for low-power embedded operating systems, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 37: Gerald J. Popek , Bruce J. Walker, The LOCUS distributed system architecture, Massachusetts Institute of Technology, Cambridge, MA, 1986
• 38: G. J. Pottie , W. J. Kaiser, Wireless integrated network sensors, Communications of the ACM, v.43 n.5, p.51-58, May 2000 [doi>10.1145/332833.332838]
• 39: Richard F. Rashid , George G. Robertson, Accent: A communication oriented network operating system kernel, Proceedings of the eighth ACM symposium on Operating systems principles, p.64-75, December 14-16, 1981, Pacific Grove, California, United States
• 40: Takahiro Sakamoto , Tatsurou Sekiguchi , Akinori Yonezawa, Bytecode Transformation for Portable Thread Migration in Java, Proceedings of the Second International Symposium on Agent Systems and Applications and Fourth International Symposium on Mobile Agents, p.16-28, September 13-15, 2000
• 41: Tajana Simunic , Luca Benini , Peter Glynn , Giovanni De Micheli, Dynamic power management for portable systems, Proceedings of the 6th annual international conference on Mobile computing and networking, p.11-19, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345914]
• 42: Emin Gün Sirer , Robert Grimm , Arthur J. Gregory , Brian N. Bershad, Design and implementation of a distributed virtual machine for networked computers, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.202-216, December 12-15, 1999, Charleston, South Carolina, United States
• 43: Georg Stellner, CoCheck: Checkpointing and Process Migration for MPI, Proceedings of the 10th International Parallel Processing Symposium, p.526-531, April 15-19, 1996
• 44: M. Stemm and R. Katz. Measuring and Reducing Energy Consumption of Network Interfaces in Handheld Devices. In Proc. of MoMuc, Princeton, NJ, September 1996.
• 45: Takashi Suezawa, Persistent execution state of a Java virtual machine, Proceedings of the ACM 2000 conference on Java Grande, p.160-167, June 03-04, 2000, San Francisco, California, United States [doi>10.1145/337449.337536]
• 46: Eli Tilevich , Yannis Smaragdakis, J-Orchestra: Automatic Java Application Partitioning, Proceedings of the 16th European Conference on Object-Oriented Programming, p.178-204, June 10-14, 2002
• 47: C. Toh. Maximum Battery Life Routing to Support Ubiquitous Mobile Computing in Wireless Ad Hoc Networks. IEEE Communications, June 2001.
• 48: Eddy Truyen , Bert Robben , Bart Vanhaute , Tim Coninx , Wouter Joosen , Pierre Verbaeten, Portable Support for Transparent Thread Migration in Java, Proceedings of the Second International Symposium on Agent Systems and Applications and Fourth International Symposium on Mobile Agents, p.29-43, September 13-15, 2000
• 49: Kevin Walsh , Emin Gün Sirer, Staged simulation: A general technique for improving simulation scale and performance, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.14 n.2, p.170-195, April 2004 [doi>10.1145/985793.985797]
• 50: M. Welsh and G. Mainland. Programming Sensor Networks Using Abstract Regions. In Proc. of NSDI, San Francisco, CA, March 2004.
• 51: Kamin Whitehouse , Cory Sharp , Eric Brewer , David Culler, Hood: a neighborhood abstraction for sensor networks, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990079]
• 52: Stefanos Zachariadis , Licia Capra , Cecilia Mascolo , Wolfgang Emmerich, XMIDDLE: information sharing middleware for a mobile environment, Proceedings of the 24th International Conference on Software Engineering, May 19-25, 2002, Orlando, Florida [doi>10.1145/581339.581463]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Network operating systems

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.0 General

General Terms:
Design, Management