INFORMATION TO USERS
`
`1bis manuscript _bas been reproduced from the microfilm master. UMI
`films the ten directly from the original or copy submitted. Thus, some
`thesis and dissertation c:opies are in typewriter face, while others may
`be from any type of computer printer.
`
`Tile qality of dlis reprodaetia is depeadeat apoa tile qulity of tile
`eopy ...-utted. Broken or indistinct pr:i!l.lt colored or poor quality
`illustrations aDd photop'aphs, print bleedtbrouab. substandard margiDS,
`and imploper aligmneut am adversely affect reproductiOD.
`
`In the unlikely. event that the author did not send UMI a complete
`ID8DUIClipt and there are missing pages, these will be noted. Also, if
`unautbolized copyright material bad to be remowed, a note will indicate
`the deletioD.
`
`Oversize materials (e..., maps, drawinp, c:1wts) are reproduced by
`sectiOJiiDa the oriplal, besianiq at the upper left·hand corner aad
`CDIJijnuing from left to ript in equal sections with small overlaps. Each
`original is also photoaraphed in one exposure and is included in
`reduced form at tbe back of the book.
`
`Pboqraphs iDc1uded in the orf&iDal maDUSCript have been reproduced
`xerographically ill this copy. lfi&her quality 6• x 9" black and white
`photopaphic prints are available for IllY photopaphs or illustradons
`appearina in this copy for an additioaal c:balJe. Contact UMI direet1y
`to order.
`
`UM1
`
`A Bell & Mowelltntormataon Company
`300 Nottl"l Zeeb Road. Ann ArbOr. MI4S1Q6.1346 USA
`313!761-4700 800.'521-0600
`
`LG Electronics, Inc. et al.
`EXHIBIT 1005
`IPR Petition for
`U.S. Patent No.7, 149,511
`
`

`
`REALIZING MOBILE COMPUTING PERSONAE
`
`A Dissertation
`
`Submitted to the Graduate School
`
`of the University of Notre Dame
`
`In Partial Fulfillment of the Requirements
`
`of the Degree of
`
`Doctor of Philosophy
`
`by
`
`Michael Raymond Casey. B.S.E.E., M.S.E.E.
`
`OA.•rJ !. ~
`
`David L. Cohn. Director
`
`Department of Computer Science and Engineering
`
`Notre Dame. Indiana
`
`April 1995
`
`

`
`UMI Number: 9527070
`
`OMI Microfora 9527070
`Copyright 1995, by OMI Coapany. All rights reserved.
`
`This aicrofora edition is protected against unauthorized
`copying under Title 17, United States Code.
`
`UMI
`
`300 Borth Zeeb Road
`Ann Arbor, MI 48103
`
`

`
`REALIZING MOBILE COMPUTING PERSONAE
`
`Abstract
`
`hy
`
`Michael Raymond Casey
`
`The proliferation of computers has made it possible to do computer-related tasks
`
`in many places. At each place a user works. he or she runs applications. specifies
`
`prcferem:es for them. and is allowed to access resources and files according to
`
`local rules. These elements. together with other mappings. can he referred to as
`
`a user's computin~ persona. Currently. implicit personae are created wherever
`
`users usc machines. and their personae evolve as applications. preferences and
`
`resources change. This work outlines a method for making personae explicit, user(cid:173)
`
`centric. and mobile. thus creating mohile computing personae and describes the
`
`underlying components needed to support this shift First, this work identifies the
`
`important characteristics of a mobile file system. Second. a set of application(cid:173)
`
`based checkpoint and restart protocols is proposed to allow migration between
`
`heterogeneous platforms. Next the design and implementation of a user-centric.
`
`di~conncctahlc and reliable communications mechanism called mohile sockets is
`
`analyzed. A suite of mobile applications is then described that were built using
`
`a structured memory lihrary as part of a mobility toolkit to show the feasibility of
`
`such an approach to mobility. Lastly. a resource resolution protocol is presented
`
`that simplifies the transition from one environment to another by providing the
`
`ability to find resources at new locations.
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`

