Transcript palm

Palm Calculus
Made Easy
The Importance of the Viewpoint
JY Le Boudec
1
Contents
1. Informal Introduction
2. Palm Calculus
3. Other Palm Calculus Formulae
4. Application to RWP
5. Other Examples
6. Perfect Simulation
2
1. Event versus Time Averages
Consider a simulation, state St
Assume simulation has a stationary regime
Consider an Event Clock: times Tn at which some specific changes
of state occur
Ex: arrival of job; Ex. queue becomes empty
Event average statistic
Time average statistic
3
Example: Gatekeeper
job arrival
0
90 100
190 200
290 300
t (ms)
5000
5000
1000
5000
1000
1000
4
Sampling Bias
Ws and Wc are different
A metric definition should mention the sampling method (viewpoint)
Different sampling methods may provide different values: this is the
sampling bias
Palm Calculus is a set of formulas for relating different viewpoints
Can often be obtained by means of the Large Time Heuristic
5
Large Time Heuristic Explained on an
Example
6
7
8
The Large Time Heuristic
We will show later that this is formally correct if the simulation is stationary
It is a robust method, i.e. independent of assumptions on distributions (and
on independence)
9
Impact of Cross-Correlation
job arrival
0
90 100
190 200
290 300
t (ms)
5000
5000
1000
5000
1000
1000
Sn = 90, 10, 90, 10, 90
Xn = 5000, 1000, 5000, 1000, 5000
Correlation is >0
Wc > W s
When do the two viewpoints coincide ?
10
Two Event Clocks
timeout
t0
t0
t1
t (ms)
0,a
0,a
a
0,a
Stop and Go protocol
Clock 0: new packets; Clock a: all transmissions
Obtain throughput as a function of t0, t1 and loss rate
11
timeout
t0
t0
t1
t (ms)
0,a
0,a
a
0,a
12
timeout
t0
t0
t1
t (ms)
0,a
0,a
a
0,a
13
Throughput of Stop and Go
Again a robust formula
14
Other Samplings
15
Load Sensitive Routing of Long-Lived IP Flows
Anees Shaikh, Jennifer Rexford and Kang G. Shin
Proceedings of Sigcomm'99
ECDF, per packet viewpoint
ECDF, per flow viewpoint
16
17
18
2. Palm Calculus : Framework
A stationary process (simulation) with state St.
Some quantity Xt measured at time t. Assume that
(St;Xt) is jointly stationary
I.e., St is in a stationary regime and Xt depends on the past,
present and future state of the simulation in a way that is
invariant by shift of time origin.
Examples
St = current position of mobile, speed, and next waypoint
Jointly stationary with St: Xt = current speed at time t; Xt = time to be
run until next waypoint
Not jointly stationary with St: Xt = time at which last waypoint
occurred
19
Stationary Point Process
Consider some selected transitions of the simulation, occurring
at times Tn.
Example: Tn = time of nth trip end
Tn is a called a stationary point process associated to St
Stationary because St is stationary
Jointly stationary with St
Time 0 is the arbitrary point in time
20
Palm Expectation
Assume: Xt, St are jointly stationary, Tn is a stationary point
process associated with St
Definition : the Palm Expectation is
Et(Xt) = E(Xt | a selected transition occurred at time t)
By stationarity:
Et(Xt) = E0(X0)
Example:
Tn = time of nth trip end, Xt = instant speed at time t
Et(Xt) = E0(X0) = average speed observed at a waypoint
21
E(Xt) = E(X0) expresses the time average viewpoint.
Et(Xt) = E0(X0) expresses the event average viewpoint.
Example for random waypoint:
Tn = time of nth trip end, Xt = instant speed at time t
Et(Xt) = E0(X0) = average speed observed at trip end
E(Xt)=E(X0) = average speed observed at an arbitrary point in time
Xn+1
Xn
22
Intensity of a Stationary Point Process
Intensity of selected transitions:  := expected number of transitions
per time unit
25
Two Palm Calculus Formulae
Intensity Formula:
where by convention T0 ≤ 0 < T1
Inversion Formula
The proofs are simple in discrete time – see lecture notes
26
27
3. Other Palm Calculus Formulae
28
Feller’s Paradox
29
30
Rate Conservation Law
31
32
33
Campbell’s Formula
Total load
t
T1
T2
T3
Shot noise model: customer n adds a load h(t-Tn,Zn) where Zn is some
attribute and Tn is arrival time
Example: TCP flow: L = λV with
L = bits per second, V = total bits per flow and λ= flows per sec
34
Little’s Formula
Total load
t
T1
T2
T3
35
Two Event Clocks
Two event clocks, A and B, intensities λ(A) and λ(B)
We can measure the intensity of process B with A’s clock
λA(B) = number of B-points per tick of A clock
Same as inversion formula but with A replacing the standard clock
36
Stop and Go
A
B
A
B
B
A
B
37
4. RWP and Freezing Simulations
Modulator Model:
38
Is the previous simulation stationary ?
Seems like a superfluous question, however there is a difference in
viewpoint between the epoch n and time
Let Sn be the length of the nth epoch
If there is a stationary regime, then by the inversion formula
so the mean of Sn must be finite
This is in fact sufficient (and necessary)
39
Application to RWP
40
Time Average Speed, Averaged over n
independent mobiles
Blue line is one sample
Red line is estimate of E(V(t))
41
A Random waypoint model that has no
stationary regime !
Assume that at trip transitions, node speed is sampled
uniformly on [vmin,vmax]
Take vmin = 0 and vmax > 0
Mean trip duration = (mean trip distance) 
1
vmax
vmax

