NWSLite: a light-weight prediction utility for mobile devices

ABSTRACT

Computation off-loading, i.e., remote execution, has been shown to be effective for extending the computational power and battery life of resource-restricted devices, e.g., hand-held, wearable, and pervasive computers. Remote execution systems must predict the cost of executing both locally and remotely to determine when off-loading will be most beneficial. These costs however, are dependent upon the execution behavior of the task being considered and the highly-variable performance of the underlying resources, e.g., CPU (local and remote), bandwidth, and network latency. As such, remote execution systems must employ sophisticated, prediction techniques that accurately guide computation off-loading. Moreover, these techniques must be efficient, i.e., they cannot consume significant resources, e.g., energy, execution time, etc., since they are performed on the mobile device.In this paper, we present NWSLite, a computationally efficient, highly accurate prediction utility for mobile devices. NWSLite is an extension to the Network Weather Service (NWS), a dynamic forecasting toolkit for adaptive scheduling of high-performance Computational Grid applications. We significantly scaled down the NWS to reduce its resource consumption yet still achieve accuracy that exceeds that of extant remote execution prediction methods. We empirically analyze and compare both the prediction accuracy and the cost of NWSLite and a number of different forecasting methods from existing remote execution systems. We evaluate the efficacy of the different methods using a wide range of mobile applications and resources.

REFERENCES

• 1: Anand Balachandran , Geoffrey M. Voelker , Paramvir Bahl , P. Venkat Rangan, Characterizing user behavior and network performance in a public wireless LAN, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 2: 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]
• 3: Fran Berman , Geoffrey Fox , Anthony J. G. Hey , Tony Hey, Grid Computing: Making the Global Infrastructure a Reality, John Wiley & Sons, Inc., New York, NY, 2003
• 4: Francine D. Berman , Rich Wolski , Silvia Figueira , Jennifer Schopf , Gary Shao, Application-level scheduling on distributed heterogeneous networks, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.39-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States [doi>10.1145/369028.369109]
• 5: G. Bottomley and S. Alexander. A novel approach for stabilizing recursive least squares filters. IEEE Transactions on Signal Processing, 39, 1991.
• 6: D. Burger and T. Austin. The simplescalar tool set, version 2.0. Technical Report 1342, UW Madison Computer Sciences, June 1997.
• 7: Compaq Computer Corporation. iPAQ Pocket PC. http://www.compaq.com/products/handhelds/pocketpc/.
• 8: 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
• 9: Jason Flinn , SoYoung Park , M. Satyanarayanan, Balancing Performance, Energy, and Quality in Pervasive Computing, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.217, July 02-05, 2002
• 10: Jason Flinn , M. Satyanarayanan, Energy-aware adaptation for mobile applications, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.48-63, December 12-15, 1999, Charleston, South Carolina, United States
• 11: Ian Foster , Carl Kesselman, The grid: blueprint for a new computing infrastructure, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 12: GLVU source code and documentation, Feb 2002. http://www.cs.unc.edu/walk/software/glvu/.
• 13: The grid application development software project (GrADS). http://hipersoft.cs.rice.edu/grads/.
• 14: S. Gurun, C. Krintz, and R. Wolski. Efficient Prediction. Technical Report 2003-34, University of California, Santa Barbara, 2003.
• 15: Minkyong Kim , Brian Noble, Mobile network estimation, Proceedings of the 7th annual international conference on Mobile computing and networking, p.298-309, July 2001, Rome, Italy [doi>10.1145/381677.381705]
• 16: U. Kremer, J.Hicks, and J.M.Rehg. A compilation framework for power and energy management on mobile computers. In International Workshop on Languages and Compilers for Parallel Computing (LCPC'01), August 2001.
• 17: Chandra Krintz, Coupling on-line and off-line profile information to improve program performance, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 18: Chandra Krintz , Brad Calder, Using annotations to reduce dynamic optimization time, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.156-167, June 2001, Snowbird, Utah, United States
• 19: Dushyanth Narayanan , M. Satyanarayanan, Operating system support for mobile interactive applications, 2002
• 20: Dushyanth Narayanan and M. Satyanarayanan. Predictive resource management for wearable computing. In International Conference on Mobile Systems, Applications, and Services, 2003.
• 21: Brian D. Noble , M. Satyanarayanan , Dushyanth Narayanan , James Eric Tilton , Jason Flinn , Kevin R. Walker, Agile application-aware adaptation for mobility, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.276-287, October 05-08, 1997, Saint Malo, France
• 22: The Network Weather Service Home page -- http://nws.cs.ucsb.edu.
• 23: Alexey Rudenko , Peter Reiher , Gerald J. Popek , Geoffrey H. Kuenning, The remote processing framework for portable computer power saving, Proceedings of the 1999 ACM symposium on Applied computing, p.365-372, February 28-March 02, 1999, San Antonio, Texas, United States [doi>10.1145/298151.298385]
• 24: Alexey Rudenko , Peter Reiher , Gerald J. Popek , Geoffrey H. Kuenning, Saving portable computer battery power through remote process execution, ACM SIGMOBILE Mobile Computing and Communications Review, v.2 n.1, p.19-26, January 1998 [doi>10.1145/584007.584008]
• 25: Wireless LAN Traces from ACM SIGCOMM'01. http://ramp.ucsd.edu/pawn/sigcomm-trace/.
• 26: Michael D. Smith, Overcoming the challenges to feedback-directed optimization (Keynote Talk), Proceedings of the ACM SIGPLAN workshop on Dynamic and adaptive compilation and optimization, p.1-11, January 2000
• 27: João Pedro Sousa , David Garlan, Aura: an Architectural Framework for User Mobility in Ubiquitous Computing Environments, Proceedings of the IFIP 17th World Computer Congress - TC2 Stream / 3rd IEEE/IFIP Conference on Software Architecture: System Design, Development and Maintenance, p.29-43, August 25-30, 2002
• 28: N. Spring and R. Wolski. Application level scheduling: Gene sequence library comparison. In Proceedings of ACM International Conference on Supercomputing, July 1998.
• 29: Sezgin Sucu , Chandra Krintz, ACE: A Resource-Aware Adaptive Compression Environment, Proceedings of the International Conference on Information Technology: Computers and Communications, p.183, April 28-30, 2003
• 30: Martin Swany , Rich Wolski, Representing Dynamic Performance Information in Grid Environments with the Network Weather Service, Proceedings of the 2nd IEEE/ACM International Symposium on Cluster Computing and the Grid, p.48, May 21-24, 2002
• 31: A. J. Willmott. Radiator source code and online documentation, Oct 1999. http://www.cs.cmu.edu/ ajw/software/.
• 32: Rich Wolski, Dynamically forecasting network performance using the Network Weather Service, Cluster Computing, v.1 n.1, p.119-132, 1998 [doi>10.1023/A:1019025230054]
• 33: Rich Wolski , Neil T. Spring , Jim Hayes, The network weather service: a distributed resource performance forecasting service for metacomputing, Future Generation Computer Systems, v.15 n.5-6, p.757-768, Oct. 1999 [doi>10.1016/S0167-739X(99)00025-4]
• 34: Peter Young, Recursive estimation and time-series analysis: an introduction, Springer-Verlag New York, Inc., New York, NY, 1984
• 35: 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]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Modeling and prediction

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Measurements

General Terms:
Measurement, Performance

Keywords:
CPU availability estimation, fidelity, network performance estimation, prediction, remote execution, resource-restricted devices