`
`DEDICATION
`
`This work is dedicated to my wife, Val~rie, and our son, Alex. Their patience has
`allowed me to fulfill a dream, and their smiles kept me going. I would also like
`to thank my parents, Kevin and Meg, for their many years of support.
`
`ii
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`

`
`TABLE OF CONTENTS
`
`LIST OF FIGURES ............................................. vi
`
`ACKNOWLEDGEMENTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
`
`I. INTRODUCTION .......................................... .
`
`2. FILE SYSTEM SUPPORTING USER MOBILITY
`
`. . . . . . . . . . . . . . . . . . . .
`
`2.1 Network File Systems without Local Client Caching . . . . . . . . . . . . . . . .
`2.2 Network File Systems with Local Client Caching
`. . . . . . . . . . . . . . . . . .
`2.2.1 AFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`2.2.2 The Little Work Project
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`2.2.3 Coda
`2.2.4 Mobile File System
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`2.3 Prospero . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`2.4 The Ideal File System
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`2.5 The Chosen System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`5
`
`5
`5
`7
`7
`8
`8
`9
`10
`11
`
`3. PERSONA MANAGEMENT
`
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`12
`
`3.1 Hardware-based Environment Management . . . . . . . . . . . . . . . . . . . . . .
`3.2 Unix for Nomads
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`3.3 Mohile Windowing Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`3.3.1 BNU Project . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`3.3.2 Xerox PARC
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`3.4 Migration in a Homogeneous Environment . . . . . . . . . . . . . . . . . . . . . .
`3.5 Hindrances to Migration in Heterogeneous Environments . . . . . . . . . . . .
`3.6 Migration using a Persona Manager . . . . . . . . . . . . . . . . . . . . . . . . . . .
`3.6.1 UNIX Character-mode Checkpointing . . . . . . . . . . . . . . . . . . . . . .
`3.6.2 X Windows Checkpoint Mechanism . . . . . . . . . . . . . . . . . . . . . . .
`3.7 OS/2 Character Mode Checkpoint Mechanism
`. . . . . . . . . . . . . . . . . . .
`3.R Presentation Manager Checkpoint Mechanism . . . . . . . . . . . . . . . . . . . .
`3.9 Additional Persona Manager Functions
`. . . . . . . . . . . . . . . . . . . . . . . .
`
`13
`13
`14
`14
`16
`21
`23
`25
`26
`29
`31
`33
`34
`
`iii
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`

