MOBILE COMPUTING THE KLUWER INTERNATIONAL SERIES IN ENGINEERING AND COMPUTER SCIENCE MOBILE COMPUTING edited by Tomasz Imielinski Rutgers University Henry F. Korth AT&T Bell Laboratories W KLUWER ACADEMIC PUBLISHERS Boston / Dordrecht / London Distributors for North America: Kluwer Academic Publishers 101 Philip Drive Assinippi Park Norwell, Massachusetts 02061 USA Distributors for all other countries: Kluwer Academic Publishers Group Distribution Centre Post Office Box 322 3300 AH Dordrecht, THE NETHERLANDS Library of Congress Cataloging-in-Publication Data A CJ.P» Catalogue record for this book is available from the Library of Congress. Copyright ® 1996 by Kluwer Academic Publishers All rights reserved. No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, mechanical, photo-copying, recording, or otherwise, without the prior written permission of the publisher, Kluwer Academic Publishers, 101 Philip Drive, Assinippi Park, Norwell, Massachusetts 02061 Printed on acid-free paper. Printed in the United States of America CONTENTS PREFACE XXI INTRODUCTION TO MOBILE COMPUTING Tomasz Imielinski and Henry F. Korth 1 1 Introduction 1 2 Technology Overview 3 3 Research Issues 17 4 Book Content 33 REFERENCES 39 THE PARCTAB UBIQUITOUS COMPUTING EXPERIMENT Roy Want, Bill N. Schilit, Norman I. Adams, Rich Gold, Karin Petersen, David Goldberg, John R. Ellis, and Mark Weiser 45 1 Introduction 45 2 Ubiquitous Computing 47 3 PARCTAB System Design 50 4 User-Interface Design for Palm-Sized Computers 57 5 PARCTAB System Architecture 63 6 Developing System and Application Components 71 7 A Classification of PARCTAB Applications 75 8 Experiences with the PARCTAB System 81 9 Conclusion 91 REFERENCES 97 vi MOBILE COMPUTING SCALABLE SUPPORT FOR TRANSPARENT MOBILE INTERNETWORKING David B. Johnson 103 1 Introduction 103 2 Problem Analysis 105 3 The Basic Mobile IP Protocol 108 4 Route Optimization 115 5 Protocol Scalability 121 6 Conclusion 124 REFERENCES 125 LOCATION MANAGEMENT FOR NETWORKS WITH MOBILE USERS B. R. Badrinath and Tomasz Imielinski 129 1 Introduction 129 2 Location Management in the Internet 133 3 Location Management in Cellular Telephone Networks and in PCN 141 4 Performance Issues 145 5 Future: Adaptive Location management 147 6 Conclusions 150 REFERENCES 150 DYNAMIC SOURCE ROUTING IN AD HOC WIRELESS NETWORKS David B. Johnson and David A. Maltz 153 153 157 157 162 169 174 178 179 1 2 3 4 5 6 7 Introduction Assumptions Basic Operation Optimizations Performance Evaluation Related Work Conclusion REFERENCES Contents vii 6 ROUTING OVER MULTI-HOP WIRELESS NETWORK OF MOBILE COMPUTERS Charles E. Perkins and Pravin Bhagwat 183 1 Introduction 184 2 Overview of Routing Methods 185 3 Destination-Sequenced Distance Vector (DSDV) Protocol 187 4 Examples of DSDV in Operation 193 5 Properties of the DSDV Protocol 199 6 Comparison with Other Methods 200 7 Future Work 202 8 Summary 203 REFERENCES 205 7 IMPROVING THE PERFORMANCE OF RELIABLE TRANSPORT PROTOCOLS IN MOBILE COMPUTING ENVIRONMENTS Ramon Cdceres and Liviu Iftode 207 1 Introduction 208 2 Wireless Networking Testbed 209 3 The Effects of Motion 212 4 Improving Performance 218 5 Wireless Transmission Errors 225 6 Conclusions 227 REFERENCES 228 8 INDIRECT TRANSPORT LAYER PROTOCOLS FOR MOBILE WIRELESS ENVIRONMENT Ajay V. Bakre and B.R. Badrinath 229 1 Introduction 229 2 System Model 230 3 Indirect Transport Layer 233 4 Implementation and Handoffs 238 5 Performance Results 240 6 Alternatives to Indirect Protocols 247 7 Conclusion and Future Work 249 viii MOBILE COMPUTING REFERENCES 251 9 CONNECTING MOBILE WORKSTATIONS TO THE INTERNET OVER A DIGITAL CELLULAR TELEPHONE NETWORK Markku Kojo, Kimmo Raatikainen and Timo Alanko 253 1 Introduction 253 2 Mobile Nodes and TCP/IP Protocols 256 3 The Mowgli Communication Architecture 259 4 Enhanced Functionality for Mobility 265 5 Discussion 268 REFERENCES 269 10 ASYNCHRONOUS VIDEO: COORDINATED VIDEO CODING AND TRANSPORT FOR HETEROGENEOUS NETWORKS WITH WIRELESS ACCESS Johnathan M. Reason^ Louis C. Yun, Allen Y. Lao, and David G. Messerschmitt 271 1 Introduction 272 2 MPEG and Mobile Channels 273 3 System Level Considerations 276 4 QOS and Traffic Capacity 281 5 Video Coding for a Substream Transport 286 6 Results 293 7 Conclusions and Future Work 296 REFERENCES 297 11 WIRELESS PUBLISHING: ISSUES AND SOLUTIONS T. Imielinski and S. Viswanathan 299 1 Introduction 299 2 Publishing Mode 301 3 Publishing Using Temporal Addresses 308 4 Publishing Using Multicast Addresses 318 5 Adaptive Publishing 321 Contents ix 6 Other Information Delivery Methods 325 7 Conclusions and Implementation Status 327 REFERENCES 328 12 BROADCAST DISKS: DATA MANAGEMENT FOR ASYMMETRIC COMMUNICATION ENVIRONMENTS S. Acharya, R. Alonso, M. Franklin, and S. Zdonik 331 1 Introduction 332 2 Structuring the Broadcast Disk 335 3 Client Cache Management 341 4 Modeling the Broadcast Environment 343 5 Experiments and Results 346 6 Previous Work 356 7 Summary and Future Work 358 REFERENCES 360 13 APPLICATION DESIGN FOR WIRELESS COMPUTING Terri Watson 1 Introduction 2 Application Design for a Wireless Environment 3 Wireless Platform 4 W* : A Wireless Application 5 Experiences 6 Conclusions REFERENCES 363 363 365 366 367 369 371 371 14 MOBISAIC: AN INFORMATION SYSTEM FOR A MOBILE WIRELESS COMPUTING ENVIRONMENT Geoffrey M. Voelker and Brian N. Bershad 375 1 Introduction 375 2 System Overview 378 3 Using Dynamic URLs 380 4 Active Documents 382 MOBILE COMPUTING 5 Mobisaic on the Desktop 386 6 Implementation 386 7 Future Work 389 8 Conclusions 393 REFERENCES 394 15 PROVIDING LOCATION INFORMATION IN A UBIQUITOUS COMPUTING ENVIRONMENT Mike Spreitzer and Marvin Theimer 397 1 Introduction 398 2 Architecture 400 3 Design Considerations 407 4 Status and Experience 413 5 Conclusions 419 REFERENCES 423 16 UNIX FOR NOMADS: MAKING UNIX SUPPORT MOBILE COMPUTING Michael Bender, Alexander Davidson, Clark Dong, Steven Drach, Anthony Glenning, Karl Jacob, Jack Jia, James Kempf, Nachiappan Periakaruppan, Gale Snow, and Becky Wong 425 1 Introduction 426 2 The Power Management Framework 427 3 System State Checkpoint and Resume 432 4 PCMCIA on Unix 435 5 Serial Wide-Area Connectivity and Link Management 440 6 Nomadic Electronic Mail 443 7 Summary 446 REFERENCES 447 17 SCHEDULING FOR REDUCED CPU ENERGY Mark Weiser, Brent Welch, Alan Demers, and Scott Shenker 449 1 Introduction 450 2 An Energy Metric for CPUs 450 Contents xi 3 Approach of This Paper 452 4 Trace Data 452 5 Assumptions of the Simulations 453 6 Scheduling Algorithms 455 7 Evaluating the Algorithms 457 8 Discussion and Future Work 462 9 Conclusions 467 REFERENCES 469 APPENDIX A 469 A.l Description of Trace Data 470 18 STORAGE ALTERNATIVES FOR MOBILE COMPUTERS Fred Douglis, Ramon Cdceres, M. Frans Kaashoek, P. Krishnan, Kai Li, Brian Marsh, Joshua Tauher 473 1 Introduction 474 2 Architectural Alternatives 476 3 Hardware Measurements 477 4 Trace-Driven Simulation 480 5 Results 486 6 Related Work 498 7 Conclusions 500 8 Differences from the Preceding Version 503 19 DISCONNECTED OPERATION IN THE CODA FILE SYSTEM James J. Kistler and M. Satyanarayanan 507 507 508 511 515 525 530 531 532 533 1 2 3 4 5 6 7 8 Introduction Design Overview Design Rationale Detailed Design and Implementation Status and Evaluation Related Work Future Work Conclusions xii MOBILE COMPUTING 20 EXPERIENCE WITH DISCONNECTED OPERATION IN A MOBILE COMPUTING ENVIRONMENT M. Satyanarayanan, James J. Kistler, Lily B.Mummert, Maria R. Ebling, Puneet Kumar, and Qi Lu 537 1 Introduction 537 2 Constraints of Mobile Computing 538 3 Overview of Coda File System 539 4 Implementation Status 541 5 Qualitative Evaluation 542 6 Quantitative Evaluation 554 7 Work in Progress 563 8 Conclusions 568 REFERENCES 569 21 MOBILITY SUPPORT FOR SALES AND INVENTORY APPLICATIONS Narayanan Krishnakumar and Ravi Jain 1 Introduction 2 Application Scenario: Mobile Sales and Inventory 3 System Architecture 4 Database System Design 5 Mobile Sales Transactions 6 Maintaining Service Profiles 7 Conclusions REFERENCES 571 572 573 574 577 583 588 592 592 22 STRATEGIES FOR QUERY PROCESSING IN MOBILE COMPUTING Masahiko Tsukamoto, Rieko Kadobayashi and Shojiro Nishio 595 1 Introduction 595 2 Techniques Used in Mobile Communication Protocols 596 3 Query Processing for Location Sensitive Queries 600 4 Evaluation 608 5 Conclusions 617 REFERENCES 618 Contents xiii 23 THE CASE FOR WIRELESS OVERLAY NETWORKS Randy H. Katz and Eric A. Brewer 621 1 Introduction 621 2 Applications Enabled by Wireless Overlays 623 3 Applications Viewpoint 625 4 Gateway-Centric Network Management 628 5 Overlay Network Management 635 6 Applications Support Services 640 7 Related Work 644 8 Summary and Conclusions 648 REFERENCES 648 24 THE DIANA APPROACH TO MOBILE COMPUTING Arthur M. Keller, Tahir Ahmad, Mike Clary, Owen Densmore, Steve Gadol, Wei Huang, Behfar Razavi, and Robert Pang 651 1 Introduction 651 2 DIANA—The Overall Architecture 656 3 User Interface and Display Independence 660 4 The DIANA Network Architecture 665 5 Application Development Methodology 670 6 Current Implementation 674 7 Future Issues 674 8 Concluding Remarks 677 REFERENCES 677 25 THE CMU MOBILE COMPUTERS AND THEIR APPLICATION FOR MAINTENANCE Asim Smailagic and Daniel P. Siewiorek 681 1 Introduction 681 2 CMU Mobile Computers and Their Applications 683 3 VuMan as a Maintenance Assistant 684 4 Application Software 688 5 Conclusions 689 xiv MOBILE COMPUTING 6 Figures 691 REFERENCES 698 26 GENESIS AND ADVANCED TRAVELER INFORMATION SYSTEMS Shashi Shekhar and Duen-Ren Liu 699 699 704 708 715 720 721 725 1 2 3 4 5 Introduction Genesis System Data Management in Genesis Performance Issues in Genesis Conclusions REFERENCES INDEX