Database Technologies CS 4440
Popular in Course
verified elite notetaker
Popular in ComputerScienence
This 0 page Class Notes was uploaded by Alayna Veum on Monday November 2, 2015. The Class Notes belongs to CS 4440 at Georgia Institute of Technology - Main Campus taught by Staff in Fall. Since its upload, it has received 10 views. For similar materials see /class/234133/cs-4440-georgia-institute-of-technology-main-campus in ComputerScienence at Georgia Institute of Technology - Main Campus.
Reviews for Database Technologies
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 11/02/15
ClientServer Computing in Mobile Environments JIN JING GTE Laboratories Incorporated ABDELSALAM SUMI HELAL University of Florida AND AHMED ELMAGARMID Purdue University Recent advances in wireless data networking and portable information appliances have engendered a new paradigm of computing called mobile computing in which users carrying portable devices have access to data and information services regardless of their physical location or movement behavior In the meantime research addressing information access in mobile environments has proliferated In this survey we provide a concrete framework and categorization ofthe various ways of supporting mobile clientserver computing for information access We examine characteristics of mobility that distinguish mobile clientserver computing from its traditional counterpart We provide a comprehensive analysis of new paradigms and enabler concepts for mobile clientserver computing including mobileaware adaptation extended clientserver model and mobile data access A comparative and detailed review of major research prototypes for mobile information access is also presented Categories and Subject Descriptors 024 ComputerCommunication Networks Distributed Systems General Terms Algorithms Design Additional Key Words and Phrases Application adaptation cache invalidation caching clientserver data dissemination disconnected operation mobile applications mobile clientserver mobile computing mobile data mobility awareness survey system adaptation 1 INTRODUCTION of computing called mobile computing in Which users Who carry portable de vices have access to information ser vices through a shared infrastructure Advances in Wireless networking tech nology and portable information appli ances have engendered a new paradigm Authors addresses J Jing GTE Laboratories Incorporated 40 Sylvan Road Waltham MA 02454 A elal Computer an n ormation Science n Engineering Department University of orida Gaines ville F 611 email helalciseu edu A Elmagarmid Computer Sciences Purdue University West Lafayette IN 907 Permission to make digitalhard copy of part or all ofthis work for personal or classroom use is granted without fee provided that the copies are not made or distributed for pro t or commercial advantage the copyright notice the title of the publication and its date appear and notice is given that copying is by permission of the ACM Inc To copy otherwise to republish to post on servers or to redistribute to lists requires prior s ecif1c ermission andor a fee 1999 ACM 0360030099060070117 500 ACM Computing Surveys Vol 31 No 2 June 1999 118 0 J Jing et al CONTE NTS 1 Introduction aradigrus of Mobile ClientrServer Coruputing 12 Organization of this Paper MobilerAware Adaptation N co m I7 5 s I s 9 E i m I a a I a E s I 33 Flexible ClientrServer Architecture Mobile Data Access 41 Server Data Dissemination 42 Client Cache Management Case Studies 5 an 6 Conclusion regardless of their physical location or movement behavior Such a new enVi ronment introduces new technical chal lenges in the area of information access Traditional techniques for information access are based on the assumptions that the location of hosts in distributed systems does not change and the con nection among hosts also does not change during the computation In a mobile environment however these as sumptions are rarely valid or appropri ate Mobile computing is distinguished from classical fixedconnection comput ing due to 1 the mobility of nomadic users and their computers and 2 the mobile resource constraints such as lim ited wireless bandwidth and limited battery life The mobility of nomadic users implies that the users might con nect from different access points through wireless links and might want to stay connected while on the move despite possible intermittent disconnec tion Wireless links are relatively unre liable and currently are two to three orders of magnitude slower than wire line networks Moreover mobile hosts powered by batteries suffer from limited battery life constraints These limita tions and constraints leave much work to be done before mobile computing is ACM Computing Surveys Vol 31 No 2 June 1999 fully enabled This remains true despite the recent advances in wireless data communication networks and handheld device technologies There has been a recent proliferation of research addressing issues of mobile systems and applications especially for the purpose of mobile information ac cess In this survey we attempt to pro Vide a concrete framework and categori zation of various methods of supporting such applications and information ac cess from the Viewpoint of clientserver computing The scope of this survey cov ers techniques and methods in support of components above the transport layer of networks In a mobile clientserver information system a loose or tight col lection of trusted information servers are connected Via a fixed network to provide information services to a much larger collection of untrusted mobile cli ents over wireless and mobile networks 11 Paradigms of Mobile ClientServer Com ut39n In this section we brie y examine the impacts of mobility on information ser Vices and applications and the new par adigms of clientserver computing needed to deal with these impacts A categorization of these computing para digms is given below This examination should facilitate our analysis and re View of the various proposed techniques for mobile information access Existing research on mobile client server computing can be categorized into the following three paradigms 1 mobileaware adaptation 2 extended clientserver model and 3 mobile data access Mobileaware Adaptation The dy namics of mobile environments and the limitations of mobile computing re sources make adaptation a necessary technique when building mobile sys tems and applications The paradigm of mobileaware adaptation covers various strategies and techniques in how sys tems and applications respond to the environmental changes and the re ClientServer Computing in Mobile Environments 0 source requirements It also suggests the necessary system services that could be utilized by mobileaware appli cations Extended ClientServer Model The extended clientserver model facilitates mobile clientserver information access One distinguishing feature is the dy namic partitioning of clientserver func tionality and responsibilities The ex tended clientserver model provides a way to support the adaptation of mobile systems and applications The paradigm of the extended clientserver model in cludes various clientserver computing architectures that enable the functional partitioning of applications between cli ents and servers Mobile Data Access Mobile data ac cess addresses issues such as how server data can be delivered to client hosts how data over wireless and mo bile networks is structured and how the consistency of client cache is ensured consistency requirements of applica tions In our view mobile data access provides another way to characterize the impact of mobile computing con straints on information access It should be noted that these new paradigms are closely related to each other For example the i l for data delivery strategies and ex tended clientserver architectures may involve the use of adaptation solutions Extended clientserver architectures might be needed to take advantage of new data delivery strategies The cate gorization of new paradigms in this sur vey paper provides a comprehensive way to understand and analyze various proposed techniques in building mobile clientserver information systems 12 Organization of this Paper The remainder of this paper is orga nized as follows In Section 2 we dis cuss the paradigm of mobile client 119 server computing namely mobile aware adaptation The emphasis in this section is on understanding how adap tation strategies can be built into sys tem and application components In Section 3 we describe how the client server model has been extended to adapt to the dynamic environments In Section 4 we examine proposed tech niques for mobile data access including server data dissemination and client cache management Finally Section 5 reviews and analyzes three research prototypes of mobile clientserver infor mation systems namely Bayou Odys sey and Rover Concluding remarks are offered in Section 6 2 MOBILEAWARE ADAPTATION Mobile clients could face wide varia tions and rapid changes in network con ditions and local resource availability when accessing remote data In order to enable applications and systems to con tinue to operate in such dynamic envi ronments the mobile clientserver sys tem must react by dynamically adjusting the functionality of computa tion between the mobile and stationary hosts In other words the computation of clients and servers has to be adaptive in response to the changes in mobile environments Katz 1994 In Satyanarayanan 1996 the range i U and system adaptation is identified as shown in Figure 1 The range is delimited by two extremes At one extreme adaptation is entirely the responsibility of individual applications This approach called laissefaire adaptation avoids the need for system support The other extreme called applicationtransparent adapta tion places the entire responsibility for adaptation on the system A typical case of this approach is to use proxies to perform adaptation on behalf of applica tions Between these two extremes lies a spectrum of possibilities that are re ferred to as applicationaware adapta tion This approach supports collabora tive adaptation between the ACM Computing Surveys Vol 31 No 2 June 1999 120 0 J Jing et al Applic ation awarene ss collaboration Laissez faire No system support Figure 1 applications and the system That is the applications can decide how to best adapt to the changing environment while the system provides support through the monitoring of resources and the enforcing of resource allocation deci sions This section will discuss different proposed adaptation approaches 21 ApplicationTransparent Adaptation Many existing clientserver applications are built around the assumption that the environment of a client does not change These applications are usually d make cer availability The approach of applica tiontransparent adaptation attempts to make these applications work with no modification in mobile environments This is done by having the system shield or hide the differences between the stationary and mobile environments from applications Examples of this ap proach include Coda Satyanarayanan et al 1990 Kistler and Satyanarayanan 1992 Little Work Honeyman et al 1992 and WebExpress Housel and Lindquist 1996 Chang et al 1997 In these examples a local proxy runs on the mobile host and provides an inter face for regular server services to the applications The proxy attempts to mit igate any adverse effects of mobile envi ronments 211 File System Proxy The basic idea is to use a file system proxy to hide mobile issues from applications and to emulate file server services on the m0 ACM Computing Surveys V01 31 No 2 June 1999 Applicationtransparent No changes to applications Range of adaptation strategies bile computers see Figure 2 The Coda file system Kistler and Satyanaray anan 1992 pioneering this approach uses a file system proxy to make exist ing applications work with no modifica tion The proxy logs all updates to the file system during disconnection and re plays the log on reconnection Auto matic mechanisms for con ict resolu tion using optimistic concurrency control are provided for directories and files through the proxy and the file server The file system proxy in Coda facilitates the following features Disconnected Operations A small col lection of trusted Coda servers exports a locationtransparent UNIX file name space to a larger collection of untrusted clients On each client a userlevel pro cess Venus manages a le cache on the local disk Venus acts as a file system proxy and bears the brunt of discon nected operations Venus operates in one of three states hoarding emulat ing and reintegrating In the hoarding state server files are prefetched onto the mobile computer Upon disconnec tion Venus enters the emulating state and begins logging updates in a client modify log In this state Venus per forms log optimizations to improve per formance and reduce resource usage Upon reconnection Venus enters the re integrating state where it synchronizes its cache with the servers propagates updates from the client modify log and returns to the hoarding state In anticipation of disconnection users may hoard data in the cache by provid ing a prioritized list of files in a per ClientServer Computing in Mobile Environments 0 121 Applications File Mobile System APIs File Server Mobile File System APIs ile System Proxy Mobile Host Fixed Network Figure 2 File system proxyi client hoard database Venus combines effective support of operations for the hoard database information with LRU Least Recently Updated informa tion to implement a cache management policy Periodically Venus walks the cache to ensure that the highest priority items are present and consistent with the servers A user may also explicitly request a hoard walk at any time Since consistency is based on optimistic rep lica control update con icts may occur upon reintegration The system ensures the detection and confinement of update conflicts and provides mechanisms to help the users recover from them Weakly Connected Operations The file system proxy prefetches server data into the client cache and uses ob ject or volume1 callbacks for the cache validation in order to support weak con nectivity Volume call back is pessimis tic in that invalidating a volume invali dates all the objects in this volume However the gain is in reducing cache invalidation information that needs to be communicated between the client and the server The file system proxy can determine based on factors such as cached data structures and connectivity changes whether object or volume call backs are best for a particular connec tion The variable granularity of call back attempts to minimize the cost of validation and invalidation to provide 1A volume is a collection of related objectsi weakly connected clients Isolationonly Transactions Discon nected operations may result in data inconsistency due to conflicting opera tions on multiple disconnected comput ers Isolationonly Transaction IOT is proposed to automatically detect read write conflicts The execution of IOT is realized by the le system proxy code in the Coda system An IOT provides con sistency guarantees depending on the system connectivity conditions Unlike traditional transactions it does not guarantee failure atomicity and only conditionally guarantees permanence When an IOT is completed it enters either the committed or the pending state depending on the connectivity condition see Figure 3 If the execution of an IOT does not contain any parti tioned file access it is committed and its result is made visible on the servers Otherwise it enters the pending state for later validation The result is tempo rarily held within the client s local cache and is visible only to subsequent processes on the same client When the relevant partitions are repaired the IOT is validated according to the isola tion consistency criteria namely serial izability If the validation succeeds the result will be immediately reintegrated and committed to the servers Other wise the IOT enters the resolution state When it is automatically or man ACM Computing Surveys Vol 31 No 2 June 1999 122 0 J Jing et al with partitioned file accesses without partitioned file accesses u ser invocation wlidation fail Pending Resolution wlidation succeed amp reintegration Figure 3 A state transition diagram for IOT executioni ually resolved it will commit the new result to the server In addition to the Coda project other projects address similar adaptation is sues for mobile file system applications In the Rover project a file system proxy is added to the Rover Toolkit s object based model Joseph et al 1996 1997 It allows the Rover Toolkit to support both a file model and an object model for mobile applications The file system proxy in Rover Toolkits also addresses a number of issues related to file caching prefetching and conflict detection and resolution These issues are similar to those addressed by the Coda file sys tem except that they are associated with integrating a file system model with an objectbased model The Rover file system proxy consists of two compo nents a userlevel installable local file system proxy located on the client and a remote file system proxy running on a Rover server The two components work together with the use of Rover s queued communication mechanism that sup ports automatic message compression and batching The Ficus file system is another file system supporting discon nected operations with application transparent adaptation but relies on version vectors to detect con icts Hei demann et al 1992 The Little Work project caches files for smooth discon nection from an AFS file system Hon ACM Computing Surveys Vol 31 No 2 June 1999 eyman et al 1992 Conflicts are de tected and reported to the user for manual resolution 212 Web Proxy Web proxy enables Web browsing applications to function over wireless links without imposing changes on browsers and servers Web proxy can be used to prefetch and cache Web pages to the mobile client s ma chine to compress and transform image pages for transmission over lowband width links and to support discon nected and asynchronous browsing op erations wireless link for the purposes of reduc ing traffic volume and optimizing the communication protocol to reduce la tency Two components are inserted into the data path between the Web client and the Web server the Client Side Intercept CSI process that runs in the client mobile device and the Server Side Intercept SSI process that runs within the wired and fixed network see Figure 4 The CSI intercepts HTTP requests and together with the 881 performs optimizations to reduce bandwidth con sumption and transmission latency over the wireless link From the viewpoint of the browser the CSI appears as a local ClientServer Computing in Mobile Environments 0 Web Express Client 123 Web Server or Proxy Server HTTP TCPIP Web Express Server Side Intercept CS1 l Mobile Hosm TCPIP Connection Side Intercept SSI Fixed Network Figure 4 The WebExpress intercept modeli Web proxy that is coresident with the Web browser On the mobile host the CSI communicates with the Web browser over a local TCP connection using the TCPIP loopback feature via the HTTP protocol Therefore no external communication occurs over the TCPIP connection between the browser and the CSI No changes to the browser are required other than specifying the local IP address of the CSI as the browser s proxy address The CSI com municates with an 881 process over a TCP connection using a reduced version of the HTTP protocol The 881 reconsti tutes the HTML data stream and for wards it to the designated CSI Web server or proxy server Likewise for responses returned by a Web server or a proxy server the CSI reconstitutes an HTML data stream received from the 881 and sends it to the Web browser over the local TCP connection as though it came directly from the Web server The proxy approach implemented in WebEXpress offers the transparency ad vantage to both Web browsers and Web servers or proxy servers and there fore can be employed with any Web browser The CSISSI protocols facili tate highly effective data reduction and protocol optimization without limiting any of the Web browser functionality or interoperability WebEXpress optimiza tion methods are summarized below Caching Both the CSI and 881 cache graphics and HTML objects If the URL specifies an object that has been stored in the 081 s cache it is returned imme diately as the response The caching functions guarantee cache integrity within a clientspecified time interval The 881 cache is populated by responses from the requested Web servers If a requested URL received from a CSI is cached in the 881 it is returned as the response to the request Differencing CSI requests might re sult in responses that normally vary for multiple requests to the same URL eg a stock quote server The concept of differencing is to cache a common base object on both the CSI and 881 When a response is received the SSI computes the difference between the base object and the response and then sends the difference to the CSI The CSI then merges the difference with its base form to create the browser response This same technique is used to deter mine the difference between HTML doc uments Protocol reduction Each CSI connects to its 881 with a single TCPIP connec tion All requests are routed over this connection to avoid the costly connec tion establishment overhead Requests and responses are multiplexed over the connection ACM Computing Surveys Vol 31 No 2 June 1999 124 0 J Jing et al Moblle Nooe leed Net MobileConnection Host Fixed Host Network Interface Figure 5 The MDngl wireless Web browsing architectural Header reduction The HTTP protocol is stateless requiring that each request contain the browser s capabilities For a given browser this information is the same for all requests When the CSI establishes a connection with its 881 it sends its capabilities only on the first request This information is maintained by the 881 for the duration of the con nection The 881 includes the capabili ties as part of the HTTP request that it forwards to the target server in the wire line network The Mowgli project Kojo et al 1994 also uses a similar approach to support Web applications over wireless links see Figure 5 A specialized HTTP agent and a specialized HTTP proxy are applied to 1 reduce unnecessary mes sage exchange 2 reduce the volume of data transmitted over the wireless link and 3 support disconnected opera tions The HTTP agent acts as a local Web proxy on mobile client hosts while the HTTP proxy is located in the fixed network With the agentproxy ap proach neither Web clients nor servers need to be modified The HTTP agent intercepts requests generated by the Web client on the mobile node It com municates with the HTTP proxy in the fixed network Both the agent and the proxy maintain a cache of their own to improve performance over lowband width links 22 ApplicationAware Adaptation The approach of applicationtranspar ent adaptation does not require chang ACM Computing Surveys V01 31 No 2 June 1999 ing existing applications to run in mo bile environments However it could sacrifice functionality and performance As applications are shielded from deal ing with mobility it might be very hard for the system to make adaptation deci sions that meet the needs of different and diverse applications As a result it may have to require some manual inter vention by the user eg having the user indicate which data to prefetch onto the mobile device to make applica tions run smoothly Such useradminis tered manual actions could be less agile to adapt to the changing environment To address these problems application aware adaptation has been developed Applicationaware adaptation allows applications or their extensions to react to the mobile resource changes One way to realize the applicationaware ad aptation is through the collaboration be tween the system and individual appli cations The system monitors resource levels notifies applications of relevant changes and enforces resource alloca tion decisions Each application inde pendently decides how best to adapt when notified In a video player applica tion for example such adaptation al lows the video player system to scale back quality and resource consump tion when application performance is poor and to attempt to discover addi tional resources by optimistically scal ing up usage Depending on where the adaptive ap plication logic resides the approaches of applicationaware adaptation can be di ClientServer Computing in Mobile Environments 0 vided into the following categories cli entbased application adaptation client server application adaptation and proxybased application adaptation The clientbased adaptation allows the ap plications on mobile clients to react to the environmental changes while cli adapt to the changes The proxybased adaptation supports applicationspecific adaptation on the proxy server in the xed networks The applicationspecific proxies have been used as an intermedi ary between existing servers and heter ogeneous mobile clients Brooks et al 1996 Brewer et al 1998 The proxies can perform aggressive computation and storage on behalf of mobile clients These approaches can be complemen tary for a clientserver information sys tem For example both clientbased and proxybased adaptation can be used to gether in a single system to deal with the mobility 221 ClientBased Application Adap tation The Odyssey project Noble et al 1997 demonstrates a clientbased collaborative adaptation approach for applications on mobile clients In the collaborative adaptation the system provides the mechanisms of adaptation while the applications are free to specify adaptation policy The division of re sponsibility addresses the issues of ap plication diversity and concurrency In a mobile information system application data can be diverse in terms of data formats and consistency requirements For example the application data may be stored in one or more generalpur pose repositories such as file servers SQL servers or Web servers Alterna tively it may be stored in more special ized repositories such as video libraries querybyimagecontent databases or back ends of geographical information systems The application data can also have different dimensions for the speci fication and representation For exam ple video data can have at least two specification dimensions frame rate 125 and image quality of individual frames Spatial data such as topographical maps has dimensions of minimum fea ture size and resolution Furthermore concurrent applications can be very use ful for mobile users For example an information filtering application may run in the background monitoring data such as stock prices and alert the user as appropriate The collaborative adap tation accommodates the application di versity by allowing applications to de termine how application data presented at a client matches the reference copy at the server based on resource levels It also supports the application concur rency by allowing the system to retain control of resource monitoring and arbi tration The applicationaware adaptation in Odyssey is performed through the use of typespecific operations between the system and applications The type awareness is incorporated into both the knowledge of data types facilitates the optimization of the resource usage for different and diverse applications For example the size distribution and con sistency requirements of data from an NFS server differ substantially from those of relational database records lm age data may be highly compressible using one algorithm but not another Video data can be efficiently shipped using a streaming protocol that drops rather than retransmits lost data in contrast only reliable transmissions are acceptable for file or database updates Odyssey incorporates typeawareness via specialized code components called wardens A warden encapsulates the systemlevel support at a client to effec tively manage a data type To fully sup port a new data type an appropriate warden has to be written and incorpo rated into Odyssey at each client The wardens are subordinate to a typeinde pendent component called the Uiceroy which is responsible for centralized re source management The collaborative ACM Computing Surveys Vol 31 No 2 June 1999 126 0 J Jing et al relationship in the applicationaware adaptation is thus realized in two parts The first between the Viceroy and its wardens is datacentric it de nes the consistency levels for each data type and factors them into resource manage ment The second between applications and Odyssey is actioncentric it pro vides applications with control over the selection of consistency levels supported by the wardens A number of similar approaches have also been discussed in the literature In the Prayer system Bharghavan and Gupta 1997 the applicationaware ad for resources An application divides its execution into adaptation blocks An ad aptation block consists of a set of alter native sequences of execution each as sociated with a QoS class At the beginning of an adaptation block an application specifies the QoS classes that it is prepared to handle along with a segment of code associated with each class and an action to take should the QoS class be violated within the code segment In Welling and Badrinath 1998 ap plicationaware adaptation is imple mented under an event delivery frame work In the framework a notification subsystem called event channel deliv ers different events that are generated by the environment monitor to applica tions based on delivery policies For ex ample a low memory event may be de livered to each application in series until enough memory is freed for other uses while a low bandwidth event can be delivered to each application in par allel The applications are notified of the events to react to the environmental changes 222 ClientServer Application Adap tation The Rover Toolkit Joseph et al 1996 1997 supports the application aware adaptation through the use of relocatable dynamic object RDO The ACM Computing Surveys V01 31 No 2 June 1999 key task of the programmer when im plementing an applicationspecific ad aptation with Rover is to define RDOs for the data types manipulated by the application and for the data transported between the client and the server The programmer divides the program that contains the RDOs into portions that run on the client and portions that run on the server these parts communicate by means of queuing RPC The pro grammer also defines the methods that update objects including code for con ict detection and resolution At the level of RDO design applica tion designers have semantic knowledge that is very useful in implementing ap plicationaware adaptation By tightly coupling data with program code appli cations can manage resource utilization more carefully than possible with a clas sic file or object system that handles only generic data For example an RDO can include compression and decom pression methods along with com pressed data in order to obtain applica tionspecific and situationspecific compression reducing both network and storage utilization The RDO ap proach provides a generic framework to i 1 yp hi or u specific operations for application aware adaptation The application that consists of these RDO modules actively cooperates with the runtime system of the Rover Toolkit to import RDOs onto the local machine invoke welldefined methods on those objects export logs of method invoca tions on RDOs to servers and reconcile the client s copies of the objects with the server s In Davis et al 1998 a tuple space based platform called L2imbo is pro posed to support mobile distributed ap plications and adaptation The platform offers an asynchronous programming model and architecture for reporting and propagating QoS information about mobile environments The L2imbo ar chitecture supports mechanisms of ad aptation with the use of system and ClientServer Computing in Mobile Environments 0 Client app App Support Low bandwidth Medium bandwidth Transcoders 127 Client app App Support Figure 69 A proxybased adaptation architecture application agents that interact with the tuple space 223 ProxyBased Application Adap tation The applicationspecific proxy has been proposed as an intermediary between clients and servers to perform computation intensive and storage in tensive tasks such as data type specific lossy compression on behalf of clients Brooks et al 1996 Brewer et al 1998 Zenel and Duchamp 1997 This proxy architecture reduces the bandwidth de mands on the infrastructure through lossy compression and allows legacy and other nonstandard including thin cli ents to interoperate with existing serv ers The proxybased application adap tation allows the proxy agents to react to the environmental changes on behalf of mobile clients This approach avoids inserting adaptation machinery at each origin server From the client s perspec tive the proxy is simply a server that gets the data from someplace else In the BARWAN project Brewer et al 1998 the application speci c proxy uses the transcoders ie proxy agents to optimize the quality of service for the client in real time see Figure 6 To use transcoding to adapt to network varia tion the proxy must have an estimate of the current network conditions along the path from the proxy to the client SPAND Shared Passive Network Per formance Discovery a network mea surement system allows a measure ment host to collect the actual applicationtoapplication network per formance eg available bandwidth and latency between proxies and clients SPAND monitors endtoend bandwidth and connectivity to the clients and servers and notifies the proxy of any changes which may result in changes in transcoding to adjust the quality of ser vice The original servers are unaware of the transformations or of the limited capabilities of the clients or networks Compact HTML CompactHTML 1998 is a W30 submission of a standard for small information appliances It defines a subset of HTML for small information appliances such as smart phones smart communicators and mobile PDAs The ACM Computing Surveys Vol 31 No 2 June 1999 128 0 J Jing et al S De nedbyw S de nedbyw Figure 79 The WAP architecture standard is intended as guidelines for manufacturers of small information de vices service providers carriers and soft ware developers Another similar lan guage which is relatively less compliant to the WSC HTML recommendation is the Handheld Device Markup Language HDML HDML 1997 The HDML stan dard has been adapted into the Wireless Markup Language WML which makes up the I and l a ers of the Wireless Application Protocol WAP stack whose specification is being developed by the WAP forum WAP 1996 as a de facto standard WAP uses WML and provides third party proxies via a sessionlayer protocol as a means to negotiate device capabilities in terms of content characteristics The WAP archi tecture is shown in Figure 7 The WAP proxies are capable of adapting to the mobile devices by negotiating and lter ing the HTML Web content Filtering is performed as a translation to and from a compact subset of the HTML language The filtering process itself can be pre scribed or automated based on capability negotiation ACM Computing Surveys V01 31 No 2 June 1999 3 EXTENDED CLIENTSERVER MODEL Another way to characterize the client server computing in mobile environ ments is to examine the effect of mobil ity on the clientserver computing model In a clientserver information system a server is any machine that holds a complete copy of one or more databases A client is able to access data residing on any server with which it can Classic clientserver sys tems assume that the location of client and server hosts does not change and the connection among them also does not change As a result the functional ity between client and server is stati cally partitioned In a mobile environ ment however the distinction between clients and servers may have to be tem porarily blurred Satyanarayanan 1996 resulting in an extended client server model shown in Figure 8 The resource limitations of clients may re quire certain operations normally per formed on clients to be performed on resourcerich servers Conversely the need to cope with uncertain connectivity requires clients to sometimes emulate ClientServer Computing in Mobile Environments 0 Client Code Server Code Mobile Host FixedNetwork Figure 89 Extended clientserver model the functions of a server An extreme case is called the thin client architecture that offloads most application logic and functionality from clients to stationary servers In the thin client architecture applications in stationary servers are usually mobileaware and optimized for mobile client devices The thin client architecture is especially suitable for dumb terminal or small PDA applica tions The other extreme case is the full client architecture The full client archi tecture emulates server functions on the client devices and therefore is able to minimize the uncertainty of connectiv ity and communications 31 Thin Client Architecture The InfoPad project Le et al 1994 demonstrates the approach of thin cli ent architecture The InfoPad system is composed of four layers shown in Figure 9 Pad InfoNet Type Servers and Ap plications The Pad is a low power por table multimedia terminal that is capa ble of displaying text and graphics playing audio and compressed video re cording audio and capturing pen input The InfoNet layer presents the soft ware layer above the Pad with an ab straction in which each pad appears as a stationary networkconnected multi media terminal This layer contains the routing algorithms to make mobility seamless and the routines to manage the wireless network resources eg al location of frequencies to pads The type servers make the pad appear as a typical workstation to applications this allows for compatibility with stan 129 dard workstation software The type servers shield applications from knowl edge of the mobile environments and terminal hardware However applica tions are optimized for use on the pad The optimization takes advantage of the special characteristics of the pad such as small screen size lack of a keyboard and support for handwriting and speech recognition While applications in the InfoPad sys tem are customized for the characteris tics of the pad they do not contain code that allows them to dynamically adapt to changes in mobile networks Instead mobileaware adaptation is largely per formed in the InfoNet and type server layers In this sense the adaptation in the InfoPad system can be characterized as applicationtransparent adaptation rather than applicationaware adapta tion The thin client architecture from CIT RIX Corporation allows a variety of re mote computers regardless of their plat form to conn ct t a Windows NT terminal server to remotely access a pow erful desktop and its applications CIT RIX 1998 A server called MetaFrame runs under Windows NT in the desktop machine and communicates with the thin clients executing at the remote computers using the Independent Computing Archi tecture protocol ICA The ICA client and the MetaFrame server collaborate to dis play the virtual desktop on the remote computer screen They also collaborate to process mouse and keyboard events and to execute programs and view data stored at the server All executions are remote and none takes place at the client porta ble computer A research project at Mo torola Duran and Laubach 1999 ex tended CITRIX s thin client architecture so that it is optimized in the wireless environment The work pointed out that bandwidth limitation is not as detrimen tal to the thin client performance as net work latency This is because the thin clients use of bandwidth is limited W4 Bartlett 1994 applies the tech nique of dividing application functional ity between a small PDA and a power ACM Computing Surveys Vol 31 No 2 June 1999 130 0 J Jing et al X Telephone Generic X Applications Application Application AudioFile Xll Type Server Type Server Type Sewer 1 II II l39 a I 139 InfoNet J r r 39 I x l J V l 1 Pad Figure 99 lnfoPad system layering ful stationary host for Web browsing Other thin client examples include the Top Gun Wingman and Top Gun Media Board applications in the BARWAN project Brewer et a1 1998 32 Full Client Architecture Mobile clients must be able to use net works with rather unpleasant charac teristics intermittence low bandwidth high latency or high expense The con nectivity with one or more of these prop erties is referred to as weak connectiv ity In the extreme case mobile clients will be forced to work under the discon nected mode The ability to operate in disconnected mode can be useful even when connectivity is available For ex ample disconnected operations can ex tend battery life by avoiding wireless transmission and reception It can re duce network charges an important feature when charge rates are high It allows radio silence to be maintained a vital capability in military applications ACM Computing Surveys V01 31 No 2 June 1999 Finally it is a viable fallback position when network characteristics degrade beyond usability A full client architecture can be used to effectively support the disconnected or weakly connected clients Compared to a thin client architecture the full client architecture is at the other ex treme of the range of extended client server model The full client architec ture supports the emulation of functions of servers at the client host so that applications can be executed without fully connecting to remote servers The emulation can be supported through a proxy or a lightweight server residing on client hosts For example a proxy can emulate some database operations to allow mobile users to work in a dis connected mode S stems enabling the full client architecture include CODA and WebExpress ClientServer Computing in Mobile Environments 0 User 2 Data Interface Application Logic Client Server 131 Figure 109 A exible clientserver computing 33 Flexible ClientServer Architecture Flexible clientserver architecture gen eralizes both thin client and full client architectures in that the roles of clients and servers and application logic can be dynamically relocated and performed on mobile and stationary hosts see Figure 10 In the exible architecture the dis tinction between clients and servers may be temporarily blurred for pur poses of performance and availability Furthermore the connection between clients and servers can be dynamically established during the execution of ap plications eg for the service hand offs 331 Mobile Objects Mobile objects also known as mobile agents are pro gramming entities that can freely roam the network Mobile objects enable cli ent functions to run not only on mobile hosts but also on stationary hosts as well Furthermore mobile objects allow clients to download the server code to the mobile host for execution Mobile objects can contain threads and therefore be active They can maintain state information and make intelligent decisions usin it They differ from downloadable applets in that they can independently roam among different machines and are not limited to being downloaded once from server to client AgentTcl developed at Dartmouth Col leage Gray 1995 Odyssey developed by General Magic General Magic 1997 and Aglets developed by IBM IBM 1997 are examples of language tools that can be used to develop mobile objects One of the challenges to using mobile objects in wireless environments is how to implement the object transportation in a frequently disconnected or a weakly connected environment The Rover Tool kit Joseph et al 1996 1997 provides mobile application support based on the mobile object idea In the Rover Toolkit a relocatable dynamic object RDO is an object code and data with a well defined interface that can be dyna mically loaded into a client computer from a server computer or vice versa to reduce clientserver communication re quirements 332 Collaborative Groups A com monly occurring case may be several users disconnected from the rest of the system while actively collaborating a canonical example is a group of col leagues taking a business trip together Rather than giving the members of this disconnected working group access only to the data that they had the foresight to copy to their personal machine a collaborative group architecture grants ACM Computing Surveys Vol 31 No 2 June 1999 132 0 J Jing et al any group member access to any data that is available to the group The architecture is based on a divi sion of functionality between servers which store data and clients which read and write data managed by serv ers r is any machine eg a mobile host that holds a complete copy of one or more databases A client is able to access data residing on any server to which it can communicate and conversely any machine holding a copy of a database including personal lap tops should be willing to service read and write requests from other nearby machines In this architecture portable comput ers can be servers for some databases and clients for others The Bayou sys tem Demers et al 1994 Terry et al 1995 is an example that implements the collaborative group architecture 333 ApplicationSpeci c Proxy The applicationspecific proxy acts as an intermediary between clients and serv ers to perform computationintensive and storageintensive tasks on behalf of clients An applicationspecific proxy on a stationary host supports proxy agents which can be fixed or mobile to dynam ically transcode or distill application data to reduce the bandwidth consump tion between the proxy and the mobile client This proxy allows legacy and other nonstandard including thin cli ents to interoperate with existing serv ers From the client s perspective the proxy is simply a server that gets the data from someplace else The examples of applicationspecific proxies are dis cussed in Brooks et al 1996 Brewer et al 1998 and Zenel and Duchamp 1997 334 Virtual Mobility of Servers In a wireless information system informa tion data servers are connected via fixed networks to provide information services to mobile users The replication or partition of information services could help reduce the latency of remote operations and balance the workloads of ACM Computing Surveys V01 31 No 2 June 1999 data servers in a distributed and multi ple networks environment The replica tion of information services in different networks can be used to support the application service handoffs for moving mobile clients In a wireless environment the client moves around perhaps to areas it has never visited before once in a new mi lieu or a new network environment it will negotiate with some nearby ma chine to become a new coordinator to continuously provide services for its op erations The movement of mobile hosts may result in a long path of communica tions in fixed networks because the physical distance may not necessarily re ect network and service distance be tween the client and the server espe cially when the movement crosses the boundary of different networks The long path of communication in fixed net works will increase the traffic and la tency of transactional services If the new coordinator could a ways use a nearby or local information service site as the client s data server the traffic and latency in fixed networks can be reduced for the continuous interaction between the client and the information service server Therefore the mobility of the client introduces the concepts of virtual mobility of servers and applica tion service handoffs An issue of supporting the virtual mo bility of servers is to minimize the over head of application service handoffs for synchronous multi server operations The work in Tait and Duchamp 1991 1992 investigates how to maintain rep licas in a distributed file system that supports mobile clients This work as sumes that 1 clients movements can not be constrained although patterns of movement may exist 2 the latency of remote operations increases as the dis tance between hosts increases 3 se quential sharing workload is not un common but simultaneous sharing other than readread workload is rare and 4 a file cache of modest size is maintained by each client The design goals in this work include minimizing ClientServer Computing in Mobile Environments 0 Matchmaka Figure 11r synchronous multiserver operations easing the addition and deletion of server sites and allowing for incomplete replication To achieve these goals a primary secondary server hierarchy architecture is proposed as shown in Figure 11 Typ ically the client need not contact any makes periodic pickups from the clients it is currently servicing and propagates updates back to the secondary servers asynchronously This pickup strategy allows the client s write operation to return immediately after placing the new value in its cache rimary servers are used as in Because the system supports replica additiondeletion and incomplete replication a primary server must learn about mapping from the file system to the secondary servers The mapping is provided by calling a map ping server function specified by the cli ent For example someone from New York who is visiting Seattle would call the Seattle matchmaker to obtain a lo cal primary server site The locallycho sen primary server then calls the map ping server in New York to locate files that the client wishes to access After the handoff of primary servers the new rimary server can lazily copy the cli ent s file from the old cache in the old Mapping Server The primarysecondary server hierarchyr 133 Secondary 2 primary server Therefore this method always connects the mobile client to the local primary server for information ac cess in a distributed file system The work in Krishnakumar and Jain 1994 Jain and Krishnakumar 1994 presents a system architecture and ap plication service handoff protocols for virtual mobility of servers The architec ture is based on replicated distributed network Under this architecture as the user moves out of one service area into another the local server at the new service area takes over providing the service This service handoff for the vir tual mobility of the server is broadly analogous to the PCS call handoffproce dure and also requires that service con tinuation is transparent with no inter ruptions For the application services handoffs a service coordinator when informed that the user has moved initiates the setup of a conference call between the current server the mobile host and the new server so that the service can be transparently handed off to the new server The coordinator can then termi nate the call with the old server Before the new server takes over dur ing a service handoff it has to know what the mobile user is currently doing with the service that is the context of the user with respect to the service Context information is the information associated with a user and a service so ACM Computing Surveys Vol 31 No 2 June 1999 134 0 J Jing et al Client Pull Broadcast E Server Chan d Client S erver Push Databases Cache Client Pull Figure 129 A mobile data access paradigmi that the user can access different serv ers transparently Part of the context is static including password and access rights that do not change as the user accesses information However the con text also includes dynamic sessionspe cific data information such as how much data has been read or modified by the user whether the changes are meant to be transactional whether the user holds any locks to access the data and so on In Elmagarmid et a1 1995 an ap proach called Reservation Algorithm RA is proposed to avoid transaction log transfer and the use of global commit protocol 4 MOBILE DATA ACCESS Mobile data access enables the delivery of server data and the maintenance of clientserver data consistency in a mo bile and wireless environment Efficient and consistent data access in mobile environments is a challenge research area because of weak connectivity and resource constraints The data access strategies in a mobile information sys tem can be characterized by delivery modes data organizations and consis tency requirements etc The mode for server data delivery can be serverpush clientpull or hybrid The serverpush delivery is initiated by server functions that push data from the server to the clients The clientpull delivery is initi ated by client functions which send re quests to a server and pull data from ACM Computing Surveys Vol 31 No 2 June 1999 the server in order to provide data to locally running applications The hybrid delivery uses both serverpush and cli entpull delivery The data organiza tions include mobilityspecific data or ganizations like mobile database fragments in the server storage and data multiplexing and indexing in the broadcast disk The consistency require ments range from weak consistency to strong consistency Figure 12 illustrates the new paradigm of mobile data access for mobile information access In this section we will examine various pro posed approaches that offer the new paradigm of data access in mobile cli entserver information systems 41 Server Data Dissemination In many applications eg Web access the downstream data volume from serv ers to clients is much greater than the upstream data volume from clients back to servers The unbalanced communica tions are referred to as asymmetrical communications between clients and servers Application examples of asym metrical communications in wireless en vironments include Hughes s DirectPC wwwhnscom and CAI s Wireless In ternet Access wwwcaiwirelessnet where clients at mobile hosts usually have a lower bandwidth cellular or PSTN link while servers at fixed hosts may have relatively high bandwidth broadcast capability A challenge problem in supporting ap ClientServer Computing in Mobile Environments 0 135 lt E Figure 139 A broadcast programi plications with asymmetrical communi cations is how to deliver server data and information to a large number of clients To address this scalability problem a new information system architecture that exploits broadcastbased dissemi nation capability of communications has been proposed Herman et al 1987 Imi elinski and Badrinath 1994 Acharya et al 1995 1997 Su and Tassiulas 1998 The central idea is that the servers ex ploit the downstream communication capacity in bandwidth by broadcasting data to multiple clients This arrange ment is called a pushbased architec ture where data is pushed from the server to the clients In contrast most traditional clientserver information systems use pullbased data delivery to provide data to locally running applica tions 411 Broadcast Disks When a server iv 1 an i n I 1 i data to a client community the broadcast channel becomes a disk from which cli ents can retrieve data as it goes by The broadcasting data can be organized as multiple disks of different sizes and speeds on the broadcast medium Acharya et al 1995 The broadcast is created by multiplexing chunks of data from different disks onto the same broad cast channel The chunks of each disk are evenly interspersed with each other The chunks of the fast disks are repeated more often than the chunks of the slow disks see Figure 13 The relative speeds of these disks can be adjusted as a param eter to the configuration of the broadcast This use of the channel effectively puts the fast disks closer to the client while at the same time pushing the slower disks further away This technique presents an opportu nity to more closely match the broadcast to the workload at the client Assuming that the server has an indication of the client access patterns either by watch ing their previous activity or from a description of intended future use from each client then hot pages or pages that are more likely to be of interest to a larger part of the client community can be brought closer while cold pages can be pushed further away This in effect creates an arbitrarily finegrained memory hierarchy as the expected de lay in obtaining an item depends upon how often that item is broadcast The broadcast disk technique therefore provides improved performance for non uniformly accessed data In the simplest scenario the server can broadcast different items at the same frequency With the flat broad cast the expected delay required prior to obtaining an item is the same for all items broadcast namely half a broad cast period regardless of their relative importance to the clients This at approach has been adopted in earlier work on broadcastbased information system such as Datacycle Herman et al 1987 and the work in Imielinski et al 1994a 1994b By comparison the server can broadcast different items with differing frequency important items can be broadcast more often than others ACM Computing Surveys Vol 31 No 2 June 1999 136 0 J Jing et al Similar to the broadcast disk concept a pyramid broadcasting method is used to provide VideoOnDemand services to mobile users Vishwanath and Imielin ski 1995 In pyramid broadcasting the most frequently requested movies are multiplexed on the broadcast network resulting in radical improvement of ac cess time and efficient bandwidth utili zation 412 Indexing on Air In the push based approach servers periodically broadcast most frequently requested data items hot spots The server should dynamically adjust the content of the broadcast hot spot depending on the periodically measured demand dis tribution The client is lazy in that it transmits only when necessary The cli ent could also stay in the doze mode turning the power off as much as pos sible To minimize wakeup time clients can use selective tuning capabilities in the broadcasting channel In Imielinski et al 1994a 1994b the authors dis cuss basic methods for data organiza tion on the broadcast channel that pro vide selective tuning capabilities for clients In these methods index infor mation is broadcast together with the data The index is structured so that the following two parameters are mini mized iQuery Time Amount of time that it takes for a client to issue a query until the answer is received by the client iListening Time Amount of time spent by the client listening to the channel Query time is proportional to the overall t index increases the overall broadcast size However the presence of the index reduces the listening time This in turn reduces energy consumption be cause clients can use the selective lis tening capabilities in broadcasting channels to stay in the doze mode and ACM Computing Surveys V01 31 No 2 June 1999 as demon 1994a minimize wakeup time strated in Imielinski et al 1994b 42 Client Cache Management Caching of frequentlyaccessed data items is an important technique that reduces contention and improves query response times on narrow bandwidth wireless links The cached data can also support disconnected or intermitted connected operations However cache prefetching and consistency strategies can be greatly affected by the disconnec tion or weak connectivity of mobile cli ents The weak connectivity makes cache coherence expensive due to com munication latency and intermittent failures Prefetching or hoarding data into the client cache prior to disconnec tion is a difficult challenge in mobile clientserver computing This subsec tion describes an automated hoarding approach and two cache validation mechanisms 421 Automated Hoarding A useful solution to support disconnected opera tions is hoarding in which nonlocal files are cached on the client cache prior to disconnection The difficult issue for hoarding is which files should be se lected and stored locally Possible solu tions include choosing the most recently referenced files or asking the user to participate at least peripherally in man aging hoard contents The former ap proach might be wasteful of scarce hoard space while the latter requires more expertise and involvement that most users are willing to offer In the SEER system an automated predictive hoarding approach is devel oped Kuenning and Popek 1997 The automated predictive hoarding is based on the idea that a system can observe user behavior make inferences about the semantic relationships between files and use those inferences to aid the user In SEER an observer component watches the user s behavior and file ac cesses classifying each access according ClientServer Computing in Mobile Environments 0 to type converting path names to abso lute format and feeding the results to a correlator component The correlator component evaluates the file references calculating the semantic distances among various files These semantic distances drive a clustering algorithm that assigns each file to one or mor projects When new hoard contents are to be chosen the correlator component examines the projects to find those that are currently active and selects the highestpriority projects until the maxi mum hoard size is reached In this way SEER is able to operate without user intervention though the user might in volve informing the computer that a t D disconnection is imminen The fundamental assumption of SEER is that there is semantic locality in user behavior By detecting and ex ploiting this locality a system can make inferences about the relationships be tween various files Once these relation ships are known it is possible to auto mate the hoarding To detect semantic locality SEER uses a concept known as semantic distance Conceptually se mantic distance attempts to quantify a user s intuition about the relationship between files A low semantic distance suggests that the files are closely re lated and thus are probably involved in the same project while a large value indicates relative independence and dif ferent projects The semantic distance is based on measurements of individual file refer ences rather than looking at the files themselves The distance between refer ences is then summarized to produce a value that is relevant to the individual files Several semantic distance mea surement methods are defined based on file references in Kuenning and Popek 1997 422 Varied Granularity of Cache Co herence Consistency methods in tradi tional clientserver architecture can be divided into two categories 1 callback approach when servers send invalida tion messages directly to the clients 137 that have cached the data items to be updated and 2 detection approach when clients send queries to servers to validate cached data The difficulty of using these traditional methods in mo bile environments is due to the discon nection and weak connectivity of clients Frequently disconnected clients make it very ineffective to use the detection ap proach On the other hand the classic callback approach may also be very ex pensive due to network latency or in termittent failures After a long discon nection many data items at the server side may have been updated In this case the time for the callback invalida tion of each data item can be substan tial on a low network In the Coda system Satyanarayanan et al 1990 Kistler and Satyanarayanan 1992 Mummert and Satyanarayanan 1994 clients can track the server state at multiple levels of granularity A server maintains version stamps for each of its file volumes in addition to stamps on individual objects or items When an object is updated the server increments the version stamp of the ob ject and that of its containing volume Clients cache volume version stamps in anticipation of disconnection When connectivity is restored after a network failure the client presents vol ume stamps for validation If a volume stamp is still valid then so is every object cached from the volume If a vol ume stamp is not valid cached objects from the volume need to be validated individually Even in this case perfor mance is no worse than in the original scheme Mummert and Satyanarayanan 1994 On the other hand if the valida tion for each individual data item is not possible due to slow connections the tion until the time when the item is used The experiments and measure ments from the Coda system confirm that the varied granularity of cache co herence dramatically improve the speed of cache validation Mummert and Saty anarayanan 1994 ACM Computing Surveys Vol 31 No 2 June 1999 138 0 J Jing et al 423 Cache Invalidation Reports A disseminationbased approach to the problem of invalidating caches in wire less environments is proposed in Bar bara and Imielinski 1994 by utilizing wireless broadcast channels In this ap proach a server periodically broadcasts an invalidation report that reports data items which have been changed Rather than querying a server directly regard ing the validation of cached copies cli ents listen to these invalidation reports over broadcast channels This approach is attractive because a server does not need to know the location and connec tion status of its clients and the clients do not need to establish an uplink connection to the server to invalidate their caches Three algorithms are presented in Barbara and Imielinski 1994 namely the Broadcasting Timestamps TS Am nesic Terminals AT and Signatures SIG In the TS algorithm the invalida tion report includes only the informa tion regarding the data items that have been updated within the preceding w seconds The report includes the names of these items and the timestamps at which they were updated The invalida tion report in the AT algorithm includes the identifiers of data items that were updated during the last broadcast pe riod L In both the TS and AT algo rithms clients must invalidate their en tire cache when their disconnection period exceeds a specified length w sec onds for TS and L seconds for AT In the SIG algorithm the report contains a set of combined signatures of data items2 The structure and size of these signatures are designed to diagnose up 2Signatures are checksums computed over the value of data items in the database A combin signature is the Exclusive OR of a set of individ ual signaturesi Each combined signature there fore represents a subset ofdata items In the SIG algorithm In combined signatures are computed such that an item i is in the set of combined signature S 1 Sj S m with probability 1f 1 Wheref is the number of differing items up to which the algorithm can diagnose m a ACM Computing Surveys V01 31 No 2 June 1999 to f differing items If more than f dif ferent items it does not matter whether these items had been cached or not are updated in the data server since the combined signatures were last cached most items cached by the clients will be invalidated by the SIG algorithm al though many are in fact valid An improved invalidation report method called BitsSequences BS is proposed in Jing et al 1997 this method adapts to long disconnected cli ents In the BitSequences BS algo rithm the server broadcasts a set of bit sequences Each sequence consists of a series of binary bits and is associated with a timestamp Each bit represents a data item in a database A bit 1 in a sequence means that the item repre sented by the bit has been updated since the time specified by the times tamp of the sequence A bit 0 means that that item has not been updated since that time Clients must check the invalidation report before they can use their caches for query processing If a bit sequence among the sequence set with the most recent timestamp equals to or predates the disconnection time of the client the sequence will be used to invalidate its caches The data items represented by these 1 bits in the sequence will be invalidated If there is no such sequence ie the disconnection time precedes the timestamp of the highest sequence the entire cache in the client will be invalidated Consider a database consisting of 16 data items Figure 14 shows a BitSe quences BS structure reported by a server at the time 250 Suppose a client listens to the report after having slept for 80 time units That is the client disconnected at the time 170 25080 which is larger than TSBZ but less than TSBl The client will then use B2 to invalidate its caches To locate the items denoted by the two 1 bits in B2 the client will check both BS and B4 sequences using the following proce ClientServer Computing in Mobile Environments 0 6789 139 10 11 12 13 14 15 16 TSB45 0 TSB3140 TSBZ1 60 TSBl200 Figure 141 ABitSequences example dure To locate the second bit that is set to 1 in B2 check the position of the second 1 bit in B3 The second 1 bit in BS is in the 5th position therefore check the position of the 5th 1 bit in B4 Because B4 is the highest sequence and the 5th 1 bit in B4 is in the 8th position the client concludes that the 8th data item was updated since the time 170 Similarly the client can de duce that the 12th data item has also effectively for clients who have been disconnected for a long time It opti mizes the i i of L L for invalidation report In Pitoura and Samaras 1998 a re vised version of invalidation reports is designed to provide the semantics of readonly transactions for mobile clients without sending uplink requests to servers 1 1 5 CASE STUDIES We conclude this review with a study of three prototype systems for mobile in formation access These systems serve as a means of demonstrating how new paradigms analyzed in the previous sec tions are being applied in practice The three systems namely Bayou Odyssey and Rover demonstrate some ap proaches of new paradigms for mobile clientserver computing Bayou provides a exible clientserver architecture in which a server can be any machine that holds a complete copy of one or more databases A portable computer may also act as a server for some databases and as a client for others Odyssey sup ports applicationaware adaptation based on typespecific operations Rover provides a toolkit for distributed object based clientserver computing The relo catable objects in Rover enable a flexi ble clientserver architecture for mobile U i The toolkit supports both applicationtransparent and applica tionaware adaptation 51 Bayou Bayou is a Xerox PARC research project led by Douglas Terry It is designed for collaborative applications in a mobile computing environment containing por table machines with intermittent net work connectivity Demers et al 1994 Terry et al 1994 1995 The focus of the Bayou system has been on exploring mechanisms that let mobile clients ac ACM Computing Surveys Vol 31 No 2 June 1999 140 0 J Jing et al Storage System Application Bayou API Client Stub Read Server State Appueatior Bayou API Client Stub Write r Storage System Server State 4 SERVER Storage V System l Server State lt e l l gt Server State SERVER SERVER Figure 15 The Bayou system model tively read and write shared data such as appointment calendars bibliographic databases meeting notes evolving de si n documents news bulletin boards etc Bayou supports applicationspecific mechanisms that detect and resolve the update conflicts ensures that replicas move towards eventual consistency and defines a protocol by which the resolu tion of update conflicts stabilizes Bayou includes consistency management meth ods for con ict detection called depen dency checks and perwrite conflict res olution based on clientprovided merge procedures To guarantee eventual con sistency Bayou servers are able to roll back the effects of previously executed writes and redo them according to a global serialization order Furthermore Bayou permits clients to observe the results of all writes received by a server including tentative writes whose con icts have not been ultimately resolved 511 The System Model In the Bayou system each data collection is replicated in full at a number of servers ACM Computing Surveys V01 31 No 2 June 1999 Applications running as clients interact with the servers through the Bayou ap plication programming interface API which is implemented as a client stub bound with the application This API as well as the underlying clientserver RPC protocol supports two basic opera tions Read and Write Read operations permit queries over a data collection while Write operations can insert mod ify and delete a number of data items in a collection Figure 15 illustrates these components of the Bayou architec ture In the Bayou system a client and a server may be coresident on a host as would be typical of a laptop or PDA running in isolation Access to one server is suf cient for a client to perform useful work The client can read the data held by that server and submit Writes to the server Once a Write is accepted by a server the client has no further responsibility for that Write In particular the client does not need to wait for the Write to propagate to other servers In other words Bayou presents a weakly consistent replication model with ClientServer Computing in Mobile Environments 0 a readanywriteany style of access While individual Read and Write opera tions are performed at a single server clients need not confine themselves to interacting with a single server In a mo bile computing environment switching between servers is often desirable and Bayou provides session guarantees to re duce clientobserved inconsistencies when accessing different servers 512 Bayou ApplicationSpeci c Con ict Resolution Applicationspecific con ict detection is adopted in the Bayou system This approach is moti vated by the observation that different applications have different notions of what it means for two updates to con ict and that such con icts cannot al ways be identified by simply observing conventional reads and writes submit ted by the applications In Bayou stor age systems provide means for an appli cation to specify its notion of a con ict along with its policy for resolving con icts In return the system implements mechanisms for reliably detecting con icts as specified by the application and for automatically resolving them when possible The Bayou system includes two mech anisms for automatic con ict detection and resolution that are intended to sup port arbitrary applications dependency checks and merge procedures These mechanisms permit clients to indicate for each individual write operation how the system should detect con icts in volving the write and what steps should be taken to resolve any detected con icts based on the semantics of the ap plication Applicationspecific con ict detection is accomplished as follows Each Write operation includes a dependency check consisting of an applicationsupplied query and its expected result A con ict is detected if the query when run at a server against its current copy of the data does not return the expected re sult This dependency check is a precon dition for performing the update that is included in the Write operation If the 141 check fails then the requested update is not performed and the server invokes a procedure to resolve the detected con ict As an example of applicationdefined con icts consider a Bayou Write opera tion that might be submitted by the meeting room scheduling application This Write attempts to reserve an hour long time slot It includes a dependency check with a single query that returns information about any previously re served meetings that overlap with this time slot It expects the query to return an empty set Bayou s dependency checks can also be used to detect WriteWrite con icts That is they can be used to detect when two users update the same data item without one of them first observing the other s update Such con icts can be detected by having the dependency check query the current values of any data items being updated and ensure that they have not changed from the values they had at the time the Write was submitted Bayou s dependency checking mecha nism is more powerful than the tradi tional use of version vectors since it can also be used to detect ReadWrite con icts Specifically each Write operation can explicitly specify the expected val ues of any data items on which the update depends including data items that have been read but are not being updated Thus Bayou clients can emu late the optimistic style of concurrency control employed in some distributed database systems For example a Write operation that installs a new program binary file might only include a depen dency check of the sources including version stamps from which it was de rived Since the binary does not depend on its previous value this need not be included Moreover because dependency que ries can read any data in the server s replica dependency checks can enforce arbitrary multiitem integrity con straints on the data For example sup pose a Write transfers 100 from ac ACM Computing Surveys Vol 31 No 2 June 1999 142 0 J Jing et al count A to account B The application before issuing the Write reads the bal ance of account A and discovers that it currently has 150 Traditional optimis tic concurrency control would check that account A still had 150 before perform ing the requested Write operation The real requirement however is that the account have at least 100 and this can easily be specified in the Write s depen dency check Thus only if concurrent updates cause the balance in account A to drop below 100 will a con ict be detected Once a con ict is detected a merge procedure is run by the Bayou server in an attempt to resolve the con ict Merge procedures included with each Write operation are general programs written in a highlevel interpreted lan guage They can have embedded data such as applicationspecific knowledge related to the update that was being attempted and can perform arbitrary Reads on the current state of the serv er s replica The merge procedure asso ciated with a Write is responsible for resolving any con icts detected by its dependency check and for producing a revised update to apply The complete process of detecting a con ict running a merge procedure and applying the re vised update is performed atomically at each server as part of executing a Write Supporting dependency checks sepa rately allows servers to avoid running the merge procedure in the expected case where the Write does not introduce a con ict Bayou merge procedures are written by application programmers in the form of templates that are instantiated with the appropriate details filled in for each Write The users of applications do not have to know about merge procedures and therefore about the internal work ings of the applications they use except when automatic con ict resolution can not be done In the case where auto matic resolution is not possible the merge procedure will still run to com pletion but it is expected to produce a revised update that logs the detected ACM Computing Surveys V01 31 No 2 June 1999 con ict in a way that will enable a person to resolve the con ict later To enable manual resolution the con ict ing updates must be presented to a user in a manner that allows him to under stand what has happened Bayou allows replicas to always re main accessible This permits clients to continue to Read previously written data and to continue to issue new Writes In the meeting room scheduling application for example a user who only cares about Monday meetings need not concern himself with scheduling con icts on Wednesday The potential drawback of this approach is that newly issued Writes may depend on data that is in con ict and may lead to cascaded con ict resolution 513 Bayou Replication Management While the replicas held by two servers at any time may vary in their contents because they have received and pro cessed different Writes a fundamental property of the Bayou design is that all servers move towards eventual consis tency However it cannot enforce strict bounds on Write propagation delays since these depend on network connec tivity factors that are outside of Bayou s control Two important features of the Bayou system design allow servers to achieve eventual consistency First Writes are performed in the same well defined order at all servers Second the con ict detection and merge procedures are deterministic so that servers resolve the same con icts in the same manner When a Write is accepted by a Bayou server from a client it is initially deemed tentative Tentative Writes are ordered according to timestamps as signed to them by their accepting serv ers Committed Writes are ordered ac cording to the times at which they commit and before any tentative Writes The only requirement placed on time stamps for tentative Writes is that they should be monotonically increasing at each server so that the pair timestamp ID of server that assigned it produce a total order on Write operations Bayou ClientServer Computing in Mobile Environments 0 servers maintain logical clocks to times tamp new Writes A server s logical clock is generally synchronized with its realtime system clock but in order to preserve the causal ordering of Write operations the server may need to ad vance its logical clock when Writes are received during antientropy Enforcing a global order on tentative as well as committed Writes ensures that an isolated cluster of servers will come to agreement on the tentative res olution of any con icts that they en counter This is not strictly necessary since clients must be prepared to deal with temporarily inconsistent servers in any case Moreover clients can expect that the tentative resolution of con icts within their cluster will correspond to their eventual permanent resolution provided that no further con icts are introduced outside the cluster Because servers may receive Writes from clients and from other servers in an order that differs from the required execution order and because servers immediately apply all known Writes to their replicas servers must be able to undo the effects of a previous tentative execution of a Write operation and reap ply it in a different order The number of times that a given Write operation is reexecuted depends only on the order in which Writes arrive via antientropy and not on the likelihood of con icts involving the Write Conceptually each server maintains a log of all Write oper ations that it has received sorted by their committed or tentative times tamps with committed Writes at the head of the log The server s current data contents are generated by execut ing all of the Writes in the given order Bayou guarantees that merge proce dures which execute independently at each server produce consistent updates by forcing them to depend only on the server s current data contents and on any data supplied by the merge proce dure itself In particular a merge proce dure cannot access timevarying or serv erspecific environment information suc as the current system clock or 143 server s name Moreover merge proce dures that fail due to exceeding their limits on resource usage must fail deter ministically This means that all serv ers must place uniform bounds on the CPU and memory resources allocated to a merge procedure and must consis tently enforce these bounds during exe cution Once these conditions are met two servers that start with identical replicas will end up with identical repli cas after executing a Write 514 Bayou Applications The Bayou system is designed to support a variety of nonrealtime collaborative applica tions such as shared calendars mail and bibliographic databases program development and document editing for disconnected workgroups as well as ap plications that might be used by indi viduals at different hosts at different times Meeting Room Scheduler The meet ing room scheduling application enables users to reserve meeting rooms At most one person or group can reserve the room for any given period of time This meeting room scheduling program is intended for use after a group of people have already decided that they want to meet in a certain room and have determined a set of acceptable times for the meeting It does not help them to determine a mutually agreeable place and time for the meeting it only allows them to reserve the room Thus it is a much simpler application than one that supports general meeting scheduling In this application Bayou users could interact with a graphical interface for the schedule of a room that indicates which times are already reserved much like the display of a typical calendar manager The meeting room scheduling program periodically rereads the room schedule and refreshes the user s dis play This refresh process enables the user to observe new entries added by other users The user s display might be outofdate with respect to the con firmed reservations of the room for ex ACM Computing Surveys Vol 31 No 2 June 1999 144 0 J Jing et al ample when it is showing a local copy of the room schedule on a disconnected laptop Bayou users reserve a time slot sim ply by selecting a free time period and lling in a form describing the meeting Because the user s display might be out ofdate there is a chance that the user could try to schedule a meeting at a time that was already reserved by someone else To account for this possi bility users can select several accept able meeting times rather than just one At most one of the requested times will eventually be reserved A user s reservation rather than be ing immediately confirmed or rejected may remain tentative for a while While tentative a meeting may be re scheduled as other interfering reserva tions become known Tentative reserva tions are indicated as such on the display by showing them grayed The outdatedness of a calendar does not prevent it from being useful but simply increases the likelihood that tentative room reservations will be rescheduled and finally committed to less pre ferred meeting times A group of Bayou users although dis connected from the rest of the system can immediately see each other s tenta tive room reservations if they are all connected to the same copy of the meet ing room schedule If instead users are maintaining private copies on their lap top computers local communication be tween the machines will eventually syn chronize all copies within the group The meeting room scheduling applica tion provides good examples of con ict resolution procedures that are specific not only to a particular application but also to a particular Write operation In this application users well aware that their reservations may be invalidated by other concurrent users can specify alternate scheduling choices as part of their original scheduling updates These alternates are encoded in a merge pro cedure that attempts to reserve one of the alternate meeting times if the origi nal time is found to be in conflict with ACM Computing Surveys V01 31 No 2 June 1999 some other previously scheduled meet ing A different merge procedure alto gether could search for the next avail able time slot to schedule the meeting which is an option a user might choose if any time would be satisfactory Bibliographic Database The applica tion allows users to cooperatively man age databases of bibliographic entries A user can freely read and write to any copy of the database such as the one that resides on his laptop For the most part the database is appendonly though users occasionally update en tries to fix mistakes or add personal annotations In bibliographic databases each entry has a unique humansensible key that is constructed by appending the year in which the paper was published to the first author s last name and adding a character if necessary to distinguish be tween multiple papers by the same au thor in the same year Thus the rst paper by Jones et al in 1995 might be identified as Jones95 and subsequent papers as Jones95b Jones95c and An entry s key is tentatively assigned when the entry is added A user must be aware that the assigned keys are only tentative and may change when the en try is committed In other words a user must be aware that other concur rent updaters could be trying to assign the same key to different entries Only one entry can have the key the others will be assigned alternative keys by the system Thus for example if the user employs the tentatively assigned key in some fashion such as embedding it as a citation in a document then he must also remember to check later that the key assigned when the entry was com mitted is in fact the expected one Because users can access inconsistent database copies the same bibliographic entry may be concurrently added by dif ferent users with different keys To the extent possible the system detects du plicates and merges their contents into a single entry with a single key In this ClientServer Computing in Mobile Environments 0 application a Bayou user may choose to opera e in disconnected mode even if constant connectivity were possible For example a Bayou user may be in a university library looking up papers He occasionally types bibliographic refer ences into his laptop or PDA 52 Odyssey Odyssey is a CMU research project led by M Satyanarayanan It addresses an applicationaware adaptation approach to deal with application diversity and concurrency in mobile environments The applicationaware adaptation is im plemented with the support of system coordinated typespecific operations It supports concurrent execution of di verse mobile applications that execute on mobile clients but read or update remote data on servers Kumar and a i l o i 3 et al 1995 Noble et al 1995 1997 521 Odyssey Client Architecture In Odyssey the data accessed by an application may be stored in one or more generalpurpose repositories such as file servers SQL servers or Web servers It may also be stored in more specialized repositories such as video libraries querybyimagecontent data bases or backends of geographical in formation systems Ideally a data item available on a mobile client should be indistinguish able from that available to the accessing application if it were to be executed on the server storing that item But this correspondence may be difficult to pre serve as mobile resources become scarce some form of degradation may be inevitable In Odyssey fidelity is used to describe the degree to which data presented at a client matches the reference copy at the server Fidelity has many dimensions One wellknown universal dimension is consistency For Video applications data has at least two additional dimensions frame rate and image quality of individual frames Odyssey provides a framework within 145 Viceroy Generic Support Wardens TypeSpeci c Support Apphca or s Cache Manager API Extensions Kernel Figure 16 Odyssey client architecture which diverse notions of fidelity can be incorporated Odyssey implements an approach of applicationaware adaptation The sys tem monitors resource levels notifies applications of relevant changes and enforces resource allocation decisions Each application independently decides how best to adapt when notified Odys sey incorporates typeawareness via specialized code components called war dens A warden encapsulates the sys temlevel support at a client necessary to effectively manage a data type To fully support a new data type an appro priate warden has to be written and incorporated into Odyssey at each cli ent The wardens are subordinate to a typeindependent component called the viceroy which is responsible for central ized resource management see Figure 16 The collaborative relationship in the applicationaware adaptation is re alized in two parts The first between the viceroy and its wardens is data centric it defines the fidelity levels for each data type and factors them into resource management The second be tween applications and Odyssey is ac tioncentric it provides applications with control over the selection of fidelity levels supported by the wardens 522 Odyssey System Components Odyssey supports applicationaware ad aptation by enabling an application to ioperate on Odyssey objects ACM Computing Surveys Vol 31 No 2 June 1999 146 0 J Jing et al iexpress resource expectations ibe notified when expectations are no longer met an irespond by changing delity Operating on Odyssey Objects Odys sey is integrated into NetBSD as a new VFS file system Noble et al 1997 As shown in Figure 16 the Viceroy and wardens are implemented in user space rather than in the kernel Operations on Odyssey objects are redirected to the Viceroy by a small inkernel requesmn path in resourcedescriptor out requestidgt Cancelm requestidgt a Resource Negotiation Operations resourcerid nd narne ofupcall handler b Resource Descriptor Fields Network BandWidtn bytessecond Networ Latency microseconds Disk Cache Space byte CPU SPECCmt95 Battery Power utes Money module All other system calls are han dled directly by NetBSD Wardens are statically linked with the Viceroy and the ensemble executes in a single address space with userlevel threads Communication between the Viceroy and wardens is through proce dure calls and shared data structures The wardens are entirely responsible for communicating with servers and caching data from them when appropri ate applications never contact servers directly Expressing Resource Expectations Applications communicate resource ex pectations to Odyssey using the request system call shown in Figure 17a The call takes a resource descriptor identify ing a resource and specifying a window of tolerance base upon availability This call expresses the application s de sire to be told if the availability of the resource strays outside the window If at the time of the request the availabil ity of the resource is within the window of tolerance the Viceroy registers the request and returns a unique identifier for it This identifier can be used by the Viceroy in notifying the application that the resource has left the requested bounds or by the application in a future cancel system call to discard the regis tered request If the resource is currently outside the bounds of the tolerance window an error code and the current available re source level are returned The applica tion is then expected to try again but ACM Computing Surveys V01 31 No 2 June 1999 c Generic Resource in Odyssey nanoteriin requestid in resourceid id resourcetevet d Upcan Handler tsopin path in opcode in insize in input inout outsize out outbuO e TyperSpecific Operations Figure 11 Odyssey APL this time with a new window of toler ance that corresponds to a new fidelity level The fields of a resource descriptor are shown in Figure 17b Each re source is named by a unique resource identifier Figure 17c lists the generic resources that Odyssey manages The most critical resource in mobile comput ing is the network bandwidth The win dow of tolerance is indicated by lower and upper bounds A resource descriptor also specifies the name of a procedure that will be called to notify the applica tion that the resource has left the win dow Notifying Applications When the Viceroy discovers that the availability of a resource has strayed outside a regis tered window of tolerance it generates an upcall to the corresponding applica tion The application adjusts its fidelity according to its individual policy It then issues another request call to reg ister a revised window of tolerance ap propriate to the new fidelity ClientServer Computing in Mobile Environments 0 147 I CLIENT I I 0d Viceroy yssey xmm 3 Video l API Video Server I Warden I Figure 189 Video player in Odysseyi An upcall handler is invoked with three parameters as shown in Figure 17d The first parameter identifies the request operation on whose behalf the upcall is being delivered The second parameter identifies the resource whose availability has changed and the third parameter gives the new availability Upcalls closely resemble UNIX signals but offer improved functionality Like signals upcalls can be sent to one or more processes can be blocked or ig nored and have similar inheritance se mantics on the process fork Unlike sig nals upcalls offer semantics in a specific order only once for each receiver of a particular upcall Further upcalls allow parameters to be passed to target processes and results to be returned Changing Fidelity Requests for fidel ity changes do not map well to the Net BSD file system interface Further many data types have natural access methods that are not well supported by the untyped byte stream model To ad dress these shortcomings a general es cape purpose mechanism called tsop or typespecific operation is included shown in Figure 17e The arguments to tsop specify an Odyssey object and the opcode of a typespecific operation to be performed on it Input and output parameters are specified as unstruc tured memory buffers in the spirit of the ioctl system call 523 Odyssey Applications Several applications are modified to demon strate Odyssey s ability to support ap plication diversity Two of them are drawn from the domain of mobile infor mation access a video player and a Web browser Each application requires a different strategy for integration into Odyssey and each has distinct notions of fidelity Video Player Video Player is based on xanim a publicdomain software pack local file A warden is written to satisfy client requests and fetch data from the server as shown in Figure 18 Each movie is stored in multiple tracks at the server one track per fidel ity level Three levels of fidelity for Quicktime video data are incorporated JPEGcompressed color frames at quali ties 99 and 50 and blackandwhite frames The warden supports two tsops to read a movie s metadata and to get a particular frame from a specified track The warden performs readahead of frames to lower latency When the player opens a movie it calculates the bandwidth requirements of each track from the movie metadata The player begins the movie at highest possible quality and registers the corresponding window of tolerance with Odyssey When it is notified of a significant change in bandwidth the player deter mines a new fidelity level and switches to the corresponding track If the player switches from a low fidelity track to a higher one the warden discards the prefetched lowquality frames Web Browser Netscape browser s proxy facility is exploited to take advan tage of Odyssey as shown in Figure 19 All of Netscape s requests are redirected ACM Computing Surveys Vol 31 No 2 June 1999 148 0 J Jing et al Vicaoy Video Warden to Web S avers nmman n Server HTTP Web Brow ser Cellophane CLIENT Figure 199 Web browser in Odysseyi to a client module called the cellophane Together Netscape and the cellophane lects delity levels Netscape passively bene ts from the adaptation initiated by the cellophane The cellophane trans forms HTTP requests from Netscape into file operations on Odyssey Web ob jects The Web warden forwards these requests via the client s mobile network connection to a distillation server At the highest fidelity images are uncom pressed Progressively lower levels cor respond to JPEGcompressed images of decreasing quality The warden pro vides a tsop to set the fidelity level The distillation server fetches requested ob jects from the appropriate Web server distills them to the requested fidelity level and sends the results to the war den The data is then passed to Netscape via the cellophane These steps are completely transparent to both Netscape and the Web server each perceives normal Web access 53 Rover Rover is a research project at MIT led by M Kaashoek The Rover toolkit of fers an environment to support both applicationtransparent and applica tionaware adaptation for mobile client server applications Joseph et al 1996 1997 The applicationtransparent ad aptation is realized by developing prox ies for system services that hide the mobile characteristics of the environ ment from applications The applica tionaware adaptation is supported by ACM Computing Surveys Vol 31 No 2 June 1999 the use of relocatable dynamic objects in the construction of client and server applications The Rover toolkit provides a framework to construct mobile appli cations with exible clientserver archi tecture 531 Rover Toolkits The Rover Toolkit offers applications a distributed object system based on a clientserver architecture Joseph et al 1997 see Figure 20 Clients are Rover applica tions that typically run on mobile hosts but can also run on stationary hosts as well Servers which may be replicated typically run on stationary hosts and hold the longterm state of the system Communication between clients is lim ited to peertopeer interactions within a mobile host using the local object cache for sharing and mobile host server interactions there is no support for peertopeer mobile host to mobile host interactions The Rover toolkit pro vides mobile communication support based on two ideas relocatable dynamic object RDO and queued remote proce dure call QRPC A relocatable dynamic object is an object code and data with a welldefined interface that can be dy namically loaded into a client computer from a server computer or vice versa to reduce clientserver communication re quirements Q call is a communication system that permits applications to continue to make nonblocking remote procedure calls even when a host is disconnectedi requests and responses are exchanged upon network reconnection Rover gives applications control over the location where the computation will ClientServer Computing in Mobile Environments 0 Client Client Application Application Rover Library 1 Object ache Network lt RDO Schedule gt QPRC Log RDO Access Manager on Mobile Host 149 ServersideApplica on ModifyResolve Con ict Import RDO Export RDO Figure 20 Rover s relocatable dynamic object RDO architectural be performed In an intermittently con nected environment the network often separates an application from the data upon which it is dependent By moving RDOs across the network applications can move data andor computation from the client to the server and vice versa Use of RDOs allows mobileaware ap plications to migrate functionality dy namically to either side of a slow net work connection to minimize the amount of data communicated across the network Caching RDOs reduces la tenc and L J L l In terface functionality can run at full speed on a mobile host while large data manipulations may be performed on the wellconnected server All application code and all applicationtouched data are written as RDOs RDOs may exe cute at either the client or the server Each RDO has a home server that maintains the primary canonical copy Clients import secondary copies of RDOs into their local caches and export tentatively updated RDOs back to their home servers RDOs may vary in com plexity from simple calendar items with a small set of operations to modules that encapsulate a significant part of an application eg the graphical user in terface for an email browser Complex RDOs may create a thread of control when they are imported Rover clients use QRPC to lazily fetch RDOs from servers see Figure 20 When an application issues a QRPC Rover stores the QRPC in a local stable log and immediately returns control to the application If the application has registered a callback routine then when the requested RDO has arrived Rover will invoke the callback to notify the application Alternatively applications may simply block to wait for critical data although this is an undesirable action especially when the mobile host is J J When the mobile host is connected the Rover network sched uler drains the log in the background forwarding any queued QRPCs to the server When a Rover application modifies a locally cached RDO the cached copy is marked tentatively committed Updates are committed by using QRPC to lazily propagate the mutating operations to This allows the application to continue execution even if the mobile host is dis connected As shown in Figure 21 the Rover Toolkit consists of four key components the access manager the object cache clientside only the operation log and ACM Computing Surveys Vol 31 No 2 June 1999 Netw ork S cheduler Mobile Host Figure 219 the network scheduler Each machine has a local Rover access manager which is responsible for handling all interac tions between clientside and server side applications and among clientside applications The access manager ser vices requests for objects RDOs medi ates network access logs modifications to objects and on the clients side man ages the object cache Clientside appli cations communicate with the access manager to import objects from servers and cache them locally Serverside ap plications are invoked by the access manager to handle requests from client side applications Applications invoke the methods provided by the objects and using the access mana er make the changes globally visible by export ing them back to the servers Within the access manager RDOs are imported into the object cache while QRPCs are exported to the operation log The access manager routes invoca tions and responses between applica tions the cache and the operation log The log is drained by the network scheduler which mediates between the various communication protocols and network interfaces The object cache provides stable stor age for local copies of imported objects The object cache consists of a local pri vate cache located within the applica tion s address space and a global shared cache located within the access manag er s address space Clientside applica tions do not usually interact directly ACM Computing Surveys V01 31 No 2 June 1999 Rover component architecture with the object cache When a client side application issues an import or ex port operation the Toolkit satisfies the request depending on whether the ob ject is found in a local cache and on the consistency option specified for the ob ject Once an object has been imported into the clientside application s local ad dress space method invocations without side effects are serviced locally by the object At the application s discretion method invocations with side effects may also be processed locally inserting tentative data into the object cache Op erations with side effects also insert a QRPC into a stable operation log lo cated at the client Each insert is a synchronous action Support for inter mittent network connectivity is accom plished by allowing the log to be incre mentally flushed back to the server Thus as network connectivity comes and goes the client will make progress towards reaching a consistent state The network scheduler contributes to log transmission optimization by group ing operations destined to the same server for transmission and selecting the appropriate transport protocol and medium over which to send them Rover is capable of using a variety of network transports Rover supports both connec tionbased protocols eg HTTP over TCPIP networks and connectionless protocols eg SMTP over IP or nonIP networks The network scheduler lever ages the queuing of QRPCs performed ClientServer Computing in Mobile Environments 0 by the log to gain transmission effi ciency 532 Constructing Mobile Applica tions Using Rover There are several steps involved in porting an existing application to Rover or creating a new Roverbased application Each step re the application developer to make several implementation choices The first step is to split the application into components and identify which components should be present on each side of the network link The division will be mostly static because most of the file system components will remain on the server and most of the GUI compo nents will remain on the client How ever those components that are depen dent upon the l i network or computational resources or are infrequently used may be dynami cally relocated Once the application has been split into components the next step is to appropriately encapsulate the applica tion s state within objects that can be replicated and sent to multiple clients In migrating to the mobile environment the application s reading of files is re placed by importing of objects and its writing of files is replaced by exporting of changes to objects The file system interface still exists in the serverside of the application However inserted be tween the two halves of the application is an object layer One of the primary purposes of the object layer is to provide a means of reducing the number of network mes sages that must be sent between the client and the server this is done by migrating the computation The next step is to add support for interacting with the environment For example in an email message one of the important pieces of message meta data that a folder object contains is the message size and the size of any attach ments This information can be used by the application and conveyed to the user to allow useful decisions to be made Support for prefetching is another envi 151 ronment interaction issue Also the ap plication developer must decide which mechanisms to use for notifying users of the status of displayed data The final and important step is the addition of applicationspecific con ict resolution procedures For most station ary environments conflicts are infre quent For the mobile environment they will be more common Application developers can leverage the additional semantic information that is available with Rover s operationbased instead of valuebased approach to object updat i sion import export and invoke Client U call create session once with authentication information to set up a connection with the local access manager and receive a session identi fier The authentication information is used by the access manager to authenti cate the client requests sent to Rover servers To import an object an application calls import and provides the object s unique identifier the session identifier a callback and arguments In addition the application specifies a priority that is used by the network scheduler to reorder QRPCs The import function im mediately returns a promise to the ap plication The application can then wait on this promise or continue execution Rover transparently queues QRPCs for each import operation in the stable log When the requested object is received by the access manager the access man ager updates the promise with the re turned information In addition if a callback was specified the access man ager invokes it Once an object is imported an appli cation can invoke methods on it to read andor change it Applications export each local change to an object back to the servers by calling the export opera tion and providing the object s unique identifier the session identifier a call back and arguments Like import ex ACM Computing Surveys Vol 31 No 2 June 1999 152 0 J Jing et al port immediately returns a promise When the access manager receives re sponses to export it updates the af fected promises and invokes any appli cationspecified callbacks 533 Rover Applications Two mo biletransparent applications that have been implemented using the Rover Tool kit are Rover NNTP proxy a USENET reader proxy and Rover HTTP proxy a proxy for Web browsers Mobileaware applications implemented using Rover are Rover xmh an email browser Rover Webcal a distributed calendar tool Rover Irolo a graphical rolodex tool and Rover Stock Market Watcher a tool that obtains stock quotes Two of the mobileaware applications Exmh TclTkbased email browser Rover Webcal is a port of Ical a TclTk and C based distributed calendar and scheduling program writ ten by Sanjay Ghemawat Rover Irolo and the Rover Stock Market Watcher were built from scratch The Rover HTTP and NNTP proxies demonstrate how Rover mobileaware proxies support existing applications eg Netscape and xrn without modifi cation ie mobiletransparent applica tions Rover NNTP proxy Using the Rover NNTP proxy users can read USENET news with standard news readers while disconnected and receive news updates even over very slow links Whereas most NNTP servers download and store all available news the Rover proxy cache is filled on a demanddriven basis When a user begins reading a news group the NNTP proxy loads the head ers for that newsgroup as a single RDO while articles are prefetched in the background As the user s news reader requests the header of each article the NNTP proxy provides them by using the local newsgroup RDO As new articles arrive at the server the serverside of the proxy constructs operations to up ACM Computing Surveys V01 31 No 2 June 1999 date the newsgroupheader object Thus when a news reader performs the common operation of rereading the headers in a newsgroup the NNTP proxy can service the request with min imal communication over the slow link Rover HTTP proxy This application allows users of existing Web browsers to click ahead of the arrived data by re questing multiple new documents before earlier requests have been satisfied The proxy intercepts all web requests and if the requested item is not locally cached returns a null response to the browser and enqueues the request in the operation log When a connection becomes available the page is automat ically requested In the meantime the user can continue to browse already available pages and issue additional re quests for pages without waiting The granularity of RDOs is individual pages and images The client and server coop erate in prefetching The client specifies the depth of prefetching for pages while the server automatically prefetches in lined images The proxy uses a separate window from the browser to display the status ofa page loaded or pending If an uncached file is requested and the network is unavailable an entry is added to the window As pages arrive the window is updated to re ect the changes This window exposes the ob ject cache and operations log directly to the user and allows the user limited control over them Rover Exmh Rover Exmh uses three types of RDOs mail messages mail folders and lists of mail folders By using this level of granularity man user requests can be handled locally without any network traffic Upon start up Rover Exmh prefetches the list of mail folders the mail folders the user has recently visited and the messages in the user s inbox folder Alternatively using a finerlevel granularity eg header and message body would allow for more prefetching but could delay servicing of user requests especially ClientServer Computing in Mobile Environments 0 153 Summary of the Bayou system database appointment calendars evolving design documents news applicationspeci c adaptation to disconnection amp intermittent connectivity meeting room scheduler and bibliographic bulletin boards applications are permitted to make tradeoff of replicated data consistency amp Table System Bayou v v My 11 1 v Adaptation availability by using individually selectable session guarantee Model disconnected client architecture Mobile Data s collaborative and exible groupbased clientserver Architecture and full or system support for detection of update con icts applicationspecific resolution of update con icts eventual replica convergence through a peerwise antientropy process and perclient consistency guarantees during periods of disconnection Using a larger granularity eg entire folders would seriously affect usability and re sponse time for slow links Some computation can be migrated to servers For example instead of per forming a glimpse search of mail folders locally at the client and thus having to import the index across a potentially low bandwidth link the client can con struct a query request RDO and send it to the server The GUI indicates that an operation is tentative through color coding Con ict detection is based upon a log of changes to RDOs this allows the server to detect and resolve a con ict such as one user adding a message to a folder and another user deleting it Unresolv able con icts are re ected back to the user Rover Webcal This distributed calen dar tool uses two types of RDOs items appointments daily todo lists and daily reminders and calendars lists of items At this level of granularity the client can fetch calendars and then prefetch items using a variety of strate eg plus or minus one week a month at a time etc Rover Webcal uses color coding to aid the user in identifying those objects that have been locally modified but not yet propagated to a server Con ict de tection is based upon a log of changes to RDOs this allows the server to detect and resolve a con ict such as one user adding an item to a calendar and an other user deleting it Rover Irolo This graphical rolodex application uses two types of RDOs en tries and indices lists of entries The GUI displays the last time an entry was updated and indicates whether the item is committed or tentative Con ict de tection is based upon a log of changes to RDOs this allows the server to detect and resolve a con ict such as one user adding an entry to an index and another user deleting it Rover Stock Market Watcher This ap plication uses both computation migra tion and faulttolerance techniques The client constructs RDOs for stocks that are to be monitored and sends them to the server The server uses faulttoler ant techniques to store the realtime information retrieved from stock ticker services 54 Summary Tables I II and III summarize the three systems Bayou Odyssey and Rover used as case studies in this sec tion The tables highlight the applica tions each of these systems supports and the mobile clientserver computing strategies and techniques each of them has implemented 6 CONCLUSION With advances in wireless data telecom munications and portable computers nomadic users will soon enjoy Virtually unlimited access to information and ser vices anytime and anywhere There are ACM Computing Surveys Vol 31 No 2 June 1999 154 0 J Jing et al Table II Summary of the Odyssey system System Odyssey Applications le system access video playing and Web browsin Adaptation clientbased application adaptation with the system support that provides resource monitoring notifies applications of resource changes and enforces resource allocation decisions Model classic clientserver architectur Mobile Data e client pull based data distilled copies delivery Table III Summary of the Rover system Syste in Applications Adaptation r email appointments todo lists reminders calendars Web pages and ima es clientserver application adaptation with the use of Rover Toolkits that deal with intermittent and lowbandwidth connection and resourcepoor clients application transparent adaptation by using Model Mobile Data Rover proxies exible clientserver architecture with the use of RDOs asynchronous RDOs pull import and push export however obstacles and limitations inherent in the wireless environment The unpredictable mobility of the user adds a great deal of complexity to the problem Such obstacles render the tra ditional approach to designing and implementing clientserver applications insufficient in meeting nomadic users expectations Using assumptions linked to second generation wireless networks and to less than ideal mobile computers gen eral purpose portable computers with limited resources researchers realized that either application or system adap tation is a key requirement in any mo bile computing system Researchers also realized that they must identify and systematically eliminate the limitations of this new environment through vari ous optimizations This survey explores issues related to the development and deployment of adaptive mobile applications In particular it focuses on new designs and computing paradigms for mobile cli entserver applications It also reviews system architecture that supports such applications The survey identifies key characteristics that distinguish mobile clientserver computing from its tradi tional counterpart The survey also ex amines how these computing character istics impact information services and ACM Computing Surveys V01 31 No 2 June 1999 applications and discusses new comput ing paradigms that are required to deal with these impacts One contribution of this survey is a categorization of emerg ing computing paradigms for mobile cli entserver applications The mobile aware adaptation extended clientserver model and mobile data access are three categories that are explained and ana lyzed For each category examples that show the related design and implemen tation issues are detailed The survey also provides a comparative review of three major and ongoing research prototypes of mobile clientserver infor mation systems namely Bayou from Xerox Labs Odyssey from CMU and Rover from MIT These prototypes dem onstrate the applications of new com puting paradigms in building adaptive mobile clientserver systems and appli cations Mobile computing including mobile clientserver information access is a rapidly changing research field that de pends on a rapidly evolving set of tech nologies The advent of the socalled third generation wireless communica tion systems such as UMTS is an indi cation of the importance of research in this area Researchers however should monitor these advances closely and should adapt and direct their research based on the parameters of the latest ClientServer Computing in Mobile Environments 0 technology This is important because some of the strong assumptions regard ing the limitations of the wireless net work or the mobile computer are being relaxed or nullified by newer technolog ical developments Many problems still remain to be un posed models and techniques because of the lack of available application experi ences and samples Experimentation with these models should be the critical next step in mobile computing research We hope that this comprehensive re view will help enhance the understand ing of the opportunities and limitations of mobile clientserver computing We also hope that the review substantiates the importance of recognizing and un derstanding emerging technologies in shaping the future directions of re search in this area REFERENCES ACHARYA SI ALONSO RI FRANKLIN MI ZDONIK S 1995 Broadcast disks management for asymmetric communication environments In Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data SIGMOD 95 San Jose CA May 23725 1995 MI Carey and D Schneider Edsi ACM Press New York NY 19972109 ACHARYA SI FRANKLIN M AND ZDONIK S 19979 Balancing push an pull for data broadcasti SIGMOD Rec 26 2 18371949 BARBARA D AND IMIELINSKI T 19949 Sleepers and workaholics Caching strategies in mobile environments In Proceedings of the 1994 ACM Conference on SIGMOD Minneapolis MN May ACM Press New York NY 17129 BARTLETT Jr 1994 W47The wireless world wide the ZIst International Computer Software and Applications Conference COMPSAC 97 IEEE Computer Society New York NY 5737 5 I BREWER El KATz RI CHAWATHE Yr GRIBBLE SI HODEs TI NGUYEN E M M HENDER SON T AMIR PADMANABHAN VI ESHAN S 19989 A network architecture for heterogeneous mo 155 bile computing IEEE Personal Commun 5 5 8724 BROOKS CI MAZER MI MEEKS 8 AND MILLER J 19961 Applicationspecific proxy servers as HTTP stream transducers In Proceedings of the 4th International World Wide Web Confer ence WWW4 CHANG HI TAIT CI COHEN NI SHAPIRO MI MAs TRIANNI SI FLOYD RI HOUSEL B AND 1997 Web browsing in environment Disconnected re rocee ACMIEEE International Conference on Mor bile Computing and Networking MOBICOM 97 Budapest Hungary Septi 26730 1997 LI Pap KI Sohraby D B Johnson and CI Rose Edsi ACM Press New York NY 2607 269 CITRIX 19989 httpwwwicitrixicomi COM THTML 19989 httpwwwIWSIorgsub mission1998 04 DAVIS NI FRIDAY AI WADE 8 AND BLAIR G 19989 L2imbo A distributed systems platform for mobile computing Mobi Netwi Appli 32 14371569 DEMERs AI PETERSEN KI SPREITZER MI TERRY DI THEIMER M AND WELCH B 19949 The Bayou architecture Support for data sharing 39 In Proceedings of the tems an pplications Cruz CA IEEE Press Piscataway NJ DURAN J LAU39BACH 19999 Virtual per I sonal computers and the portable network Press Los Alamitos CA ELMAGARMID AI JING Jr AND BU39KHRES O I efficient and r liable reservation algorithm for mobile transactions In my ceedings of the 1995 International Conference on Information and Knowledge Management CIKM Baltimore MD Novi 287Deci 2 1995 NI Pissinou AI Silberschatz El KI Park KI Makki and CI Nicholas Edsi ACM Press New York NY 90 7959 FOX AI GRIBBLE SI BREWER El AND AMIR E 19 Adapting to network and client varia tion via ondemand dynamic distillationi In Proceedings of the 7th International Conferr c on Architectural Support for Programr ming Languages and Operating Systems AS PLOSVII Cambridge MA Oct 175 1996 B Dally and SI Eggets Edsi ACM Press New York NY GENERAL MAGIC INCI 1997 Odyssey Product Information httpdwwwigenmagicicom agentsodysseyihtmli GRAY RI 9959 AgentTcl Atransportable agent system In Proceedings of the CIKJW Workr shop on Intelligent Information Agentsi HDML 1997i httpdwwwiuplaneticomi ACM Computing Surveys Vol 31 No 2 June 1999 156 0 J Jing et al HEIDEMANN J PAGE T GUY R AND POPEK G 1992 Primari y disconnected operation EX perience with Ficus In Proceedings of the 2nd Workshop on Management of Replicated Data Monterey CA Nov HERMAN OPAL EE K AND WEINRIB A Datacycle architecture for very high May 2729 1987 U Dayal Ed ACM Press New York NY HONEYMAN P HUSTON L REES J AND BACH MAN D 1992 The LITTLE WORK project In Proceedings of the 3rd Workshop on Work station Operating Systems Key Biscayne FL HOUSEL AND LINDQU39IST D B 1996 WebEXpress A system for optimizing Web browsing in a wireless environment In Pror ceedings ofthe 2nd Annual International Conr ference on Mobile Computing and Networking MOBICOM 96 Rye New York NoV 10712 1996 H Ahmadi R H Katz 1 F Akyildz and Z J Haas Eds ACM Press New York NY 1087116 IBM TOKYO RESEARCH LABS 1997 The Aglet Workbench Programming Mobile Agents in Java httpWwwwtrlibmcojpaglets IMIELINSKI T AND BADRINATH B R 1994 Mobile wireless computing Challenges in data managemen Commun ACM 37 10 Oct 1994 18728 IMIELINSKI T VISHWANATH S AND BADRINATH B Energy ef cient indexing on air Proceedings of the 1994 ACM SI GM 0D I nterr national Conference on Management of Data SIGMOD 94 Minneapolis MN May 24727 1994 R T Snodgrass Winslett Eds A M Press New York NY IMIELINSKI T VISWAN HAN S AND BADRINATH B 994 Power ef cient filtering of data In Proceedings of the Fourth Internar tional Conference on Extending Database Technology Advances in Database Technology EDBT 94 Cambridge UK Mar 28731 1994 M Jarke J Bubenko and K Jeffery Eds Proceedings of the Second Symposium on Advances in Spatial Databases vol 779 SpringerVerlag New York NY 2457 58 JAIN R AND KRISHNAKUMAR N Service handoffs and virtual mobility for delivery of personal information services to mobile users Technical Report TM24696 Bellcore NJ JING J ELMAGARMID A AND ONSO R 1997 Bitsequences An adap tive cache invalidation method in mobile cli entserver environments Mob Netw Appl 2 2 1157127 JOSEPH D AND KAASHOEK M F 1997 Building reliable mobileaware applications using the Rover toolkit Wireless Networks 3 5 4057419 ACM Computing Surveys V01 31 No 2 June 1999 JOSEPH A D TAUBER J A AND KAASHOEK M F 1997 Mobile computing with the Rover tool IEEE Trans Comput 46 3 3377352 KATZ R 1994 Adaptation wireless information systems sona ommun 7 KISTLER J J AND SATYANARAYANAN M 1992 Disconnected operation in the Coda File Sys tem Trans Comput Syst 10 1 Feb 1992 3725 KOJO M Kw I AND ALANKO T 1994 Connecting mobile workstations to the internet over a digital cellular tele phone network In Proceedings of the Mobir data Workshop Rutgers University Press New Brunswick N KRISHNAKUMAR N AND JAIN R 1994 Protocols for maintaining inventory databases and user I Proceedings t obi ata rk Shop Rutgers University Press New Brun swic KUENNING G H AND POPEK G J 1997 Automated hoarding for mobile comput ers ACM SIGOPS Oper Syst Rev 31 5 2647275 KUMAR P SATYANARAYANAN M Supporting applicationspecific resolution in an optimistically replicated file system In Proceedings of the 4th Workshop on Workstar tion Operating Systems Napa CA Oct LE M SESHAN S BURGHARDT F A RABAEY J 1994 Software architecture of the InfoPad system In Proceedings f the Mobidata Workshop on Mobile and Wireless Information Systems Rutgers NJ Nov MU39MMERT L AND SATYANARAYANAN 1994 Large granularity cache coherence in the coda file system In Proceedings of the USENIX Summer Conference Boston Mass USE X Assoc Berkeley CA NARAYANASWAMY ET AL 1996 and network support for InfoPad sonal Commun 3 NOBLE 3 PRICE M AND SATYANARAYANAN M 1995 A programming interface for ap plicationaware adaptation in mobile comput ing In Proceedings ofthe 2nd USENIX Symr posium on Mobile and Locatioanndependent Computing NOBLE B D SATYANARAYANAN M NARAYANAN D TILTON J E FLINN J AND WALKER K R 1997 Agile applicationaware adapta tion for mobility ACM SIGOPS Oper Syst Rev 31 5 2767287 PITOURA E AND SAMARAS S 1998 Data Many agement for Mobile Computing Kluwer Aca demic Publishers Hingham SATYANARAYANAN M Accessing informa tion on demand at any location mobile infor mation access EEE Personal Commun 3 Application I EEE Perr SATYANARAYANAN M KISTLER J J KUMAR P OKASAKI M E SIEGEL E H AND STEERE D