Delay‐Tolerant Routing in Opportunistic Delay‐Tolerant Routing in Opportunistic and Intermittent Networks and Intermittent Networks

A Brief to Delay‐Tolerant Networking
 Opportunistic and Intermittent Networks
 Routing Requirements
● Our Ideas and Some Proposals
 Density‐Aware Routing
 Coding‐Based Routing to Multiple Receivers
● Concluding Remarks

1. Delay‐Tolerant Routing in Opportunistic 
and Intermittent Networks
Delay‐Tolerant Routing in Opportunistic 
and Intermittent Networks Chih‐Lin Hu（胡誌麟）
Department of Communication Engineering
National Central University
Taiwan
[email protected]
2013‐3‐11
Chih‐Lin Hu（胡誌麟）
Department of Communication Engineering
National Central University
Taiwan
[email protected]
2013‐3‐11

2. Outline ●
A Brief to Delay‐Tolerant Networking

Opportunistic and Intermittent Networks

Routing Requirements
●
Our Ideas and Some Proposals

Density‐Aware Routing

Coding‐Based Routing to Multiple Receivers
●
Concluding Remarks
2

3. 3
Fukushima, Two Years After

4. 4
1997

5. 5
2009

6. 6
2012

7. 7
2012

8. 8
Source: http://www.spaceref.com/focuson/ipn/

9. Environments & Applications 
Interplanetary Internet, which 
focused primarily on deep‐space 
communications in high delay 
environments

Sensor‐based networks,using 
scheduled intermittent 
connectivity

Terrestrial wireless networks 
cannot ordinarily maintain end‐to‐
end connectivity

Satellite networks with moderate 
delays and periodic connectivity

Underwater acoustic networks 
with moderate delays and frequent 
interruptions due to 
environmental factors

Interplanetary space

Natural disasters

Agricultural lands

Fishery grounds

Forest parks

Grazing areas

Wilderness
[RFC 4838, by Vint Cerf, et al (April 2007 )]
9

10. DTN Routing
10

11. History of Delay‐Tolerant Networking 
[Wiki]
●
In the 1980s, while the field of ad‐hoc routingwas inactive …
●
In the 1990s, the widespread use of wireless protocols 
reinvigorated the field as mobile ad‐hoc networking (MANET)
and vehicular ad‐hoc networking (VANET)became areas of 
increasing interest.
●
In the 2002, the term delay‐tolerant networking and the DTN
acronym were coined. [Kevin Fall, VintCerf, et al.]
●
The mid‐2000s brought about increased interest in DTNs, as well 
as growing interest in combining work from sensor networks 
and MANETswith the work on DTNs. 
11

12. Delay‐Tolerant Networking (DTN) ●
Delay‐tolerant networking (DTN)is an approach to computer 
network architecture that seeks to address technical issues in 
heterogeneous networks that are characterized by tight 
resource constraints on intermittent connectivity, available 
storage, and internode bandwidth throughput. 

Delay/Disruptions may happen because of the limited wireless radio 
range, sparsityof mobile nodes, energy resources, attack, and 
communication noise.

Classicalexamples of such networks are those operating in mobileor 
extremeterrestrialenvironments, or plannednetworks in space.

Recentworks on DTNs bring growing interest in combining works from 
Sensor Networksand MANETs.
12
In 2002, the term delay‐tolerant networking (DTN )was coined. 
[Kevin Fall, VintCerf, et al.]
Classicalexamples of such networks are those operating in mobileor
extreme terrestrialenvironments, or plannednetworks in space.
Recentworks on DTNs bring growing interest in combining works from
Sensor Networksand MANETs.

13. Delay‐Tolerant Routing: Why ●
Existing Internet routing and messaging mechanisms do not 
work well for DTNs due to several fundamental assumptions:

An end‐to‐end path between source and destination exists for the 
duration of a communication session. [y/n?]

Retransmissions based on timely and stable feedback from data receivers 
is an effective means for repairing transmission errors. [y/n?] 

End‐to‐end loss is relatively small. [y/n?] 

