# Composing optimal invalidation reports for mobile databases.

ASTRACT: Caching can reduce expensive data transfers and improve the performance of mobile computing. In order to reuse caches after short disconnections, invalidation reports are broadcast to clients to identify outdated items. Detailed reports may not be desirable because they can consume too much bandwidth. On the other hand, false invalidations may set in if accurate timing of updates is not provided. In this research, we aim to reduce the false invalidation rates of cached items. From our analysis, we found that false invalidation rates are closely related to clients' reconnection patterns (i.e., the distribution of the time spans between disconnections and reconnections). We show that in theory for any given reconnection pattern, a report with a minimal false invalidation rate can be derived. Experimental results have confirmed that our method is indeed more effective in reducing the false invalidation rate than others.Categories and Subject Descriptors

B.3 [Memory Structures]: B.3.2 [Design Styles]; Cache memories; C.1 [Processor Architectures]

General Terms

Mobile computing, Cache memories

Keywords: Mobile computing, cache invalidation, wireless, data broadcast, invalidation report, disconnection, failure.

1. Introduction

In a mobile or nomadic computing environment, a set of database servers disseminates information via wireless channels to mobile clients. This environment no longer requires clients to stay in fixed positions in the network. Clients can relocate and connect to different database servers at different times. Due to the narrow bandwidth of wireless channels, communication between the clients and servers ought to be minimized to reduce contentions. Caching of frequently accessed data at mobile clients has been shown to be a very effective mechanism in handling this problem. Other benefits of caching include energy savings (by reducing the amount of data transferred) and cost savings (especially if one is billed on a pay-per-packet basis).

It is generally assumed that updates are broadcast without much delay to clients by the server. Therefore, as long as the clients stay connected, their caches are current. However, in a mobile database environment, clients are frequently disconnected due to some battery power saving measures or unpredictable failures. Discarding entire caches after short disconnections could be wasteful as many data items in the caches may still be valid; this is especially true for a mobile database environment, where the bandwidth is narrow and battery power (of clients) is limited. Therefore, an efficient scheme for the reuse of cache is much needed.

Many caching coherence algorithms have been proposed for conventional client-server architectures [Carey 91, Fran 92, Wang 91, Wilk 90]. However, due to the unique features of the mobile computing environment, such as narrow bandwidth, frequent disconnections, weak communication capability (of clients), etc., these algorithms may not be directly applicable. There have been some researches on cache management for mobile computing published recently in the literature [Barb 99, Budi 04, Cai 97, Chun 96, Elma 95, Lai 03, Lee 02, Lu 03, Shao 03, Wu 96, etc.]. To reuse the caches after short connections, a common approach is to broadcast invalidation reports to clients to identify outdated items in the caches [Barb 94, Jing 97]. Detailed reports can be long, consuming much bandwidth and thus may not be desirable. On the other hand, without detailed timing information, cached items can be falsely invalidated. In this paper, we discuss how to compose a report with a minimal false invalidation rate. We have observed that false invalidation rates have to do with clients' reconnection patterns (i.e., the distribution of the time spans between disconnection and reconnection). By applying Newton's method to the clients' reconnection pattern, we showed that a report with a minimal false invalidation rate can be derived. Simulation results have also confirmed that our near-optimal method is fast and effective in reducing false invalidations.

The rest of the paper is organized as follows. In Section 2, we review the mobile computing environment. Section 3 reviews works in composing invalidation reports. In Section 4, we show that by using Newton's method, reports with minimal false invalidation rate can be composed. Simulation results are presented in Section 5, and we conclude our study in Section 6.

2. Preliminary

In a mobile client-server computing paradigm, there are two distinct sets of entities: a large number of mobile client hosts (MCHs) and relatively fewer, but more powerful fixed hosts that are connected through a wired network. MCHs usually run on small batteries, such as AA, while fixed hosts may have continuous power supplies. MCHs usually have weaker transmitting capability than fixed hosts. Some of the fixed hosts, called the MSS (Mobile Support Stations), are equipped with a wireless interface to communicate with mobile client hosts, which are located within a radio coverage area, called a wireless cell.

A wireless communication channel comprises an uplink (from a client to the server) and a downlink (from the server to a client) subchannels. An MCH submits requests to the local MSS via an uplink channel and receives the results via a downlink channel. Due to the weaker transmitting capability of the mobile clients (as compared to the fixed hosts), an asymmetric communication with much smaller uplink bandwidth than downlink is created. Receiving messages is less costly than sending messages for clients.

Caching can reduce client-server interactions, lessening the network traffic and message-processing overhead for both the servers and clients. Various cache coherence schemes [Carey 91, Gray 89, Wang 91, Wilk 90, etc.] have been developed for conventional client-server architectures. However, due to the unique characteristics of mobile computing, such as limited battery power, mobility of clients, limited and asymmetric communication, these schemes are not readily applicable to the mobile environment and new methods have to be designed.

