Mobile Computing with the Rover Toolkit by Anthony Douglas Joseph Submitted to the Department of Electrical Engineering and Computer Science in partial fulfillment of the requirements for the degree of Doctor of Philosophy at the MASSACHUSETTS INSTITUTE OF TECHNOLOGY November 1997 (cid:1)c Massachusetts Institute of Technology 1997. All rights reserved. Author .............................................................. Department of Electrical Engineering and Computer Science November 26, 1997 Certified by.......................................................... M. Frans Kaashoek Associate Professor Thesis Supervisor Accepted by......................................................... Arthur C. Smith Chairman, Departmental Committee on Graduate Students Mobile Computing with the Rover Toolkit by Anthony Douglas Joseph Submitted to the Department of Electrical Engineering and Computer Science on November 26, 1997, in partial fulfillment of the requirements for the degree of Doctor of Philosophy Abstract Rover is one of the first architectures that supports the construction of both mobile- adaptive applicationsandmobile-adaptive proxiesformobile-transparent applications. To excel in the harsh conditions of a mobile environment, mobile-adaptive applica- tions are aware of and take an active part in adapting to those conditions. The mobile-transparent approach is appealing because it allows applications to be run without alteration. The contributions of this thesis include the Rover architecture and a reference implementation, the Rover Toolkit. Together, the architecture and toolkit support a set of programming and communication abstractions that enable and simplify the construction of both mobile-adaptive proxies for mobile-transparent applications and new mobile-adaptive applications. The programming abstractions include Relocatable Dynamic Objects, a form of code- and data-shipping, along with remote invocation and method logging, that allows mobile-adaptive applications to dynamically adapt to environmental changes, and programming language extensions for reliable execution of applications at servers. The communication abstractions are based uponQueued Remote Procedure Call,a formof remoteinvocation thatprovides asynchronous, reliable delivery of requests and results. Using the Rover abstractions, applications obtain increased availability, concurrency, resource allocation efficiency, code reuse, fault tolerance, data consistency, application adaptation to environmen- tal changes, and more efficient scheduling and utilization of communication channels. Experimentalevaluationofasuiteofmobileapplicationsbuiltwiththetoolkitdemon- strates that such application-level control can be obtained with relatively little pro- gramming overhead and allows correct operation, increases interactive performance, and reduces network utilization under intermittently connected conditions. Thesis Supervisor: M. Frans Kaashoek Title: Associate Professor Mobile Computing with the Rover Toolkit by Anthony Douglas Joseph Submitted to the Department of Electrical Engineering and Computer Science on November 26, 1997, in partial fulfillment of the requirements for the degree of Doctor of Philosophy Abstract Rover is one of the first architectures that supports the construction of both mobile- adaptive applicationsandmobile-adaptive proxiesformobile-transparent applications. To excel in the harsh conditions of a mobile environment, mobile-adaptive applica- tions are aware of and take an active part in adapting to those conditions. The mobile-transparent approach is appealing because it allows applications to be run without alteration. The contributions of this thesis include the Rover architecture and a reference implementation, the Rover Toolkit. Together, the architecture and toolkit support a set of programming and communication abstractions that enable and simplify the construction of both mobile-adaptive proxies for mobile-transparent applications and new mobile-adaptive applications. The programming abstractions include Relocatable Dynamic Objects, a form of code- and data-shipping, along with remote invocation and method logging, that allows mobile-adaptive applications to dynamically adapt to environmental changes, and programming language extensions for reliable execution of applications at servers. The communication abstractions are based uponQueued Remote Procedure Call,a formof remoteinvocation thatprovides asynchronous, reliable delivery of requests and results. Using the Rover abstractions, applications obtain increased availability, concurrency, resource allocation efficiency, code reuse, fault tolerance, data consistency, application adaptation to environmen- tal changes, and more efficient scheduling and utilization of communication channels. Experimentalevaluationofasuiteofmobileapplicationsbuiltwiththetoolkitdemon- strates that such application-level control can be obtained with relatively little pro- gramming overhead and allows correct operation, increases interactive performance, and reduces network utilization under intermittently connected conditions. Thesis Supervisor: M. Frans Kaashoek Title: Associate Professor Acknowledgments This thesis is the result of a long arduous trip through graduate school. Along the way, many people have made the trip more enjoyable and pleasant. I owe a special debt of gratitude to Kim Nelson for helping me get through graduate school and for putting up with all the nights and weekends I spent in the lab. Special thanks to Frans Kaashoek for providing me with guidance, support, and encouragement. Frans is a great advisor and a fun, exciting person to work with. John Guttag also deserves thanks for mentoring me over the years. I thank him for the guidance he has given me, especially when I was changing research groups and during my search for a job. I thank David Gifford for his efforts during the design stages of the Rover toolkit, in particular his ideas for the semantics of QRPC. I thank my parents for the motivation they instilled in me, for all the support they have provided, and for their faith in me. I owe a lot of thanks to the rest of the Rover project team: Joshua Tauber, George Candea, Constantine Cristakos, Alan F. deLespinasse, and Michael Shurpik. Special thanksgotoJoshforallthegreatdesignarguments/discussions wesharedthathelped shape the Rover architecture and for his help in building and debugging applications. I thank the Parallel and Distributed Operating Systems group for reading many drafts of the papers behind this thesis (thanks Massimiliano Poletto, Eddie Kohler, and Greg Ganger) and for providing me with a fun, exciting, and sometimes loud (thanks David Mazieres and Emmett Witchel), research environment. Thanks also to Neena Lyall for making the administrative side of the project much more pleasant. Thanks go to my roommates (Dave Gardner, Sanjay Ghemawat, and Parry Hus- bands) for tolerating my equipment (and other) messes and being great roommates. Finally,Ithankmysponsors forproviding theresources usedby theRover project. This work was supported in part by the Defense Advanced Research Projects Agency under contract DABT63-95-C-005, by an NSF National Young Investigator Award, by an Intel Graduate Fellowship, and by grants from Intel, IBM and AT&T. Contents 1 Introduction 13 1.1 Mobile versus Stationary Environment . . . . . . . . . . . . . . . . . 15 1.2 Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.3 Rover: A Toolkit-based Approach . . . . . . . . . . . . . . . . . . . . 19 1.4 Building and Using Mobile Applications . . . . . . . . . . . . . . . . 21 1.5 Arguments for Mobile-Adaptive Computing . . . . . . . . . . . . . . 23 1.6 Contributions and Results . . . . . . . . . . . . . . . . . . . . . . . . 24 1.7 Outline of the thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2 Related Work 28 2.1 Relocatable Dynamic Objects . . . . . . . . . . . . . . . . . . . . . . 28 2.2 Queued Remote Procedure Call . . . . . . . . . . . . . . . . . . . . . 30 2.3 Mobile-Transparent File Systems . . . . . . . . . . . . . . . . . . . . 31 2.4 Mobile-Adaptive Applications . . . . . . . . . . . . . . . . . . . . . . 32 2.5 Reliable Execution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3 Design of the Rover Toolkit 36 3.1 Design Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.1.1 Why Use a Toolkit? . . . . . . . . . . . . . . . . . . . . . . . 37 3.1.2 Failures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.1.3 Mobile Environment Problems Addressed by Rover . . . . . . 39 3.1.4 The Synergy Between the Solutions . . . . . . . . . . . . . . . 43 3.2 Relocatable Dynamic Objects . . . . . . . . . . . . . . . . . . . . . . 43 5 3.2.1 RDO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.2.2 Using RDOs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.2.3 The Reliable Execution of RDOs at Servers . . . . . . . . . . 51 3.2.4 Using RDOs for Computation Relocation . . . . . . . . . . . . 53 3.2.5 The Safe Execution of RDOs . . . . . . . . . . . . . . . . . . 53 3.3 Queued Remote Procedure Call . . . . . . . . . . . . . . . . . . . . . 55 3.3.1 QRPC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.3.2 Using QRPC . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.3.3 QRPC Failure Recovery . . . . . . . . . . . . . . . . . . . . . 58 3.3.4 Client Communication Scheduling . . . . . . . . . . . . . . . . 61 3.4 RDO Replication and Consistency . . . . . . . . . . . . . . . . . . . . 65 3.4.1 Replication . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.4.2 Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.5 Mobile-Adaptive Application Support . . . . . . . . . . . . . . . . . . 71 3.6 Design Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 4 Implementation of the Rover Toolkit 74 4.1 Implementation Overview . . . . . . . . . . . . . . . . . . . . . . . . 74 4.2 Client-side Implementation . . . . . . . . . . . . . . . . . . . . . . . . 76 4.2.1 Access Manager . . . . . . . . . . . . . . . . . . . . . . . . . . 76 4.2.2 Persistent RDO Cache . . . . . . . . . . . . . . . . . . . . . . 77 4.2.3 Stable QRPC Log . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.2.4 Network Scheduler . . . . . . . . . . . . . . . . . . . . . . . . 79 4.3 Server-side Implementation . . . . . . . . . . . . . . . . . . . . . . . . 81 4.3.1 Access Manager . . . . . . . . . . . . . . . . . . . . . . . . . . 82 4.3.2 Network Scheduler . . . . . . . . . . . . . . . . . . . . . . . . 83 4.3.3 Stable QRPC Log . . . . . . . . . . . . . . . . . . . . . . . . . 84 4.4 Implementation Summary . . . . . . . . . . . . . . . . . . . . . . . . 88 5 Applications Using Rover 89 5.1 Using Objects Instead of Files . . . . . . . . . . . . . . . . . . . . . . 89 6 5.2 Toolkit Programming Interface . . . . . . . . . . . . . . . . . . . . . 92 5.3 Rover Application Suite . . . . . . . . . . . . . . . . . . . . . . . . . 93 5.3.1 Proxies for Mobile-Transparent Applications . . . . . . . . . . 95 5.3.2 Mobile-Adaptive Applications . . . . . . . . . . . . . . . . . . 99 5.3.3 Developing Reliable Applications . . . . . . . . . . . . . . . . 100 5.3.4 Stock Market Tracker . . . . . . . . . . . . . . . . . . . . . . . 101 5.3.5 Rover Web Browser proxy . . . . . . . . . . . . . . . . . . . . 102 5.3.6 Text file search . . . . . . . . . . . . . . . . . . . . . . . . . . 102 5.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 6 Experiments 106 6.1 Experimental Environment and Methodology . . . . . . . . . . . . . . 107 6.2 Null QRPC Performance . . . . . . . . . . . . . . . . . . . . . . . . . 108 6.2.1 QRPC Client Costs . . . . . . . . . . . . . . . . . . . . . . . . 111 6.2.2 QRPC Compression Costs . . . . . . . . . . . . . . . . . . . . 111 6.2.3 QRPC Transport Cost . . . . . . . . . . . . . . . . . . . . . . 111 6.2.4 QRPC Stable Logging Cost . . . . . . . . . . . . . . . . . . . 113 6.2.5 QRPC Server Costs . . . . . . . . . . . . . . . . . . . . . . . . 114 6.3 Discussion of QRPC Costs . . . . . . . . . . . . . . . . . . . . . . . . 115 6.4 QRPC Batching and Compression . . . . . . . . . . . . . . . . . . . . 116 6.5 Mobile-Transparent Application Performance . . . . . . . . . . . . . . 121 6.5.1 Rover File System Proxy . . . . . . . . . . . . . . . . . . . . . 124 6.6 Mobile-Adaptive Application Performance . . . . . . . . . . . . . . . 125 6.7 Fault-Tolerant Applications . . . . . . . . . . . . . . . . . . . . . . . 127 6.7.1 Stable Variables . . . . . . . . . . . . . . . . . . . . . . . . . . 128 6.7.2 Rover Web Browser proxy . . . . . . . . . . . . . . . . . . . . 128 6.7.3 Text file search . . . . . . . . . . . . . . . . . . . . . . . . . . 129 6.8 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 7 Future Work and Conclusion 134 7.1 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 7 7.2 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 8