Rajesh Krishna Balan

Simplifying Cyber Foraging Degree Type: Ph.D. in Computer Science
Advisor(s): Mahadev Satyanarayanan
Graduated: August 2006

Abstract:

The rapid proliferation of mobile handheld computing devices, such as cellphones and PDAs, has led to an unfortunate conflict. On one hand, we have light mobile computing devices that can be carried anywhere. However, on the other hand, these devices are frequently unable to execute applications that are of highest value to a mobile user such as language translators and speech recognizers. One way to resolve this conflict is to use cyber foraging - utilize compute resources available in the environment to augment the capabilities of mobile devices.

A key challenge in enabling cyber foraging is that there exist many applications of high value to a mobile user that must be quickly, easily, and effectively retargeted to support cyber foraging. This retargeting is made more difficult as applications can be written in any programming language and style. In this thesis, quickly refers to the retargeting time, easily refers to the retargeting effort, and effectively refers to the retargeted application's runtime performance.

This dissertation shows that it is possible to quickly, easily, and effectively retarget computationally-intensive useful applications for cyber foraging. I developed a process called RapidRe that allows even novice developers to easily, quickly, and effectively retarget large unfamiliar applications for cyber foraging. To create RapidRe, I first developed a powerful remote execution system, called Chroma, that is able to achieve excellent application performance in mobile environments. Chroma uses the concept of tactics to greatly reduce its search space when deciding the optimal remote partitioning of applications. Tactics are enumerations of the useful application partitionings. At runtime, Chroma picks the tactics that would have the optimal performance for the given resource environment and user preferences.

I then developed a domain-specific language, called Vivendi, that allows developers to specify the adaptive characteristics of an application that are relevant for mobile computing. These characteristics include the parameters, fidelity variables, and tactics of the application. The parameters give hints about the expected application resource usage. These hints are used by Chroma to decide the optimal tactic. The fidelity variables are application settings that Chroma must set based on the available resources. Finally, tactics are described in two parts; the first part is the list of application procedures that can be remotely executed and the second is the possible ways to combine these procedures to do useful work.

RapidRe is language agnostic and consists of four steps. In step 1, application developers specify the adaptive characteristics of the application using Vivendi. In step 2, the stub generator processes this description and creates most of the interface code needed for the application to work with Chroma. In step 3,the developer inserts automatically generated API calls, created in step 2, into the application to create the client and server components of the applications. Finally, in step 4, the client and server components are compiled, together with the automatically generated code and the Chroma libraries, to create the final retargeted adaptive application.

I validated my dissertation in the following way. I first conducted an extensive user study that showed that novice developers can use RapidRe to quickly, easily, and effectively retarget large applications for cyber foraging. In particular, novice developers can retarget large, complex, and unfamiliar applications in under 4 hours with no knowledge of Chroma and minimal knowledge of the application. I also show that these novice-retargeted applications achieve comparable performance to expert-retargeted applications. I then present extensive runtime system measurements that show that these expert-retargeted applications can achieve excellent performance under various cyber foraging scenarios. Finally, I validated that RapidRe is versatile by performing all of the previous validations using a large and diverse set of computationally-intensive useful mobile applications.

Thesis Committee:
Mahadev Satyanarayanan (Chair)
David Garlan
Gregory Ganger
Srinivasan Seshan
Hari Balakrishnan (Massachusetts Institute of Technology)

Jeannette Wing, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science

Keywords:
Interactive applications, mobile computing, pervasive computing, ubiquitous computing, remote execution, software engineering, stub generation, user study, usability testing, operating system support