Transcript A Delay-Tolerant Network Architecture for Challenged Internets

A Delay-Tolerant Network
Architecture for Challenged
Internets
Kevin Fall
July 7, 2015
Anshul Kantawala
1
Challenged Networks
 Terrestrial mobile networks
 Unexpected partitions due to node
mobility or RF interference
 Periodic, predictable partitions
 e.g. Commuter bus acting as store and
forward switch
July 7, 2015
Anshul Kantawala
2
Challenged Networks (cont.)
 Exotic Media Networks
 Near-Earth satellites, very long-distance
radio (deep space) etc.
 High latencies with predictable interruption
 Outage due to environmental conditions
 Predictably available store and forward
network service – e.g. low-earth orbiting
satellites
July 7, 2015
Anshul Kantawala
3
Challenged Networks (cont.)
 Military Ad-Hoc Networks
 Operate in hostile environments
 mobile nodes, environmental factors or
intentional jamming cause disconnections
 Data traffic may be pre-empted by
higher priority voice traffic
 Strong infrastructure protection
requirements
July 7, 2015
Anshul Kantawala
4
Challenged Networks (cont.)
 Sensor networks
 Limited end-node power, memory and
CPU capability
 Thousands or millions of nodes per
network
 Communication scheduled to conserve
power
 Interfaced to other networks using proxy
nodes
July 7, 2015
Anshul Kantawala
5
Current Solutions
 Link-repair approach
 Engineer problem links to appear similar
to regular links
 Use proxy agents
 Attach challenged networks at edges
using proxy agents
 Does not provide a general way to use
these networks for data transit
July 7, 2015
Anshul Kantawala
6
Characteristics of Challenged
Networks
 Path and Link characteristics
 Network architectures
 End System characteristics
July 7, 2015
Anshul Kantawala
7
Path and Link characteristics
 High latency, low data rate
 e.g. 10 kbps, 1-2 second latencies
 Asymmetric data rates
 e.g. remote instruments – large return
channel, small uplink for device control
 Protocols should be terse and dynamic
control functions performed open-loop or
hop-by-hop
July 7, 2015
Anshul Kantawala
8
Path and Link characteristics
 Disconnection
 Non-faulty disconnections
 Motion
 Predictable: satellite passes, bus acts as router
 Random: motion of nodes/routers, interference
 Low-duty-cycle operation
 Routing subsystem should not treat
predictable disconnections as faults and
can use this information to pre-schedule
messages
July 7, 2015
Anshul Kantawala
9
Path and Link characteristics
 Long queueing times
 Conventional networks rarely greater
than a second
 Challenged network could be hours or
days due to disconnection
July 7, 2015
Anshul Kantawala
10
Network Architectures
 Interoperability considerations
 Networks may use application-specific
framing formats, data packet size
restrictions, limited node addressing and
naming etc.
 Security
 End-to-end approach not attractive
 Require end-to-end exchanges of keys
 Undesirable to carry traffic to destination
before authentication/access control check
July 7, 2015
Anshul Kantawala
11
End System Characteristics
 Limited longevity
 Round-trip time may exceed node’s
lifetime making ACK-based policies
useless
 Low duty cycle operation
 Disconnection affects routing protocols
 Limited resources
 Affects ability to store and retransmit
data due to limited memory
July 7, 2015
Anshul Kantawala
12
Can we use TCP/IP?
 Transport layer (TCP)
 High latency and moderate to high loss
rates severely limit TCP’s performance
 Network layer (IP)
 Performance affected by loss of
fragments
 Routing
 High latency will cause current routing
protocols to incorrectly label links as
non-operational
July 7, 2015
Anshul Kantawala
13
Proxies and Protocol Boosters
 Proxies and protocol boosters are
inherently fragile
 Increase system complexity if mobility is
frequent
 May require both directions to flow
through the proxy – fail for asymmetric
routing
 Application proxies have limited re-use
abilities and may fail to take advantage
of special resources of the proxy node
July 7, 2015
Anshul Kantawala
14
Delay Tolerant Message-Oriented
Overlay Architecture
July 7, 2015
Anshul Kantawala
15
Abstraction
 Message switching
 Use message aggregates or “bundles”
 Allows network’s path selection and scheduling
