Center for Networked Computing
Agenda • Introduction Ø Current network trends Ø New opportunities in wireless communication
• Routing Design Ø Related Works Ø Cooperative forwarding
• Experiments • Conclusion and future works
Center for Networked Computing
• From Internet to Internet of Things Ø Powerful computation, sensing, and communication abilities v Smartphones, vehicles, wearable devices, etc.
Ø Wide availability of (various) devices
v 8 billions of mobile-ready devices, 10 times of PCs [Cisco White Paper]
Internet of things, pervasive computing, Ubiquitous computing, edge computing, etc.
past
now Center for Networked Computing
• Store-Carry-Forward (Mobility) Ø Mobile nodes physically carry data as relays Ø Forwarding data upon contacts v Forwarding path: path S-B-D and path A-C-E B
A
C
Ø Delay-tolerant (location-based) applications: v Emails, news, advertisements dissemination v Social networks updates Center for Networked Computing
• Applications Ø Opportunistic mobile social networks v Data offloading, disaster communication
Ø Vehicular networks v Autonomous Driving, intelligence transportation system •
,
Mobile social networks
Vehicular networks Center for Networked Computing
• Epidemic
Ø Every node can forward data to every one Ø 2-hop extension: only the data source can copy to others
• Delegation forwarding
Ø The relay forwards the message to an encounter with a higher quality than those in all previous nodes seen so far. Algorithm Epidemic
delay Minimum
2-hop extension Moderate Delegation
Cost (n) Knowledge N No N/2
Compared to Epidemic √N
No Yes Center for Networked Computing
• Can the data always be fully transferred in a contact (a common assumption)? Ø Not always! We verified through two human traces. 0.2
0.05 0
0.6 (2, 0.41)
0.4
(4, 0.07) (6, 0.04) 10
Raw data Exp. curved
Probability
Probability
0.15 0.1
0.8
Raw data Exp. curved
0.2
20
30
Contact duration (min)
INFOCOM trace
40
0
(3, 0.18) 0
5
10
15
20
Contact duration (min)
SIGCOMM trace
• Observation: Ø Longer contacts are just a few while short contacts are many. Ø The contact duration distribution fits the exponential distribution. Center for Networked Computing
• A better contact model: Ø Delivery probability is not a constant value, P. Ø We model the delivery probability of a node as
All contact opportunities
where ! " is a non-increasing decay function with data size, s.
• Cooperative forwarding: Ø Partition original data into small data chunks! Ø Cooperative forwarding: maximally improve the probability of data delivery by sending data segments through multiple paths v Forwarding path: a sequence of contact Center for Networked Computing
•
Distinguish with replication-based routing Ø All previous algorithms (e.g., Epidemic, 2-hop, Delegation forwarding routing). Original data with size S S S
source
S S/2 S/2
destination
Replication-based routing
• Success: Data in any path is delivered; • Data size: original data size.
source
destination
Cooperative-based routing
• Success: Data in every path is delivered. • Data size: small data chunk Center for Networked Computing
• A motivation example Ø The expected delivery probability of different strategies: vSingle path routing P = 0.22 vWith one replication
Data size S Probability 0.22
S/2 0.67
S/3 0.74
P = 1 – (1 – 0.22) (1 – 0.22) = 0.39 vSplit to 2 data chunks P = 0.67*0.67 = 0.45 vSplit to 3 data chunks p = 0.74*0.74*0.74 = 0.41 Center for Networked Computing
• Cooperative Data Forwarding Ø How to determine the optimal partition v Good: higher delivery probability for each small data chunk v Bad: need to receive data from multiple forwarding paths Theory: To maximize data delivery probability if nodes’ mobility follows the random-waypoint model and β(s) is a decreasing function, the optimal datapartitioning strategy within deadline T in the epidemic routing is: ! = −$
%&(() * %(
Ø Algorithm o Calculate the optimal chunk size o if there exists some chunks that the encountered node does not have o Replicate data chunk in a round-robin fashion. Center for Networked Computing
• Cooperative Data Forwarding Epidemic
Single-copy probability-based
With partition
EP
SP
Without partition
EN
SN
0.4
0.8
Delivery ratio
Delivery ratio
1
0.6 EN EP SN SP
0.4 0.2 0
4
6
8
10
Data size (MB) INFOCOM trace
12
EN EP SN SP
0.3 0.2 0.1 0 100
200
300
400
500
600
Data size (MB)
SIGCOMM trace Center for Networked Computing
• Extension Ø Disadvantage: if one of the data chunk is missed, the data forwarding fails. Ø Solution: network coding technique! 1
0.8
delivery ratio
delivery ratio
1
0.6 0.4 With NC Without NC
0.2 0
0
50
deadline (hour) INFOCOM trace
100
With NC Without NC
0.8 0.6 0.4 0.2 0
0
20
40
60
80
deadline (hour) SIGCOMM trace Center for Networked Computing
• Opportunistic networks Ø There are many opportunistic contacts in IoT environment Ø Opportunistic communication (Store-Carry-Forward)
• Routing methods Ø The contact duration might be insufficient for data transmission v Cooperative Data Forwarding v Verified through two human traces
• Future works Ø Try more data traces, e.g, vehicular traces. Ø Try to use network knowledge to optimize routing performance.
Center for Networked Computing
Thank you!
[email protected]
Center for Networked Computing
