Transcript Single-copy Routing

ATCN: Delay Tolerant Networks (III)
(1/12/08)
Thrasyvoulos Spyropoulos (Akis)
[email protected]
Why Performance Analysis?
 Simulations are not enough

Long time to run for each new parameter set (min, hours, days!)

Do not scale to large number of nodes (memory, processing issues)

Can get lost in the details of elaborate implementation

Design and Optimization is heuristic
 Traces and experiments are not enough

Usually even smaller than simulations; proof of concept

Too difficult to check/try various design alternatives

Design and Optimization is heuristic
 Theory

Quick rough estimate of performance

Interpretability of design choices and their effect on performance

Modeling and Optimization
2
Epidemic Routing
 Give a message copy to every node encountered

essentially: flooding in a disconnected context
D
F
E
D
B
D
D
D
D
A
C
3
Delay of Epidemic Routing
1 M K
Ti
ED 


M  1 K 1 i 1
D
2
T1 = 1 red → 1any blue
2
T2 = any of 2 red → any blue
S

M nodes

I.I.D. mobility
4
Contact and Inter-Contact Times
 Meeting (contact) time: Time until two nodes starting from the
stationary distribution come in communication range
 Inter-meeting (inter-contact) time: Time until two nodes starting from
within communication range come in communication range (again)
2D (pure) Random Walk
A
B
p = 0.25
A
Meeting time
Inter-Meeting time
DEPENDING ON THE MOBILITY MODEL, THESE TWO
MIGHT HAVE VERY DIFFERENT STATISTICS!!
5
Delay of Epidemic Routing (2)
 Start: only source has copy
 T1: time until source node encounters any node with no copy

i.e. any of the remaining M-1 nodes
 MS,j = random variable; meeting time between SRC (S) and node j
 T1 = minj {MS,j} (random variable)

Prob ( T1 < t ) = Prob ( Ms,1 < t or Ms,2 < t … or Ms,N-1 < t)
 If we know the mobility model, then (sometimes) we can derive Ms,j

More about this later
 If we know Ms,j, we can derive T1 (and T2, T3, etc.)
6
Delay of Epidemic Routing (3)
Ms,1
Ms,2
Ms,3
Ms,4
 M-1 clocks counting down do zero, with randomly chosen initial time
 What is the time until the first one finishes?
7
Delay of Epidemic Routing (4)
But how do we calculate Ti?
 What if we assume Ms,j are exponentially distributed?

E[Ms,j] = EMs,j
(expected meeting time between s and j)

P(Ms,j > t) = e-(t/EMs,j)

common for a number of phenomena, e.g. lifetime of components,
time between human initiated actions
 Assume also that all M nodes behave the same? i.e. EMs,j
= EM?
 T1 is also exponentially distributed with ET1 = EM/(M-1)
8
Delay of Epidemic Routing (5)
D
2
EM
M -1
1
2
S
EM
2(M - 2)
EDopt

M nodes

Tx Range = K
HM-1
 EM
(M - 1)
where HM-1 is the
harmonic sum
M1
1
HM1  
i1 i
9
Checkpoint Questions: Spray and Wait
 Q1: What is the expected remaining delay for Spray and Wait after
all L copies have been spread?
 Q2: What is the probability that the destination is “found” before all L
copies are distributed?
10
Delay of 2-hop Scheme
 2-hop scheme (v2): source -> everyone, relay ->dst only
 Delay?
ET1 = time until source meets any node (among M-1)
ET2 = time until source meets any node (among M-2)

epidemic: time until 2 red meet any of M-2 (smaller)
M  n 1
ED(n)  ETn 1 
ED(n  1)
M n
Rem. Delay after
n copies
Prob{next node not
DST)
BUT: a relay node may meet destination in the meantime!
11
Modeling Epidemic Spreading: Markov Chains (MC)
Prob(ii+1,t) = (N-i)*i*t
N+1: nodes
1/ = EM (meeting time)
state i: i copies
state A: DST found
Epidemic Routing
2-hop Routing
12
Modeling Content Dissemination with MCs
 PodNet
 No-cooperation strategy
(N 1) 

1
2


N1
(N  i) 
(N  2) 
i

2


N-1
N
1 N1 1
1 N1 1 1
E[Todt ]    
   HN1


N

i
 j1 j 
i1 i
i1
1
 Unlimited cooperation
(N 1) 


1
E[Todt ] 

i(N  i) 
2(N  2) 
2

i

2(N  2) 

(N 1) 
N-1
N
13
2
H N 1
N
13
Fluid Models (Deterministic)
 Assume N (num. of nodes)  
 I(t) = average number of “infected” nodes at time t
'
I (t)  λ (N  I) I
(1)
 P(t) = P(Td <t) CDF of delivery delay
