Wei-Hsing Lee, Dominik Buszko

Abstract: This paper examines how the limitations of mobile devices pose new challenges to the application developer and the techniques used to solve these problems. Applications that have utilized these techniques indicate the feasibility in producing useful applications on a resource-limited system. Although feasibility is no longer an issue, system cost and performance has hindered the acceptance of this computing model.

Introduction: The differences in the mobile environment and standard wired connections impose great challenges on the application developer. Certain constraints inherent to mobile computing are resource limitations of the hardware, availability of the mobile host, and bandwidth limitations. Two main resources restrict the rest of the hardware system, mainly battery power and weight limitations. Powerful processors tend to use more watts than a low powered system. If a more powerful processor is chosen, then the power source must also be upgraded. To increase the supply of power, the weight and portability of the system will have to be compromised. Today’s mobile devices use either NiCad or lithium ion technologies. There will not be a dramatic improvement in either of these in the foreseeable future. Availability refers to the frequency of disconnection due to battery limitations, voluntary or involuntary shutdown, and connection coverage. Wireless connections are bombarded with interference from other appliances such as cellular phones, microwaves, atmospheric conditions, etc. Low bandwidth in the wireless model is prevalent. Lost packets due to handoffs and bad carrier signals all require special adaptive protocols to cope with these adverse environmental conditions. Of the limitations presented, the only aspect that an application programmer can deal with, but not control, is low bandwidth. Disconnection due to other causes, such as power, coverage, etc. is out of the application programmer’s domain. State recovery and reduction on bandwidth requirements are the major focus of mobile application developers.

Applications developed for the fixed network environments often do not place major emphasis on bandwidth reduction and state recovery. Fixed applications can count on an unlimited power source and high-powered processors. Also, disconnection is not a normal behavior, but rather the exception. Needless to say, fixed applications can offer more features, and higher reliability at a lesser cost than mobile apps.

Adaptations: Two extremes, the application-aware adaptation and the system-aware adaptations, characterize the strategies used to come with mobile limitations. Within these two extremes, lies a collaborative adaptation strategy in which both the system and application contribute. Each method has its advantages and disadvantages. See Figure 1.

Application-aware adaptations assume the application itself, is responsible in coping with frequent disconnection, lost packets, low bandwidth, etc. In this case, there is no system support for the mobile environment. Increases in efficiency resulting from a more specific adaptation protocols are the advantages of this model. The system can be left intact, with no change, since the responsibility is totally shifted to the application side. There may be difficulties however, in implementing application-side adaptations without system support resulting in inefficient workarounds for many problems. Another disadvantage of the model include increased development costs since every application, either existing or new applications, will require a unique protocol.

System-aware adaptations assume the system itself is responsible in coping with the mobile environment, leaving the applications unaware. One of the major advantages in shifting responsibility to the system is that existing software does not need to be modified and should execute fine. These applications, originally developed for a fixed network, can be left untouched. This reduces the number of protocols needed, by allowing them to be domain specific rather than application specific. This model, however, does have its limitations as well. The main problem is trying to implement efficient adaptations using general protocols rather than specific protocols. It may not be possible to implement all the adaptations on the system side since many of the limitations of the mobile environment may be application specific. As with the application-aware adaptation model, workarounds may be inefficient or impossible.

Collaborative adaptations distribute the requirements to both the system and the application. Adaptations of this nature allow for the most efficient possible implementation resulting in more robust applications as well as increased user acceptance. The system provides support for the mobile-aware applications in providing special services not available to the application-aware model. The system is also not burdened with the protocols that are too general to be of any use, since the application is aware of the environment. The problem with this model is the level of cooperation required between system developers and application developers in creating protocols acceptable to both groups. Also, an increased development cost may be initially incurred since adaptations are required at both ends.

Three of the most crucial characteristics a mobile application should avoid are blatant bandwidth consumption, unrecoverable disconnection, and high latency. The former two are the easiest to control and adapt to. High latency may be a byproduct of the hardware in the wireless network and of the mobile device. By preventing the first two characteristics, the latency of the application can be reduced. In a wired network, the bandwidth is not a paramount concern for application developers, but in mobile environment, reduced bandwidth consumption could mean the difference between an acceptable and useable application or a failed attempt. Several techniques have been developed to cope with these limitations. These techniques "cope" but do not solve the problem as many of them compromise many of the extended features of the application. Connection quality affects bandwidth availability. During "clean" connections, the mobile application should provide services reflection the connection quality. Adaptation on-the-fly is important in this sense.

