Transcript “Data over Time” Delay Tolerant Networks

“Data over Time”
Delay Tolerant Networks
Joy Ghosh
LANDER
cse@buffalo
Overview



Challenged Internets (CI)
Shortfalls of TCP/IP in CI
Concept of DTN
Message-oriented
 Overlay architecture
 Classes of Service (CoS)



Routing Issues
Conclusion
Challenged Internets (CI)

Some causes:
Host / Router mobility extremes
 Power management
 Interference


Examples
Terrestrial mobile nets: partitions
 Sensor / Actuator: power saving
 Military ad-hoc: jamming

Paths & Links

High end-to-end latency





Transmission time
Propagation delay
Processing time
Queuing time
Low asymmetric data rates



Return channel may be even absent
Avoid chatty conversation
Data carousels / de-fragmentation
Paths & Links

Non-faulty Disconnection

Due to motion





Due to low-duty-cycle




Predictable (satellites, busses)
Opportunistic (node coming in range)
End user or router motion
Third entity motion causing block
Predictable
Low capability devices save power
Usually triggered by events - sensors
Routing


lack of reach is normal – not a fault
Pre-schedule data based on outage info
Paths & Links

Long Queuing Times
Next hop unavailable
 Alternative next hops
 Persistent storage

Network Architecture

Interoperability considerations






Most protocols only use LL & MAC
Simple & local in scope
May use application specific framing
formats
May fail to implement reliability,
congestion control, and security
Not well matched for Internet Protocols
Minimal assumptions of underlying
protocol stack capabilities for
interoperation
Network Architecture

Security
Exotic media  forwarding costly
 Protection of forwarding service
 Access control matrix for CoS
 Authentication at critical points
 End-to-end security not suitable

Too much delay for key exchange
 Drop unwanted traffic ASAP

End System Characteristics

Limited longevity
Hostile environments
 Power exhasution
 Delegation of reliable delivery


Low duty cycle


Save power / event triggered
Limited resources

Limited memory & processing
Overview



Challenged Internets (CI)
Shortfalls of TCP/IP in CI
Concept of DTN
Message-oriented
 Overlay architecture
 Classes of Service (CoS)



Routing Issues
Conclusion
TCP/IP basics

Expectations of TCP/IP


Fundamental service


Map: IP packet format, domain names
 physical network
Fully-connected, best-effort, unicast
datagram transport
Suffers when:


Links change radically (wireless, ATM)
Service enhanced significantly (IP
multicast, QoS)
TCP/IP applied directly to CI

Transport Layer (TCP, SCTP,
UDP)
RTT too high for slow start
 Waste of bandwidth
 False congestion indication
 MSL in RFC793 is 2 mins  Low

TCP/IP applied directly to CI

Network Layer (IP)
Lossy network  smaller frames
 Frequent fragmentation
 No fragment retransmission
 Maximum TTL is 225  Low

TCP/IP applied directly to CI

Application Layer (Routing)
Delayed soft-state refreshes
 Label links as non-operating (e.g.,
RIP, BGP)
 Lack of response to HELLO
messages (e.g., OSPF)


Application Layer (Others)
Delay cause application timeout
 Delay may outlive application life

Application Development Practice






Network based applications
Application level timeouts
Lack of failover – no auto route
Synchronous programming
Chatty applications protocols
(FTP requires 6 RTT)
New network API required
Proxies & Protocol Boosters



Performance Enhancing Proxies (PEPs),
Protocol Boosters - Link repair approaches
“fool” TCP/IP based end stations to operate
more efficiently over paths with poor links
Different levels of transparency







Local connection termination
Modification of TCP ACK stream
Retransmit lost TCP packets w/o end user input
Use of PEPs discouraged due to fragility
Confound end-to-end diagnostics
Hurt security below transport (IPSEC)
Alternative: application layer proxies

Internet to special network name mapping and
protocol translation
Use of Electronic Mail

Pros
Asynchronous message delivery
 Delay tolerance
 Flexible name/address semantics


Cons
Lack of dynamic routing
 SMTP is a chatty protocol
 Mostly reliable with likely failure
notification

Overview



Challenged Internets (CI)
Shortfalls of TCP/IP in CI
Concept of DTN
Message-oriented
 Overlay architecture
 Classes of Service (CoS)



Routing Issues
Conclusion
Delay Tolerant Network
message-oriented overlay architecture