There have been some researches on designing cache coherence schemes for mobile computing. Refresh time [Gray 89] has been used to determine the validity of cached items. Each item cached is associated with a refresh time. When the refresh time expires, the client contacts the server for the updated value. However, appropriate refresh durations are difficult to determine. Dynamic refresh time [Fran 92], based on the update frequency of the items, has been proposed as an improvement. However, many cached items can still be falsely invalidated (i.e., valid items considered as invalid) while others may be falsely validated (i.e., invalid items considered as valid). The cache coherency is not maintained effectively and consistently.

The cache invalidation method was proposed [Barb 94] to minimize the data transfer in both directions: the downlink and the uplink. In this approach, the server, periodically or asynchronously, broadcasts reports containing items that have been updated. When a client receives such reports, it checks against its cache and invalidate. Due to its simplicity and efficiency, invalidation reports have been adopted in many recent researches [Kaho 00, Lai 03, Shao 03, Wang 03, etc].

3. Invalidation Reports

Based on the timing of the invalidation messages being broadcast by the servers, cache invalidation methods can be either asynchronous or synchronous. In an asynchronous approach [Kaho 00, Walu 04, Wang 03], a server broadcasts an invalidation message as soon as an item changes its value. A client who is connected can immediately invalidate these items in its cache. The problem with the asynchronous approach is its unpredictable waiting time for such invalidation messages, which depends on the update activities on the database. Some improvements have been made in [Shao 03] such that even when the updating frequency is low, it is assured that at least one broadcast is sent in a certain period.

In the synchronous approach [Barb 94, Walu 04, Wilk 90], cache invalidation messages are broadcast periodically. That is, the server gathers updates for a period of time and then broadcasts these updates with the time of updates all in one message. Some latency could be induced between the actual updates and notification of the updates to the mobile clients. Once invalid items are found in the cache, the client submits an uplink request for updated values. The invalidation report divides the time into intervals. Despite the differences in cache coherence schemes, it is generally assumed that outdated items in caches are updated immediately. Therefore, as long as a client stay connected, its cache remains current.

While invalidation reports can be used to invalidate outdated items in the cache, another use of invalidation reports is to help reconnected users identify outdated items without discarding the cache after short disconnections. Discarding entire caches after short disconnections can be wasteful, as many data items in the caches may still be valid. This is particularly important to the mobile databases, where the bandwidth is narrow and battery power (of clients) is limited. It is generally assumed that a reconnected client cannot answer any queries until it has received the newest invalidation report and updated its cache. In the following, we will focus on composing invalidation reports for reconnected clients

3.1 Broadcasting Timestamp (BT) Strategy

Broadcasting timestamp (BT) strategy [Barb 94] was developed based on the synchronous invalidation approach. The report is composed of a set of pairs (ID, timestamp), in which ID specifies an item that has been updated, and the timestamp indicates when a change was made to that item. Note that a report can only cover the activities of a limited period of time, called a window period. The longer the window period of a report, the larger the invalidation report, which can lead to a long latency in the dissemination of reports. Normally, for each item cached, the client either purges it from the cache if the item is reported to have been changed, or changes the item's timestamp to the timestamp of the report (i.e., up to date). Note that the entire cache will have to be discarded if the client has disconnected longer than the period covered by the report.

3.2 Bit-Sequence (BS) Approach

In the BT approach, updated items are indicated by IDs and their respective timestamps in the report. When the number of itemsupdated is large, the size of the invalidation report can become large too. In order to save bandwidth, the bit-sequence (BS) approach is proposed [Jing 97]. Two techniques, the bit-sequence mapping and the update aggregation, are used to reduce the size of the report. The bit-sequence mapping aims to reduce the naming space of the items, while the update aggregation aims to reduce the number of timestamps used in the report. Since our approach is based on the BS approach, we shall elaborate on this approach a little more here.

In the BS approach, each data item is mapped to a bit of an N-bit sequence, where N is the total number of data items in the database. That is, the nth bit in the sequence corresponds to the nth data item in the database. A value "1" in a bit indicates the corresponding data item has been changed; and "0" indicates otherwise. This technique reduces the naming space from Nlog(N) bits for N items (needed in BT approach) to N bits here. It is noted that at least log(N) bits are needed to store an item's ID in the BT approach. The bit-sequence mapping is illustrated in Figure 1.

[FIGURE 1 OMITTED]

Another technique, called the update aggregation [Jing 97], is used in conjunction with the bit-sequence mapping to reduce the number of timestamps in a report. Instead of having one timestamp for each updated item, the report uses only one timestamp. A bit value "1" in the bit-sequence now indicates that the corresponding item has been updated since the timestamp of the report. A bit value "0" indicates no change has been made to that item since the timestamp.