Most collaborative groupware provide a "What You See Is What I See" interface. WYSIWIS interface requires continual updates resulting in bandwidth intensive applications. A mobile application can ill afford to indulge in this overhead. Incremental updates implement a "What You See Is Eventually What I See" interface. WYSIEWIS can dramatically decrease the bandwidth requirement for the Graphical User Interface (GUI), freeing up additional bandwidth for critical messages – what is critical is application dependent of course. The frequency of the updates can be application specific and adjusted on-the-fly according to the quality of the connection.

Another viable option is to reduce some of the features and create a simplified GUI as illustrated in Figure 2. The theory behind feature restriction is a belief that a less complete or less feature-rich interface generally will require less bandwidth to update. A careful line must be drawn between necessary features and extraneous features. Again, this is something that can be adapted on-the-fly according the quality of the connection and the bandwidth available.

Implementing a more efficient concurrency control mechanism provides yet another method in reducing bandwidth requirements. An additional concern in concurrency controls of mobile applications is fault tolerance. A mobile application exists in a very unreliable environment. Special consideration should be provided in removing single-point of failure. Even under ideal circumstances, this requires replication of the control mechanism and an increased overhead in communication. Mobile application developers must regard disconnection as frequent occurrences as opposed to a rarity.

Mobile hosts are often disconnected due to lack of service coverage and battery limitations. Since a mobile device spends most of its time disconnected, a different development model must be chosen. In the disconnected mode of operation, the mobile device may want to provide "connected" functionality to the user. This requires the mobile host to act like a server resulting in an extended client-server model. Techniques in read-ahead pre-fetching and caching optimizations help make this model possible. Cache coherency strategies incorporated in the application help reduce conflicts. Such strategies include semantic callbacks and the use of validators. Not only does this provide a performance boost by decreasing latency, but also it aids the system in portraying a connected environment to the user. Upon involuntary disconnection, the state of the application cannot be lost since this poses a great inconvenience and cost on the mobile host.

State recovery and backup systems need to be incorporated in wireless collaborative groupware. Since user initiated backup may not be sufficient for such an unreliable environment, automatic backups should be implemented. Again this is adaptable on-the-fly according to the network connection quality. During poor connections, the backup system could increase the frequency saves are performed. Good network connections will not have the disconnection frequency of poor connection, thus an increase in the granularity of backups is appropriate.

In this section we examine few case studies in which applications were specifically adapted and optimized for use in mobile environment.

Calliope

Calliope is a multi-user text editor developed by Tara Whalen and James P. Black from University of Waterloo. The main feature of Calliope is that it provides adaptability, which allows the application to take advantage of favorable network conditions and to react to difficult conditions as they occur. This solution uses the application-aware paradigm where only the application is aware of the mobility. Whalen and Black propose several strategies that make groupware application more suitable for mobile environment. These strategies were applied to several of Calliope’s features and as a result significantly improved its performance.

Telepointer and Scrollbar. Telepointer is intended to provide awareness of other users’ actions, by showing the movement of each user’s mouse pointer in a document. However, due to frequent updates this feature requires a significant amount of bandwidth that is generally not available in a mobile environment. A few strategies can be applied in order to improve application’s performance in this area. This can be achieved by decreasing the frequency of updates, which will result in the decrease of needed bandwidth with a minimal impact on usability. In some cases, when the available bandwidth is really low, instead of scaling back, this feature could be disabled altogether. Since telepointer is not a vital feature of this particular system, the user’s awareness can be sacrificed in order to maintain the overall usability of the application. Similarly, the scrollbar is also used to increase the users’ awareness of other participants. It is used to track the location of users in the document. This feature can also be optimized for mobile environment by reducing the frequency of updates. For example, when a user scrolls through a large document there is no need to send the location update after each page, since other users are not interested in the intermediate screens. Instead, the final update should be sent only after the user has reached the final destination in that document.

