Transcript forwarding metrics

On Exploiting Transient Social Contact Patterns
for Data Forwarding in Delay-Tolerant Networks
Wei Gao
Guohong Cao
Tom La Porta
Jiawei Han
Presented by Michael Conlan
1
Agenda
Introduction
Overview of Network Model and Algorithm
Trace-Based Pattern Formulation
Data Forwarding Metric
Exploiting Transient Community Structure
Performance Evaluation
Conclusion
Introduction: Problem Statement



Delay Tolerant Networks (DTN) populated by
mobile devices have intermittent connectivity
and low node density
Data forwarding metrics determined by
stochastic processes and predicted node
mobility limited by human randomness
Problem Statement: How best to forward/relay
data in DTNs to ensure timely and efficient
delivery?
Introduction: Social Contact Patterns

Node forwarding capability characterized by their
Social Contact Patterns:





Centrality – connectivity to many nodes that enables
wider or faster delivery
Community – naturally occurring grouping of connected
nodes
Consider on global scope and local scope
Most social aware forwarding schemes based on
cumulative social contact patterns
BUT cumulative contact patterns differ from
transient contact patterns
Introduction: Proposed Solution

Proposed Solution: Exploit Transient Social Contact
Patterns to improve data forwarding by considering
these perspectives of contact patterns:





Transient Contact Distribution – rate of contacts over time
Transient Connectivity – formation of transient connected
subnets (TCS) for periods of time
Transient Community Structure – different communities created
through the day
Show that these perspectives have predictable behavior
representable by Gaussian functions
Develop forwarding metrics based on these functions to
use in a forwarding strategy for better data delivery
Overview: Forwarding Algorithm


Forwarding decision of whether nodei sends data, dk, to nodej
dependent on node forwarding metrics and forwarding
strategy

mj = data forwarding metric of nodej

Qi = strategy based metric of i to compare with mj
Common strategy that forwards data dk to nodej if:




Nodej is the destination node
Else if nodej is in the community of the destination node and
nodei is not
Else if Qi < mj
Calculate m based on transient contact perspectives
Overview: Transient Perspectives

These perspectives provide more accurate estimation on the node's
capability of contacting others within a given scope and time period


Fig (a) shows that λ, rate of contacts, varies over time and
transient values provide greater fidelity than cumulative
Fig (b) shows how B may be a better choice than C due to
indirect access to more nodes despite a lower contact rate
Overview: Transient Perspective



Rates are further refined by
considering scope over time
Rate is weighted higher
when node is in a community
local to the destination node
For example, if the transient
community structure of C is
not considered, then λt of
node C would be 2.83
((2x1+3x5)/6) and C would
look better than A
Trace-Based Pattern Formulation


Performed study on multiple networks to understand
and characterize their transient contact patterns
Network model and assumptions include

Contacts are symmetric

Stochastic contact process modeled as edge

Data is small such that bandwidth and buffering are
considered irrelevant
-Bluetooth devices
detect peers nearby and
make contact to them
-WiFi search access
points (AP) and make
contact with others on
same AP
9
Pattern Formulation: Transient Contact Distribution
On-period of length Lon is
when there are a set of
contacts within a
threshold time Ton
Stable and predictable onperiods
10
Pattern Formulation: Transient Contact Distribution
For Ton set to 8 hrs, results are:
11
Pattern Formulation: Transient Contact Distribution


Graphs show that the distribution of on and off
periods can be accurately approximated by normal
distribution using mean and variance below
Model validated by mean on and off adding to 24
hrs, and >80% of contacts occur during on-periods
12
Pattern Formulation: Transient Connectivity


A node's connectivity is represented by the size of
it's TCS (Transient Connected Subnet)
The TCS of node i during time period [t1,t2] consists
of all nodes that have end to end comms with node i
during that period

13
Pattern Formulation: Transient Connectivity

TC depends on distribution of contact duration.


MIT: 20% > 1hr, UCSD: 30% > 1hr, Infocom: 5% >
30mins.
The average TCS size of each node.

MIT: over 50% > 3, UCSD: over 50% > 100, Infocom:
negligible due to 30min issue above.

14
Pattern Formulation: Transient Connectivity

The average TCS of all nodes can be
approximated by:
* A = amplitude function

Fig 3 & Fig 9 correlate therefore demonstrate that
TC is proportional to the amount of contacts during
time period t
Pattern Formulation: Transient Community
Structure

Community structure only exists if there are more nodes than a
certain threshold that form a stable community