Although update aggregation reduces the size of a report, it decreases the accuracy of the report. Since there is only one timestamp in the report, all items mentioned in the report have to be treated as being updated at the time indicated by the timestamp. As a result, valid items could be falsely invalidated; that is, false invalidations set in. For example, consider a client disconnected at time d. After reconnected, it received a report with a timestamp t < d. Recall that updates are broadcast by the server and are immediately reflected in clients' caches. Therefore, the client still has valid copies for those items updated between t and d. Since there is no way to tell these items from items updated after d in the report, all the items mentioned in the report will all have to be purged when the client reconnects.

In order to reduce false invalidations, a hierarchically structured, more detailed report has been proposed [Jing 97]. Instead of using just one bit-sequence (and a timestamp), n bit-sequences (n > 1) are used in the report to show the update activities of n overlapping subintervals. Specifically, the ith sequence (0 [less than or equal to] i [less than or equal to] n-1), denoted by [B.sub.i], has a length of N/[2.sup.i] bits, where N is the number of data items in the database, and it records the latest N/[2.sup.i+1] update activities. Each bit-sequence is associated with a timestamp T([B.sub.i]) indicating since when there have been such N/[2.sup.i+1] updates. As shown in Figure 2, the first bit-sequence [B.sub.0] has a length of N and half of it are "1' bits, indicating that N/2 items (out of N) have been updated since T([B.sub.0]). The second sequence [B.sub.1] has N/2 bits, each corresponding to a data item that has been updated since T([B.sub.0]) (i.e., a "1" bits in [B.sub.0]). Again, half of the bits in [B.sub.1] (i.e., N/4 bits) have the value "1", indicating half of the N/2 items that have been updated since T([B.sub.0]) were actually updated after T([B.sub.1]). In general, the jth bit of the [B.sub.i] corresponds to the jth "1" bit in the [B.sub.i-1], and half of each bit-sequence are 1's. It can be observed that the total number of bit-sequences n is log(N).

3.2.1 A Dynamic BS Scheme

The above BS scheme has been modified in [Jing 97] to accommodate a variable number of updates (instead of just N/2) for the reported period. The modified scheme is called the dynamic BS. Instead of mapping an item to a bit in [B.sub.0], each updated item is represented explicitly by its ID in the dynamic BS. Thus, [B.sub.0] is now made of the IDs of those items that have been updated since T([B.sub.0]). The rest of bit-sequences ([B.sub.1], ..., [B.sub.n-1]) are composed in the same way as in the original BS. That is, sequence [B.sub.i] (0 [less than or equal to] i [less than or equal to] n-1) has k/[2.sup.i-1] bits, with half of them being "1"s, where k is the number of items updated since T([B.sub.0]).

If both an ID and a timestamp are implemented as a 32-bit integer, the total size of a report can be calculated approximately as 32k + 2k + 32 log(k), where 32k is the size of k IDs (i.e., [B.sub.0]), 2k is the size of the rest of the bit-sequences (i.e., [B.sub.1], ..., [B.sub.n-1]), and log(k) is the number of timestamps (or the number of bit sequences) [Jing 97].

[FIGURE 2 OMITTED]

4. Composition of Optimal Hierarchical Bit-Sequences

Although Jing's [Jing 97] hierarchically structured bit-sequences discussed above reduced the naming space of items and the number of timestamps, there is no justification for why the bit-sequence hierarchy should be partitioned based on half of the updates, i.e., N/ [2.sup.i] or k/[2.sup.i] updates. In fact, this "half-update-partition" scheme could favor one situation over another. Here, we use Figure 2 again as an example. After reconnecting at the current time, clients 1 and 2 can use [B.sub.0] to invalidate their items, and client 3 will use [B.sub.1]. Since clients 1 and 2 disconnected between T([B.sub.0]) and T([B.sub.1]), as explained earlier, all cached items updated during this period will have to be invalidated and some of them might be falsely invalidated. Thus, if there are a large number of clients like clients 1 and 2, who disconnected during this (likely long) period, there can be a lot of items falsely invalidated. On the other hand, since there is no client disconnected between T([B.sub.n-2]) and T([B.sub.n-1]), the bit-sequences Bn-2 is wasted. The above scenario is likely to happen because the time span between T([B.sub.0]) and T([B.sub.1]) is likely much longer than that between T([B.sub.n-2]) and T([B.sub.n-1]). As observed, there are more bit-sequences covering the more recent but shorter periods than the earlier but longer periods in Jing's approach. Clearly, this "half-update" scheme may not yield minimal false invalidations.

In this research, we attempt to find hierarchically structured bit-sequences that minimize the false invalidation rate. Specifically, we will investigate the division of the n overlapping subintervals in the report such that the false invalidations can be minimized.

4.1 Reconnection Patterns

It is observed that the false invalidations are due to the inaccuracy of the report as the exact time of updates has been replaced by fewer rough timestamps (to save bandwidth). Increasing the number of bit-sequences (and also the timestamps) can certainly increase the accuracy of the report and thus reduce the false invalidation; however, this could also compromise the goal of saving bandwidth. In this research, we consider how to make the best use of bit sequences to lower the false invalidations.

