Transcript Dynamic Page Migration

International Graduate School
of Dynamic Intelligent Systems,
University of Paderborn
Dynamic Page Migration
with Stochastic Requests
Marcin Bieńkowski
International Graduate School
of Dynamic Intelligent Systems,
University of Paderborn
Motivation
Mobility:

mobile nodes on the (unbounded) plane
 nodes move with constant speeds
 wireless (radio) communication
Parallel program:
 A parallel application running on all the nodes
 Application uses shared variables stored in the local
memories of nodes
We restrict our attention to one such variable called
(memory) page
D.P.M. with Stochastic Requests / M. Bienkowski 2
Motivation (movement)
International Graduate School
of Dynamic Intelligent Systems,
University of Paderborn
 Typically page is big (of size ) and indivisible
 Nodes want to access (read or modify) just one unit of data
from the page
D.P.M. with Stochastic Requests / M. Bienkowski 3
International Graduate School
of Dynamic Intelligent Systems,
University of Paderborn
Motivation (costs)
Snapshot at
 Cost incurred can be measured in terms of energy usage
 In one step it is proportional to the distance
to some
power
(propagation exponent of the medium) plus a
constant overhead for communication
 For any two nodes
and


their distance:
cost of sending one unit of data
D.P.M. with Stochastic Requests / M. Bienkowski 4
International Graduate School
of Dynamic Intelligent Systems,
University of Paderborn
Motivation (costs cont.)
 After serving a request the
page can be moved (migrated)
to a new node
 Cost of moving the page from node
is equal to
(in this example:
)
to
Goal: minimize the total cost of communication
D.P.M. with Stochastic Requests / M. Bienkowski 5
International Graduate School
of Dynamic Intelligent Systems,
University of Paderborn
Dynamic Page Migration: Modelling
An online problem
 We assume discrete time steps

processors
in a metric space
 Input: configuration + request sequences
In one step




Positions of the nodes are defined by
Node
issues a request
Algorithm pays for serving the request
Algorithm optionally moves the page
(constant speed!)
Performance metric:
We measure the efficiency of an algorithm by standard
competitive analysis – competitive ratio
D.P.M. with Stochastic Requests / M. Bienkowski 6
International Graduate School
of Dynamic Intelligent Systems,
University of Paderborn
Previous results
Results for Dynamic Page Migration for
B., Byrka, Dynia, Korzeniowski, Meyer auf der Heide:
Competitive ratios
 For adaptive adversaries:
 For oblivious adversaries:
For
the lower bounds are even higher replaced by
is
D.P.M. with Stochastic Requests / M. Bienkowski 7
Possible relaxations of the model
International Graduate School
of Dynamic Intelligent Systems,
University of Paderborn
A) Replace the adversarial description of the mobility by the
random walk of the nodes (considered in [BKM04,BK05] for
a kind of Brownian motion of the nodes)
B) Generate requests randomly (this paper)
 In one step
is drawn uniformly and independently
according to the probability distribution
 The mobility is still dictated by an adversary!
Performance metric: algorithm is
if for all configuration sequences
-competitive with prob.
and all
holds
D.P.M. with Stochastic Requests / M. Bienkowski 8
International Graduate School
of Dynamic Intelligent Systems,
University of Paderborn
Our contribution
 A deterministic algorithm MTFR, which achieves constant
competitive ratio with high probability
High probability
probability == for
for any
any we
we may
may achieve
achieve aa probability
probability
 High
ifif the
the input
input sequence
sequence is
is sufficiently
sufficiently long.
long
 Using potential functions and amortized analysis we proved
also that in the worst case (both and
generated by
an adversary) the competitive ratio of MFTR is
 The expected value of the competitive ratio is
on sufficiently long sequences
D.P.M. with Stochastic Requests / M. Bienkowski 9
International Graduate School
of Dynamic Intelligent Systems,
University of Paderborn
Static placement is bad
 Assume that our algorithm knows
 Then the best possible static placement strategy is to
choose a node
with maximum
 Strategy for the adversary:
Then OPT places the page at
The cost of the algorithm is
Thus, for large
exp. cost
the competitive ratio is at least
D.P.M. with Stochastic Requests / M. Bienkowski 10
International Graduate School
of Dynamic Intelligent Systems,
University of Paderborn
A better solution
 We may choose a node randomly according to
constant competitive ratio in expectation, but
the variance is high.
 Better: we may choose a new position for the page
randomly not once, but from time to time, once for
steps
 Our algorithm MTFR:
 Divides time into phases of length
 use actual outcomes of the random process: at the beginning of a
phase moves to the node which issued a request
 We prove that MTFR is
-competitive
D.P.M. with Stochastic Requests / M. Bienkowski 11
Average cost of communication
International Graduate School
of Dynamic Intelligent Systems,
University of Paderborn
Consider any positions of the nodes in time
We define average cost of communication in step
Let
be the maximum cost of communication between
two nodes in time .
and
We relate costs of OPT and MTFR to
D.P.M. with Stochastic Requests / M. Bienkowski 12
Lower bound on OPT
International Graduate School
of Dynamic Intelligent Systems,
University of Paderborn
Lemma:
Situation in step
Proof by triangle inequality (on costs)
Thus,
Moreover, this lower bound on
only on steps and
.
depends
D.P.M. with Stochastic Requests / M. Bienkowski 13
International Graduate School
of Dynamic Intelligent Systems,
University of Paderborn
Expected value -> High probability
 We have a sequence of independent variables
, s.t.


 We have no global bound on
...
 ... but we can relate
in two consecutive steps:
If
, then two consecutive
differ by at most
Combinatorial Lemma: If we have more than
such variables, then their sum differs by at most a constant
factor from its expectation with probability
w.h.p.
D.P.M. with Stochastic Requests / M. Bienkowski 14
International Graduate School
of Dynamic Intelligent Systems,
University of Paderborn
Cost of MTFR
phase
 The cost in time step depends only on
and the node
holding the page (equal to
)
The expectation is also
 Problem: more dependencies
 Solution: Consider a cost in the whole phase without its
first step – independent for two different phases
 Bound cost in first steps separately (phases are quite long)
Variant of Combinatorial Lemma implies that for input
sequences longer than
holds w.h.p.
D.P.M. with Stochastic Requests / M. Bienkowski 15
Final remarks
International Graduate School
of Dynamic Intelligent Systems,
University of Paderborn
 Is there an algorithm which performs well both in the
adversarial scenario and under stochastic requests?
 What happens if we make
different for each step?
 In general – we cannot get a better bound than the fully
adversarial scenario
 What if
depends only on the node which issued request
in the last step?
D.P.M. with Stochastic Requests / M. Bienkowski 16
International Graduate School
of Dynamic Intelligent Systems,
University of Paderborn
Thank you for your attention.
Lower bound for adversarial scenario
International Graduate School
of Dynamic Intelligent Systems,
University of Paderborn
 For the deterministic case:
time
decision point


D.P.M. with Stochastic Requests / M. Bienkowski 18