Keystroke Updates. Ideally, groupware applications should try to maintain WYSIWIS (What You See Is What I See) interface, and broadcast the changes to other participants as soon as it is possible. However, doing so requires a significant amount of bandwidth which is further exaggerated due to the overhead resulting from the inherent design of the underlying transport layer (in this case TCP/IP protocol). For example an update of a single character (1 byte of data) in a shared document requires sending around 217 bytes of data. By decreasing update frequency a significant amount of that bandwidth can be saved. With decreased update frequency the changes performed by the client are buffered. Only when the buffer becomes full, the update is propagated to other participants. This adaptation should be performed automatically by the application, so that the best update frequency is used for the given network conditions. The quality of the connection will also dictate the size of the buffer that can be changed on the fly to reflect the changing network conditions. With a fast and reliable network the buffer should be as small as possible so that the changes in the document are quickly broadcast to other clients. As the connection quality deteriorates the size of the buffer should increase and adapt to the decreased bandwidth. This approach uses the WYSIEWIS paradigm. The tradeoff with this approach is that the updates are not immediately visible to other users who could try to modify the same part of text. To avoid having to implement conflict resolution algorithms, each user can be required to first acquire a lock on the part of text that needs to be modified to ensure an exclusive access to that part of the text. This way with slow networks the user will not become frustrated by having to wait until each update has been propagated. With such implementation there is also a need to have a periodic timeout value for the updates so that in case an update that doesn’t fill up the buffer entirely is still propagated after a certain period of time. All of the adaptation process should be completely transparent to the user – the application itself monitors the connection quality and adjusts accordingly. However, more advanced users who desire more control of the application, should be also given a choice to voluntarily propagate any updates, so that the user is not completely dependent on the application.

Concurrency control. Concurrency control allows users to acquire an exclusive access to selected part of text. Calliope supports four level of concurrency control: selection, word, line, and paragraph. In a mobile environment concurrency control has to deal with the following issues: lock management, bandwidth, and disconnections. Since the mobile environment is highly unreliable a solution that introduces a single point of failure must be avoided at all cost, so that the system is fault-tolerant. Therefore, instead of using a centralized lock manager, the lock management should be replicated among the participants. This way each client has its own copy of all the locks currently held, so that when one of the clients becomes disconnected it doesn’t disrupt the entire collaborative group. The strategy to reduce the traffic is to use highly pessimistic concurrency control – meaning that a requested lock is usually bigger than it has to be. For example instead of requesting a lock on two lines of text, which would result in two separate lock request, a request can be made for the entire paragraph containing those two lines, which would result in only a single request. Another issue is that the application must be able to gracefully deal with frequent disconnections of users who are currently holding a lock. Any lock that is being held by a client that’s no longer a part of the group should be releases as soon as possible.

Document Overview. In certain situations a group might collaborate on a large document, but in reality only use a small subset of that document (for example a single chapter from a multi-chapter document). In such case, the application can be optimized so that only each client downloads the part of the document that is currently needed. This could result in significant saving of the bandwidth. Another advantage of such approach is that it reduces the amount of data that needs to be temporarily stored on the client, which is especially important with mobile clients since they usually have limited resources in this particular area.

Another example of implementing an application-aware system is the dynamic documents project by M. Frans Kaashoek, Tom Pinckney, and Joshua A. Tauber from MIT Laboratory for Computer Science. They have proposed to use dynamic documents as a way to extend and customize web browsers for mobile environments. The idea behind this concept is to modify the browser such that it runs the dynamic documents – programs executed on a mobile client to generate a document – that are retrieved through an interpreter. Kaashoek, Pinckney, and Tauber believe that information retrieval is going to be of primary interest to a mobile user, and therefore an emphasis should be placed on trying to retrieve and present as much information as possible given the limited resources of mobile environment. However, this assumption might not necessarily be valid if we consider a collaborative group setting where providing retrieving and sharing information is equally important.

