Transcript Hybrid Architectures: Accounting for Networks Exuding DTN and

Darien Hirotsu
UC Santa Cruz

Gregg Bachmeyer
 Integrating UMTS and Bluetooth
 Integrating Infrastructure-based and
Infrastructure-less Networks

Darien Hirotsu
 Integrating DTN and MANET Paradigms

My apologies to Rance and Philip…
 I hope I don’t steal your thunder here (I promise to keep
this short)
 Feel free to interrupt/augment any explanations at any
time

What constitutes a DTN?
 Traditional IP networks (both wired and even MANET)
suffer in performance when seeing certain qualities:
▪ Large delays
▪ Frequent disruptions
▪ Disconnected network graphs
 The DTN architecture attempts to address these issues

Examples where a DTN architecture helps:
 Sparsely connected sensor networks
 Networks with frequent disconnections due to
node mobility (interplanetary networks)
The DTN protocol
stack provides a
bundle layer
 This allows for a
DTN overlay
network to be
built over the
existing
architecture
 DTN nodes
typically use
spray-and-wait
between hops
 Note that
internet routers
can be integrated
between existing
DTN nodes


DTN Assumptions:
 Connectivity is typically achieved without fixed
infrastructure
 Nodes move independently and freely
 Nodes are typically NOT CONNECTED due to node
mobility or sparse node density
▪ The topology that a node sees is limited to ONLY what is
“locally connected”
▪ A route typically does NOT exist between the sender and
receiver
▪ As a result,a persistent store and forward model is needed to
allow traffic to be routed and forwarded to the end
destination

MANET Assumptions:
 Connectivity is typically achieved without fixed
infrastructure
 Nodes move independently and freely (although only
moderate movement is tolerable)
 Nodes are inherently CONNECTED via a reasonably
dense or stable topology or redundancy of routes
▪ A full topology of the network is maintained by each node
▪ If a route to an end-node does not exist with protocols like
AODV or DSR, packets are not routed or forwarded to the
next-hop
▪ If a stale route exists, packets are “black-holed”

There are many scenarios in which a MANET
would benefit from DTN capability
 Sensors in a densely connected MANET may
experience battery failure causing sparse
connectivity
 Failed sensors may cause
A
X
X
X
D
X
X
X
C
X
X
B
A to become
disconnected from B
 If A and B were DTN
nodes, A could “save” the
data until a path to B
became available again
 In the MANET, scenario
all may be lost

There are many scenarios in which a DTN
may benefit from MANET features
 DTN’s typically make forwarding decisions based
on node availability rather than optimal paths
2  Suppose C moves at a
A
constant rate with slight
pauses between points 1, 2
C
1
D
E
B

At point 1, C can forward
traffic between A, B

A MANET could p0tentially
discover the more optimal
path (A-C-B) over the typical
one (A-D-E-B)

Connectivity-focused routing solutions
 Implement a routing protocol that can build BOTH
optimal end-to-end paths when available but also
leverage store-and-forward if needed
▪ HYMAD
▪ HYbrid MANET-DTN routing protocol
▪ DTN-AODV

“Cooperative” routing solutions
 Allow nodes to cooperate to use available bandwidth
optimally
▪ TIL
▪ Transient Information Level based routing

Higher node density makes
a strong case for MANET
since a path likely exists
end-to-end

High node mobility makes a
strong case for DTN since
the network is likely to
become disconnected

A hybrid network that falls
in between the extremes
could benefit from both
paradigms

Also, networks can flip-flop
between the two types to
have characteristics of both

The goal of HYMAD is to group individual
nodes such that only groups need to
exchange data between each other
Inter-group routing can be achieved via DTN.
Intra-group routing can be achieved via
MANET. This simplifies the topology from 12
connected nodes to 3 connected groups.

Intra-group routing (control plane)
 Distance vector routing messages to achieve
mesh like connectivity
Nodes within a group exchange distance
vector routing messages much like AODV.

Inter-group routing (control plane)
 Border nodes are elected for the group
 Border nodes use a flag in the routing messages to discover each other
 Spray-and-wait routing of data between border nodes
A
B
Nodes A and B are border nodes use a spray-andwait type routing to forward messages between
groups.

Data plane operation
 Suppose A wants to send a “bundle” of data to B
▪ A forwards the message to the border node C
A
Group 3
C
Group 1
Group 2
The data from A is first forwarded to C which
is the border node. C notes that A is the
“custodian” for the bundle. C being a border
node has routing knowledge of both Group 1
B
and 2.

A
Data plane operation
 Suppose A wants to send a “bundle” of data to B
▪ C forwards the bundle to node D which is a border node
for Group 2
Group 3
C
D Group 2
Group 1 Border nodes maintain a “messages-in-grouplist” which contains a list of data needing to be
delivered. C compares its list with D and sees
that D does not have the bundle from A, so it’s
B

A
Data plane operation
 Suppose A wants to send a “bundle” of data to B
