Transcript DTCAST: Delay Tolerant Multicast Routing

DTCAST: Delay Tolerant
Multicast Routing
On-Demand Hybrid Multicast Routing
Guaranteed Data Delivery
Short-Term Disconnection Tolerance
Long-Term Disconnection Tolerance
Zhenkai Zhu ([email protected])
Keith Mayaral ([email protected])
Alexander Afanasyev ([email protected])
Tutors: Soon Oh ([email protected])
Uichin Lee ([email protected])
UCLA Computer Science Department
1
Applications
Broadcast nature of wireless should be
exploited for multicast data delivery
Mobile ad hoc networks with intermittent
connectivity
 Critical information dissemination in emergency
situations
 Ad hoc networks experienced short-term and
long-term disconnectivity periods

UCLA Computer Science Department
2
Assumptions

All nodes are trusted

Source knows list of destinations whom it should
deliver data
Destinations know multicast address of the
dissemination data



Data messages have long actuality period (e.g. from
1 hour to 1 day)
Data rate is small (1-16 KiBytes/s)
UCLA Computer Science Department
3
DTCAST relation to other
protocols
User
Application
Messaging Service
…
Message Payload
DTCAST
Transport Layer (Optional)
IPv4
Data Link Layer
802.11 (LNK)
Physical Layer
802.11 (PHY)
Physical Medium
UCLA Computer Science Department
4
DTCAST Features
On-Demand Hybrid Multicast
Routing and Data Delivery
Multicast Group
Based Routing
Source
Learning
(RQ)
Responsibility
List Learning
Delay and
Disruption
Tolerance
Guaranteed delivery –
Implicit / Explicit Acks
Robustness to
network
topology changes
Local
recovery –
Route
Injection
Epidemic
recovery –
Data Run
After Nodes
UCLA Computer Science Department
5
DTCAST: On-Demand Hybrid
Multicast Routing
Based on RouteRequest / RouteReply ODMRP scheme
 Includes Local Recovery of the E-ODMRP
 Each node learns for which the destinations it is on the path
– responsibility list learning
 Adds forward path learning for explicit (passive) data
acknowledgement

Common features:
◦
◦
◦
◦
Source path learning
Underlaying protocol independence
Soft states – forwarding tables pruned on timeout
Shortest (fastest) path maintaining using Route Request caching
or TTL field
◦ Robustness to node disconnections
UCLA Computer Science Department
6
ODMRP: Routing Phase
Forwarding Group
S
R
F
F
F
R
Join Query
Join Reply
Forwarding Node
Link
Multicast Route
F
R
R
 On-demand approach: A source initiates JOIN QUERY flooding only when it has data to
send
 Using JOIN QUERY intermediate nodes set up route to sender (source path
learning)
 Members send Join Reply messages using via source path
 Routes from sources to receivers build a mesh of nodes called “forwarding group”.
UCLA Computer Science Department
7
DTCAST: Routing Phase

On-Demanding: Flooding Route Request only if there is data to send

Source path learning

Destinations respond with Route Reply

Forward path learning

All nodes are virtually sources –
real or temporary)
Request
Reply
Request
Reply
Request
Reply
From=5
Mcast=X
Dst=8
From=8
Mcast=X
Dst=8
From=3
Mcast=X
Dst=6,8
From=1
Mcast=X
UCLA Computer Science Department
8
DTCAST: Routing Phase (cont.)
Routing Tables


Source Routing Table
Source Node ID
Next Node ID to Source
<XX>
<YY>
<XX>
SELF
…
…
Responsibility List (Forwarding Table)
DST ID
FW_FLAG
Source Node ID
Multicast ID
<A>
TRUE
<XX>
<YY>
<B>
FALSE
…
…
…
…
UCLA Computer Science Department
9
DTCAST: Routing Phase (cont.)
Route Request and Route Reply Packets
IP header
DTCAST
header
Only NEXT ID node
should process Reply packet
For responsibility list
learning
UCLA Computer Science Department
10
DTCAST Features
On-Demand Hybrid Multicast
Routing and Data Delivery
Multicast Group
Based Routing
Source
Learning
(RQ)
Responsibility
List Learning
Delay and
Disruption
Tolerance
Guaranteed delivery –
Implicit / Explicit Acks
Robustness to
network
topology changes
Local
recovery –
Route
Injection
Epidemic
recovery –
Data Run
After Nodes
UCLA Computer Science Department
11
DTCAST:Delay tolerated guaranteed
data delivery to multicast group nodes