functions a-priori knowledge of the size and
performance requirements of data transfers
 Overlay architecture
 DTN will operate over existing protocol stacks
and provide a gateway when a node touches two
or more dissimilar networks
July 7, 2015
Anshul Kantawala
16
Regions and DTN Gateways
 DTN gateways are interconnection points
between dissimilar network protocol and
addressing families called regions
 e.g. Internet-like, Ad-hoc, Mobile etc.
 DTN gateways




Perform reliable message routing
Perform security checks
Store messages for reliable delivery
Resolve globally-significant name tuples to
locally-resolvable names for internal destined
traffic
July 7, 2015
Anshul Kantawala
17
Name Tuples
 Two variable length portions
 Region name
 Globally-unique hierarchically structured region
name
 Used by DTN gateways for forwarding messages
 Entity name
 Resolvable within the specified region, need not
be unique outside it
 E.g. { internet.icann.int, http://www.ietf.org/ }
July 7, 2015
Anshul Kantawala
18
Class of Service
 Similar to the Postal service
 Delivery priority: low, ordinary, high
 Notifications of mailing, delivery to
receiver and route taken
 Reliable delivery using custody transfer
at each routing hop
July 7, 2015
Anshul Kantawala
19
Path Selection and Scheduling
 End-to-end path routing path cannot
be assumed to exist
 Can solve a multicommodity flow
optimization problem using
approximate algorithms, since the
protocol is message based
July 7, 2015
Anshul Kantawala
20
Custody Transfer
 Two types of message nodes
 Persistent (P) and non-persistant (NP)
 P nodes assumed to contain persistent
memory storage and participate in
custody transfer
 Custody Transfer
 Acknowledged delivery of message from
one DTN hop to the next and passing of
reliability delivery responsibility
July 7, 2015
Anshul Kantawala
21
Custody Transfer (cont.)
 Advantages
 Relieves potentially resource-poor end
nodes from maintaining end-to-end
connection states
 Useful for overcoming high loss rates
along the delivery path
 As reliable as typical end-to-end
reliability
July 7, 2015
Anshul Kantawala
22
Protocol Translation and
Convergence Layers
 Bundle forwarding function assumes
underlying reliable delivery capability with
message boundaries
 Convergence layer augments underlying network
protocols appropriately
July 7, 2015
Anshul Kantawala
23
Time Synchronization
 Need for time synchronization
 Provide a mechanism to deliver preprogrammed control instructions to be
executed at future points in time
 Use for scheduling, path selection and to
remove expired pending messages
 Propose time synchronization on the
order of 1 ms
July 7, 2015
Anshul Kantawala
24
Security
 Each message contains
 Identity of sender
 Requested class of service (CoS)
 Use public key cryptography
 First DTN router verifies user and
validates CoS request
 Re-signs message using its key
 Core routers need only cache keys of
their neighbours
July 7, 2015
Anshul Kantawala
25
Congestion and Flow Control
 Flow control is hop-by-hop
 Uses underlying protocols mechanisms if
they exist
 Congestion control
 Refers to contention of persistent storage
at a DTN forwarder
 Current approach uses a priority queue
 Priority inversion and head-of-line
blocking can occur
July 7, 2015
Anshul Kantawala
26
Application Interface
 Applications must be able to operate
in a regime where request/response
time may exceed the longevity of the
client and server processes
 Application interface is non-blocking
 Also has registration and callback
functions between bundle-based
applications and the local forwarding
agent
July 7, 2015
Anshul Kantawala
27
Implementation
July 7, 2015
Anshul Kantawala
28
Implementation (cont.)
 Prototype DTN system under Linux
 Application interface
 Rudimentary bundle forwarding across
scheduled and “always on” connections
 Detection of new and lost contacts
 Two convergence layers
 TCP/IP
 Bundle-based proxy to the Berkeley mote
network
July 7, 2015
Anshul Kantawala
29
Conclusion
 DTN architecture attempts to provide
interoperable communications
between and among challenged
networks
 Design uses message switching with
in-network retransmission, latebinding of names and routing tolerant
of network partitioning
July 7, 2015
Anshul Kantawala
30