`
`4. APPLICATION CHECKPOINTING
`
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`36
`
`4.1 Effective Checkpoints for Mobile Applications . . . . . . . . . . . . . . . . . . .
`4.::! Checkpoint Notification and Response . . . . . . . . . . . . . . . . . . . . . . . . .
`4.2.1 Single-threaded, character-mode applications . . . . . . . . . . . . . . . . .
`4.2.2 Multi-threaded, character-mode applications
`. . . . . . . . . . . . . . . . .
`4.2.3 The Original X Windows Checkpoint Procedure
`. . . . . . . . . . . . . .
`4.::!.4 Robust X Windows Checkpoint Procedure
`. . . . . . . . . . . . . . . . . .
`4.2.5 Original Checkpointing Procedure for PM Applications in OS/2
`. . .
`4.2.6 Modified OS/2 Checkpoint Mechanism . . . . . . . . . . . . . . . . . . . . .
`4.3 Choosing Applications and Restarting from the Effective State . . . . . . . .
`
`36
`37
`38
`40
`41
`42
`44
`46
`47
`
`5. MOBILE COMMUNICATIONS
`
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`50
`
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`5.1 Basic TCP/IP
`5.2 Mobile IP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`5.2.1 Loose Source Routing
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`5.2.2 Mobile IP using Repackaging
`. . . . . . . . . . . . . . . . . . . . . . . . . . .
`5.3 Mobile Sockets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`5.4 Mobile Sockets for Clients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`5.5 Client Calling Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`5.6 Mobile Sockets for Servers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`5. 7 Mobile Sockets for Peer-to-Peer Applications . . . . . . . . . . . . . . . . . . . .
`5.X Internals of Communication Surrogates
`. . . . . . . . . . . . . . . . . . . . . . . .
`5.9 Performance Analysis of the Modified TCPIIP Library Routines . . . . . . .
`
`50
`52
`56
`57
`59
`60
`63
`64
`67
`70
`72
`
`6. SUITE OF MOBILE APPLICATIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`76
`
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`6.1 Application Support Toolkits
`6.2 Calculator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`6.3 Editor
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`6.4 Terminal Emulator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`6.5 Talk/Chat Application
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`76
`78
`82
`88
`90
`
`7. MOBILITY TOOLKIT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`93
`
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`7. I Structured Memory Library
`7.'2 Checkpoint-Helper Routine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`93
`96
`
`8. RESOURCE RESOLUTION PROTOCOL
`
`. . . . . . . . . . . . . . . . . . . . . . . . .
`
`99
`
`8.1 General Model - Supports Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`X.:! Defining Resources
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`8.3 Finding Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`99
`101
`101
`
`iv
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`

`
`8.4 Accessing/Using Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`8.5 HTTP Server Implementation
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`102
`I 03
`
`9. CONCLUSIONS
`
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`104
`
`I 0. APPENDIX
`
`. . . . . . . . . . . . . . . . . . . . . . . .
`I 0. I Library Routines for Mobile Sockets
`I 0.1.1 Function: connect_() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`10.1.2 Function: peer_connect_() . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`I 0.1.3 Function: read_()
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`10.1.4 Function: disconnect() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`I 0.1.5 Function: reconnect()
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`10.2 Structured Memory Library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`10.2.1 Data Type Identifiers
`10.2.2 Function: str_mem() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`I 0.2.3 Function: deallocate() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`10.2.4 Function: find_str() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`I 0.2.5 Function: mem_pkg() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`I 0.2.6 Function: mem_make() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`I 0.3 Checkpoint-Helper Routines
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`I 0.3.1 Function: XSave()
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`I 0.3.2 Function: X Restore()
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`10.3.3 Function: PMSave()
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`I 0.3.4 Function: OS2Restore() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`107
`
`107
`107
`108
`108
`108
`109
`109
`109
`110
`110
`110
`110
`Ill
`Ill
`112
`112
`112
`113
`
`II. REFERENCES
`
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`114
`
`v
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`

`
`LIST OF t~IGURES
`
`Figure 1 Mobile user interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`Figure 2 Routing between PARCfab and application computer . . . . . . . . . . . . .
`Figure 3 X Windows Client and Server
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`Figure 4 Mobile windowing through xmove surrogate
`. . . . . . . . . . . . . . . . . . .
`Figure 5 Normal TCP/IP routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`Figure 6 Initial routing in a virtual network
`. . . . . . . . . . . . . . . . . . . . . . . . . .
`Figure 7 Mobile host receives beacon message . . . . . . . . . . . . . . . . . . . . . . . .
`Figure 8 Loose source routing redirects messages at their origin . . . . . . . . . . . .
`Figure 9 Mobile IP packaging and unpacking message for MH . . . . . . . . . . . . .
`Figure 10 Communications through a local surrogate . . . . . . . . . . . . . . . . . . . .
`Figure 11 Communications through remote surrogate . . . . . . . . . . . . . . . . . . . .
`Figure 12 Server connected to surrogate on local machine
`. . . . . . . . . . . . . . . .
`Figure 13 Server reconnects to surrogate from remote machine . . . . . . . . . . . . .
`Figure 14 Initial peer-to-peer communication configuration . . . . . . . . . . . . . . . .
`Figure 15 Local disconnection with multi-step reconnection . . . . . . . . . . . . . . .
`Figure 16 Direct reconnection to remote surrogate
`. . . . . . . . . . . . . . . . . . . . .
`Figure 17 Motif calculator
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`Figure 18 Motif Multi-file editor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`Figure 19 Multiple Presentation Manager editors replace single Motif editor . . . .
`Figure 20 Motif talk/chat application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`15
`17
`18
`20
`52
`54
`55
`57
`58
`61
`62
`65
`66
`67
`68
`69
`79
`83
`87
`91
`
`vi
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`

`
`ACKNOWLEDGEMENTS
`
`Thanks is due to all the members of the Distributed Computing Laboratory, both
`past and present, and especially to my advisor, Dr. Cohn. Each person helped me
`with ideas and encouraging words. May you all see the light at the end of your
`tunnels. A special thanks is due to Arindam Banerji for all his help in getting to
`the end.
`
`Much of my time at Notre Dame was sponsored by the IBM Corporation, both
`through an IBM Graduate Fellowship as well as funding to the DCRLab. For their
`help I am forever grateful.
`
`vii
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`