Community relationship defined as a “joint-period” when a pair of
nodes are in the same community
Detection of communities by k-clique and modularity method
Fig. 10 shows low community change at peak of node contacts (see
Fig. 3 ) when community is stable and at night when only few
contacts occur
Pattern Formulation: Transient Community
Structure

Joint period can be also accurately
approximated by normal distribution


Note μco is less than μon
Low variance indicates
large communities
17
Forwarding Metric





Data forwarding metric based on node centrality
Measure node centrality for a given scope and time
constraint using transient contact distribution and
transient connectivity
Ci is node i's centrality calculated by the sum of cij, the
number of nodes i can contact by contacting j
Direct contacts determined from transient contact
distribution
Indirect contacts through j based on transient
connectivity of node j
Forwarding Metric:Incorporating Transient
Contact Pattern



For each pair of nodes i and j, the parameters of their on-period and
off-period are updated every time they directly contact each other
Each node detects its TCS when contacted by broadcasting a
detecting beacon
Transient connectivity is then updated by Gaussian curve fitting
based on the recorded TCS sized during different hours
Forwarding Metric: Update Algorithm
20
Forwarding Metric: Contact Probability
The contact process is stable
and predictable only during
on-periods as in case 1(a)
and 2 (b)
Contact occurrence
probability
pij=pij1+pij2
Probability of contact during
on-period
pc(t1,t2)=1-e-λ(t2-t1)
21
Forwarding Metric: Contact Probability
Case 1
Case 2
Forwarding Metric: Incorporating Transient Connectivity
Case 2
Case 1
Incorporate TCS where
size given by:
Similar transformation
pij from last page
but now:
finally,
Forwarding Metric:Prediction Error


Contact occurs but not known to be the
start of an on-period or still an off-period

But 80% of contacts occur during
on-period according to previous
results
Long off periods lower accuracy of Case 2
24
Exploiting Community Structure

As in case (b) above, the forwarding metric is
weighted by community membership over time

Network periodically detects community members

Can incorporate joint-period statistics
25
Performance Comparison: Setup

Used the test networks and randomly
picked source and destination nodes



Social contact patterns are characterized
real time as described
Community structure measured by
modularity method
Performance criteria are data delivery ratio
and forwarding cost
Performance Comparison: Setup

Compared with other forwarding metrics:




Betweenness-social importance of a node facilitating
communication among others
Cumulative contact probability (CCP)-prob of contacting others
based on cumulative contact rates
Forwarding Strategies used




Contact counts (CC)-calculated cumulatively since network
start
Compare-and-forward-forward to all nodes with higher metric
than itself
Delegation forwarding-forward to all nodes with higher metric
than the highest it has ever had
Spray-forward limited set of copies to nodes with highest
metric, each relay node forwards one copy to highest
Epidemic is the benchmark and BUBBLE Rap also
tested
Performance Comparisons – Data Delivery
Ratio



Using compare and forward strategy with different metrics
When time constraint is short, transient approach far
outperforms all others and matches epidemic
With a longer time constraint, the cumulative
characteristics become more consistent and transient
advantage decreases
28
Performance Comparisons – Forwarding
Costs


Graphs show transient metric results in 20%
lower forwarding cost
General uptrend with increasing time
constraint since more time allows more to be
forwarded nodes to
Performance: Impact of Ton


Ton of 8 hrs has optimal performance
Smaller time contraint is more sensitive
to sub-optimal Ton
30
Performance: Impact of Transient
Connectivity



Transient metric Ci is calculated considering direct contacts
only
Performance still better at lower time constraint, worsens at
higher time
Delta performance across networks due to large TCS size in
USCD and short contact duration in Infocom
31
Performance: Case 1&2 Contact Prediction


Case 1 predicts an on-period will continue and
contributes more to delivery with low time
constraint
Case 2 predicts future on-periods and has more
accuracy with a longer time constraint
32
Performance: Static Community Structure


Using a static community structure shows
decreased delivery with a high time constraint
With low time constraint, most delivery must be
local anyway
33
Performance: Community detection
Comparison of community detection methods show
little difference in cost but better performance with
modularity
Performance: Transient Community Structure with
Different Forwarding Strategies


Delegation best overall with near max performance and
lower cost since it's forwarding is more selective
Spray has limited cost and limited performance due to
limited node
Conclusion

Transient social contact patterns are an
effective way to determine a forwarding metric



Demonstrated predictive behavior of social
contact patterns
Developed transient forwarding metric
based on transient social contact pattern
parameters
Evaluated forwarding performance and
showed improved performance over static
methods