Transcript A Delay-Tolerant Network Architecture for Challenged Internets

A Delay-Tolerant Network Architecture
for Challenged Internets
SIGCOMM’03
Kevin Fall ([email protected])
Intel Research, Berkeley
Nov. 26, 2003
Presented by Sookhyun, Yang
Contents

Introduction

Background

Challenges for Internetworking

Delay Tolerant Networking (DTN)

Application Interface

Conclusion
Computer Network Lab
Lab Seminar 2003
2
Introduction (1/2)

TCP/IP based Internet


Packet-switched model
Implicit assumption
• End-to-end path between source and destination node exits
• Maximum round-trip time between any node pairs in the network is not
excessive
• End-to-end packet drop probability is small

Challenged network

Violate one or more of Internet’s assumptions
• Very long delay path
• Frequent network partitions, etc..



Have their own specialized protocol stacks
Have naming semantics for their particular application domain
Not be well served by the current end-to-end TCP/IP
Computer Network Lab
Lab Seminar 2003
3
Introduction (2/2)

Challenged network (cont’d)

Examples
•
•
•
•

Terrestrial mobile networks
Exotic media networks
Military ad-hoc networks
sensor/actuator networks
In this paper



Achieve interoperability between very diverse networks
Propose a network architecture and application interface
Form an “internetworking of challenged internets”
Computer Network Lab
Lab Seminar 2003
4
Background

Overview of Challenged networks
Mobile network
Ad hoc network
MH
Movement
FA
FA
Sink
MH
FA
Sensor network
Computer Network Lab
Lab Seminar 2003
Sensor field
5
Challenges for Internetworking

Path and link characteristics


High latency, low data rates
Disconnection
• Faulty
• Non-faulty : motion and low-duty-cycle operation

Long queuing times
• Need to be stored for potentially long periods of time at routers

Network architectures


Interoperability considerations
Security
• Endpoint involving security is not very attractive

End system characteristics

Limited longevity
• Conventional end-to-end acknowledgement for reliable delivery should be delegated

Low duty cycle operation
• Scheduling a-priori in concert with path selection

Limited resources
• Do not necessarily have to wait for an end-to-end acknowledgement
Computer Network Lab
Lab Seminar 2003
6
Delay Tolerant Networking (1/3)

Characteristics


Operate as an overlay above the existing transport layers
Based on an abstraction of message switching
• Bundle
• Bundle forwarder (DTN gateway)
• Store-and-forward gateway function between different networks
source

DTN gateway
DTN gateway
destination
Constituent of DTN architecture

Region
• Similar network stack and addressing

DTN gateway
• Interconnection point between region boundaries
• Logically two of halves

Name Tuple
• {Region name, Entity name}
Computer Network Lab
Lab Seminar 2003
7
Delay Tolerant Networking (2/3)

Architecture
Region A - Internet
data
{B, R2}
data
{A, R1}
Region D
{A, R2}
{D, R4}
Region B – Sensor network
data
{C, R4}
Region C - Intranet
UserHost
{A, UserHost}
{C, R3}
{B, R3}
data
DTN gateway
Computer Network Lab
Lab Seminar 2003
8
Delay Tolerant Networking
DTN Gateway (1/5)

Routing (path scheduling) and message scheduling


End-to-end routing path cannot be assumed to exist
Route
• Cascade of time-dependent contacts (communication opportunity) from source to
destination
• Contact = {start_time, end_time, …}

Measure contact’s predictability
• Select the next message to be sent
• Choose next-hop forwarders
RPC Server
DTN
Application
DTN library+RPC
Scheduling and Message Forwarding
Internet
Convergence
Layer
Sockets
TDP
UDP
SensorNet
Convergence
Layer
SCTP
Sensor Network Other Transport
Stack
Or
Raw Protocols
(TBD)
(TBD)
IP
Computer Network Lab
802.3
802.11
Database
Manager
Sensor Net API
File
Store
Bundle
data
Other
Convergence
Layer
Other
Serial
Port
Lab Seminar 2003
File
Store
Bundle
data
9
Delay Tolerant Networking
DTN Gateway (2/5)