▪ D randomly elects E as the “custodian” of the bundle
and forwards it
E
C
D Group 2
Group 1 D sees that the destination B is not within its
group. D elects E randomly to be the
“custodian” of the DTN bundle from “A” and
forwards it accordingly. D adds the bundle to its
B
“messages-in-group-list.”
Group 3

Data plane operation
 Suppose A wants to send a “bundle” of data to B
▪ E happens to be a border node as well to Group 3
A
E
Group
3
F
C
D Group 2
Group 1 E references its “messages-in-group-list” and
sees F is missing the bundle in A. E forwards
the “bundle” accordingly via “spray-and-pray.”
B

A
Data plane operation
 Suppose A wants to send a “bundle” of data to B
▪ F sees B is in its group and forwards the “bundle” as
needed
E
Group
3
F
C
D Group 2
Group 1 F sees that B is a member of its group. F
forwards the datagram to B using distance
vector like routing.
B

Group formation (control plane revisited)
 Intra-group disconnections may cause new groups to form
▪ Border nodes are re-elected
▪ “Messages-in-group” list allows “bundles” to be re-forwarded as
needed
 Dmax is a group diameter that represents the maximum
number of allowable hops to reach the farthest node of a group
(restricts group membership)
 When routes are lost due to disconnections, data is stored by
the “custodian” rather than dropped
Group 1 may disconnect into different groups
should node mobility cause link disconnections
A
B
If Dmax=2, node B cannot join the adjacent
group since it’s 3 hops away from node A.

Benefits of HYMAD:
 Outperforms a standard spray-and-wait forwarding
scheme in terms of delay and delivery-ratio over a
variety of mobility scenarios
▪ Random Waypoint (synthetic)
▪ Rollernet (trace-based group movement)
 Performance in terms of overhead is NOT dependent
on Dmax
▪ Increasing Dmax increases the group size which increases the
amount of control plane messages within the group
▪ As a tradeoff, this also decreases the amount of control
messages between groups

Detriments of HYMAD:
 Over a wide variety of scenarios, Epidemic routing still
outperforms HYMAD in terms of delay and delivery-ratio
▪ In Epidemic routing, random pairs of nodes that establish
connectivity exchange information as needed
 Performance is strongly tied to timer values of the control
plane messages
 All nodes need to be DTN nodes
▪ All nodes need to have storage for the batch layer
 Assumes that the “custodian” of data can store data for a
period long enough for delivery
▪ How does it deal with storage failure?

The goal of AODV with DTN capability is to
extend the reach of AODV by discovering DTN
nodes
If DTN nodes (D) are able
to speak AODV at the IP
layer, DTN nodes can
extend the reach of AODV
to allow nodes such as
originator (O) to reach
targets that would be
unreachable (T) under
typical circumstances.

Integrating AODV with DTN:
 Need to expand the route discovery process and
processing of RREQ/RREP messages
▪ Add a flag in the AODV header to tell nodes to check for the
DTN header shown below

Integrating AODV with DTN (RREQ):
▪ O wants to send data to T
▪ O generates a RREQ as per usual
O
A
O generates a RREQ and forwards it to adjacent
nodes. Node A is a non-DTN AODV speaker, so
it does not toggle the DTN flag in the header,
but still forwards the RREQ accordingly.
T

Integrating AODV with DTN (RREQ):
▪ O wants to send data to T
▪ B is a DTN speaker so it toggles DTN bit in the header and adds its
DTN header telling AODV nodes it has DTN capability
O
A
B
B toggles the DTN bit in the AODV header. B
also adds the DTN Router Info extension to the
RREQ including a hop count to O. The RREQ is
then forwarded normally.
T

Integrating AODV with DTN (RREQ):
▪ O wants to send data to T
▪ D also is a DTN node so it adds another Router Info. Extension
header to the RREQ and adds B to its list of DTN nodes
O
A
B
C
D
C is a non-DTN node, so it forwards the RREQ per normal
AODV. D sees the DTN bit toggled already, but it still
needs to add its Router Info header to the RREQ. It also
adds node B to its list of DTN aware nodes establishing a
full DTN overlay topology.
T

Integrating AODV with DTN (RREP):
▪ O wants to send data to T
▪ T sees that it’s the target for node O so it generates an RREP
O
A
B
C
D
T generates the RREP and copies all Router Info extension
headers from the RREQ onto the RREP and forwards it
normally. If node T does not understand the DTN
extension, all Router Info extension headers are dropped.
T

Integrating AODV with DTN (RREP):
▪ O wants to send data to T
▪ Nodes may also learn about DTN information based on RREP
O
E
A
B
C
D
Node E can also see RREP packets and also learn about
DTN nodes B and D through that process. This ensures
robustness for nodes in learning the DTN overlay
network.
T

Integrating AODV with DTN (RREP):
▪ O wants to send data to T
▪ Node O can make in intelligent decision on how to forward traffic
to T based on the DTN information it has received
O
E
A
B
C
D
Node O processes RREP normally. All intermediate nodes
may now make “optimal” forwarding decisions based on
the knowledge of both the AODV network and the DTN
overlay network. The DTN Router Info. header has a
“metric” field which potentially could indicate how
trustworthy a DTN route is.
T