Interoperability among CI & Internet
Overlaid above different protocol stacks in
various networks
Store & forward message delivery for noninteractive traffic
a-priori knowledge of communication
capacity needs (intermediate storage,
retransmission bandwidth)
Virtual circuits unsuitable due to preestablishment of network
Favors asynchronous I/O programming
Network of Regional Networks


Similar protocol stacks in one region
DTN Gateways – Metanet Waypoint




Provides entry to a region (protocol translation)
Name mapping from global tuple to locally resolved name
Enforces policy and control
Persistent storage for reliable delivery
Delay Isolation via
Transport Layer Termination
Persistent
storage
Bundle Encapsulation

Bundles consist of 3 things:



Source application’s user data
Control information from source application to
destination application (how to handle data)
Bundle header
DTN Region Naming
Name Tuples
(Late Binding)
InterPlaNetary (IPN) Internet
Class of Service (CoS)



Challenged Internet  limited
resources
Priority based resource
allocation
Subset of types of service by
USPS
Class of Service (CoS)





Challenged Internet  limited resources
Priority based resource allocation
USPS has simple but elaborate services
Subset of types of service by USPS
DTN CoS






Custody Transfer
Return Receipt
Custody-Transfer Notification
Bundle-Forwarding Notification
Priority of Delivery: Bulk, Normal, Expedited
Authentication
DTN Class of Service (CoS)
Custody Transfer
Path Selection & Scheduling



No end-to-end path
Routes are a cascade of time-dependent
contacts
Contact parameters









Start & end times
Capacity
Latency
End points
Direction
Predictable vs. Opportunistic contacts
Multi-commodity flow optimization problem
“flows over time” optimization problem –
NP-hard
More under “Routing Issues”
Protocol Translation &
Convergence Layers

Bundle forwarder may augment
underlying protocol stack






Reliable delivery
Connection setup with notification
Flow control
Congestion control
Message boundaries
May fall back to retransmission
timers in case of failed connections
Structure of Bundle Forwarder
Time Synchronization






Required for scheduling, path
selection, and congestion
management
Devices in challenged environments
often collect data / position w.r.t. time
Pre-programmed control instructions to
be executed in future time
Reliability of post-facto data analysis
Removal of expired pending messages
Protocols like NTP are used
Security
User
certificate




Per-hop security to avoid delay
Drop unwanted packets ASAP
Only edge routers need per user certificate
Not secure against router compromise
Congestion & Flow Control

Flow



DTN forwarder uses available underlying regionlocal transport protocol
If not available, its constructed at the DTN
convergence layer
Congestion



Long absence of contacts leads to massive storage
of data
Data for which custody has been accepted cannot
be discarded
Priority queue for custody storage



Potential problems




Large messages are denied custody
Messages are spooled FCFS based on priority
Priority invasion (lower custodially recvd blocks high)
Head-of-line blocking (custodially recvd w/o contact)
Proactive : admission control
Reactive: reservation, rejection, etc.
Overview



Challenged Internets (CI)
Shortfalls of TCP/IP in CI
Concept of DTN
Message-oriented
 Overlay architecture
 Classes of Service (CoS)



Routing Issues
Conclusion
Network model for Routing
Routing Issues

No end-to-end path


Capacity is time dependent


Both proactive and reactive fail
Long buffering of messages
Multiple contacts

Might be more optimal to wait for
future contact than send on
available one
Routing Objective




Maximize probability of message delivery
Prevent buffer overflow
Speed up the release of resources
Minimize the end-to-end delay


Per-hop routing preferred over Source
routing


Use knowledge of future topology dynamics in
path selection
Flexibility to change next hop
Message splitting is allowed


Fragmentation of large messages
Each fragment routed independently
Knowledge Oracles

Contacts Summary Oracle


Contacts Oracle


Time-varying DTN multi-graph
Queuing Oracle


Time-invariant / aggregate
characteristics of contacts
Buffer occupancy at any node at
any time
Traffic Demand Oracle

Future traffic demand
Routing Algorithm Classes

Zero Knowledge


Complete Knowledge


No oracles / minimal extreme
All oracles / LP formulation
Partial Knowledge
One or more oracles
 Practical algorithms

Knowledge vs. Performance
Zero Knowledge Routing

First Contact (FC)





Forward to first available contact
No sense of direction / may oscillate
Requires only local knowledge
Trivial implementation
Improvements


Incorporate sense of trajectory
Use path vector to prevent loops
Partial Knowledge Routing


Assigns cost to edges
Costs reflect estimated delay on edge