`
`1. INTRODUCTION
`
`Today's computer users are not confined to working at a single location or on a single
`
`host. Instead, with the proliferation of networked workstations and stand-alone personal
`
`computers, users create environments at a variety of locations. I DougHs, 1992] points
`
`out, however, that the workstation is just a "waystation" for the tools and environment of
`
`a user, and that any environment that is created should be user-cefltric. This would
`
`enable the environment to be associated with a person and to be moved as he or she goes
`
`from place to place. He describes many of the "implications of mobility", but leaves
`
`open the question of how to address them.
`
`In IBanerji 1993J, the concept of a mobile
`
`computing per:wna containing all the user's running applications, preferences, and
`
`resource mappings was proposed, but no underlying technology was described. This
`
`document presents a set of enabling technologies and explains how mobile personae can
`
`be built and used.
`
`A user's environment may look different on different platforms, but, in general, it
`
`contains several common components. Running applications (e.g. a word processor),
`
`preferences (e.g. UNIX environment variables) and resource mappings (e.g. default
`
`printers) form its basis. Most users would find having a single view of this world
`
`beneficial: it would reduce the work required to map operations onto available resources.
`
`However, since this persona and its mappings can change, the new persona should be
`
`moveable between machines. This dissenation describes the design and implementation
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`

`
`of a set of technologies to manage a mobile computing persona.
`
`The persona may be addressed as two separate parts for manageability. The first is
`
`a file system, and the second is everything else. One of the first problems in migrating
`
`environments is having a file system that can follow the user as he or she moves. AFS
`
`(Howard. 1988], Coda (Satyanarayanan. 19901 and the Little Work project (Huston, 1993]
`
`are network file systems that allow a user to see the same files from multiple machines
`
`in a network. Prospero I Neuman, 19931 allows the remapping of files and other resources
`
`depending on the user's location. Current work at Notre Dame (Saldanha, 1993] has
`
`proposed a mobile file .'iystem that expands Coda's functionality and sharing capabilities.
`
`It caches files for increased performance while connected and greater availability during
`
`disconnected operation and provides file coherency between multiple caches as the user
`
`moves.
`
`A major part of migrating a user's environment is moving the active applications. In
`
`order to migrate an application, its state must be saved and then used to restart the
`
`application. An application-based checkpointing scheme is proposed here that can be
`
`built on top of existing operating systems. Applications define an effective state which
`
`contains enough information to allow a restart without the loss of information. Because
`
`it is application-specific, effective state is more easily saved. restored and translated
`
`across heterogeneous machine architectures than a memory dump of a previously running
`
`application.
`
`Some running applications include active communication links as an integral pan of
`
`their state. These links must be suspendable if the applications are to be movable. Then,
`
`2
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`

`
`when the applications are restarted. the links must be able to receive any communications
`
`that were sent during the transition. Ideally, any implementation of such disconnectable
`
`communications should be backwards compatible with existing communications protocols.
`
`To coordinate the checkpointing and restarting of applications. this work describes the
`
`creation of a persona manager to manage the user's environment. The persona manager
`
`is a set of processes that use system-specific inter-process communication to send
`
`checkpoint requests to applications and receive and store their effective states. Having
`
`been restarted at a new location, the persona manager maps previously running
`
`applications onto locally available applications and passes the new applications the stored
`
`effective states.
`
`A suite of mobile applications was built to demonstrate the feasibility of mobile
`
`application creation and to provide a basis for the analysis of difficulties which might
`
`arise when a particular class of applications is used in a mobile environment. In order
`
`to support mobile, communicating applications. a modified TCP/IP library that provides
`
`a user-centric communications mechanism was also built. When combined with a
`
`structured memory library and a set of checkpoint-helper routines. current applications can
`
`be extended to be mobile applications.
`
`This document also outlines a resource re:wllltion protocol to map the desired
`
`resources onto available resources. This work not only aids users in moving between
`
`networked machines, it also supports users who move between portables, laptops and
`
`Personal Digital Assistants (PDAs) and networked machines.
`
`These analyses identify the benefits of making a user's persona explicit. The work
`
`3
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`

`
`shows that by reifying personae, personae can be moveable and user-centric. This will
`
`bring users closer to a universal, personal computing environment.
`
`The next chapter describes a mobile file system. Chapter 3 expands the ideas of
`
`persona and persona management; Chapter 4 treats application checkpointing. Chapter
`
`5 proposes an approach to communication for mobile applications and implementation
`
`details for a prototype. Chapter 6 describes a suite of applications built to analyze the
`
`problems in implementing mobile applications. Chapter 7 outlines other pans of a toolkit
`
`designed to help make applications mobile and is followed by a chapter containing a
`
`description of the resource resolution protocol. Conclusions end the document.
`
`4
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`