Integrating AODV with DTN (RREP):
▪ Failure of RREQ
▪ The first DTN node in a path for an RREQ is responsible for
ensuring the RREQ reaches the destination
O
E
A
B
C
D
B is the first DTN node in the path from O to T. It
maintains a timer that kicks off after getting the RREQ
and listens for an RREP from T. If node T fails and does not
send an RREP before B’s timer expires, B sends a special
“DTN-Only” RREP to allow nodes to still learn the DTN
overlay network.
T
X

Benefits of DTN-AODV
 Allows for the dynamic establishment of the DTN
overlay network over the AODV network
▪ Normally overlay networks requires static configuration
▪ BGP is an example
 Allows for the learning of a granular view of the
network to provide optimal forwarding decisions
▪ Knowing both AODV and DTN nodes allows the mobile
node to intelligently determine an optimal next-hop

Benefits of DTN-AODV
 Evaluation of a similar implementation shows
performance improvement over Epidemic routing
in terms of delivery-ratio and delay
▪ Implementation (called adaptive routing) was slightly
different but still integrated AODV and DTN capability
 Not all nodes have to be DTN speakers
▪ Not all nodes even have to understand the DTN
extensions

Detriments of DTN-AODV
 Overhead increases with the number of DTN nodes
▪ Since each DTN node adds its Router Info header to the
RREQ, more DTN nodes yields higher protocol overhead
 DTN-AODV results in a lot of queueing
▪ DTN-AODV results in far more queuing on average per node
compared to Epidemic routing
 Route cacheing may cause issues with AODV-only
speakers
▪ If an AODV-only node receives an RREQ and responds via
route-cache, it will only send AODV routes limiting the full
realization of the DTN network

Created for directional tactical networks using
RF and optical links (free-space optical
networks)

Directional networks
 Sometimes nodes can’t transmit data in the optimal
path due to interference or physical conditions
 A satellite may not be pointing the optimal direction
C
B
D
A
Node A needs to
transmit to D, but it
can’t send data directly
due to the direction of
the antennae. Instead,
it takes a suboptimal
path through B and C.

The goal of TIL is to have nodes coordinate
together and share bandwidth optimally based
on a “DTN algorithm” using a called TIL
 An individual node in a network is typically selfish
 Since bandwidth is finite, there is some benefit for
nodes to “cooperate” and share to maximize
bandwidth

Built primarily for DTN’s, but the paper claims
that the solution works for directional MANET’s
as well
Consider the scenario
where Gregg and Darien see
an 802.11n and 802.11a
access point
 Both of us knowing 802.11n
is faster, we both join that
access point and potentially
contend over the available
bandwidth
 If we played nicer and
coordinated, we could work
together and join different
access points to potentially
maximize our perceived
service

802.11n
802.11a
X
Gregg
Darien

Assumes the following:
 All nodes have perfect knowledge of:
▪ Location of nodes in the network
▪ Amount of network traffic at each node
▪ Connectivity of the network

If all nodes have this complete information,
an algorithm can be used by each node to
minimize the amount of work needed to
move data from source to destination

The goal is to forward traffic based on the
lowest TIL value for all nodes i and j

T(i, j) : amount of traffic needing to be delivered
from node i to node j
D(i, j) : distance between node i and node j
h(i, j) : amount of traffic being retained via DTN
on the path from node i to j



Detriments:
 Impractical
▪ Is it even possible for to get this granular information AND
disperse it through a network?
 All nodes have to be DTN nodes

Benefits:
 Novel solution
▪ Cooperation makes sense when “fighting” over a shared
resource
 Simulations show the protocol shows correctness in
delivering data over an RF, optical network

Varying simulation tools
 Different simulators have different capabilities
 Comparing performance of unlike protocols in unlike tools
is inefficient

Congestion control mechanisms
 The possibility exists for congestion to occur at DTN
capable nodes
 Does the bundle layer need additional congestion control
mechanisms?

Security
 DTN nodes present a natural target for DoS

Thanks for listening

Why not use MANET only?
 MANET routing protocols use
Hellos for neighbor discovery
which could be wasteful if
nodes are rarely connected
 MANET forwarding is based
on availability, so if an endto-end path does not exist,
traffic is dropped
 This is not optimal if the
network graph is typically
disconnected or constantly
changing

Why not use DTN only?
 DTN forwarding is often
based on a per-encounter
basis (the node that is
connected the “most” based
frequency of connectivity
may become the best hop)
 This means the most optimal
path through the network is
not always utilized (DTN
nodes don’t know the full
topology)
 Without constant topology
discovery, suboptimal
forwarding/routing is a
possibility

Persistent storage
 The assumption is a DTN node shall retain any data in the instance of a system
restart

Storage distribution
 Storage has to be well distributed through the network
▪ Issues with congestion management
▪ Denial-of-Service mitigation

Routing is still a challenge
 Lossy media
 Unknown intermittent connectivity

Store-and-Forward
 Traditional routers are only store-and-forward for a limited duration of time
 Is store-and-forward a better alternative than continuous connectivity or
other alternatives?