As noted earlier, some of the bit-sequences are of little or no use because there are few or no clients disconnected during that period. That is, the effectiveness of the bit-sequences is closely related to the reconnection patterns of mobile clients; i.e., how long clients are likely to reconnect after disconnection. Therefore, to reduce the false invalidation rates, a reorganization of the bit-sequences that takes into account clients' reconnection patterns needs to be devised.

Assume that the reconnection pattern can be represented by a certain probability distribution such as the one shown in Figure 3, where the X-axis is the time lapse from the last disconnect time to the reconnect time, while the Y-axis represents the number of clients.

[FIGURE 3 OMITTED]

Let us analyze the relationship between the false invalidations and the reconnect distributions. Assume that a mobile client disconnected at time x. After it reconnects and receives its first report, it looks for a sequence, say [B.sub.i], in the report with the largest timestamp that is less than or equal to its disconnection time x (i.e., T([B.sub.i]) [less than or equal to] x). If the client did not disconnect at exactly T([B.sub.i]) , there might be a chance for false invalidation, because the client may have already updated some of the items in its cache between T([B.sub.i]) and x when it was still connected. The larger the difference between x and T([B.sub.i]), the more items might have been updated by the clients before disconnection, and those items would be falsely invalidated when reconnected.

4.2 An Optimal Report with Minimal False Invalidation

Now, let us derive the relationship between the false invalidation and the partition of window for a given reconnection pattern. Here, we assume that the window size W is fixed, predetermined by the system.

Since the server receives update requests from users of all kinds, we may assume that updates to the database are independent. Let c be the update arrival rate during the window period. Then, the expected number of items falsely invalidated for a client disconnected at x, denoted FI(x), is cx(x-T([B.sub.i])).

Let f(x) be the reconnection pattern (probability density function). Then, the expected total number of falsely invalidated items, denoted by TFI, is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4.1)

where n is the number of bit-sequences in the report, T([B.sub.n]) = CT (i.e., the current time). To illustrate our algorithm, we give the following Theorem first:

Theorem. Suppose f(x) is a continuous positive real function on interval [a, b], and n is a positive integer. Then, there exists a vector X = [x1, ..., [x.sub.n-1]]T such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

attains its maximum, where a = [x.sub.0] [less than or equal to] [x.sub.1] [less than or equal to] ... [less than or equal to] [x.sub.n-1] [less than or equal to] [x.sub.n] = b. Furthermore, the value X is the solution of nonlinear system

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4.2)

Proof: Because [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and g(X) is a continuous function of X on the closed interval, there exist a maximum and a minimum values g (X) of for certain X.

a = [x.sub.0] [less than or equal to] [x.sub.1] [less than or equal to] ... [less than or equal to] [x.sub.n-1] [less than or equal to] [x.sub.n] = b.

When , a = [x.sub.0] = [x.sub.1] = ... = [x.sub.n-1], [x.sub.n] = b we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] which is the minimum value.

g (X) g is smooth and it can attain its maximum. Hence, the solution [x.sub.1], ..., [x.sub.n-1] of [partial derivative]g(X)/[partial derivative][x.sub.i] = 0, i = 1,2, ..., n-1 must be the values such that g (X) attains maximum at X = [[[x.sub.1], [x.sub.2], ..., [x.sub.n-1]].sup.T].

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4.3)

Therefore, the equation (4.2) has solutions.

End of Proof #

In order to design an algorithm to find the n subintervals to minimize TFI based on the above theorem, we need to do a little conversion.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4.4)

To minimize TFI is equivalent to maximizing [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a constant. The problem becomes how to partition the window into n subintervals to maximize. Hence, T([B.sub.i]) i=1,..n-1 are the solution of (4.2) by the Theorem.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[F.sub.i](X) = [partial derivative](X)/[partial derivative][x.sub.i] Let , then Eq. (4.2) is equivalent to F(X) = [[[F.sub.1], [F.sub.2](X), ..., [F.sub.n-1](X)].sup.T], F(X) = 0, (4.4)

where 0 is a n-1 dimension vector [[0, 0, ..., 0].sup.T]. In general, with the existence result of the solution of (4.2), by using Newton's iterative method, we can find the approximation of the solution [X.sub.*] as following:

F([X.sub.k]) + F'([X.sub.k])([X.sub.k+1] - [X.sub.k]) = 0 [X.sub.k+1] - [X.sub.k] = -F'[([X.sub.k]).sup.-1]F([X.sub.k]) = -DF[([X.sub.k]).sup.-1]F([X.sub.k]), k = 0, 1,2,3 ... (4.5)

We know that , Xk [right arrow] [X.sub.*] [X.sub.*] is the solution of Eq. (4.3) such that g(X) attains its maximum at [X.sub.*].

We choose initial value

[X.sub.0] = [[[x.sub.0,1], [x.sub.0,2], ..., [x.sub.0,n-1]].sup.T], a [less than or equal to] [x.sub.0,i] [less than or equal to] b for i = 1,2, ..., n-1. In Eq. (4.3), DF (X) is the Jacobian matrix and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4.6)

