DTN Research Group Hong-Yeon Yu Internet Draft Sim-Kwon Yoon Intended status: Experimental Seok-Kap Ko Expires: May 1, 2012 Byung-Tak Lee ETRI November 1, 2011 Extensions of Probabilistic Routing Protocol for Intermittently Connected Networks draft-softgear-dtnrg-eprophet-01.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. 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. 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 HongYeon, et al. Expires May 1, 2012 [Page 1] Internet-Draft Extension of PRoPHET November 2011 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. HongYeon, et al. Expires May 1, 2012 [Page 2] Internet-Draft Extension of PRoPHET November 2011 Table of Contents 1. Introduction ................................................. 4 2. Terminology .................................................. 4 3. Contact Duration based P_encounter function .................. 5 3.1. Overview ................................................ 5 3.2. Contact Duration Time Considered Delivery Predictability. 5 4. Expiration based Forwarding Strategy ......................... 6 5. Security Considerations ...................................... 7 6. IANA Considerations .......................................... 7 7. Acknowledgments .............................................. 8 8. References ................................................... 8 8.1. Normative References ................................... 8 8.2. Informative References .................................. 8 HongYeon, et al. Expires May 1, 2012 [Page 3] Internet-Draft Extension of PRoPHET November 2011 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 Network) which are intermittently connected networks. The PRoPHET draft-09 have 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 for interval is shorter than the typical time(I_typ). However, the calculation of the predictability in PRoPHET draft-09 does not consider the contact duration when interval is longer. This document describes this problem and suggest to use a P_encounter function of the contact duration but interval. PRoPHET and [lindgren_06] provides several forward strategies. the overlay. All strategies are in a kind of 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. 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]. HongYeon, et al. Expires May 1, 2012 [Page 4] Internet-Draft Extension of PRoPHET November 2011 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) [I- D.irtf-dtnrg-prophet-09]. It is intuitively reasonable that the longer, and the relatively more stable the encounter nodes have with their neighbors is, the higher Delivery Predictability values should be. For example if node A keeps in contact with node B for 10 seconds and it also has 5 times of 2 second long contacts with node C, P_(A,B) should be larger than P_(A,C). The different duration of contact nodes have must make Delivery Predictabilities different. However the Delivery Predictability equations introduced in [I- D.irtf-dtnrg-prophet-09] do not have this feature properly (constant P_encounter, CST). 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 is proposed to be a function of the interval since the last encounter in Fig. 2 from [I-D.irtf-dtnrg- prophet-09] (contact interval based P_encounter, CIB). Nevertheless, it still does not reflect the duration of contact. 3.2. Contact Duration Time Considered Delivery Predictability The Delivery Predictability value for the node which guarantees stably long enough contact time must be larger than that for the node which does not, as mentioned in the previous section. Therefore we propose to make P_encounter a function of contact time duration as follows. P_encounter(t)=P_encounter_max * (1 - e^(-epsilon * t)) (2) where t is the sum of contact duration since the last calculation, epsilon is a contact differentiating constant, and P_encounter_max is the limiting value for P_encounter from '0' to '1' (contact duration time based P_encounter, CDB). To analyze 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 punish the short contact durations. I_typ 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 interval & short contact', 'short interval & normal contact' and 'long interval & short contact'. HongYeon, et al. Expires May 1, 2012 [Page 5] Internet-Draft Extension of PRoPHET November 2011 The first scenario of 'short interval & short contact' 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. In the second scenario where relatively stable contact but still short contact intervals take place, CIB keeps its Delivery Predictability's increment as low as node B is considered to be inappropriate one for delivery the bundle to the destination. In contrast, the proposed CDB scheme rapidly considers the contact duration and raises the possibility of forwarding the bundle to the node B. The last scenario is that the contact interval is very long but contact duration is short. Both CIB and the proposed CDB reflect the number of contacts into Delivery Predictability calculation and result in high Delivery Predictability value. On the contrary, the Delivery Predictability value is kept still low under the proposed scheme, because of short contact duration. Therefore we see that it is very important to reflect contact duration into Delivery Predictability calculation to in order to reduce Delivery Predictability distortion. 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. HongYeon, et al. Expires May 1, 2012 [Page 6] Internet-Draft Extension of PRoPHET November 2011 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). 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 HongYeon, et al. Expires May 1, 2012 [Page 7] Internet-Draft Extension of PRoPHET November 2011 7. Acknowledgments TODO - fill in 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. HongYeon, et al. Expires May 1, 2012 [Page 8] Internet-Draft Extension of PRoPHET November 2011 Author's Addresses Hong-Yeon Yu ETRI 1000-6 Oryong-dong, Buk-gu, Gwangju, 500-480, Korea Phone: +82-62-970-6672 Email: keister@etri.re.kr . Sim-Kwon Yoon ETRI 1000-6 Oryong-dong, Buk-gu, Gwangju, 500-480, Korea Phone: +82-62-970-6969 Email: yoonsk@etri.re.kr Seok-Kap Ko ETRI 1000-6 Oryong-dong, Buk-gu, Gwangju, 500-480, Korea Phone: +82-62-970-6677 Email: softgear@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 HongYeon, et al. Expires May 1, 2012 [Page 9]