Each DTCAST data message has period of actuality
(1 hour, 1 day, …)
Each data message associated with multicast group
ID and list of destinations
On receiving data message, each node on forwarding
path saves message in local queue and sends implicit
or explicit ACK, containing list of the destinations
node responsible for
On receiving ACKs, node subtractsdestination list in
queued packed and destinations list in ACK
Message is deleted from local queue iff destination
list in queued packed is empty
UCLA Computer Science Department
12
DTCAST: Data Transfer Phase
Full connectivity
Node 4 queue
MSG 1
•6
DATA
SEQ: 1
DATA
SEQ: 1
DATA
SEQ: 1
Node 1 queue
MSG 1
•6
•8
Node 3 queue
MSG 1
•6
•8
Node 5 queue
MSG 1
•8
Acknowledgement Message (Implicit or Explicit)
UCLA Computer Science Department
13
DTCAST: Data Transfer Phase (cont.)
Data and Acknowledgment Packet
IP header
DTCAST
header
Timestamp till which network
would try to deliver data message
To subtract IDs from
responsibility list
UCLA Computer Science Department
14
DTCAST Features
On-Demand Hybrid Multicast
Routing and Data Delivery
Multicast Group
Based Routing
Source
Learning
(RQ)
Responsibility
List Learning
Delay and
Disruption
Tolerance
Guaranteed delivery –
Implicit / Explicit Acks
Robustness to
network
topology changes
Local
recovery –
Route
Injection
Epidemic
recovery –
Data Run
After Nodes
UCLA Computer Science Department
15
DTCAST: Robustness to network
topology changes

Node mobility (new set of neighbors)
 New path discovery through RQ/RR after timeout
 Local path recovery – destination locally floods RouteReply
packet with NextNode=All field

Short-term disconnection (e.g. signal interference)
 Epidemic flooding if node disappeared from forwarding path
 Data rebroadcasting after timeout until ACK received

Long-term disconnection (e.g. power failure)
 Continue delivery tries until message time actuality (TA)
exceeded
 Message will not be deleted from source or intermediate
node queues until it was delivered or TA exceeded
UCLA Computer Science Department
16
DTCAST: Local Path Recovery
Route Injection. Fast receiver mobility routing

Triggering heuristics:
timeout after last data message.
Top process after second
timeout

In local path recovery node
floods one-hop neighbors with
RouteInject packets – force
all neighbors to establish
forwarding route if they have
source path

If data is available, it can be
forwarded multiple times until
route prune timeout
6
6
Route Inject packet
UCLA Computer Science Department
17
DTCAST: Epidemic Flooding
Fast node mobility. Data message runs after node

8
8
Triggering heuristics: if
forwarding path exists and no
ACK for two retransmission
Set ER flag and flood data in
two-hop range
 If node receive data with ER and
it has forwarding path – it fourhop floods ACK with ER flag


If no ACK before timeout,
intermediate node become
source for data packet -Route
Request/Reply scheme until time
of actuality reached

Route will be rebuild after
route prune timeout (RQ/RR)
UCLA Computer Science Department
18
Implementation using Click
Broadcast
Medium
Source Data Multiplexer
Route Request Initiator
Data Queue
Epidemic Data Run Initiator
Source Routing Table
Forwarding List Table
Broadcast
Medium
Data Demultiplexer
Route Reply Generator
Route Injection Generator
UCLA Computer Science Department
19
Experimental Testbed Scheme
Connectivity
Node 1: Test Data Generation
Node 5,7,6: Multicast Test Data
Receivers
Data transfer
Data message size 1024 bytes
Continuous data transfer 1 min
Message actuality 20 min
Node 3: Non-critical path forwarder
Node 4: Critical path forwarder
UCLA Computer Science Department
20
Performance Evaluation
(TODO)

Ratio of the received data using different
generation speed

Recovery delay after node connection
lost/recovery for different disconnection
periods

Recovery delay (network stress period) if
disconnected node is on non-critial and
critical path
UCLA Computer Science Department
21
Conclusion
ODMRP-comparable performance in the
case of full-connectivity
 Fast recovery from topology disruptions

◦ Short term disconnectivity
◦ Long term disconnectivity
◦ Node mobility

Transport layer guarantee for data
delivery within message period of
actuality
UCLA Computer Science Department
22