From Eq. (4.2), we know that [partial derivative][F.sub.i]/[partial derivative][x.sub.j] = 0 for j = 1, ..., i-2,i+2, ..., n-1, i.e., i-1, i, i+1 for j are excluded.

[partial derivative][F.sub.i]/[partial derivative][x.sub.i-1] = f([x.sub.i]) and [partial derivative][F.sub.i]/[partial derivative][x.sub.i] = -2f([x.sub.i]+([x.sub.i-1]-[x.sub.i])f'([x.sub.i]),[partial derivative][F.sub.i]/[partial derivative][x.sub.i+1] = f([x.sub.i+1]) for i = 1,2, ..., n-1. Hence

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is a symmetric tridiagonal matrix and Eq. (4.3) is equivalent to the linear system equations

DF ([X.sub.k]) (X - [X.sub.k]) = -F([X.sub.k]) (4.7)

By using LU decomposition method [Axel 94], we can solve the linear equations (4.7) to obtain [X.sub.k+1]. We know that the complexity of this method is O(n), where n is the order of the tridiagonal matrix. We can solve (4.6) for sequence {[X.sub.k]}, k = 1,2,.... After N steps of iteration, the complexity is N.O(n) = O(n). That is, we can obtain the arbitrary approximation of the solution in polynomial time. We can use

[[parallel][X.sub.k+1]-[X.sub.k][parallel].sup.2.sub.2] = [[n-2. summation over i=1]([x.sub.k+1,i])-[x.sub.k,i]).sup.2] [less than or equal to][epsilon], [epsilon] > 0.

to find the number of steps N. Hence the result satisfies the precision requirement.

Here is the algorithm for finding the optimal window partition (from [x.sub.0] = T([B.sub.0]) to [x.sub.n] = T([B.sub.n])) for any reconnection pattern f(x).

Algorithm: optimal window partition

Step1. Evaluate

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

If we find the maximum of g(X) a [x.sub.0] [less than or equal to] [x.sub.1] [less than or equal to] ... [less than or equal to] [x.sub.n-1] [less than or equal to] [x.sub.n], stop and return [x.sub.1], ..., [x.sub.n-1]. Otherwise, go to step 2.

Step 2. Solve the nonlinear equation (4.2).

If we find the exact solution, stop and return [x.sub.1], ..., [x.sub.n-1]. Otherwise, goto step 3 for an approximation solution.

Step 3. For a given approximation error [epsilon] let k = 0;

[X.sub.0] = [[[x.sub.0,1], [x.sub.0,2], ..., [x.sub.0,n-1]].sup.T], where [x.sub.0,i] = a + ix(b-a)/n for i = 1,2, ..., n-1

Loop:

Solve (4.7) for by using LU decomposition

while

[[parallel][X.sub.k+1]-[X.sub.k][parallel].sup.2.sub.2] = [[n-2. summation over i=1]([x.sub.k+1,i])-[x.sub.k,i]).sup.2] > [epsilon]

return [X.sub.k+1]

Example. Assume we are to divide a window of size 10 into 3 subintervals, and the reconnect distribution follows the formula

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4.6)

Then, from the above theorem, we know that there exists a maximum value of g(X), where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and 0 [less than or equal to] [x.sub.1] < [x.sub.2] [less than or equal to] 10. If 0 [less than or equal to] [x.sub.1] [less than or equal to] 5, 5 < [x.sub.2] [less than or equal to] 10,

g(X) = 1/2[x.sub.2][([x.sub.2] - 10).sup.2] - 1/2[([x.sub.2] - 10).sup.2][x.sub.1] + 25[x.sub.1] - 1/2[x.sub.1.sup.3].

If 0 [less than or equal to] [x.sub.1] < [x.sub.2] [less than or equal to] 5,

If 5 < [x.sub.1] < [x.sub.2] [less than or equal to] 10,

g(X) = 1/2[x.sub.2][([x.sub.2] - 10).sup.2] - 1/2[([x.sub.2] - 10).sup.2][x.sub.1] + 25[x.sub.1] - 1/2[x.sub.1.sup.3].

From the above equation, we obtained that g(X) has the maximum value of 86.9385 when [x.sub.1] = 3.1008 and [x.sub.2] = 5.4005. Thus, we will divide the window at 3.1008 and 5.4005.

4.3. A Dynamic Scheme

