Topology Change Tolerant Routing
for Delay Tolerant Networks

Hideya Ochiai Hiroshi Esaki
The University of Tokyo / NICT

Outline• Introduction• Topology Change Tolerant Routing– Next hop selection and message forwarding– Potential-field computation• Prototype Implementation• Conclusion

Background and Goal
• Communication over intermittently connected links– Message delivery over cyclic mobile node
– Application of Delay Tolerant Networks (DTN)
MessageAB
C
Circle: Transmission Range• Proposal: Message Routing in DTNs
– where physical topology frequently changesI.e., intermittent connectivity

Delay Tolerant Networks• Message Delivery Scheme– Hop-by-Hop Message Delivery– End-to-End Asynchronous Communication– Store-Carry-Forward

Mail

Node AMailMail

Mail

Mail

DTN Router

DTN Router

DTN Router

DTN Router

CDEF

Link Disruption

Mail

Node BApproach: Potential-Based Routing (PBR)
Potential
Internet
Gateway

Data Flow

InternetInternet

Truck
Data Flow

SensorDelivering sensor data to the Internet gateway
Wireless Device

Outline• Introduction• Topology Change Tolerant Routing– Next hop selection and message forwarding– Potential-field computation• Prototype Implementation• Conclusion

Terminology• A set of nodes: N• A node: n  N• A set of neighbors: nbr (n)Nodes that are within
direct transmission range• A neighbor node: k  nbr (n)dn• Potential for destination d at : V ( n)  R• with explicit t : V d ( n, t )• The next hop nodes for destination d at n :dnexthop (n)<< TCTR >>Next hop selection and message forwarding
Force at node n toward node k  nbr (n) :F n   V (n)  V (k )dkdd

Next hop nodes for destination d :k  nbr (n) F n     nexthop (n)  dkdEmpty Set

k  nbr (n) F n   dk nexthop d (n)  k | Fkd (n)  max F jd (n) : threshold (const.)

jnbr ( n )Message for d

M d ( n, t )Force for k2

Fkd2 n, t V  x, t dn

Force for k1

Fkd1 n, t k2

k1

Message
Delivery Pathd

F n, t   F n, t   F n, t     nexthop (n, t )  kdk1

dk2

dk1

d1

<< TCTR >>Potential-Field Computation
Definition by a recurrence formulaV d (n, t  1)  V d (n, t )  D min V d (k , t )  V d (n, t )  knbr ( n )Boundary condition
Initial condition

td  N , V d (d , t )  0dn, d  N , V (n,0)  0

D : const. 0  D  1
 : const. 0    D

<< TCTR >>Potential-Field Computation and Message Delivery (1/6)

n11n5n1n0n10n9n2n4n6n3V n 6 ( n)Potential-Field for n6n7n8Connected Network

<< TCTR >>Potential-Field Computation and Message Delivery (2/6)

n0V n6 n 

n1n11n3n2n5n4n10n7n6n8n9

<< TCTR >>Potential-Field Computation and Message Delivery (3/6)

n11n5n1n0n2n9n4
Link disruption

n3n10n6

V ( n)

n6

Potential-Field for n6n7n8

When a link disrupts

<< TCTR >>Potential-Field Computation and Message Delivery (4/6)

n0n1n2

V n 6 n, t tn3

Increase at speed Vn6n n11n5n4n10n7n6n8n9

<< TCTR >>Potential-Field Computation and Message Delivery (5/6)
Connected !!

n11n1n5n10n9n0n2n4n6n3n6V ( n)Potential-Field for n6n7n8

When connected by another link<< TCTR >>Potential-Field Computation and Message Delivery (6/6)

n2n1

Vn6n 

Vn3n0n6

n, t   0

tSudden decrease(with delivering messages)

n5n4

n11n10n7n6n8n9

Features of TCTR
• Routing without global knowledge of topology.
– Potential-field computationV d (n, t  1)  V d (n, t )  D min V d (k , t )  V d (n, t )  knbr ( n )– Message forwarding (i.e., next hop selection)k  nbr (n) F n   dk

 nexthop d (n)  k | Fkd (n)  max F jd (n)jnbr ( n )• Message delivery is achieved totally relying onneighbor information.
• Thus, TCTR is tolerant for topology changes.

Outline• Introduction• Topology Change Tolerant Routing– Next hop selection and message forwarding– Potential-field computation• Prototype Implementation• Conclusion

Prototype Implementation
Function Blocks in Node nApplication(Message Send / Receive)V ( n, t )V ( n, t )nexthop(n)V (k , t )k  nbr (n)UDP Multicast(Advertisement)

V (k , t )k  nbr (n)Message
Pool

Message Manager

Advertisement Manager

Potential Table Forwarding Table

UDP Socket(Message Transfer)Message Delivery on Node Mobility
Experiment of Potential Computation and Message Delivery 4  1t=01234t = 60

1234t = 540

1234t = 660

1234t = 1140

1234t = 1200(sec)1234Home A

Meeting PointHome BPotential Computation & Message Delivery
Message Delivery

n4  n1

Outline• Introduction• Topology Change Tolerant Routing– Next hop selection and message forwarding– Potential-field computation• Prototype Implementation• Conclusion

Conclusion• TCTR is tolerant for topology changes– Routing without global knowledge of topology.
– Routing uses only neighbor status.

• Potential-field computationV d (n, t  1)  V d (n, t )  D min V d (k , t )  V d (n, t )  knbr ( n )• Future work
– Various mobility pattern– Multiple replica cases