Queuing time: time till contact available
Transmission delay: time to inject into edge
Propagation delay: time to travel on edge
Computes minimum cost path
Conveniently uses different oracles
Computationally efficient distributed
algorithms already exist for shortestpath based routing problems
Finds however single path from source
to destination – no optimal splitting
Partial Knowledge Routing

Cost function: ω (e, t)



If message arrives at node ‘u’ at time ‘t’, and if edge ‘e’
(between ‘u’ & ‘v’) is chosen, message will reach node ‘v’
at time ‘t + ω (e, t)’
FIFO: if t1 < t2, t1 + ω (e, t1) <= t2 + ω (e, t2)
Algorithm with Time-invariant Costs


Use modified Dijkstra’s algorithm
If L[v] > (L[u] + ω (e, L[u] + T)) then
L[v]  (L[u] + ω (e, L[u] + T))







(T  start time)
Minimum Expected Delay (MED)
Oracles: Contacts Summary
Edge cost = avg. wait time + prop delay + trx delay
Proactive routing is used for time-invariant cost
Fixed routes for all messages
Minimizes avg. waiting time but doesn’t optimize path
Improvement


Dynamically make use of superior contacts per-hop
Multiple disjoint paths to balance load
Partial Knowledge Routing

Cost function: ω’ (e, t, m, s)
Edge ‘e’, time ‘t’, message size ‘m’, node assigning cost ‘s’
 ω’ (e, t, m, s) = t’ (e, t, m, s) – t + d (e, t’)
where,






c (e, t)  capacity of edge ‘e’ at time ‘t’
Q (e, t, s)  queue size at source of edge ‘e’, at time ‘t’ as
predicted by node ‘s’
t’  earliest time queues data at ‘e’ and message can be
injected into the edge
Integral  volume of data through ‘e’ in interval [t, t’’]
d (e, t’)  propagation delay seen by message
Partial Knowledge Routing


Algorithms with Time-varying Costs
Earliest Delivery (ED)





Earliest Delivery with Local Queuing (EDLQ)




Contacts Oracle
Q (e, t, s) = 0
Source routed
Buffer overflow  cascaded delay
Contacts Oracle
Q (e, t, s) = data queued for ‘e’ at ‘t’ if e = (s , *)
= 0 otherwise
Per-hop routed  path vector to avoid loops
Earliest Delivery with All Queues (EDAQ)




Contacts + Queuing Oracles
Q (e, t, s) = data queued for ‘e’ at ‘t’ at node s
Source routed
Reservation of edge capacity along computed path
Complete Knowledge Routing
Complete Knowledge Routing
Complete Knowledge Routing
Simulation Scene 1:
Routing to Remote Village





Village: Kwazulu-Natal
City: Capetown
Country: South Africa
Dialup  4 Kb/s, (11pm to 6am contact)
3 PACSAT satellites



3 motorbikes  1Mbps (5 min contacts)


Each making several trips in day
Messages


OSCAR-11, PACSAT, PCSAT
Each making 4 trips over city & village
(connecting them)
From Village  1 KB, From City  10 KB
Time

48 Hrs, starting 01/11/2004 11:59pm
Simulation Scene 1:
Routing to Remote Village
Simulation Scene 2:
Network of City Buses








20 city buses in San Francisco
3 scheduled bus trips (A, B, C)
“stop” generated at each turn
Constant speed between stops
Pause of 0 to 5 min at each stop
Speed between 10 and 20 m/s
Radio range 100 m by default
Traffic: 12 hrs, 1 hr intervals, 20 random src / dst
bus pairs, 200 messages per interval
Simulation Scene 2:
Network of City Buses
Overview



Challenged Internets (CI)
Shortfalls of TCP/IP in CI
Concept of DTN
Message-oriented
 Overlay architecture
 Classes of Service (CoS)



Routing Issues
Conclusion
Delay Tolerant Network
Overlay Architecture






Need to explore challenged Internets
Interoperability amongst different
regions of networks
Current Internet Protocol stack not
suitable
Delay Tolerant Network is an option
Overlaid architecture above
Transport protocols
Routing protocols for DTN need to
cope with “Data over Time”
References



Kevin Fall, A Delay-Tolerant Network
Architecture for Challenged Internets, Intel
Research Berkeley, Technical Report, IRBTR-03-003
S. Jain, K. Fall, R. Patra, Routing in a
Delay Tolerant Network, ACM
SIGCOMM’04, Sep, 2004
Forrest Warthman, (Warthman Associates),
Delay-Tolerant Networks (DTNs), A
Tutorial, Version 1.1, 3/5/03