Class of service (CoS)


Priority-based resource allocation
US Postal Service
• Non-interactive
• Coarse granularity and intuitive character : low, ordinary, high

Option of reliable delivery
• Handled differently by the routing system
• Persistent storage
• Custody transfer

Custody transfer and reliability

Two distinct types of message routing nodes
• Persistent (P)
• Non-persistent (NP)

Hop-by-hop reliability
• Acknowledged delivery of message from one DTN hop to next
• Delegate reliable delivery responsibility
Computer Network Lab
Lab Seminar 2003
10
Delay Tolerant Networking
DTN Gateway (3/5)

Supplementary function for transport layer


Bundle forwarding function
Transport-protocol-specific convergence layer
• Within the regions containing a DTN P node
• Reliable delivery capability with message boundaries

Failure detection
• Retransmission timer

Congestion control
• Handle of contention for the persistent storage
• Buffer space as a function of CoS


Shared priority queue for custody transfer
Messages are spooled based on priority and useful lifetime
• Priority inversion & head-of-line blocking problem
Computer Network Lab
Lab Seminar 2003
11
Delay Tolerant Networking
DTN Gateway (4/5)

Time synchronization





Identify message fragments
Purge messages that have exceeded their source-specified lifetime
DTN’s scheduling and path selection
DTN’s congestion management technique
Security



Verifiable access to the carriage of traffic at a particular class of service
Avoid carrying traffic long distances later found to be prohibited
Postage stamp
• ID of sender || Class of service || Cryptographic material
Computer Network Lab
Lab Seminar 2003
12
Delay Tolerant Networking
DTN Gateway (5/5)

Security (cont’d)
EKRA(M || CA)
Sender A
EKRB(M || CB)
DTN gateway B
EKRC(M || CC)
DTN gateway C
destination
DKUA(EKRA(M || CA))D=KUMB(E
|| KR
CAB(M || CB)) = M || CB
Computer Network Lab
Lab Seminar 2003
13
Application Interface

Be careful not to expect timely response

Generally operate where a request/response turn-around time
exceeds the expected longevity of the client and server processes

Supported function




Name tuple creation, manipulation, and registration
Class of service classifier
Authentication information
Continue operate in the face of reboots or network partitioning as
much as possible
Computer Network Lab
Lab Seminar 2003
14
Conclusion

DTN’s contribution




Provide interoperable communications between a wide range of
networks
Advocate a change to the basic service model and system interface,
mostly accustomed Internet-style applications
Suggest model while keeping the current service model and existing
TCP/IP based protocols constant
DTN’s different choices in the architectural design




Messages vs. packets
Hop-by-hop reliability and security vs. end-to-end
Name-based routing vs. address-based routing
Partially-connected routing vs. fully-connected network graph
Computer Network Lab
Lab Seminar 2003
15
DTN Gateway
DTN library+RPC
RPC Server
DTN
Application
Scheduling and Message Forwarding
Internet
Convergence
Layer
Sockets
TDP
UDP
SensorNet
Convergence
Layer
Other
Convergence
Layer
Sensor Net API
SCTP
Sensor Network Other Transport
Stack
Or
Raw Protocols
(TBD)
File
Store
(TBD)
IP
Bundle
data
802.3
802.11
Database
Manager
Other
Serial
Port
File
Store
Bundle
data
< DTN (Bundle) Gateway >
Computer Network Lab
Lab Seminar 2003
16
DTN Gateway
DTN library+RPC
RPC Server
DTN
Application
Scheduling and Message Forwarding
Internet
Convergence
Layer
Sockets
TDP
UDP
SensorNet
Convergence
Layer
Other
Convergence
Layer
Sensor Net API
SCTP
Sensor Network Other Transport
Stack
Or
Raw Protocols
(TBD)
File
Store
(TBD)
IP
Bundle
data
802.3
802.11
Database
Manager
Other
Serial
Port
File
Store
Bundle
data
< DTN (Bundle) Gateway >
Computer Network Lab
Lab Seminar 2003
17