Like the dynamic BS scheme [Jing 97], we can modify our method to further reduce the size of the report when the number of items updated is small. That is, instead of using an N-bit sequence for [B.sub.0], we explicitly use the IDs of items that have been update since T([B.sub.0]). Other bit sequences ([B.sub.1], ..., [B.sub.n-1]) are composed as before. If both IDs and timestamps are implemented as 32-bit integers, the overall size of the report is 32k + [[summation].sup.i=n-1.sub.i=1][absolute value of [B.sub.i]] + + 32n, where the first term is the size of k IDs (or [B.sub.0]), the second term is the size of the rest of the bit-sequences (i.e., [B.sub.1], ..., [B.sub.n-1]), and the last term is the size of n timestamps. Note that the number of timestamps (or bit sequences) in our approach is, in general, different from that of Jing's. We will pick up this issue later.

5. Simulation Results

In this section, we report simulation results on Jing's and our approaches based on the size of invalidation reports and false invalidation rate. We chose the dynamic versions of these two approaches for comparisons because of their flexibility in accommodating a variable number of updates in the report. The results should be applicable to the original schemes without much difference. A report has two parts--bit-sequences and timestamps. Since item IDs are used as the first bit-sequence [B.sub.0] in the dynamic schemes of both approaches, we shall exclude [B.sub.0] from the "bit-sequences" in the following discussion, unless otherwise stated. We will also discuss the effect of timestamps on the overall size of a report later.

The purpose of the simulations is mainly to compare the size of the reports and the effectiveness of the bit-sequences in reducing the false invalidation rate, denoted FIR, which is defined as

FIR = number-of-items-falsely-invalidated/number-of-items-invalidated

Since the compositions of the bit-sequences are different in these two approaches, the lengths of bit-sequences will also be different. In order to make fair comparisons of the effectiveness of bit-sequences in correctly invalidating items, we define an effectiveness measure, denoted EF, as

EF = 1-FIR/length-of-bit-sequences

This measure tells the percentage of correct invalidations per unit length of bit-sequences. We shall compute the relative effectiveness (REF), the ratio of our EF to Jing's EF, as, to show the how effective our approach is when compared to Jing's approach.

W have chosen two patterns, a uniform distribution and a non-uniform distribution as described in Section 4.1, for our simulations. It is noted that cache size has no effect on FIR, which is due to the inaccuracy of the report. We have also tested with various database update rates, 10%, 20%, 30%, 40%, and 50%, which are the percentages of items updated during the last window period, to see their effects on the false invalidation rate. The lengths of the bit-sequences in the two approaches are usually different. As mentioned earlier, the expected size of Jing's bit-sequences (excluding [B.sub.0]) can be calculated beforehand as 2k, where k is the number of items updated since T([B.sub.0]); in our approach, it depends on the number of subintervals in the window, which can be chosen as desired. In order to compare the effectiveness of bit-sequences, we have chosen the number of subintervals to be 3 in our approach so that the lengths of our bit-sequences can be as close to Jing's as possible. Note that we can divide our window into any number of subintervals as desired to reduce the false invalidation rate, but Jing's cannot (size = 2k).

As discussed earlier in Section 4, for a uniform reconnection pattern, an evenly divided window yields the optimal performance. For the convenience of calculation, the window size has been set to be 10 time units in all simulations. In the following tables, in the "Length" column we report the length of bit-sequences in bits. The row "Ratio" shows the ratios of the length and FIR of the optimal method to Jing's.

W have chosen two patterns, a uniform distribution and a non-uniform distribution as described in Section 4.1, for our simulations. It is noted that cache size has no effect on FIR, which is due to the inaccuracy of the report. We have also tested with various database update rates, 10%, 20%, 30%, 40%, and 50%, which are the percentages of items updated during the last window period, to see their effects on the false invalidation rate. The lengths of the bit-sequences in the two approaches are usually different. As mentioned earlier, the expected size of Jing's bit-sequences (excluding [B.sub.0]) can be calculated beforehand as 2k, where k is the number of items updated since T([B.sub.0]); in our approach, it depends on the number of subintervals in the window, which can be chosen as desired. In order to compare the effectiveness of bit-sequences, we have chosen the number of subintervals to be 3 in our approach so that the lengths of our bit-sequences can be as close to Jing's as possible. Note that we can divide our window into any number of subintervals as desired to reduce the false invalidation rate, but Jing's cannot (size = 2k).

As discussed earlier in Section 4, for a uniform reconnection pattern, an evenly divided window yields the optimal performance. For the convenience of calculation, the window size has been set to be 10 time units in all simulations. In the following tables, in the "Length" column we report the length of bit-sequences in bits. The row "Ratio" shows the ratios of the length and FIR of the optimal method to Jing's.