0
dv
 
v
Mean trip duration is infinite !
Was often used in practice
Speed decay: “considered harmful” [YLN03]
42
What happens when the model does not
have a stationary regime ?
The simulation becomes old
Stationary Distribution of Speed
(For model with stationary regime)
Closed Form
Assume a stationary regime exists and simulation is run long enough
Apply inversion formula and obtain distribution of instantaneous speed V(t)
Removing Transient Matters
A (true) example: Compare impact of
mobility on a protocol:
Experimenter places nodes uniformly
for static case, according to random
waypoint for mobile case
Finds that static is better
Q. Find the bug !
A. In the mobile case, the nodes are
more often towards the center, distance
between nodes is shorter, performance
is better
The comparison is flawed. Should use
for static case the same distribution of
node location as random waypoint. Is
there such a distribution to compare
against ?
Random waypoint
Static
46
A Fair Comparison
We revisit the comparison by sampling the static case from
the stationary regime of the random waypoint
Static, same node location as RWP
Random waypoint
Static, from uniform
Is it possible to have the time distribution of speed uniformly distributed in
[0; vmax] ?
48
5. PASTA
There is an important case where Event average = Time average
“Poisson Arrivals See Time Averages”
More exactly, should be: Poisson Arrivals independent of simulation state See
Time Averages
49
50
51
Exercise
52
Exercise
53
6. Perfect Simulation
An alternative to removing transients
Possible when inversion formula is tractable
Example : random waypoint
Same applies to a large class of mobility models
54
Removing Transients May Take Long
If model is stable and initial state is drawn from distribution
other than time-stationary distribution
The distribution of node state converges to the time-stationary
distribution
Naïve: so, let’s simply truncate an initial simulation duration
The problem is that initial transience can last very long
Example [space graph]:
node speed = 1.25 m/s
bounding area = 1km x 1km
55
Perfect simulation
is highly desirable (2)
Distribution of path:
Time =
50s
Time =
500s
Time =
100s
Time =
1000s
Time =
300s
Time =
2000s
56
Solution: Perfect Simulation
Def: a simulation that starts with stationary distribution
Usually difficult except for specific models
Possible if we know the stationary distribution
Sample Prev and Next waypoints from their joint stationary distribution
Sample M uniformly on segment [Prev,Next]
Sample speed V from stationary distribution
Stationary Distrib of Prev and Next
Stationary Distribution of Location Is also
Obtained By Inversion Formula
59
60
No Speed Decay
Perfect Simulation Algorithm
Sample a speed V(t) from the time stationary distribution
How ?
A: inversion of cdf
Sample Prev(t), Next(t)
How ?
Sample M(t)
62
Questions
Q1: A node receives messages from 2
sensors S1 and S2. Each of the sources
sends messages independently of each
other. The sequence of time intervals
between messages sent by source S1 is
iid, with a Gaussian distribution with
mean m1 and variance v1 and
similarly for S2. The node works as
follows. It waits for the next message
from S1. When it has received one
message from S1, it waits for the next
message from S2, and sends a message
of its own.
Q2: A sensor detects the
occurrence of an event and sends a
message when it occurs. However,
the sensing system needs some
relaxation time and cannot sense
during T milliseconds after an
event was sensed. There are l
events per millisecond. Can you
find the probability that an event is
not sensed, as a function of T?
How much time does, in average, the
node spends waiting for the second
message after the first is received ?
63
Questions
Q3: Consider the random waypoint model,
where the distribution of the speed drawn
at a random waypoint has a density f(v)
over the interval [0, vmax]. Is it possible to
find f() such that (1) the model has a
stationary regime and (2) the time
stationary distribution of speed is uniform
over [0, vmax] ?
Q4: A distributed protocol establishes
consensus by periodically having one host
send a message to n other hosts and wait
for an acknowledgement. Assume the times
to send and receive an acknowledgement
are iid, with distribution F(t). What is the
number of consensus per time unit
achieved by the protocol ? Give an
approximation when the distribution is
Pareto, using the fact that the mean of the
kth order statistic in a sample of n is
approximated by F−1( k/ n+1).
Q5: We measure the distribution of flows
transferred from a web server. We find that
the distribution of the size in packets of an
arbitrary flow is Pareto. What is the
probability that, for an arbitrary packet, it
belongs to a flow of length x ?
Q6: A node receives messages from 2
sensors S1 and S2. Each of the sources
sends messages independently of each
other. The sequence of time intervals
between messages sent by source S1 is iid,
with a Gaussian distribution with mean m1
and variance s12 and similarly for S2. The
node works as follows. It waits for the next
message from S1. When it has received one
message from S1, it waits for the next
message from S2, and sends a message of its
own.
How do you implement a simulator for this
system ?
How much time does, in average, the node
spends waiting for the second message after
the first is received ?
64
Conclusions
A metric should specify the
sampling method
Different sampling methods may
give very different values
Palm calculus contains a few
important formulas
Which ones ?
Freezing simulations are a pattern
to be aware of