All routers and end stations support the TCP/IP protocols. [y/n?]

Selecting a single route between sender and receiver is sufficient. [y/n?]
●
Did you ever get false answers in mind? 

Delay‐tolerant networking may be one of many alternatives to resolve 
the issues.
13
Did you ever get false answers in mind? 
Delay‐tolerant routing may be one of important alternatives to resolve the issues.

14. DTN Architecture: How ●
The DTN architecture provides a common method for 
interconnecting heterogeneous gateways or proxies that 
employ store‐and‐forward message routing to overcome 
communication disruptions. 
[Classical Definition in RFC 4838]
●
The use of the bundle layer is guided not only by its own design 
principles, but also by a few application design principles:

Applications should minimize the number of round‐trip exchanges

Applications should cope with restarts after failure while network 
transactions remain pending

Applications should inform the network of the useful life and relative 
importance of data to be delivered

[RFC 5050] Bundle Protocol Specification
14

15. DTN Architecture: Reference 
[RFC 4838]
15
Source: Kevin Fall, A Delay-Tolerant Network Arch itecture for Challenged Internets, SIGCOMM’03.

16. Delay‐Tolerant Routing in DTNs ●
In DTNs, instantaneous end‐to‐end paths are difficult or 
impossible to be established and guaranteed

Lack of network connectivity by many realistic constraints: 
►
intervening objects, sparse node densities, limited radio range, limited 
energy resource, and node mobility
●
Popular ad hoc routing protocols, such as ad‐hoc on‐demand 
distance vector (AODV)and dynamic source routing (DSR), may 
fail to establish routes in these challenging environments. 

These protocols try to first establish a complete route and then, after the 
route has been established, forward the data. 
16

17. Delay‐Tolerant Routing in DTNs ●
Routing protocols can take to a store, carry and forward
approach.

Data are sent to intermediate (relay) nodes where store and send data 
later over multiple paths to final destinations or to other relay nodes. 
17

18. Delay‐Tolerant Routing in DTNs ●
Two major performance problems in DTNs

Long transfer delay time

Low message delivery ratio
●
Replicating many copies of the message is a common technique 
used to maximize the probability of a message being 
successfully received.

It’s feasible only on networks with large local storage and internode 
bandwidth relative to the expected traffic. 
●
A more discriminating algorithm is required, however, when 
available storage and internode throughput opportunities are 
more tightly constrained.
18

19. Existing DTN Routing Protocols ●
Replica‐based protocols are feasible only when the networks can provide 
large amounts of local storage and internode bandwidth relative to expected 
message traffic and resource waste. 
●
History‐based protocols require nodes to extra maintain a history of 
frequency with ever‐encountered nodes, complicating the forwarding 
decision and inducing considerable computation and maintenance costs 
when node population is large. 
●
Location‐based protocols were based on a weak premise that all nodes have 
special localization abilities, e.g., GPS. 
●
Coding‐based protocols much concentrate on special codingtechnologies, 
e.g., erasioncoding and network coding, rather than developing any routing 
algorithm itself in DTNs.
19
delivery ratio / delivery time / message traffic

20. Existing Delay‐Tolerant Routing Protocols
20
Sourec: T. Spyropoulos, et al., Routing for disruption tolerant networks: taxonomy and design, Wireless Networks,
16:2349–2370, 2010.

21. Our Ideas and Proposals
‐
Density‐Aware Routing with Node Density
‐
Coding‐based routing to Multiple Receivers
21

22. Literature Review on Density‐Aware 
Routing ●
Using different concepts of “density”

Node density [a]

Replication density [b]

Map‐based density [c]

Information density [d] 
22

23. Density‐Aware Routing with Node Density ●
This work traced real message traffic produced by people 
wearing in‐line skates during city tour activities. 
●
This work analyzed the accordionphenomenon of node 
distribution in DTNs.
●
This paper proposed a modified SnWprotocol where the 
number of distributed messages is proportional to the number 
of neighboring nodes in the vicinity. 
23
P.-U. Tournoux, J. Leguay, F. Benbadis, V. Conan, V. Conan, and J. Whitbeck, “The accordion
phenomenon: Analysis, characterization, and impact on DTN routing,” in Proceedings of IEEE INFOCOM,
April 2009, pp. 1116–1124.

