Information Technology Reference
In-Depth Information
If the mobile peer sent an announcement for
D
,
D
is very important for the mobile peer, and its
neighbors may rely on it for
D
, thus the mobile
peer is not free to put reliance on its neighbors
and give up prefetching
D
. However, if it received
e n o u g h a n n o u n c e m e n t s f r o m n e i g h b o r s (g*
n >
1),
which means it is possible that the mobile peers
share common access interests for
D
and too many
mobile peers will prefetch D and the neighborhood
is wasting cache space, then it is good that one
or several (but not all) of them finally choose not
to prefetch
D
. This decision is made by tossing
a coin. Even though some mobile peers having
made announcement may choose not to prefetch
D
after the coin flip, the overall availability of
D
is guaranteed by the process of coin flips, with a
high probability.
Suppose the mobile peers are doing demand-
driven caching, and
M
b
and
M
c
have data object
D
1
at time
t
;
M
a
decides not to cache
D
1
because
its neighbors
M
b
and
M
c
have it;
M
a
has a query for
D
1
at time
t
+
t
'/2 + D
t
. Notice that when
M
a
wants
to access
D
1
, its neighbors with
D
1
have moved
away. The latency of the access is the time dura-
tion from time
t
+
t
'/2 + D
t
to the time when
D
1
is
broadcast. The latency can be represented as:
t
'
t
'
−D
t
,
if
D≤
t
−D−
2
2
t
'
t
'
t
'
(
t
)%( ')),
t
if
D >
t
2
2
In the expression, “%” is the
remainder
op-
eration.
However, if the mobile peers are prefetching,
and
M
b
and
M
c
will prefetch
D
1
, and
M
a
decides
not to prefetch
D
1
because its neighbors
M
b
and
M
c
will prefetch it, then when
M
a
has a query for
D
1
at time
t
+
t
'/2 + D
t
, its access latency will be:
discussion on relying on neighbors
ACP and CPIX are quite different on the problem
of whether to rely on current neighbors for caching
some data objects. In CPIX, a peer's neighborhood
does not directly participate when the peer makes
a caching decision. In ACP, a peer's prefetching
decision is partially based on neighbors' inten-
sions on prefetching.
ACP's approach of relying on current neighbors
may seem to be inconsistent with the analysis and
arguments we made in the background section
that a mobile peer should not make caching deci-
sions based on the cache contents of its
current
neighbors, but in fact this is not a conflict because
prefetching is very different from demand-driven
caching. Let's use an example to show the dif-
ference.
Suppose the current time is
t
and data object
D
1
appears on the broadcast channel, and
D
1
will
be broadcast again at time
t+t'
(
D
1
is broadcast
every
t'
time units). Mobile peer
M
a
gets
D
1
at
time
t
.
M
a
has neighbors
M
b
,
M
c
and
M
d
.
M
b
and
M
c
will move out of
M
a
's communication range
at time
t+t'/2
.
t
'
t
'
−D
t
,
if
D≤
t
2
2
t
'
0,
if
D>
t
2
The difference is in the second case where
'
t
D>
. In prefetching, the access latency could
be 0 because at time
t+t'
(which is before
t
+
t
'/2 + D
t
),
M
a
will make prefetching decision for
D
1
again and may cache it locally if this time
no neighbors will prefetch it. Recall that
D
1
is
broadcast every
t'
and prefetching is driven by
broadcast program.
The point is that in ACP, a peer will notice the
move-away of neighbors (who prefetched an in-
teresting object) when the data object is broadcast
again. In the example, when
D
1
is broadcast again,
M
a
will make a new prefetching decision on
D
1
.
If at this time
M
b
and
M
c
are not around, then
M
a
2
Search WWH ::
Custom Search