As mentioned before, mobile environment and mobile clients suffer from several limitations such as low bandwidth, poor network conditions, and lack of resources such as CPU, disk, or memory. Current implementations of popular web protocols such as HTML are highly inflexible and they assume a high-quality and fast network connection. As a result when trying to access resources that are optimized for wired networks using a mobile client the results are usually highly unsatisfactory. One of the problems is that mobile clients have difficulty dealing with the multimedia-rich content, so prevalent in wired environment. As a result mobile users quickly become frustrated trying to access such information. Dynamic documents are supposed to alleviate this problem, by interpreting the data and adapting it to the available resources and the environment. In this implementation the dynamic documents are implemented using Tcl scripts, which actually generate the information that is eventually displayed to the user. For example with high-bandwidth network and plethora of available resources, the interpreter generates context-rich documents with feature-rich interface. However, if the bandwidth is limited and the resources are scarce, the generated documents are scaled down versions of the original documents that sacrifice the appearance of document for the sake of usability. Such features as elaborate graphics, flashy animations and sounds, which usually serve no purpose other than being an "eye-candy", are replaced with a scaled down, more robust version that maintains most of the usability of the original document. This usually means trying to format the document so that it provides the most readability given the limited viewing capacities. However, this approach has a significant drawback. Since all the information must go through an interpreter, the result is that all the document processing is performed on the client. As we know, in a lot of cases the mobile client has very limited CPU power. As a result the actual improvements might not be as significant as originally thought, especially for low-powered devices. We also have to remember that whenever we rely on the mobile client for computation, we not only increase the response latency, but also increase the power consumption, thus reducing the availability of the mobile client.

Another improvements discussed by Kaashoek, Pinckney, and Tauber is the use of caching, hoarding, and prefetching in order to fully optimize the performance of mobile applications. Caching is an effective technique for improving the interactive response of the system. This however assumes that the mobile client has the resources available that allow for an effective implementation of a cache. In this design a session-persistent cache is maintained on each client. Whenever, a request is made the cache is first checked to see whether such document might have already been accessed recently. Only if no such document is found the connection to the outside host is attempted. Another technique for improving the interactive performance is prefetching. The idea behind this concept is to try to predict what resources the user will access next, and try to cache them before the actual request is issued. However, it has been determined that in reality such approach provides very little, if any, improvement in an interactive performance. The problem is that currently there are no good algorithms that would successfully predict the users’ behavior. As a result the majority of prefetched pages are never used. In addition prefetching introduces another problem – excessive bandwidth utilization. Prefetching works under a principle that pages are prefetched only when the user is not using the network resources, and prefetching is suspended as soon as the user tries to use the network. However, with mobile environment several users often share the bandwidth, as in the case of access points in wireless LAN’s. In those situations prefetching actually might take the resources away from other users. Since, prefetching appears to be highly ineffective at the present time, the bandwidth is effectively wasted. Finally, hoarding can be used to prefetch and cache some documents in order to prepare for imminent disconnection from the network. This concept can be useful in network with frequent disconnections, so that whenever a connection is available the hoarding can prepare the user for an upcoming network outage whether planned or unplanned.

WebExpress

WebExpress is a system for optimizing web browsing in a wireless environment. The idea behind it is that the bandwidth requirements can reduced by using an interception technology that is completely transparent to the application (in this case a web browser). As such WebExpress is an example of system-aware paradigm. It improves the performance of the underlying HTML protocol – which is the most prevalent protocol used by modern browsers. In addition to the overhead introduced by the design of TCP/IP protocol, the use of HTTP protocol brings other issues to light. One is the costly connection overhead, which results from the need to set up a network connection every time an object (in this case a page, image, etc.) needs to be accessed. So for example if a given page contains seven graphics object, for each of those object a separate connection needs to be set up. Another issue is that by design HTTP protocol is a stateless protocol, meaning that with each connection the state information (such as browser type, browser’s capabilities, etc.) must be transmitted. Since the state information for the most part remains the same (the users don’t change their browsers halfway through the session). It is evident that the overhead quickly adds up and constitutes a significant part of the network traffic. The final limitation is that HTTP requests are encoded as human-readable ASCII code instead of more efficient binary code, which results in greater bandwidth requirements.