24. Density‐Aware Routing with Replication 
Density ●
Replication density indicates that a ratio of a number of 
encountered nodes that already have the particular message by 
a total of encountered nodes within a time period.
●
This work changed the replication policy in the epidemic routing 
protocol.

When a node determines that the current replication density is higher 
than a threshold, it will lower the probability of copying messages to 
neighboring nodes to reduce traffic load in the same area. 
24
X. Wang, Y. Shu, Z. Jin, Q. Pan, and B. S. Lee, “Adaptive randomized epidemic routing for disruption
tolerant networks,” in Proceedings of the 5th International Conference on Mobile Ad-hoc and Sensor
Networks, December 2009, pp. 424–429.

25. Density‐Aware Routing with Map‐based 
Density ●
This work assumed that all nodes have GPS facilities and use 
location‐aided knowledge to route messages in DTNs. 
●
Mobile nodes can mark the dense areas on the geographic map, 
and then forward query messages towards dense areas to 
receive fast responses. 
25
J. Li and P. Mohapatra, “Laker: loca tion aided knowledge extraction rout ing for mobile ad hoc networks,”
in Proceedings of IEEE Wireless Communications and Networking Conference, March 2003, pp. 1180–
1184.

26. Density‐Aware Routing with Info. Density ●
This work addressed the content retrieval based on information 
density in semantic DTN environments. 
●
Each node can overhear the content of any passing messages to 
learn semantic distances to the source and destination nodes in 
DTNs. 
●
Accordingly, a node can direct query message towards the area 
with higher information density to reduce the traffic by query 
messages.
26
M. Fiore, C. Casetti, and C.-F. Chiasserini, “Informa tion density estimation for content retrieval in
manets,” IEEE Transactions on Mobile Computing, vol. 8, no. 3, pp. 289–303, 2009.

