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 I1<g<=I2 (3)
P_encounter (g) = P_encounter_max if g>I2
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]