Information Technology Reference
In-Depth Information
cooperative caching and cooperative prefetching
for mobile peers.
ability be 3% and its broadcast frequency be 0.5%.
The PIX score of
D
a
is 5, and the PIX score of
D
b
is 6. Object
D
b
may cause longer access latency,
so
D
b
will be cached if only one object can be
cached. PIX is an optimal individual caching
scheme for non-uniform broadcast because an
object's PIX score is the expectation of the object's
access latency.
Individual Caching
We refer to the caching schemes that do not
consider the collaboration among mobile peers
as
individual caching
schemes.
Classic caching algorithms (like LRU) de-
signed for client-server environments may result
in poor performance in a broadcast system. In
a client-server environment, accessing differ-
ent data objects from the server takes similar
amount of time. That being the case, caching the
hottest data objects is a good idea. However, in a
non-uniform broadcast environment where data
objects are broadcast with different frequencies,
the latencies for accessing different objects from
the broadcast channel may vary greatly. This
difference makes the idea of caching the most
accessed data object not the best choice.
Caching strategies for mobile broadcast envi-
ronments were proposed in (Acharya, 1995; Su,
1998; Xu, 2000; Xu, 2004). Here we briefly review
the main idea of a scheme called PIX (Acharya,
1995). Knowing PIX will be helpful for under-
standing CPIX, which is the cooperative caching
scheme that we will discuss in detail later.
PIX
. PIX is specifically designed for non-
uniform broadcast environments. The basic idea
is for mobile peers to store those data objects
for which the local probability of access is sig-
nificantly greater than the object's frequency of
broadcast. PIX (P Inverse X) uses the ratio
P
i
/
X
i
, where
P
i
is the probability of access to a data
object
D
i
and
X
i
is the broadcast frequency of
D
i
,
to decide whether
D
i
should be cached in local
memory. A mobile client estimates the value of
P
i
using its data access history, and derives the
value of
X
i
from broadcast index. A data object
with a higher PIX score will replace a data object
with a lower PIX score. For example, let object
D
a
's access probability be 5% and its broadcast
frequency be 1%, and let object
D
b
's access prob-
Individual Prefetching
As in individual caching, we refer to the prefetch-
ing schemes that do not consider the collaboration
among mobile peers as
individual prefetching
schemes.
Prefetching from broadcast channel is very
different from prefetching from a server in tra-
ditional client-server systems or prefetching from
hard disk to main memory. The most important
characteristic of prefetching from broadcast
channel is that the prefetching (and the related
cache management scheme) is driven by broad-
cast program: each time a data object appears
on the broadcast channel, the mobile peer needs
to decide whether to prefetch the data object
locally. This is also the fundamental difference
between prefetching and demand-driven caching
in broadcast environments. Recall that in demand-
driven caching, the caching scheme is triggered
only when there is an access and the needed data
object is received.
The advantage of prefetching from broadcast
channel is that it improves response time and
does not add any extra workload and overhead to
the broadcast server—the mobile peers prefetch
by just listening to the broadcast channel. The
disadvantage is that it incurs additional energy
consumption at the mobile peer, as the mobile
peer needs to be in active mode and listens to
the broadcast channel when prefetching. Thus
in applications where response time is the major
concern and where mobile peer has enough en-
ergy supply (e.g., computing device on vehicles),
prefetching will be preferable.
Search WWH ::
Custom Search