27. Density‐Aware Routing in DTNs Chih‐Lin Hu and Bing‐Jung Hsieh, “A Density‐Aware Routing Scheme in Delay 
Tolerant Networks,” Proceedings of the 27th ACM Symposium on Applied 
Computing (ACM SAC'12), Riva del Garda (Trento), Italy, March 25‐29, 2012.
27

28. Density‐Aware Routing Protocol ●
The distribution of node population is non‐uniform 
(sparse/dense) in the geographic scale, and time scale. 
●
In DTNs, ideally, nodes should move or copy messages to 
encountered nodes that are going into dense areas.

The inter‐meeting time between two consecutive encounters in dense 
areas is shorter than that in sparse areas

Nodes may distribute messages rapidly in DTNs, hopefully reducing 
transfer delay and increasing message delivery ratio.
28
…
…
…
…
…
…
…
…
…
…
…
…

29. Our idea stems from … ●
Keeping messages in the dense area

Considering non‐uniform node distributions, it has higher probability to 
encounter target nodes with lower delay time.
●
Generating a small, fixed number of message copies

Avoiding congestion and resource waste, where available storage and 
inter‐node throughput opportunities are more tightly constrained
●
Without auxiliary equipment (e.g. GPS)
●
Exploiting the tendency of Inter‐Meeting‐Time

Good scalability (The factor is independent of node population)

Low complexity
29

30. DTN Context ●
Two general assumptions

Nodes can be aware of their motion speeds in 

Each node can keep track of its Inter‐Meeting‐Time (I) with any 
encountered nodes.rto normalize I
30

31. Density‐Aware Routing Scheme ●
Four design phases
(1) Inter‐meeting time normalization
(2) Density estimation
(3) Boundary detection
(4) Message forwarding 
31

32. (1) Inter‐Meeting Time Formulation ●
Design Properties：

Each node N
n
estimates its local density with       

With respect to any encountered nods N
1,
N
2,
N
3
at time t
1
, t
2
, 
each node can have a sequence of I =     ,       ,      …
●
Node N
n
estimates its local density with .

At t
1
, N
n
encounters a node and updates 
where 
α
is the number of the preceding Is.

At t
0
and                , N
n
immediately updates
32



) (
1



k
k
n n
I I



) (
1
0




k
k
n n
I I

i
n
I
i
n
I
n n
I
0
I
1
n
I
2
n
I
3
n
I

33. Normalized Inter‐Meeting Time ●
In the Random WayPoint(RWP) mobility model, the expectation 
of I is in inverse proportion toa node’s motion speed v[8].
A  : size of network area
R  : transmission range
: expected epoch distance
: expected epoch duration
: average pause time after an epoch
: normalized relative speed
33
) (
2) 1(2 ˆ
1
][
stop
m rwp m
rwp
T T
LR
A
p vp
IE
 

L
stop
T
rwp
vˆT

34. Normalized Inter‐Meeting Time ●
With the simple simulation, the expectation of I is in inverse 
proportion toa node’s motion speed v.
●
Normalized I: 
34
v
v
I I


35. (2) Line‐Based Density Estimation (1/3) ●
Considering the factor of mobile trajectory, 
it could be beneficial to develop an incremental density 
estimation to enhance the estimation measure.
●
Estimation incorporation 

to obtain more estimation 
information from encountered 
nodes in the surrounding area 
to enhance its estimation of 
node density in the current area.
35

36. Line‐BasedDensity Estimation (2/3) ●
Define the density estimation D
n
(t) in [0 ~ 0.5 ~1]
36
n n n n
n n n n
n n n n
n n n n
n n
n n
n
I I and I I
I I and I I
I I and I I
I I and I I
I I
I I
tD
 
 
 
 










0
0
0
0
2 ,
2 ,
2 ,
2 ,
2 1
0
2 1
0
)(










37. Line‐Based Density Estimation (3/3)  ●
Two encountered nodes exchange their values of 
density estimate, i.e., D
n
(t)and D
e
(t)
●
For simplification, anode N
n
defines the real density 
estimate 
á
in [0,1], given as 
37
2))( )(()(tD tD t D
e n
n
 
similar D
n
(t)different D
n
(t)

38. 1
n
I
2
n
I
0
n
I
3
n
I
1
n
I
2
n
I
1
2
I
0
n
I
3
n
I
1
1
I
2
1
I
1
9
I
Tree‐BasedDensity Estimation (1/4) ●
Keep track of         Iinstead of only considering α I.
●
Two encountered nodes exchange their values of 
density estimate, i.e., SD
n
(t)and SD
e
(t)
38


1
2
i
i

39. Tree‐Based Density Estimation (2/4) ●
Building the tree based on the history table.
39
2
e
I
1
9
I
1
e
I
1
n
I
1
2
I
2
n
I
1
n
I
2
n
I
1
2
I
2
e
I
1
e
I
2
2
I
1
n
I
2
n
I
1
2
I
1
e
I
2
e
I
1
9
I
1
9
I
1
3
I
3n
I
 
1
8
I
 
n
e
V
V

 
e
n
V
V


40. Tree‐Based Density Estimation (3/4) ●
Weighting local density estimation:
40
1
n
I
2
n
I
1
2
I
2
e
I
1
e
I
1
n
I
2
n
I
1
2
I
2
e
I
1
e
I
)1(
2
i
-1
2
-2
2 1
2
2
I
1
9
I
2
2
I
1
9
I
1
3
I
3n
I
 
1
8
I
 
1
8
I



) (
1



k
k
n n
I I


 

) 2 (
1
,
2
1
)1 (
1


 


k
jk
n
j
n
I I

41. Tree‐Based Density Estimation (4/4) ●
Considering the encountered angle.

We try to  know the quantity of information from the 
encountered node.
41
)
2
sin 1())(
2
sin )( ()(


   t SD t SD tD
node encounter n n




42. (3) Boundary Detection ●
Two nodes determine that they should locate in a dense area 
boundary as D
n
(t)>0.5 and D
e
(t)<0.5
●
Four cases as two nodes encounter in a dense area boundary:  
42

43. (4) Forwarding Strategy ●
Quota‐based routing scheme (Spray‐and‐Wait [7])

There are a fixed number of Mmessage copies distributed in 
the network.

Binary spray delivery

Forwarding phase
●
Packet forwarding priority

Destination > Spray phase > Forwarding phase
43

44. Forwarding Strategy ●
Binary spray phase: 

The source node of a message initially starts with a replication quota of 
Mmessage copies. 

When any node (source or relay node) has more than one message 
copies and encounters another node with no copies, it hands over half of 
its message copies to the other. 
●
Wait Forwarding phase: 

When a node is left with only one copy, it switches to the wait phase.

Whenever such a node meets another node, it performs a proactive 
forwarding decision according to density estimation in proximity and 
boundary detection. 
►
The message copy is sent to a node being in or going to a dense area.
44

45. Simulation Environment 
The ONE Simulator (Opportunistic 
Network Environment)

Simulation area : 2400*2000 m
2

Number of node : 100~1000 (300)

Transmission rate : 250 KB/s

Transmission range : 10 m

Buffer size : 10 MB

Message generation period : 50 
seconds

Message size : 50 KB

Time to Live (TTL) : 9000 seconds

Number of copies per message : 8

Extended Random WayPoint
Mobility model

Regarding the center of the map 
as a dense area, a parameter P
indicates the probability of a node
moving toward the dense area

P: 0.1~0.9

Motion speed : 0.5~2.5 m/sec

Pause times : 0 second

Number of preceding inter‐
meeting times: α= 1~6 
45
The simulator runs in 345600seconds and
sends out 5912original packets in total.

46. Effective Density Estimation ●
P = 0.6
46

47. Delivery Ratio (Line based)  
with Different Values of Pand α
47

48. Delivery Ratio (Tree based)  
with Different Values of Pand α
48

49. Delivery Ratio
in Different Number of Dense Areas 
49
●
P = 0.6

50. 0.65
0.7
0.75
0.8
0.85
0.9
100 200 300 400 500 600 700
Delivery Ratio
(%)
Number of nodes SnW
Line Based
Tree Based
Delivery Ratio
in Different Number of Nodes
50

51. 0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
0.10.250.512345678910100
Delivery Ratio
(%)
Buffer size(MB)
SnW
Line Based
Tree Based
Epidemic
Delivery Ratio
in Different Buffer size
51

52. 0
100
200
300
400
500
600
700
800
100 200 300 400 500 600 700 800 900 100
Transmission overhead
Number of nodes
SnW Line Based Tree Based Epidemic
Transmission Overhead 
in Different Number of Nodes
52

53. 0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
123456789101112
Delivery Ratio
(%)
Number of copies
SnW
Line Based
Tree Based
Delivery Ratio 
in Different Number of Copies
53

54. Delivery Ratio 
in Different Speeds
54
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
0.1 0.2 0.4 0.8 1.6 3.2 6.4 12.8
Delivery Ratio
(%)
Speed(m/s)
SnW Line Based Tree Based

55. 0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
1200×1000 2400×2000 3600×3000 4800×4000 6000×5000
Delivery Ratio
(%)
Map size(m ×m)
SnW
Line Based
Tree Based
Delivery Ratio 
in Different Map Sizes
55

56. Summary ●
The proposed DARS enables mobile nodes to estimate the local 
density and keep messages in dense areas, significantly 
increasing the message delivery ratio in DTNs.
●
This design generates only a small, fixed number of message 
copies to avoid congestion and resource waste.
●
DARS is affected by the number of dense areas.

DARS outperforms the SnWand Epidemic methods with the buffer size of 
2‐5 MB,.

DARS can further improve the delivery ratio of SnWby 8% (as α = 4 and P 
= 0.6).
56

57. Concluding Remarks ●
Many natural environments introduce a lot of delay‐tolerant 
networks and application domains.
●
Traditional routing techniques in computer networks, as well as 
in MANETs, may be questionable.
●
New routing methodologies will be required to meet realistic 
constraints.
●
The proposed routing scheme with density‐awareness 

This design is free from egoistic assumptions.

This design competes with other routing techniques with better 
performance.
57

58. Open Issues Yet ●
Unicasting versus Multicasting in DTN

Most of previous research efforts were dedicated to the 
performance regarding how to send onemessage from the 
source to the destination.
●
In‐network Intelligence
●
The relationship with social community
58

59. Q
&
A
Thank you for your listening.
59

60. Applied Network Domains  [RFC 4838, by Vint Cerf, et al (April 2007 )] ●
Interplanetary Internet, which focused primarily on the issue of 
deep‐space communication in high delayenvironments

NASA researchers quarrel over how to network outer space. 
[JoabJackson, IEEE Spectrum, Aug. 2005 ]

It would use optical communications using laser beams for their lower 
ping rates than radiowaves.
●
Sensor‐based networksusing scheduled intermittent 
connectivity
●
Terrestrial wireless networks that cannot ordinarily maintain 
end‐to‐end connectivity
●
Satellite networks with moderate delays and periodic 
connectivity
●
Underwater acoustic networks with moderate delays and 
frequent interruptions due to environmental factors
60

61. Application Domains ●
Interplanetary space
●
Natural disasters
●
Agricultural lands
●
Fishery grounds
●
Forest parks
●
Grazing areas
●
Wilderness
61

62. DTN Architecture: Why? ●
The existing Internet architectures do not work well for DTN 
environments due to some fundamental assumptions:

An end‐to‐end path between source and destination exists for the 
duration of a communication session

Retransmissions based on timely and stable feedback from data receivers 
is an effective means for repairing errors

End‐to‐end loss is relatively small

All routers and end stations support the TCP/IP protocols

Packet switching is the most appropriate abstraction for interoperability 
and performance

Selecting a single route between sender and receiver is sufficient

Applications need not worry about communication performance

Endpoint‐based security mechanisms are sufficient for meeting most 
security concerns
62

63. DTN Architecture: What ●
The DTN architecture is conceived to relax most of these 
assumptions, based on a number of design principles here.

Use variable‐length messages (possibly long; not streams or limited‐sized 
packets) as the communication abstraction to help enhance the ability of 
the network to make good scheduling/path selection decisions as possible

Use a naming syntax that supports a wide range of naming and 
addressing conventions to enhance interoperability

Use storage within the network to support store‐and‐forwardoperation 
over multiple paths, and over potentially long timescales 

Provide security mechanisms that protect the infrastructure from 
unauthorized use by discarding traffic as quickly as possible

Provide coarse‐grained classes of service, delivery options, and a way to 
express the useful lifetime of data to allow the network to better deliver 
data in serving the needs of applications
63

64. Delay‐Tolerant Routing in DTNs ●
Use storage within the network to support store‐and‐
forwardoperation over multiple paths, and over 
potentially long timescales 
●
Provide coarse‐grained classes of service, delivery 
options, and a way to express the useful lifetime of 
data to allow the network to better deliver data in 
serving the needs of applications
64

65. Delivery Ratio with Multiple Dense Areas
65

66. Communication Cost by Node Population
66

67. Delivery Ratio 
Dense Area =1

Dense Area = 1~9
67
α: the number of the recent Is
p: the probability of a node moving toward the dense area
number of 
dense areas
DARS can further improve the delivery ratio of SnW by 8% (as α = 4 and P = 0.6).

68. Sensitivity to Node Population 
Delivery Ratio

Communication Cost
68
Epidemic: a flooding‐type approach can 
induce a huge amount of messages to 
attain a high delivery ratio. 
DARS is more effective in the case of larger 
node population.
DARS can further improve the delivery ratio 
of SnW by 8%.

69. Coding‐Based Routing to Multiple Receivers 
in DTNs Yu‐Feng Hsu and Chih‐Lin Hu*, “Erasure Coding‐Based Routing for Message Multicasting in 
Delay‐Tolerant Networks,” Proceedings of the 2012 IET International Conference on 
Frontier Computing ‐Theory, Technologies and Applications (IET FC'12), Xining, China, 
August 2012.
Yu‐Feng Hsu, and Chih‐Lin Hu*, “Network Coding with Remix Qualification for Multicasting 
in Delay‐Tolerant 
Networks,” accepted by IEEE Wireless Communications and Networking 
Conference 2013 (IEEE WCNC'13), Shanghai, China, April 7‐10, 2013. 
69

70. Introduction ●
Premise in many studies of mobile ad hoc networks 
(MANETs)

There exists at least one end‐to‐end path between every pair 
of nodes in the network most of the time
.
►
Short Delay
●
Delay Tolerant Network (DTN)

Intermittent and opportunistic network connectivity

It is very difficult to guarantee any persistent end‐to‐end 
routing path between a source and a destination.
►
Intermittent Connectivity
►
Long Delay
70

71. Message Forwarding ●
Traditional routing paradigms

Assume that a route should be first determined before 
sending out any messages
●
For DTNs, an opportunistic routing approach is 
assumed with the way “store‐carry‐and‐forward.”

A message can be stored and carried by a node when the 
node has no opportunity to forward the message.
71

72. Store, Carry, and Forward
72
Source ‐> Relay node 1Relay node 1 ‐> Relay node 2Relay node 2 ‐> Destination
Relay race

73. Routing in DTNs ●
Recent research efforts have proposed a variety of 
routing mechanisms, such as replication‐basedand 
coding‐basedrouting techniques.
●
Replication‐based

Replicating an original message, and then forwarding copies 
to encountered nodes.
●
Coding‐based

Coding an original message into many coded blocks, and 
then forwarding coded blocks.
73

74. Replication v.s. Coding
74
Message r copies Received Message
Relay path
Replicate
Replication factor (r)=2
r relays
n relays

75. Performance Measurement on DTNs ●
Message delivery delay

The time duration from the moment which a message is sent by a source 
till the moment which this message is received by a destination.

Many research works were dedicated to the average delay.
75

76. Performance Measurement on DTNs ●
Message delivery delay

The time duration from the moment which a message is sent by a source 
till the moment which this message is received by a destination.

Many research works were dedicated to the average delay.
76
Worst‐case delay

77. Objective ●
According to previous studies, the erasure coding 
scheme is able to moderate the worst‐case delay.
●
This study aims to exploit the essence of the Erasure‐
Coding (EC)technology for not only message unicasting 
but also multicastingin DTN environments.
77

78. Delay Distribution Analysis ●
To derive mathematic formulations of delivery delay 
distribution.

The previous study applied the order statisticto address 
theoretical behavior of delivery delay distribution on the 
base of the EC‐based model.

We apply the order statistic to analyze the delay distribution 
for message multicasting.
78

79. Principle of Order Statistics ●
Considering nindependent and identically distributed (i.i.d.) 
random variables x
1
,…,x
n
, then sorting these nrandom variables 
by ascending order can generate nnew random variables y
1
,…,y
n
as y
1
=min{x
1
,…,x
n
}and y
n
=max{x
1
,…,x
n
}
●
The random variable y
k
is called the k
th
order statistic.
●
Let F(x)be the cdfof x
i, and f(x)be the pdfof x
i, then the pdfof 
y
k
is
79
--
!
() () ()(- ())
(-)!(-)!
nknk
k
n
y x fx Fx Fx
knk

1
1
1
(1)

80. Delay of Erasure Coding ●
Considering a basic EC approach with a replication factor rand a 
split degree k. (n=kr)
●
Applying the order statistics, the delivery delay by EC is       .
●
The delivery delay by simple replication is      .
80
n
k
Y
r
Y
1
n relays

81. Delay of Erasure Coding
81
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
123456789
CDF
Delay ( Units )
k=1 k=2 k=4 k=8 k=16 k=32
Given that x is under a Pareto distribution
Delivery delay of erasure coding scheme(k>1) and replication scheme (k=1) as r =2.
() ( ) , ., fx x

  


1
06 1

82. Multicasting Delay ●
Considering there are Ndestination nodes, the delay for 
multicasting is the delay of the N‐thdestination node .
●
Assuming the delay from a source to a destination is a random 
variable with distribution w
i
.
●
Applying the order statisticsto obtain the delay distribution of 
multicasting with Ndestination nodes:
82
!
() () () ( ())
()!( )!
()* *()
NNNN
N
N
N
Z w fw Fw Fw
NNN
fw NFw






1
1
1
1
(2)

83. 0
0.2
0.4
0.6
0.8
1
1 3 5 7 9 11 13 15 17 19 21
CDF
Delay ( units )
EC(1,2) EC(2,4) EC(4,8)
0
0.2
0.4
0.6
0.8
1
1 3 5 7 9 11 13 15 17 19 21
CDF
Delay ( units )
EC(1,2) EC(2,4) EC(4,8)
Reducing Delivery Delay by EC
83
() ( ) , ., fx x

  



1
06 1
Assume that the delay of coded block is under Pareto distribution
EC (k, kr)
1 destination 16 destinations

84. Simulation Environment ●
Using the Opportunistic Network Environment 
Simulator.
●
The mobility model follows the Self‐similar Least‐Action 
Human Walk (SLAW) mobility with default values.
●
Comparisons:

Erasure coding with r and k ：EC(k, kr)

Simple replication with r ：EC(1, r)
84

85. Sensitivity to the Number of Destination 
Nodes ( N )
85
1 destination 16 destinations
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
0 50000 100000 150000 200000 250000
CDF
Delay time (seconds)
EC(1,2) EC(2,4) EC(4,8)
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
0 50000 100000 150000 200000 250000
CDF
Delay time (seconds)
EC(1,2) EC(2,4) EC(4,8)

86. Upper Bound for the Number of Divided 
Blocks (k)
86
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
0 20000 40000 60000 80000 100000 120000 140000
CDF
Delay time (seconds)
EC(1,2) EC(2,4) EC(4,8) EC(8,16) EC(16,32) EC(32,64)
EC(8,16)
16 destinations , replication factor r = 2
K
max
=8

87. Sensitivity to the replication factor (r)
87
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
0 50000 100000 150000
CDF
Delay time (seconds)
EC(1,2) EC(2,4) EC(4,8) EC(8,16) EC(16,32) EC(32,64)
EC(8,16)
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
0 20000 40000 60000 80000
CDF
Delay time (seconds)
EC(1,8) EC(2,16) EC(4,32) EC(8,64)
EC(2,16)
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
0 50000 100000 150000
CDF
Delay time (seconds)
EC(1,4) EC(2,8) EC(4,16) EC(8,32) EC(16,64)
EC(4,16)
K
max
r = 16
100 nodes
16 destinations
Replication factor = 2Replication factor = 4
Replication factor = 8

88. Sensitivity to Node Population and 
Density
88
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
0 50000 100000 150000 200000
CDF
Delay time (seconds)
EC(1,2) EC(2,4) EC(4,8) EC(8,16) EC(16,32) EC(32,64)
E
C(
1
6,3
2
)
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
0 50000 100000 150000
CDF
Delay time (seconds)
EC(1,4) EC(2,8) EC(4,16) EC(8,32) EC(16,64)
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
0 20000 40000 60000 80000 100000
CDF
Delay time (seconds)
EC(1,8) EC(2,16) EC(4,32) EC(8,64)
EC(8,32)
EC(4,32)
Replication factor = 2Replication factor = 4
Replication factor = 16
K
max
r = 32
200nodes
16 destinations

89. Summary ●
The delivery delay distribution is much affected by the 
number of divided blocks.
●
As the number of destination nodes increases, the 
performance gain by EC can become better in terms of 
either overall delay or worst case delay.
●
There should be an upper bound for the number of 
coded blocks under a fixed value of replication factor.
●
This upper bound is sensitive to the replication factor 
and node density in DTNs.
89

90. Q
&
A
Thank you for your listening.
90