P(t+dt)-P(t) = Prob{t ≤ Td ≤ t + dt}
= Prob{DST meets one of nI(t) infected nodes in [t,t+dt]} * Prob(Td>t)
= E[Prob(DST meets nI(t) | nI(t)] * (1-P(t))
= E[nI(t)dt]*(1-P(t))
=  I(t) * (1-P(t)) dt
=>
P (t)  λ I (1  P)
'
(2)
14
Fluid Models (Deterministic) (2)
 Ordinary Differential Equations (ODEs)


Or systems of ODEs
Sometimes PDEs, too.
 Solve (1) for I(t) – it’s a separable ODE
N
I(t) 
1  (N  1)e  λNt
 Replace I(t) in (2) and solve for P(t)
N
P(t) 
(N  1)  e  λNt
 Expected Delay

lnN
ETd   (1  P(t))dt 
λ(N  1)
0
15
Random Walk: Hitting Time (Tx Range K ≥ 0)

Hitting time ET = EXTA (EM equal to ET/2)
A(K)
1) EXTA = EXTY - EATY
Y
p = 0.25
K=3
X
2) EXTY = cNLogN
 2K 1  K  2 
  N
3) E A TY  
K
 2 1 

2K 1  K  2 

ET  N cLogN 
K
2 1 

16
Random Waypoint
 Choose a point in the network uniformly

Choose speed randomly
 Pause for a random amount of time
 Choose another point uniformly and repeat
Pause
17
Random Direction (Random Waypoint): Hitting Time

N
Movement is a set of “epochs”
Method:
1.
D
Probability that any given epoch hits the
destination
epoch
finish
2KL
Phit 
N
2.
Expected number of such epochs
(geometric)
Ne 
3.
1
N

Phit 2KL
Multiply by the expected duration of each
4.
epoch Te
N
ET 
Te
2KL
N
K
epoch
start S
L
EM: divide by (normalized) relative


E[|
v

v
S
D |]
speed between S and D, vr 
]
E[| v S |]
ET
EM 
vr
18
Real Mobility Traces
 WLAN Traces

Associations between AP and terminal
 Encounter-based traces

Give wireless devices to people

Log encounters (associations) between them
 Vehicular Traces

GPS traces
 Trace Analysis: reality is different from simple
random models

Heterogeneity, time-dependency, location-preference
19
Inter-contact Times Measurements
 Consecutive transmission opportunities to a given node
 Contact-based trace measurements: what is the
distribution of inter-contact times?

WLAN traces (Dartmouth, UCSD)

Inter-node (ad hoc mode) traces (Cambridge, Toronto)
20
CCDF for Inter-contact Times
 LOG-LOG plots
 Straight line in log-log plot => power law/heavy-tailed (slope = exponent)
21
CCDF for Inter-contact Times (2)
 WLAN traces: similar behavior
22
Power Law Distributions




P[X > x] = x-a
Infinite variance
a < 2: infinite mean
There is a high probability that some very large values will
be drawn if X is sampled sequentially
 Contrast: exponential decay variables

Very large values: almost improbable
Most of the mobility models (synthetic) presented so far
had exponential tails
23
Power Law Distributions: Complications
 Theory: most analysis (Markov, ODEs, combinatorics)
assumes exponential tail

Essentially for X1,X2,…,Xn IID and exponential

E[min{X1,X2,…,Xn}] = EX / n
 Protocol Performance

Opportunistic routing: give a copy randomly

Depending on the exponent (a) any opportunistic protocol
(e.g. direct transmission, 2-hop, spray&wait) may have
infinite delay!
24
But is it REALLY Heavy-tailed?
 Power-law only within a range of CCDF
 What about the rest of the tail (artifact of experiments, or not power-law
really)?
25
A Primer on Random Walks (on Graphs)
 A graph G(V,E)
 Edges (in E) represent probabilities of moving from current location
to another
 A “random walker” starts from a vertex and randomly goes from
vertex to vertex according to the edge probabilities.
pij
26
A Primer on Random Walks (on Graphs) (2)
 Most mobility models we saw could be represent as random walks
on graphs
 Random walk on 2D: graph is an NxN grid
 Random Waypoint and Random Direction
 Profile-based
Result: Time to arrive at (“hit”) any of a given subset of locations on the
graph, starting from stationary distribution => its distribution has
an exponential tail
27
A Primer on Random Walks (on Graphs) (r)
Can the inter-contact times observed in traces be explained/reproduced
with simple random walk models?
2D (pure) Random Walk
A
B
A
Mixing time
Inter-Meeting time
 Inter-contact time < mixing time: power law
 Inter-contact time > mixing time: exponential
28
Community-based Mobility (Spatial Preference)
 Multiple Communities (house, office, library, cafeteria)
 Time-dependency
Rest of the network
p23(i)
Office
C2
p12(i)
p32(i)
p21(i)
Library
C3
House
(C1)
p11(i)
Community (e.g. house, campus)
29