DTN Research Group Seok-Kap Ko Internet Draft Il-Kyun Park Intended status: Experimental Seung-Hun Oh Expires: September 9, 2012 Byung-Tak Lee ETRI Yun Won Chung Soongsil University March 9, 2012 Extensions of Probabilistic Routing Protocol for Intermittently Connected Networks draft-softgear-dtnrg-eprophet-02.txt Abstract This document defines extensions of PRoPHET, a Probabilistic Routing Protocol using History of Encounters and Transitivity. The document presents two extensions of current PRoPHET draft-09. The first extension is to apply the contact duration to calculate the delivery predictability. The other is to provide a forward strategy which can alleviate the bundle starving problem by considering expiration of bundles. Status of this Memo This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." This Internet-Draft will expire on May 1, 2012. Copyright Notice Copyright (c) 2011 IETF Trust and the persons identified as the document authors. All rights reserved. Seokkap, et al. Expires September 9, 2012 [Page 1] Internet-Draft Extension of PRoPHET March 2012 This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Seokkap, et al. Expires September 9, 2012 [Page 2] Internet-Draft Extension of PRoPHET March 2012 Table of Contents 1. Introduction ................................................. 4 2. Terminology .................................................. 5 3. Contact Duration based P_encounter function .................. 5 3.1. Overview ................................................ 5 3.2. Contact Duration Based Delivery Predictability........... 6 3.3. Contact Gap Based Delivery Predictability ............... 6 3.4. Unified Contact Duration & Contact Gap Based Delivery Predictability ............................................... 7 4. Expiration based Forwarding Strategy ......................... 8 5. Security Considerations ...................................... 9 6. IANA Considerations .......................................... 9 7. Acknowledgments .............................................. 9 8. References .................................................. 10 8.1. Normative References ................................... 10 8.2. Informative References ................................. 10 Seokkap, et al. Expires September 9, 2012 [Page 3] Internet-Draft Extension of PRoPHET March 2012 1. Introduction PRoPHET is a variant of the epidemic routing protocol for intermittently connected networks without flooding. PRoPHET is designed for DTNs(Delay/Disruption Tolerant Networks) which are intermittently connected networks. The PRoPHET draft-09 has been submitted on April 3, 2011[I-D.irtf-dtnrg-prophet-09]. In PRoPHET draft-09, when two nodes meet, they update the delivery predictability for each other using the following equation: P_(A,B) = P_(A,B)_old + (1-delta-P_(A,B)_old)*P_encounter (1) To reduce the distortion of the delivery predictability if the contact occurs very short and frequent, PRoPHET draft-09 suggests the P_encounter function of interval to decrease the predictability when the interval is shorter than the typical time(I_typ). Although this limits the unnecessary increase of P_(A,B) due to very short and frequent contact to some extent, it still increases P_(A,B) even for very short and frequent contact. Therefore, we remove this unnecessary increase of P_(A,B) for this case by filtering very short and frequent contact. Furthermore, the calculation of the delivery predictability in PRoPHET draft-09 does not consider the contact duration at all. However, we argue that a node with longer contact duration may have higher delivery predictability if other conditions are the same. This document describes this and suggests to use a P_encounter function based on the contact duration and contact interval. PRoPHET and [lindgren_06] provides several forward strategies. All strategies are based on priority queue scheduling. Therefore, bundles in a lower priority queue may be starved by bundles in a higher priority queue. When the total departure rate is smaller than the total arrival rate, the queues will be fulfilled and some bundles are dropped. If we use a priority queue scheduling, the lower priority queue will not be served forever. This document provides a forward strategy which can reduce the starving using the expiration of the bundle. It combines the predictability value for the destination of the bundle and the expiration of the bundle. Seokkap, et al. Expires September 9, 2012 [Page 4] Internet-Draft Extension of PRoPHET March 2012 2. Terminology The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119]. To make explanation of the proposed P_encounter function clear, we assume a scenario in that node A meets node B at time t1, they separate at time t2, and they meet again at time t3. In this scenario, we define contact interval between nodes A and B as the time interval between two consecutive encounters between nodes A and B, and it is obtained as t3 - t1. Interval and encounter interval are also interchangeably used to denote contact interval. Contact duration is defined as the time that two nodes have kept in contact with each other continuously and it is obtained as t2 - t1. For notational convenience, we define t3 - t2 as contact gap, which is the time that two nodes have been out of contact with each other previously when they meet again. Therefore, the relationship contact interval = contact duration + contact gap holds. 3. Contact Duration based P_encounter function 3.1. Overview Delivery predictability P_(A,B) is based on the history of encounter between node A and B which is reflected in the equation (1) as P_encounter [I-D.irtf-dtnrg-prophet-09]. P_encounter may take various forms. For example, it has a constant value, irrespective of contact interval or contact duration and we call this as constant (CST) P_encounter. However, this constant P_encounter may increase delivery predictability unnecessarily, even for very short and frequent contact. In order to remove the distortion of the delivery predictability value which is caused by several communication opportunities closely spaced in time due to wireless physical characteristic, P_encounter was proposed to be a function of the interval since the last encounter in Fig. 2 from [I-D.irtf-dtnrg- prophet-09], and contact interval-based (CIB) P_encounter was used. In this draft, we argue that it is intuitively reasonable that if a node has longer and stable contact duration with another node, the value of delivery predictability between these two nodes should be larger. We suggest to use a contact duration based (CDB) P_encounter in this draft. Seokkap, et al. Expires September 9, 2012 [Page 5] Internet-Draft Extension of PRoPHET March 2012 3.2. Contact Duration Based Delivery Predictability The delivery predictability value for a node which has stably long enough contact time must be larger than that for a node which does not, as mentioned in the previous section. Therefore, we propose to make P_encounter as a function of contact duration as follows: P_encounter(d)= P_encounter_max * (1 - e^(-epsilon * d)), (2) where d is the sum of contact duration since the last normal contact, epsilon is a contact differentiating constant, and P_encounter_max is the limiting value for P_encounter from '0' to '1'. To analyze the performance of the proposed delivery predictability calculation, we assume an opportunistic link between nodes A and B. We set a contact differentiating constant (epsilon) low (0.1) enough to minimize the effect of short contact durations. I_typ defined for CIB is set to 10 seconds due to average time between transfer opportunities, and we use 1 second time unit for delivery predictability aging equation. Three contact scenarios can be considered: 'short gap & short contact duration', 'short gap & long contact duration' and 'long gap & short contact duration'. The first scenario of 'short gap & short contact duration' shows that delivery predictability with CST is rapidly increasing because it has constant P_encounter. However other two methods, CIB and our CDB, avoid the delivery predictability distortion by increasing delivery predictability slightly, because these reflect contact interval and contact duration respectively. If interval of second scenario is the same as that of third scenario, P_encounter values obtained by CIB are the same. In contrast, the P_encounter by CDB in second scenario is higher than that in the last scenario because CDB considers contact duration. 3.3. Contact Gap Based Delivery Predictability Although CIB P_encounter limits the unnecessary increase of P_(A,B) in CST P_encounter due to very short and frequent contact to some extent, it still increases P_(A,B) even for very short and frequent contact. Therefore, we remove this unnecessary increase of P_(A,B) for this case by filtering very short and frequent contact in CIB P_encounter. We call this as contact gap based (CGB) P_encounter and CGB P_encounter function is defined as the following equation: P_encounter (g) = 0 if g<=I1 Seokkap, et al. Expires September 9, 2012 [Page 6] Internet-Draft Extension of PRoPHET March 2012 P_encounter (g) = P_encounter_max *(g-I1)/(I2-I1) if I1I2 If contact gap is very short, P_encounter (g) becomes zero to remove unnecessary increase of P_(A,B) due to very short and frequent contact. The graph of P_encounter (g) function is drawn as follows: | P_encounter_max + ----------- | / | / | / | / | / +-----------------------------> g 0 I1 I2 3.4. Unified Contact Duration & Contact Gap Based Delivery Predictability Since the proposed CDB P_encounter does not consider contact gap and the proposed CGB P_encounter does not consider contact duration, we combine both function to take the merit of both scheme and define unified contact duration and contact gap based (CDGB) P_encounter as follows: P_encounter(d,g) = P_encounter_duration(d) * P_encounter_gap(g) (4) The function P_encounder_duration(d) is CDB P_encounter in equation (2) and the function P_encounter_gap(g) is CGB P_encounter in equation (3). By using unified CDGB P_encounter(d,g) given in equation (4), we can consider contact duration and contact gap together and thus, may obtain more reasonable delivery predictability value. Seokkap, et al. Expires September 9, 2012 [Page 7] Internet-Draft Extension of PRoPHET March 2012 4. Expiration based Forwarding Strategy In PRoPHET, nodes decide on which bundles they wish to exchange with the peer node during the information exchange phase. PRoPHET draft-09 describes 7 basic forward strategies : GRTR, GTMX, GTHR, GRTR+, GTMX+, GRTRSort, and GRTRMax. The node which sending a bundle does not delete the bundle after sending it as long as there is sufficient buffer space available. However, when the total departure rate is smaller than the total arrival rate, the queues will be fulfilled and some bundles are dropped. The departure rate is the total effective bandwidth from this node to other nodes when the forwarding condition in such a forwarding strategy is satisfied. Because all strategies are in a kind of priority queue scheduling, the bundles to the specific destination will be discarded. For the fairness, the bundle which has short expiration and has been served rarely should be served before the bundle which has long expiration and has been served frequently. PRoPHET draft-09 describes P_ewma, a smoother value of the predictability. This document approximates ET, the expected delivery time from P_ewma with the following equation. ET is the average contact interval. ET = log_gamma ( P_ewma / P_encounter_first ) As PRoPHET draft-09, A and B are the nodes that encounter each other, and the strategies are described as they would be applied by node A. The destination node is D. P_(X,Y) denotes the delivery predictability stored at node X for destination Y, NF is the number of times A has given the bundle to some other node, EX is the remained expiration of the bundle, and ET(X,Y) is the expected delivery time which is approximated by P_(X,Y). P_(X,Y) is P_ewma(X,Y). Seokkap, et al. Expires September 9, 2012 [Page 8] Internet-Draft Extension of PRoPHET March 2012 GEXRSort Select bundles in ascending order of the value of (NF + 1) / (EX / ET(B,D)). Forward the bundle only if P_(B,D) > P_(A,D) The larger predictability value causes shorter ET. Therefore, this strategy gives high priority to the larger predictability path. This strategy gives high priority to the bundle which has short expiration and gives low priority to the bundle which has been forwarded more times. GEXRSort+ Select bundles in ascending order of the value of (NF + 1) / (EX / ET(B,D)). Forward the bundle if P_(B,D) > P_(A,D) or EX/ET(A,D)<1 This strategy is like GEXRSort, but if the expiration is very short, forward the bundle to the other. 5. Security Considerations TODO - fill in 6. IANA Considerations TODO - fill in 7. Acknowledgments TODO - fill in Seokkap, et al. Expires September 9, 2012 [Page 9] Internet-Draft Extension of PRoPHET March 2012 8. References 8.1. Normative References [I-D.irtf-dtnrg-prophet-09] A. Lindgren, A. Doria, E. Davies, S. Grasic, "Probabilistic Routing Protocol for Intermittently Connected Networks", draft-irtf-dtnrg-prophet-09 (work in progress), April 3, 2011. 8.2. Informative References [lindgren_06] Lindgren, A. and K. Phanse, "Evaluation of Queueing Policies and Forwarding Strategies for Routing in Intermittently Connected Networks", Proceedings of COMSWARE 2006 , January 2006. Seokkap, et al. Expires September 9, 2012 [Page 10] Internet-Draft Extension of PRoPHET March 2012 Author's Addresses Seok-Kap Ko ETRI 1000-6 Oryong-dong, Buk-gu, Gwangju, 500-480, Korea Phone: +82-62-970-6677 Email: softgear@etri.re.kr Il-Kyun Park ETRI 1000-6 Oryong-dong, Buk-gu, Gwangju, 500-480, Korea Phone: +82-62-970-6651 Email: ikpark@etri.re.kr Seung-Hun Oh ETRI 1000-6 Oryong-dong, Buk-gu, Gwangju, 500-480, Korea Phone: +82-62-970-6655 Email: osh93@etri.re.kr Byung-Tak Lee ETRI 1000-6 Oryong-dong, Buk-gu, Gwangju, 500-480, Korea Phone: +82-62-970-6624 Email: bytelee@etri.re.kr Yun Won Chung Soongsil University 511 Sangdo-Dong, Dongja-Gu, Seoul, 156-743, Korea Phone: +82-2-820-0908 Email: ywchung@ssu.ac.kr Seokkap, et al. Expires September 9, 2012 [Page 11]