It can be observed from Table 1 that our bit-sequence size is around 80% of Jing's (i.e., 0.7589, 0.7879, 0.7984, 0.8067, 0.8091 for 10%, 20%, 30%, 40%, 50% update rates, respectively). This result is consistent with our analysis on the estimations of bit-sequence sizes. Recall that the length of Jing's bit-sequences is 2k (excluding [B.sub.0]), while ours is k + (2/3)k = (5/3)k, where k is the size of [B.sub.1] (and also the number of items updated), and (2/3)k is the expected size for [B.sub.2]. That is, ours is only 83% ((5/3)k / 2k H" 0.83) of Jing's.

The FIRs basically remain the same for different database update rates in each approach, that is, around 18.8% in our approach and 20.0% in Jing's approach. It indicates that FIR has to do with the ways of composing bit-sequences, and has nothing to do with the rates of updates.

In summary, not only are our bit-sequences shorter than Jing's, (approximately 80% of Jing's), but also achieve better (or lower) false invalidation rates (approximately 94% of Jing's). This implies our bit-sequences are more effective in lowering the false invalidation rate. According to the relative effectiveness measure REF, our bit-sequences are 25 - 34% more effective in correctly invalidatingitmes than Jing's.

Now let us consider the size of timestamps. The total size of timestamps in Jing's report is 32log(k), while it is 32n in ours, where log(k) and n are the numbers of bit-sequences in respective reports. In our report, there are 3 (i.e., n = 3) timestamps, while in Jing's report, it has log(k) timestamps (log(1,000)=10, log(2,000)=11, ..., log(5,000)=13 for 1,000, 2,000, ..., 5,000 updates, respectively, during the last window). Clearly, we use much less timestamps and consume less space than Jing's report.

In Table 2, we show the results for the non-uniform distribution described in Example 2 of Section 4.1. According to Theorem 1, we divided the window at 3.1008 and 5.4008. Again, our bit-sequences are shorter (about 80% of Jing's), and yet achieve much better (or lower) false invalidation rates (76% of Jing's). As in the uniform case, the FIRs remain the same in each approach for different item update rates. The FIRs are around 17.6% in our approach, compared to 23.1% in Jing's. In terms of the REF measure, our bit-sequences are 31-40% more effective than Jing's.

It is worth mentioning that if there is enough bandwidth for longer reports, in our approach we can easily divide the window into more subintervals (i.e., more bit-sequences) to achieve lower false invalidation rates. However, this may not be possible for Jing's approach because the number of bit-sequences (i.e., log(k)) is completely determined by the number of updates (k) in the window period. That is, even though there is still bandwidth left for use, Jing's approach simply cannot use it to reduce the false invalidation rates. Excess bandwidth may be used to reduce false invalidation by increasing the number of bit-sequences in our approach.

In summary, our approach clearly outperforms Jing's approach in terms of the length of bit-sequences, number of timestamps, effectiveness of reducing FIR, and flexibility in using excess bandwidth to reduce false invalidation rates.

6. Conclusions

In this paper, we discussed the composition of invalidation reports to achieve minimal false invalidation rates. We have found that false invalidation rates have to do with the reconnection patterns of clients, that is, the distribution of the durations between disconnections and reconnections. Based on the bit-sequence approach [Jing 97], we redesigned the hierarchy of the bit-sequences, taking into account the reconnection patterns of mobile clients. We have shown that by using Newton's method, we can derive a partition of the report window to achieve a minimal false invalidation rate for a given reconnection pattern. We have performed simulations to show that our approach of composing reports indeed has better performance than Jing's in terms of the length of bit-sequences, number of timestamps, effectiveness of reducing FIR, and flexibility in using excess bandwidth.

Received 30 Oct. 2004; Reviewed and accepted 30 Jan. 2005

References

[1] Axelsson. O. (1994). Iterative Solution Methods", Cambridge University Press.

[2] Barbara, D. (1999). Mobile Computing and Databases-A Survey, IEEE Transactions on Knowledge and Data Engineering. 11(1), 108 117.

[3] Barbara, D & Imielinski, T. (1994). Sleepers and workaholics: Caching strategies for mobile environments. Proceedings of the ACM SIGMOD Conference on Management of Data. 1 12.

[4] Budiarto, Nishio , S., & Tsukamoto, M. (2002), Data Management Issues in Mobile and Peer-to-peer Environments. Data and Knowledge Engineering, 41(2). 183 204.

[5] Cai, J., Tan, K, & Ooi, B. (1997). On Incremental Cache Coherency Schemes in Mobile Computing Environments. Proceedings of IEEE Data Engineering, 114 123.

[6]. Carey, M., Franklin, M., Livny, M. & Shekita, E. (1991). Data Caching Tradeoffs in Client-Server DBMS Architectures. Proceedings of ACM SIGMOD Conference, 357 366.

[7]. Chung, H., Cho, H. (1996). Data Caching with Incremental Update Propagation in Mobile Computing Environments, Proceedings Australian Workshop on Mobile Computing and Databases and Applications, 120 134.

[8]. Lee, K., Hong Va Leong, Si, A. (2002). Semantic Data Broadcast for a Mobile Environment Based on Dynamic and Adaptive Chunking. IEEE Transactions on Computers, 51(10) 1253 1268.

[9]. Elmargarmid, A., Jing, J., &Furukawa, T. (1995). Wireless Client-Server Computing for Personal Information Services and Applications. ACM SIGMOD Record. 43 49.

[10]. Franklin, M., Carey, M. & Livny., M. (1992). Global Memory Management in Client-Server DBMS Architectures. Proceedings. of VLDB, 596 609.

[11]. Gray, C & Cheriton, D. Leases (1989). An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency. Proceedings of SOSP, 202 210.

[12]. Jing, J., Elmagarmid, A., Helal, A. & Alonso. R. (1997). Bit-Sequences: An Adaptive Cache Invalidation Method in Mobile Client/ Server Environments. ACM/Baltzer Journal of Mobile Network and Applications, 2(2), 115 127.

[13]. Kahol, A., Khurana, S., Gupta, S., & Srimani, P. (2000). A Strategy to Manage Cache Consistency in a Disconnected Distributed Environment. IEEE Transactions on .Parallel Distrib.Systems. 12(7) 686 700.

[14]. Lai, K., Tari, Z. & Bertok P. (2003). Cost Efficient Broadcast Based Cache Invalidation for Mobile Environments. ACM Symposium on Applied Computing, 871 877.

[15]. Lu, Y. & Shao, X. (2003). Improve Performance of Disconnected Operation through Submitting by Probability and Transferring Transactions in Groups. Proceedings of International conference on Computer Networks and mobile Computing, 502 505.

[16]. Nuggehalli, P., Srinivasan, V. & Chiasserini, C. (2003). Energy-efficient Caching Strategies in Ad Hoc Wireless Networks", Proceedings of ACM International Symposium on Mobile Ad Hoc Networking and Computing, 25 34.

[17] Shao, X. & Lu, Y. (2003). Maintain Cache Consistency in Mobile Database Using Dynamical Periodical Broadcasting Strategy, Proceedings of 2nd International Conference on Machine Learning and Cybernetics, 2389 2393.

[18]. Waluyo, A., Srinivasan, B. & Taniar, D. (2004). A Taxonomy of Broadcast Indexing Schemes for Multi Channel Data Dissemination in Mobile Databases", Proceedings of 18th International Conference on Advanced Information Networking and Applications. 1, 213 218.

[19]. Wang, Y., (1991). Cache Consistency and Concurrency Control in a Client/Server DBMS Architecture. Proc. of ACM SIGMOD conference, 367 376.

[20]. Wang, Z., Das, S., Che, H. & Kumar,M. (2003). SACCS: Scalable Asynchronous Cache Consistency Scheme for Mobile Environments", Proceedings of 23rd International Conference on Distributed Systems Workshop, 797 802.

[21]. Wilkinson K, & Neimat, M. (1990). Maintaining Consistency of Client-Cached Data", Proc. of 16th VLDB, pp. 122-133, Aug.1990.

[22]. Wu, K., Yu. P. & Chen, M. (1996). Energy-efficient Caching for Wireless Mobile Computing", Proceedings of 12th International Conference on Data Engineering, 34 50.

Wen-Chi Hou, Chin-Fang Wang

Department of Computer Science, Southern Illinois University at Carbondale

Carbondale IL, 62901, U.S.A

{hou, cfw}@cs.siu.edu

Meng Su

Department of Computer Science, Penn State Erie

Erie, PA 16509, USA

mengsu@psu.edu

Table 1 Uniform Distribution Update Rate 10% 20% Length FIR Length FIR Optimal 1731 0.18830 3398 0.1878 Jing's 2281 0.2008 4313 0.2004 Ratio 0.7589 0.9379 0.7879 0.9371 REF 1.337 1.289 Update Rate 30% 40% Length FIR Length FIR Optimal 5065 0.1884 6732 0.1881 Jing's 6344 0.2001 8345 0.2006 Ratio 0.7984 0.9412 0.806 0.9377 REF 1.271 1.259 Update Rate 50% Length FIR Optimal 8397 0.1880 Jing's 10378 0.2005 Ratio 0.8091 0.9378 REF 1.253 Table 2 Non-uniform Distribution Update Rate 10% 20% Length FIR Length FIR Optimal 1754 0.1755 3444 0.1759 Jing's 2281 0.2315 4313 0.2307 Ratio 0.7690 0.7581 0.7985 0.7626 REF 1.395 1.341 Update Rate 30% 40% Length FIR Length FIR Optimal 5134 0.1755 6826 0.1754 Jing's 6344 0.2310 8345 0.2313 Ratio 0.8093 0.7598 0.8180 0.7585 REF 1.325 1.311 Update Rate 50% Length FIR Optimal 8513 0.1757 Jing's 10378 0.2309 Ratio 0.8203 0.7610 REF 1.307

Printer friendly Cite/link Email Feedback | |

Author: | Hou, Wen-Chi; Wang, Chih-Fang; Su, Meng |
---|---|

Publication: | Journal of Digital Information Management |

Date: | Jun 1, 2005 |

Words: | 7183 |

Previous Article: | Energy efficient cache invalidation in a mobile environment. |

Next Article: | Ontology-based heterogeneous XML data integration. |