To alleviate the mentioned problems WebExpress optimizes many aspects of the HTTP protocol. WebExpress actually intercepts and controls all the communication over the link, resulting in decreased traffic volume and improved latency. There are actually two Intercepts – one at the client site called Client Side Intercept (CSI) and one at the server side called Server Side Intercept (SSI). These intercepts are completely transparent to the mobile application and therefore it enables us to use the existing applications without the need to adapt them to a mobile environment. WebExpress uses several ingenious mechanisms that allow it to significantly improve the performance of the mobile connection. One is an extensive use of session-persistent caches. In this case each CSI and SSI posses their own cache. This allows WebExpress to reduce unnecessary network traffic, by retrieving from the cache the information that changes infrequently. Another optimization solution is differencing. The idea behind this concept is that a different reply from the same program (a server-side CGI script) usually contains significant amount of elements common to all documents. Instead of resending all that information with each transaction, WebExpress established a base document that contains all the elements that are common to all transactions. Then when an actual transaction is invoked only the information that’s unique to that transaction is transferred to the client where it is combined with the base document to produce the final document. Yet another optimization implemented in WebExpress is protocol reduction. Protocol reduction solutions significantly reduce the amount of data transferred by effectively reducing the overhead of multiple TCP/IP connections. In a conventional HTTP protocol each request for a resources whether a page or a graphics object requires a separate socket connection. Once the transfer of data is complete the socket is closed and retrieving another object requires another setting up another connection. This process of opening and closing sockets requires significant amount of bandwidth that’s needed for setting up a connection and transferring state information. WebExpress gets around this problem by establishing a persistent TCP connection between CSI and SSI that is used to serve several actual requests simultaneously. With such an approach the client application still opens several socket connection, but those connections are actually intercepted by CSI and merged together into a single persistent connection. This way WebExpress correctly maintains the behavior of HTTP protocol with respect to applications, but at the same time significantly improves its performance.

As can be seen from the above examples WebExpress illustrates excellent implementation of system-aware approach. By simply modifying the underlying protocol, an application that’s has been previously not suitable for mobile environment can now be effectively used without any modifications.

Location Awareness

With an increasing number of handheld, PDA’s, and other mobile devices, applications are beginning to take advantage of the mobility of these systems. As devices become smaller, lighter, and easier to use, real world practicality increases. Although these devices do have their limitations, mobile devices do offer advantages over fixed network devices. The main feature applications need to harness the power of is the portability, and mobility available. By providing location-awareness, applications can be developed to provide real-time database queries, returning concise and pertinent data. Access protocols and data models have been created and adapted to take advantage of this new functionality, mainly the X.500 directory access protocols for retrieving attribute-value-pair information. Various scenarios have been envisioned in which location-aware applications running on mobile devices cannot be replicated in a fixed network. This type of functionality may be exactly what a mobile "Killer App" takes advantage of.

Conclusion: In the last few years a new technological trend has emerged, mobile computing. System cost and performance has introduced a relatively unreliable computing environment with which the current crop of applications is poorly suited for. Such adverse conditions in the wireless environment require new, innovative computing models to be developed. Techniques, currently under development to cope with the limitations of a wireless network, have been moderately successful, but the limitations of wireless networks are still reflected in the applications. Mobile application developers are striving to bring the functionality and stability of fixed network applications to the mobile devices as well as creating the "Killer App" that cannot be replicated in a wired environment.

1. M. Satyanarayanan, "Fundamental Challenges of Mobile Computing", ACM Symposium on Principles of Distributed Computing, 1995 (PODC'95 invited lecture)
2. T. Whalen, J. P. Black, "Adaptive Groupware for Wireless Networks," University of Waterloo - Department of Computer Science.
3. Barron C. Housel Ph.d, David B. Lindquist, "WebExpress: A System for Optimizing Web Browsing in a Wireless Environment", MOBICOM 96, Rye NY USA, 1996 ACM.
4. Abdelsalam (Sumi) Helal, Jin Jing, Ahmed Elmagarmid, "Client-Server Computing in Mobile Environments", University of Florida, 1998.
5. M. Frans Kaashoek, Tom Pinckney, Joshua A. Tauber, "Dynamic Documents: Mobile Wireless Access to the WWW", Proceedings of the IEEE Workshop on Mobile Computing System and Applications, Santa Cruz, CA, 1994.