Vol. 0 No. 0??? 1959 DTN 1 1 Delay (or Disruption) Tolerant Networks(DTN) DTN Potential-Based Routing(PBR) DTN Topology Change Tolerant Routing(TCTR) TCTR TCTR 100 Topology Change Tolerant Routing for Delay Tolerant Networks Hideya Ochiai 1 and Hiroshi Esaki 1 Delay (or Disruption) Tolerant Networks (DTN) are promised as an efficient message delivery scheme in physically unstable networks like wireless networks. However, because datalinks could be physically disrupted in DTN environment, global synchronization in the network is absolutely difficult, which indicates the traditional routing schemes cannot work appropriately. We propose Topology Change Tolerant Routing (TCTR), which do not need global synchronization in the network for message delivery. In fact, TCTR is a instance of Potential-Based Routing(PBR) which selects the next hop of messages only using the relative information with its neighbor nodes. We have developed a prototype system and TCTR simulator. We have confirmed that the implementation of TCTR is feasible. We have also evaluated TCTR in terms of message delivery time, transmission cost and message pool size with the simulator. 1. MANET Delay (or Disruption) Tolerant Networks(DTN) IP TCP DTN DTN ( ) DTN 1 The University of Tokyo (e.g., RIP 14), OSPF 16), MPLS 18), AODV 17) ) DTN Topology Change Tolerant Routing(TCTR) TCTR Potential-Based Routing(PBR) TCTR 1
2??? 1959 DTN Application Protocol Data Units(APDU) 6) IP 1 DTN PBR TCTR TCTR (1) ( TCTR ) (2) ( 3.3 ) 2000[m] 2000[m] 100 (3) (4) (5) 2 3 TCTR 4 5 6 7 2. Delay (or Disruption) Tolerant Networks (DTN) 3) Epidemic Routing 20) Spray and Wait 19) (i.e., ) (i.e., ) Merugu 15) Leguay MobySpace 10) PROPHET 12) Francois 4) PBR (Gradient Descent Search) Basu 1)
Vol. 0 No. 0 DTN 3 Anycast 9)11) Volcano Routing Scheme(VRS) 5) PBR PWave 13) ZebraNet 8) History-based Protocol PBR DTN 3. TCTR TCTR PBR TCTR G = (N, E) G n( N) nbr(n) n n d( N) t d n V d (n, t) V d (n, t) d 3.1 Potential-Based Routing(PBR) t n d M d (n, t) k nbr(n) F d k (n, t) F d k (n, t) {V d (k, t) V d (n, t)} (1) M d (n, t) nexthop d (n, t) PBR k nbr(n), F d k (n, t) α nexthop d (n, t) = Φ (2) k nbr(n), F d k (n, t) > α nexthop d (n, t) = {k F d k (n, t) = max Fk d (n, t)} (3) k nbr(n) α 2 α 1 Potential-Based Routing(PBR) Fig. 1 Potential-Based Routing(PBR) (Φ ) 3 α 1 d 1 PBR G n k 1, k 2 k 1 n k 1 d PBR 3.2 PBR 2,3 1
4??? 1959 2 d = n6 Fig. 2 Potential formation and message delivery path for destination d = n6 in a physically connected network. V d (n, t + 1) = V d (n, t) + D min k nbr(n) {0, V d (k, t) V d (n, t)} +ρ (4) d N tv d (d, t) = 0 (5) n N V d (n, 0) = 0 (6) V d (n, t) D(0 < D < 1) ρ(0 < ρ < D) 5 6 0 0 V d (n, t) 3 ( 2) 2 d = n6 V n6 (n, t) 2 n6 ( 3) G 1 = (N 1, E 1 ), G 2 = (N 2, E 2 ) G 1 (i.e., d N 1 ) N 2 3 n2 n4 ; n0, n1, n2, n3 ρ Fig. 3 Potential formation when n2 n4 link has been disrupted. Potentials of n0, n1, n2, n3 goes up with the velocity of ρ. (c ) n N2 V d (n, t) ρt + c (7) (t ) 3 {n0,..., n3} ρ {n0,..., n3} ( 4) 4 n1 n5 4 {n0,..., n3} (i.e., ) 4 d d
Vol. 0 No. 0 DTN 5 4 n1 n5 n0, n1, n2, n3 Fig. 4 When n1 n5 link has been setup, potentials of n0, n1, n2, n3 goes down with making message delivery curves. 3.3 4 k nbr(n) V d (k, t) t TCTR n k ( V d n (k, t) ) k V d k (k, t) T V d k (k, t) V d k (k, t T ) = V d k (k, t) V d n (k, t) (8) V d n (k, t) V d k (k, t) T V d n (n, t) t (9) 4 i N, V d i (i, t) = V (t) V(t) 3 2,3 α = 0 nexthop d (n, t) = Φ 7 Vk d V (t) (n, t) V (t) T t 1 Fk d V (t) (n, t) = T t (10) (11) ( V (T ) t > 0) 3 nexthop d (n, t) = k nbr(n) k (12) 1 5 A, B, C A B C A C B C C A, B C A B B A C B B B C A
6??? 1959 Fig. 5 5 An example of message overflow phenomenon 4 n ( 1 ) Advertisement Manager: UDP Multicast 6 Fig. 6 Prototype System Overview 2,3 α β β < α (13) α β 9 β = T max V d (n, t) t 4 max V d (n, t) t (14) = ρ (15) β = ρ T (16) 4. 4.1 6 k nbr(n) V (k, t), V (n, t) Multicast Socket V (k, t) PotentialTable PotentialTable n V (n, t) UDP Multicast ( 2 ) Potential Table: k nbr(n) V (k, t) V (n, t) V (n, t + 1) 4 ( 3 ) Forwarding Table: Potential Table V d (n, t) k nbr(n) V d (k, t) 2 3 d ( 4 ) Message Manager: Message Manager (Send) Message Manager n (Receive) n d Forwarding Table ACK
Vol. 0 No. 0 DTN 7 7 Fig. 7 TCTR Simulator Overview Message Manager () Forwarding Table () () (Send) (Receive) C OS Linux 2.6.22 802.11g 4.2 TCTR 7 3 ( 1 ) Node: Node Node Node Locator ( ) ( 2 ) Node Locator: Node (2 ) ( 3 ) Mobility Manager: Node Locator () Forwarding Table () 8 Fig. 8 Mobility model used in the experiment () (Send) (Receive) Java JavaVM 1.5.0 OS Linux 2.6.15 5. Flooding-Based Routing(FBR) : (1) (2) (3) ( ) D ρ D = 0.2 ρ = 0.02 5.1 8 Home A Home B Meeting Point
8??? 1959 9 Fig. 9 Potential patterns with the prototype-based experiment 10 Fig. 10 Potential patterns with the simulation-based experiment 1 4 Home A B 2 3 Home A B 2 3 Meeting Point Home A, Meeting Point, Home B ( )20m 8 2 3 2 8 20 4 1 10 1 100 9 1 V 1 (n, t) t = 3600 t = 4800 (t 3600) n 1, n 2, n 3, n 4 1, 2 3 4 t = 60 n 2 n 1 V (n 2, t) t = 580 n 3 n 2 V (n 3, t) 122 n 2 n 2 n 3 Meeting Point t = 1140 n 4 n 3 n 2 n 1 n 4 n 2 n 1 105 121 n 3 n 1 TCTR 10 1 V 1 (n, t) t = 3600 t = 4800 ( (t 3600) ) 5.2 5 C 16 0 < T < 1, ρ = 0.02 0.02 α {0.000, 0.010, 0.015, 0.020, 0.025, 0.030} 5 1 α 3 5 Node A Node B (Status) A Node A B Node B Φ
Vol. 0 No. 0 DTN 9 Table 1 1 An Analysis of the Message Overflow Threshold α Node A Node B Status 1 2 3 1 2 3 0.000 B B B A A A 0.010 Φ B B A A Φ 0.015 Φ Φ B A A Φ 0.020 Φ B B Φ Φ Φ 0.025 Φ Φ Φ Φ Φ Φ 0.030 Φ Φ Φ Φ Φ Φ α α 0.02 5.3 100 Flooding-Based Routing(FBR) FBR A( N) B( N) A B M A M B A B m M A m M B T ransfer A (m, B) (17) m M B m M A T ransfer B(m, A) (18) T ransfer X (m, Y ) X m Y m(m M A m M B) (19) m FBR FBR TCTR Time To Live(TTL) (FBR TCTR ) 11 Fig. 11 Delivery Time Relationship between FBR and TCTR 2000[m] 2000[m] 0 300[m] 100 150[m] 0 0.01[Hz] Random Way Point(RWP) 2) RWP t=0 t=10000 (t=10000 TCTR ) 5.3.1 11 FBR T ime (F BR) TCTR T ime (T CT R) ( : ) T ime (T CT R) = T ime (F BR) T ime (T CT R) T ime (F BR) 12 T ime (T CT R) T ime F BR 33% (FBR) 2 50% 3
10??? 1959 Fig. 12 12 Efficiency in Delivery Time and its Distribution 14 Fig. 14 The Average Message Pool Size 5.3.3 14 FBR TCTR 13 Fig. 13 The Total Message Transmission in the Network 10 5% 5.3.2 13 FBR TCTR ( t = 10000 0 ) a( N) b( N, a b) FBR TCTR 10 FBR (=100 ) 100 100 10 6 TCTR 100 100 10 5 ( t = 10000 0 ) FBR 10000 TCTR 97 FBR 100 100 100 100 = 10000 TCTR 6. β 3.3 TCTR α 100 FBR FBR
Vol.0 No.0 DTN 11 3 TCTR FBR 10 100 TCTR 7) 7. DTN TCTR PBR TCTR TCTR 100 FBR 3 10 1 100 1 1) Basu, A., Lin, A. and Ramanathan, S.: Routing Using Potentials: A Dynamic Traffic-Aware Routing Algorithm, ACM SIGCOMM 2003, pp.37 48 (2003). 2) Bettstetter, C., Resta, G. and Santi, P.: The Node Distribution of the Random Waypoint Mobility Model for Wireless Ad Hoc Networks, IEEE Transactions on Mobile Computing, Vol.2, No.3, pp.257 269 (2003). 3) Fall, K.: A Delay-Tolerant Network Architecture for Challenged Internets, ACM SIG- COMM 2003, pp.27 34 (2003). 4) Francois, J.-M. and Leduc, G.: Delivery Guarantees in Predictable Disruption Tolerant Networks, Lecture Nodes in Computer Science, Vol.4479, pp.167 178 (2007). 5) Ganjali, Y. and McKeown, N.: Routing in a Highly Dynamic Topology, IEEE SECON, pp. 164 175 (2005). 6) Iren, S., Amer, P.D. and Conrad, P.T.: The Transport Layer: Tutorial and Survey, ACM Computing Surverys, Vol.31, No.4, pp.360 404 (1999). 7) Jain, S., Fall, K. and Patra, R.: Routing in a Delay Tolerant Network, ACM SIGCOMM 2004, pp.145 158 (2004). 8) Juang, P., Oki, H., Wang, Y., Martonosi, M., Peh, L.-S. and Rubenstein, D.: Energy- Efficient Computing for Wildlife Tracking: Design Tradeoffs and Early Experiences with ZebraNet, ACM SIGOPS, pp.96 107 (2002). 9) Kumar, P., Kuri, J., Nuggehalli, P., Strasser, M., May, M. and Plattner, B.: Connectivityaware Routing in Sensor Networks, IEEE SensorComm, pp.14 20 (2007). 10) Leguay, J., Friedman, T. and Conan, V.: DTN Routing in a Mobility Pattern Space, ACM SIGCOMM workshop on Delay-tolerant networking, pp.276 283 (2005). 11) Lenders, V., May, M. and Plattner, B.: Density-based vs. Proximity-based Anycast Routing for Mobile Networks, IEEE INFO- COM, pp.1 13 (2006). 12) Lindgren, A., Doria, A. and Schelen, O.: Probabilistic Routing in Intermittently Connected Networks, Lecture Nodes in Computer Science, Vol.3126, pp.239 254 (2004). 13) Liu, H., Zhang, Z.-L., Srivastava, J. and Firoiu, V.: PWave: A Multi-source Multi-sink Anycast Routing Framework for Wireless Sensor Networks, Lecture Nodes in Computer Science, Vol.4479, pp.179 190 (2007). 14) Malkin, G.: RFC2453: RIP Version 2 (1998). 15) Merugu, S., Ammar, M. and Zegura, E.: Routing in Space and Time in Networks with Predictable Mobility, Technical report, Georgia Institute of Technology (2004). 16) Moy, J.: RFC2328: OSPF Version 2 (1998). 17) Perkins, C., Belding-Royer, E. and Das, S.: RFC1058: Ad hoc On-Demand Distance Vector (AODV) Routing (2003). 18) Rosen, E., Viswanathan, A. and Callon, R.: RFC3031: Multiprotocol Label Switching Architecture (2001). 19) Spyropoulos, T., Psounis, K. and Raghaven-
12??? 1959 dra, C.S.: Spray and Wait: An Efficient Routing Scheme for Intermittently Connected Mobile Networks, ACM SIGCOMM workshop on Delay-tolerant networking, pp.252 259 (2005). 20) Vahdat, A. and Becker, D.: Epidemic Routing for Partially-Connected Ad Hoc Networks, Technical report, Duke University (2000).