|
CS632 Survey Paper Database Technology for Mobile Ubiquitous Computing |
|
Rimon Barr Cornell University barr-AT-cs.cornell.edu |
Introduction
Ubiquitous computing could be a reality today. Hardware with various degrees
of performance, capabilities and price already allow sophisticated
disconnected and mobile operation. Also stationary desktop personal computers
and smart consumer electronic devices exist, often connected to networks, in
great abundance. Yet ubiquitous computing, the ability to interact with a
single encompassing environment via multiple devices, which has been
forecasted for at least ten years, remains elusive.
In this paper I will discuss some of issues of ubiquitous computing by highlighting aspects of prior research. The body of research is vast and spans multiple areas. My focus will be on the data management issues in mobile systems, where system includes the mobile devices as well as the enabling infra-structure. On a superficial level, one can consider the devices as interfaces to data, perhaps allowing modifications and updates. The data represents the user environment, or a portion thereof, and must be propagated to these devices as needed. When viewed this way, we may begin to uncover research questions in the areas of distributed systems, databases and networking, and discuss how mobility affects the traditional tradeoffs and when they are no longer appropriate.
The purpose of this paper is to explain how mobile computing differs from regular networked distributed systems, and how this affects applications, specifically data dependent (database) applications, expected to work efficiently and effectively within this environment. The paper then continues to survey selected prior work in the area of databases, distributed systems and networking that addresses some of these issues.
Most of this work is concerned foremost with the efficient dissemination of information within a mobile architecture and does not yet address the more lofty goal of creating a ubiquitous user environment.
A typical mobile system
Since mobile computing is relatively new only few systems have actually been
built and most are only at the prototype stage. However, these prototypes have
been built using vast engineering knowledge from the telephone, cellular and
various data packet networks. The description below of a typical mobile system
is based on information in [Dat99, Imi94b, For94].
The classic mobile architecture is described as having a myriad of mobile battery-powered computation devices roaming within a mobility domain. This domain is, for communication purposes, divided into regions known as cells.
Each cell contains a base station that is used to transmit information to the devices and possibly receive information from them. The dimensions of the cell are determined largely by the communication requirements parameterized by aspects such as signal strength and bandwidth capacity. Each base station is stationary and connected via wires, or at least via some high bandwidth, persistent connection, to other points in the infrastructure. There may be other machines within the infrastructure, called fixed hosts, that perform management functions, but do not communicate directly with devices. Satellites are also being considered as possible base stations, but they are not stationary. This adds an extra degree of complexity as routing must now contend with a moving base station, or equivalently a moving cell.
Devices are free to roam freely among cells of the mobility domain, but it is assumed that inter-cell movement is a relatively infrequent event compared to communication time. Naturally, moving cells will increases the number of these inter-cell events dramatically.
Most mobile devices are characterized as palm-tops or lap-tops with communication devices ranging from infra-red ports to radio modems. The communication specifications of the domain determine which devices are capable of functioning within it. Most devices are assumed to support the ability to conserve energy by switching certain subsystems into an sleep state, specifically the transceiver and processor.
Fundamental differences of mobile computing
Numerous papers [Sat96, Bad93, For94, Alo93] discuss the differences between
mobile systems and traditionally networked distributed systems from various
perspectives. Fundamentally, mobile devices are resource constrained. The
capability and performance of these devices continues to improve, but they
will always lag behind devices that are stationary.
Most significantly, mobile devices must be sensitive to power consumption. The amount of power between recharging is finite, and can usually support only a few hours of active use. Applications running on these devices must be aware of the cost of device activity and manage energy expenditure. Most current applications do not incorporate device activity into the cost model, and optimize rather for running time.
Furthermore, devices will always lag, for reasons including ergonomics, power, weight and size behind state-of-the-art in the areas of memory and disk capacity and processor speed. Applications must also be conscious of these constraints.
Mobile devices may be constrained in terms of the input and output capabilities. Some devices have no keyboard and rely on pen-based or touch-screen input. In future, devices may commonly rely on voice and perhaps other sensory input. Often mobile devices also have reduced output display capability. Many devices are task-specific, very unlike traditional desktop computers.
Mobile devices, much more-so than stationary devices, are prone to damage and loss. The information on these devices should therefore be dispensable. Mobile devices should employ mechanisms to synchronize with the infrastructure, and act only as second class caches of data.
Mobile communication is relatively unreliable, may fluctuate greatly in performance, may be punctuated by short or long periods of disconnection and is of low capacity. This can greatly affect the response time, efficiency and utility of a device. Many networking protocols will not run well over this communication fabric and must be redesigned. Also, applications must be structured to work around disconnection as seamlessly as possible. Techniques such as compression, broadcast, caching, pre-fetching and logging are discussed later.
Communication is also asymmetric in that transmitting is usually more costly than receiving data. Furthermore, receiving data and even monitoring the channel also constitutes device activity, usually requiring both transceiver and processor activity and must be minimized. These factors, along with the fact that wireless bandwidth is very expensive, place a great importance on communication, which must be incorporated into application cost models. However, bandwidth management must be considered together with energy management.
Security is important in any distributed environment. It is of added importance in a mobile distributed environment, because the communication medium is more accessible and authentication is difficult. Mobile systems must be able to detect and stop attacks and user impersonation. When employing cryptographic methods the power consumption of the client must be taken into account and key management becomes a tricky.
Communication is further complicated by mobility itself. Some form of location management is required in order to facilitate routing of communication along the fixed network to and from the shortest wireless hop. Furthermore, clients may be switched on at locations topologically distant from the location at which they were last seen. In mobile environments the frequency of routing modifications increases requiring modifications to traditional networking algorithms at the infrastructure level. The cost of communication between clients must include the wireless as well as the wired communication cost.
Problems such as the above are compounded by the fact that mobile devices are expected to be far more numerous than current desktops. This requires the infrastructure to be built in a scalable, distributed, fault-tolerant manner.
Finally, with additional location information we can envision creating applications that location-aware. Currently, there is very little support for location-aware applications. The closest parallel is a laptop docking station, a modem internet connection and plug-and-play technology which affect various operating system subsystems and devices, but applications only at a very superficial level.
Application adaptation
Due to the fluctuations possible in the mobile environment, an application
must be capable of adaptation. Current applications fall into two categories.
The first class of applications are those that are self-reliant and function
well in a disconnected setting. These applications, if they communicate with
other computers at all, do so as a peripheral feature that can be left unused
when connectivity is unavailable. They are highly dependent on local state,
which is definitely not ubiquitous. The second class of applications contains
those that are designed to depend on a tight coupling with a server. The
client in these applications may be quite thin. More importantly, using the
server we can share environment and user state among applications and
computers, however if the server fails or communication with the server is
severed, the application can not function. The applications running on mobile
devices should be hybrid and incorporate the best of both these strategies by
using centralized state, but allow disconnected, independent operation.
In [Sat96], a spectrum of adaptation strategies is presented. On the one hand device operating systems could be built to abstract mobility constraints from the applications. The drawback in this approach is that the operating system may take action inappropriate or inefficient for the application context and application dependencies. On the other hand, applications could handle mobility constraints independently in a laissez-faire approach. The drawback here is that central arbitration and fairness are not possible. It is proposed that most applications be designed to collaborate with the device operating system, and for this a reasonable type and level of abstraction is needed. The paper also proposes an extended client-server model, where both the client and server have cooperating pieces of the traditional client and server. The details of these pieces is application specific and a proposed topic of research. It is clear that mobile applications require different design criteria, models and measurements.
In [Imi94b] the opinion is expressed that horizontal applications for mobile devices fall into two categories: mail-enabled applications and information services. According to the authors, mail-enabled applications will constitute the core of mobile computing applications, allowing users carrying devices to generate and read electronic mail content. Mail systems can be extended to support other interesting applications, such as workflow and document management. The second category of horizontal applications are information services, such as current movie listings and weather information.
Ubiquitous computing environments
As mentioned earlier, the vast body of work is devoted to disseminating
information, with only a few simplistic applications in mind. The use of this
information to create a ubiquitous user environment is not yet well addressed.
The research concern is focused towards enabling the use of these devices for
independent functions.
An interesting question is how we can use these devices to complement our user environment, and support device independent environments that span multiple mobile and stationary devices. Interesting work of this nature is discussed in [Wei91]. The group at Xerox PARC believes the future of computing will be via devices, called Tabs. Tabs are not necessarily mobile, but will be widely available, ubiquitous. User environments migrate to Tabs as needed. Today, a user environment is largely at the desktop or workstation and is device dependent and migrates badly, if at all.
There is some recent work in the direction of ubiquitous computing, that enhances the user environment. A project at Stanford discussed in [App99], is focussing on adding a networking layer above the application that deals with people. The idea here is that people communicate and only use applications as a medium, much like applications may use TCP as a conduit, which usually uses IP. Providing a people layer allows the integration of application functions, that a set of devices support, to achieve a single task. Since the communication task is of primary importance, different applications may be used to achieve it depending on compatibility and availability. A classification of application media types is proposed as the interface between the application and the people communication layers.
Along a similar vein, the Iceberg project at Berkeley, discussed in [Jos98], outlines a framework to integrate services available over a variety of networks. For example, they have been able to demonstrate the interoperation of voice communication between cellular handsets in a PCS cellular network and internet conferencing tools. They argue that the network layer is the correct abstraction point to meld these technologies together into a single environment.
General database issues in mobile systems
Some interesting database centric issues in mobile computing are raised in
[Alo93], and they are briefly mentioned below. Query optimizers may need to be
rewritten to search for plans that minimize power consumption or
communication. Certain new queries may be expressed relative to the current
location, and perhaps even trajectory of the mobile device. Due to potentially
long periods of disconnection the device should store copies of data locally
on which queries can be performed. The transaction processing layer must
include synchronization with the primary database, leading to various
multi-database problems. Disconnection can often be predicted by monitoring
some measures of communication. When a prediction of impending disconnection
is made the database should proactively take appropriate action. Some
suggestions are to move transactions the longer require user input out of the
device and continue them on the server and to predict data that will be
required after disconnection and download it. At times a disconnection may
even be initiated by the client device to allow power savings. Since data at a
device is more at risk of loss and corruption than data at the server updates
must be transmitted back to the primary database as soon as possible. Upon
reconnection to the server there may be much waiting communication. In cases
of short reconnections one would like the most important information to be
transmitted first, requiring individual updates to have an associated measure
of priority. Some previously mentioned concerns about security are described.
And lastly, the paper discusses how the reduced user interface requires
changes to the cumbersome query language. The authors believe that most
device-database interaction will be driven through form interfaces.
Broadcast data dissemination
Since transmitting data from a device is very costly, research work has been
directed at finding ways to reduce the need to send information up to the
server. Rather than require a client to pull data from a server each time, it
may specify it's requirements once and rely on the server to push the data
regularly, or when updates occur, according to some protocol. Because wireless
is a broadcast medium it is natural to broadcast the data. Various related papers [Ach95, Imi94a, Ach97, Dat99] propose schemes to do this.
An excellent discussion of push technology is outlined in [Fra98]. The authors outline the fundamental properties of data delivery. The difference between pull and push is whether the client or the server, respectively, initiates the information delivery. In either case the delivery can be periodic or aperiodic, sometimes referred to as polling and event-driven delivery respectively. The data delivery grid is further divided into delivery mechanisms that employ point-to-point delivery, called unicast, versus broadcast communication. Examples of applications across the spectrum of delivery possibilities are provided.
In [Ach95] the concept of broadcast disks is introduced. The principle contribution is to consider the broadcast channel as a storage medium. Data items that are transmitted (or stored) on this broadcast disk can be read by a mobile device. It is proposed that there be multiple disks spinning at different speeds. The faster spinning disks transmit data more frequently, and represent more frequently accessed items. A parallel is drawn between a rapidly spinning disk and the closeness of a cache in a memory hierarchy. An algorithm is provided to create a fixed transmission sequence of this data with the given priorities. For simplicity, it is assumed that each block of memory is self identifying, that the required data is known in advance and remains unchanged, that clients retrieve items on demand without pre-fetching and that there is no upstream communication. Next an optimal client caching strategy, PIX, is proposed which caches the pages the pages with the highest probability of access divided by the frequency of broadcast. This is optimal, but impractical since the probability of access can not be determined a priori. The paper continues to discuss simulation results and proposes an approximation client caching algorithm, called LIX, which implements LRU with a separate queue for each broadcast priority.
In [Imi94a] the need in mobile devices to reduce tuning time as well as access time is outlined. Tuning time is the sum of all times spent listening to a channel from the time the request is made until a reply is received. Access time is the time from request transmission to reply reception. The paper contributes a method to reduce tuning time by embedding indices within the broadcast. Since the broadcast is lengthened it invariably lengthens the access time. But it results in great power savings to the client, since the client can listen just to the index and then know when to tune in for the relevant data. An indexing strategy called (1,m) is proposed, which interleaves m index segments per broadcast. An improvement on this is proposed whereby the index segments are distributed such that only data immediately following the segment is actually included in an index segment. An analysis is then performed and formulas calculated for expected access and tuning times.
In [Ach97] the broadcast disk work is supplemented with back channel communication from the mobile clients to the server, to request (pull) data and send updates. A discussion of sources of communications asymmetry is provided: network asymmetry, communication bandwidth from server to client is greater than in the opposite direction; client to server ratio, a system where there is a small number of servers and many more clients; data volume, applications that request information usually make small requests and get large responses; and updates and new information: when updates must to disseminated to many clients. The back channel does not affect the transmission on the front channel and is implemented with empty slots on the broadcast disks. Clients use the back channel to request and receive information that is not available on the broadcast disk within some time threshold. Simulations are performed to study the effects of pull on response times. The number of items included in the broadcast is adjusted as well as other parameters affecting the threshold for requesting data on the back channel. Among other things, the authors conclude that push is preferable to save client power, but that using pull sparingly can reduce the broadcast disk access time since disk size is greatly reduced by omitting rarely accessed items.
In [Dat99] the first adaptive broadcast protocol is suggested. This article provides an excellent review of the field of mobile computing. Two sets of protocols for both client and server side are provided. One set of protocols use a periodic (fixed size) broadcast, while the second set is aperiodic (variable size). It defines notions of a broadcast set, those items included in a broadcast, which changes depending on client requests. The paper also defines a very complex data organization scheme of data segments interleaved with index segments to support this. Data segments consist of logical clusters of physical buckets. Index segments consist of index buckets. The buckets and indices contain information that allows the client to quickly determine the exact location of the data cluster of interest. If required data is missing it can be requested to be included in the next broadcast. In the constant size broadcast items are included based on popularity and an aging factor. The aging factor is adjusted in such a way to attempt to service a request within the time a mobile device is expected to remain in the cell. In variable size broadcasts all requested items are included. Items have a request lifetime based on how long it is expected that the requesting client will remain in the cell. An extremely detailed and lengthy analytical and simulation analysis is provided. It provides analysis of both constant and variable size broadcast protocols regarding their affects on access time, tuning time, normalized energy expenditure and number of starved clients as a function of the number clients, constant broadcast size, index ratio, access locality, and many other model parameters. [A presentation of this paper is available.]
Data replication and caching
In order to allow disconnected operation, mobile devices require the capacity
to cache server data. Several papers have been written about replication
strategies and cache invalidation.
In [Bar94] the authors describe three cache invalidation schemes suitable for mobile devices. They discovered that different cache invalidation strategies would be effective for different usage patterns of mobile devices. Continuously used devices are called workaholics, versus other devices that are inactive, called sleepers. Sleepers only wake up once in a while so they are likely to have missed many updates to the cache. The most efficient way of invalidating the cache is by sending checksum signature reports. Workaholics, on the other hand, are likely to hear most updates. Therefore, we transmit the changed data to invalidate or update the cache. If updates are infrequent timestamped update messages, containing the new information, should be used. When updates are more common the Amnesic Terminal strategy is proposed, wherein a report is sent containing indices of cache entries that are no long valid since the previous broadcast. These data should be re-requested from the server when needed.
In [Wol92] two similar distributed adaptive replication algorithms are proposed. The difference is that the two algorithms base the replication adaptation decisions on either time or cost. The driving motivation is to replicate the pieces of data to nodes that frequently read it. The advantage is that remote reads can be replaced by faster local ones. The disadvantage is that updates must be propagated to all replicas, which is expensive. The dynamic algorithm expands and contracts the replica set of each datum depending on past reads and writes. The algorithm is distributed since each node determines whether they would like to be in the replica set or not.
This idea is expanded in [Hua94] to mobile environments. A model of device communication and connection to the server is defined, and a sliding window algorithm is proposed to reduce the cost of data access, and analyzed probabilistically.
Conclusion
In this survey paper the area of mobile ubiquitous computing was discussed. A
typical mobile environment was described and a summary of the major
differences inherent to mobile systems presented. We then reviewed the
hypothesis of extending the classical client-server model to facilitate
adaptive applications. Ubiquitous environments were described contrasting the
difference between earlier work on devices such as Tabs, and the current work
on integration and bridging technologies. We briefly looked at general
problems centered around database issues, and then moved on to discuss
specific research solutions developed for disseminating data via a broadcast
medium and mobile client data replication and cache invalidation.
Bibliography