`
`2. FILE SYSTEM SUPPORTING USER MOBILITY
`
`The mobile user needs access to files wherever he or she goes. and seeing a coherent
`
`view of files from everywhere eases the transition between machines. Ideally, all files
`
`should be instantly accessible regardless of a user's location, but storage, connection and
`
`physical constraints make this impossible. Several approaches seek to provide files in a
`
`distributed environment, but offer varying degrees of computer/user autonomy.
`
`2.1 Network File Systems without Local Client Caching
`
`The most basic approach is a coherent view of files within a network via a network
`
`file :~y:~tem. Examples of this are: OS/2 LAN Server/Requester, Netware, and NFS. The
`
`classic way this is provided is by passing all file requests to a central file server. Clients
`
`request file accesses in the form of five functions: open, read, write, flush and close.
`
`However, this type of implementation requires messages to be transferred between the
`
`client and server for each requested servke. This causes both high latency and the
`
`potential for a bottleneck at the server.
`
`2.2 Network File Systems with Local Client Caching
`
`AFS, the Little Work Project, Coda, and Saldanha's Mobile File System extend the
`
`client/server model by adding caching. Servers maintain the primary copy of a file, but
`
`5
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`

`
`allow clients to check out, and locally store a secondary copy. If the secondary copy of
`
`a file is modified while it is checked-out, an invalidation request is sent to the server, and
`
`the altered copy is eventually propagated back to the server. Not only does caching
`
`improve performance during repeated use, but, in the last three systems, it also gives
`
`clients a measure of mobility. These systems let users use the secondary copy of a file
`
`during periods of disconnection. In addition, the last two approaches have methods of
`
`specifying the importance of particular files, either statically or through usage patterns
`
`which is essential in a space-constrained environment.
`
`Decentralizing the control of files also introduces a new set of reliability problems.
`
`If a client computer is removed from the network after an invalidation request is sent to
`
`the server, but before the secondary copy has been written back, a valid copy of the file
`
`no longer exists in the network. If, due to loss or damage, the computer that contains the
`
`secondary copy is never reconnected to the network, then the file may be permanently
`
`lost. Since mobile computers are more likely to be lost or destroyed than their desktop
`
`counterparts, care must be taken to make sure all altered secondary copies of files are
`
`flushed back to the server before disconnection is permitted.
`
`Another problem caused by mobility is the write-write conflict. When a client
`
`reconnects, any files that were changed by the user during disconnection must be
`
`reintegrated into the file system. However, if another user has also modified one of these
`
`files, then there is a write-write conflict. The mobile copy cannot simply replace the
`
`network copy as this would destroy information. Some current systems, like AFS, ignore
`
`this problem, but Little Work and Coda attempt to resolve it through user intervention.
`
`6
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`

`
`2.2.1 AFS
`
`AFS I Howard, 19881 presents a global file space to users making file access location(cid:173)
`
`independent. For scalability. the file system is divided into cells of replicable servers,
`
`each of which usually serves a campus or corporate environment. AFS clients identify
`
`themselves to a server in their cell using the Kerberos authentication protocol [Miller,
`
`198711Steiner, 1988], and they are issued a token to use in file system requests.
`
`AFS uses the client-server model with callbacks and invalidations to maintain file
`
`coherency. Clients use the network to notify servers when secondary copies are changed
`
`and servers notify clients when a primary copy is now newer than the cached secondary
`
`copy. AFS, however, has no support for resolving write conflicts. AFS's biggest failing
`
`is its inability to allow users to continue to use cached files in the presence of server non(cid:173)
`
`responsiveness or when a user is disconnected.
`
`2.2.2 The Little Work Project
`
`The Little Work project !Huston, 19931 has extended AFS clients to permit
`
`disconnected operation while remaining backwards compatible with existing AFS servers.
`
`Cliento; are allowed to modify files on mobile systems even when they cannot follow the
`
`normal protocol of notifying the server that modifications have been made.
`
`Instead,
`
`invalidation notifications are queued, and, when the mobile system is reconnected, the
`
`queued requests are sent to the server. If no other client has also updated a modified file,
`
`the modified files are copied back to the AFS server just as they would be from a normal
`
`AFS client. In the case of a write-write conflict, the user is prompted for a resolution
`
`strategy.
`
`7
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`

`
`2.2.3 Coda
`
`Coda [Satyanarayanan, 19901 has reworked the standard AFS model of a client-server
`
`file system to withstand disconnected operation, but without compatibility with classic
`
`AFS. Coda clients cache recently used files locally, but the normal method of caching
`
`has been augmented with the concept of hoarding preferred files. This keeps important
`
`files locally to enable disconnection without having used the files recently. When
`
`disconnected, Coda also logs file activity to enable later re-integration with the main file
`
`system. The Coda team is currently attempting to include work on application specific
`
`reintegration techniques which will allow the file system to require Jess direct user
`
`intervention in the face of write conflicts.
`
`2.2.4 Mobile File System
`
`Both Little Work and Coda support caching the most recently files so that the files
`
`can be used during disconnection.
`
`In reality, this is not the way many users operate.
`
`Users often work at a desktop machine at the office, then want to take their portable
`
`computer with them when they leave the office. To make sure that the portable computer
`
`has the right files, users explicitly tell the file system to get important files and place
`
`them in the cache. This, however, loses the information about recently used files. The
`
`Mobile File System [Saldanha, 1993) has proposed to extend the caching model to
`
`simultaneously cache files on a user's desktop and portable machines while working on
`
`the desktop machine. In this new model, the server notifies the portable machine when
`
`the desktop machine has checked out a file, and the portable requests a copy of the file
`
`also. When the desktop machine sends an invalidation notification to the server, the
`
`8
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`

`
`server passes the notification to the ponable. The ponable can then request a new copy
`
`of the file from the desktop machine. Thus, when a user takes the ponable away from
`
`the office, it will already have the files the user was using, and time is saved in
`
`comparison to the old model by eliminating the need to get files from server at the time
`
`the user wishes to leave.
`
`Also, Little Work and Coda only allow a single level of cached files. The system that
`
`checked out the file from the server is the only client that can use that file. and the file
`
`must be checked back in by that client. The proposed Mobile File System enables the
`
`responsibility for a cached file to be chained between several computers, creating a
`
`server-client list. Each computer that checks the file out becomes a new client of a new
`
`logical server and is responsible for either returning it to the logical server or returning
`
`it to the real server and informing the logical server. This file system as designed
`
`currently provides the greatest availability for a mobile user, but there does not yet exist
`
`a working implementation.
`
`2.3 Prospero
`
`Prospero !Neuman, 19931 has attempted to not only provide a global file space, but
`
`also to re-map devices and other resources according to a user's location. Such a scheme
`
`enables the user to see similar devices in different environments without having to know
`
`their device names. The user's preferences for resources is specified in terms of resource
`
`attributes, eg. cost-per-page or cost-per-megabyte. Using these preferences, the Prospero
`
`system automatically maps a resource into the file space according to the type of resource,
`
`9
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`

`
`eg. /printer, then applications that wish to print simply open the filename /printer
`
`and write the output to it.
`
`This system is the most advanced work towards unifying a user's view of his or her
`
`environment because of its ability to use resource characteristics. It, however, is
`
`unavailable for a wide range of systems.
`
`It is currently still a UNIX-only research
`
`system.
`
`2.4 The Ideal File System
`
`Each of the above systems is a step in the right direction towards providing the ideal
`
`file system, but many characteristics are still missing. File availability is enhanced via
`
`caching, but no system can guarantee that all the files needed during disconnection will
`
`be in the cache. The file system should, therefore, be integrated with communications
`
`links so that missing files can be automatically downloaded from the global file system.
`
`Another imponant characteristic for space constrained systems is automatic compression
`
`and decompression of files. This would enable a greater amount of caching space without
`
`any user intervention. None of the above systems currently supports either.
`
`A final addition to file systems will provide greater flexibility and accountability for
`
`resolving write conflicts. The servers should be modified to track not only the time of
`
`a file's last modification, but also the identity of the user who modified it. In this way.
`
`rules can be developed specifying whose changes have precedence or whom to notify to
`
`resolve conflicts.
`
`10
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`

`
`2.5 The Chosen System
`
`Unfortunately, this work cannot be built on top of the ideal file system because no
`
`such system currently exists. Instead, it is based on the most widely available service,
`
`AFS. AFS is supp