Extension of Probabilistic Routing Protocol using History of Encounters and Transitivity for Information Centric Network
draft-chung-dtn-extension-prophet-icn-00

Delay-Tolerant Networking                                 Y. W. Chung
Internet-Draft                                             M. W. Kang
Intended status: Informational                                 Y. Kim
Expires: May 17, 2018                              Soongsil University
                                                     November 15, 2017

        Extension of Probabilistic Routing Protocol using History of
        Encounters and Transitivity for Information Centric Network
               draft-chung-dtn-extension-prophet-icn-00.txt

Abstract

   This document proposes extension of probabilistic routing protocol
   using history of encounters and transitivity (PRoPHET) for
   information centric network.

Status of This memo

   This Internet-Draft is submitted 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 17, 2018.

Copyright Notice

   Copyright (c) 2017 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

Chung, et al.           Expires May 15, 2018                  [Page 1]
Internet-Draft      Extension of PRoPHET for ICN         November 2017

   (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.

Table of Contents

   1. Introduction ................................................. 2
   2. Conventions and Terminology .................................. 3
      2.1. Conventions ............................................. 3
      2.2. Terminology ............................................. 3
   3. Forwarding of Interest and Data for ICN ...................... 3
      3.1. Delivery predictability of PRoPHET ...................... 3
      3.2. Extension for Interest forwarding ....................... 4
      3.3. Extension for Data forwarding ........................... 5
      3.4. Operation of the proposed extension ..................... 6
   4. Security Considerations ...................................... 6
   5. IANA Considerations .......................................... 6
   6. References ................................................... 7
      6.1. Normative References .................................... 7
      6.2. Informative References .................................. 7

1. Introduction

   In Information centric network (ICN), a node requests Data by
   sending Interest packet and this Interest packet is forwarded
   through ICN routers. A router with the requested Data replies to the
   Interest to the requester and the Interest is delivered through a
   reverse path of the forwarded Interest. ICN router manages content
   store (CS), pending interest table (PIT), and forwarding information
   base (FIB) [George2014]. In CS, cached data is stored for future use.
   In PIT, the information of Interest, the incoming and outgoing faces
   of the Interest are stored, and this information is used to deliver
   Data to the requester using the reverse path of forwarded Interest.
   FIB is used to forward Interest to appropriate faces.

   ICN is considered important for communication of urgent messages in
   disaster situations [Edo2014]. In disaster situations, communication
   infrastructure is destroyed and networks are fragmented. In

Chung, et al.           Expires May 15, 2018                  [Page 2]
Internet-Draft      Extension of PRoPHET for ICN         November 2017

   fragmented networks where connectivity between the nodes at
   different fragmented networks is not possible, opportunistic network
   such as delay tolerant networks (DTN) can be used to deliver
   messages. In DTN, a message is delivered to a destination node via
   opportunistic contacts between intermediate nodes in a store-carry-
   forward way.

   Since forwarding of Interest and Data should be carried out
   opportunistically using DTN in fragmented networks, forwarding
   schemes of Interest and Data in connected ICN networks should be
   extended to accommodate the disruptive characteristics of DTN. In
   this draft, we consider probabilistic routing protocol using history
   of encounters and transitivity (PRoPHET)[RFC6693] for extension.
   Then, we propose forwarding schemes for Interest and Data of ICN.

2. Conventions and Terminology

2.1. Conventions

   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].

2.2. Terminology

   TBD

3. Forwarding of Interest and Data for ICN

3.1. Delivery predictability of PRoPHET

   In PRoPHET, delivery predictability is defined between any two nodes.
   The delivery predictability between node A and node B i.e., P(A,B),
   increases whenever node A and node B contact as follows:

      P(A,B)=P(A,B)_old+(1-delta-P(A,B)_old)*P_encounter,(1)

   where delta sets an upper bound for P(A,B) and P_encounter is a
   scaling factor to control the rate of increase [RFC6693].

   Also, it decreases as time elapses since the last contact as
   follows:

Chung, et al.           Expires May 15, 2018                  [Page 3]
Internet-Draft      Extension of PRoPHET for ICN         November 2017

      P(A,B)=P(A,B)_old*gamma^K,(2)

   where 0<=gamma<=1 is an aging constant and K is the elapsed time.

   Finally, the delivery predictability has a transitive property,
   i.e., if node A and B encounter frequently, and node B and node C
   encounter frequently, then node A probably encounters node C.

3.2. Extension for Interest forwarding

   Conventional DTN routing protocol is based on push model and the
   destination of a message is a specific node. However, pull model is
   used in ICN and Interest is forwarded based on content name, rather
   than node ID. In order to forward Interest to appropriate nodes
   which have the requested Data in its CS, the delivery predictability
   of a node A for the Interest i corresponding to the requested Data
   is defined as P(A,N(d_i)), similar to Eq. (1) as follows:

      P(A,N(d_i))

      =P(A,N(d_i))_old+(1-delta-P(A,N(d_i)_old)*P_encounter,(3)

   where N(d_i) represents a set of nodes with the Data corresponding
   to Interest i in its CS.

   In Eq. (3), P(A,N(d_i)) increases whenever node A contacts another
   node which has d_i in its CS, where the number of nodes having Data
   d_i is generally larger than 1, since d_i can be cached in multiple
   nodes by adopting the ICN approach. Similar to Eq. (2), the delivery
   predictability of a node to a node set N(d_i) decreases as time
   elapses since the last contact. We note that if node A has Data d_i,
   P(A,N(d_i))=1.

   When node A and node B contact, Interest i stored in node A is
   forwarded to node B, if P(A,N(d_i)) < P(B,N(d_i)), since node B is a
   more probable node to deliver Interest i to a node having d_i than
   node A. In this case, the information of requester nodes for
   Interest i is also delivered to node B. The information of requester
   nodes for the same Interest i stored in both node A and node B is
   shared, irrespective of the comparison of delivery predictabilities.
   For example, if node A has Interest i with requester R1 and if node
   B has Interest i with requester R2, both node A and node B have
   information of requesters R1 and R2 for Interest i after contact.

Chung, et al.           Expires May 15, 2018                  [Page 4]
Internet-Draft      Extension of PRoPHET for ICN         November 2017

3.3. Extension for Data forwarding

   For the delivery of Data in DTN, there is no known reverse path like
   the one using PIT in ICN. Therefore, Data also should be delivered
   using DTN routing protocol, too. In the proposed extension, the
   information of requesters for the considered Data is used to forward
   the Data. If the number of requesters for the Data corresponding to
   Interest i is only one, the forwarding scheme of conventional
   PRoPHET can be applied directly since the destination of the Data is
   a requester node and forwarding is carried out based on node ID.
   That is, if P(B,R(d_i)) is larger than P(A,R(d_i)), the Data d_i is
   forwarded to node B, where R(d_i) is defined as the requester node
   for the Data corresponding to Interest i.

   If there are multiple requesters for the Data corresponding to
   Interest i, current forwarding scheme of PRoPHET should be extended,
   too, based on the delivery predictability relationship of two
   contact nodes for each requester. In this draft, three forwarding
   schemes for multiple requesters are presented in as examples. If
   node A and B contact and node A has Data with multiple requesters,
   the Data can be forwarded to node B if any of the following
   condition is met depending on the selected policy:

   1) if the delivery predictability between node B and a requester is
   larger than that between node A and the corresponding requester for
   any requester,

   2) if the delivery predictability between node B and a requester is
   larger than that between node A and the corresponding requester for
   all requesters,

   3) if the average of the delivery predictabilities of node B and
   requesters are larger than that between node A and the corresponding
   requesters.

   For example, if node A has Data d_i with requesters R1 and R2 and if
   node B does not have Data d_i already when node A and node B contact,
   Data d_i in node A will be forwarded to node B depending on a Data
   forwarding policy as follows:

   1) if P(A,R1(d_i))<P(B,R1(d_i)) or if P(A,R2(d_i))<P(B,R2(d_i));(4)

   2) if P(A,R1(d_i))<P(B,R1(d_i)) and if P(A,R2(d_i))<P(B,R2(d_i));(5)

   3) if Average(P(A,R1(d_i)),P(A,R2(d_i)))

      < Average(P(B,R2(d_i)),P(B,R2)(d_i)).(6)

Chung, et al.           Expires May 15, 2018                  [Page 5]
Internet-Draft      Extension of PRoPHET for ICN         November 2017

   Information on requesters is also delivered if Data is forwarded. If
   both node A and node B have the same Data, the information of
   requesters is shared between node A and node B.

3.4. Operation of the proposed extension

   In the proposed forwarding scheme, whenever node A and node B
   contact, they exchange Interest list and Data list. Interest list
   contains all the Interests that they receive from other nodes, where
   information for the requesters for Interest i is also managed in
   Interest list. Data list contains all Data that they cache in their
   CS for future delivery. Also, the information for the destination
   nodes of the Data, i.e., requesters, is also managed in Data list.
   Then, node A compares its Interest list with node B's Interest list
   and forwards Interest i to Node B if node B does not have the
   Interest and P(B,N(d_i)) is larger than P(A,N(d_i)). The information
   of requester nodes for the same Interest i stored in both node A and
   node B is shared between both node A and node B after the contact.

   For Data forwarding, node A checks Data list. If node A has only one
   requester information for the considered Data, node A forwards Data
   d_i, which corresponds to Interest i, if node B does not have the
   Data and P(B,R(d_i)) is larger than P(A,R(d_i)). If node A has
   multiple requesters information for the considered Data, Data can be
   forwarded to node B if any of forwarding condition for multiple
   requesters defined in this draft is met, as proposed in Eqns. (4)-
   (6). Information on requesters is delivered if Data is forwarded. If
   both node A and node B have the same Data, the information of
   requesters is shared between node A and node B after the contact.

4. Security Considerations

   TBD

5. IANA Considerations

   TBD

Chung, et al.           Expires May 15, 2018                  [Page 6]
Internet-Draft      Extension of PRoPHET for ICN         November 2017

6. References

6.1. Normative References

   [RFC6693] Lindgren, A., Doria, A., Davies, E., Grasic, S,
             "Probabilistic routing protocol for intermittently
             connected networks", RFC 6693, August 2012.

6.2. Informative References

   [George2014]
             Xylomenos, G. Ververidis, C. N., Siris, V. A., Fotiou, N.,
             Tsilopoulos, C., Vasilakos, X., Katsaros, K. V. Polyzos, G.
             C., "A Survey of Information-Centric Networking Research",
             IEEE Communications Surveys and Tutorials, Vol. 16, No. 2,
             2014.

   [Edo2014] Monticelli, E., Schubert, B. M., Arumaithurai, M., Fu, X.,
             Ramakrishnan, K. K., "An Information Centric Approach for
             Communications in Disaster Situations," Proceedings of
             IEEE Local & Metropolitan Area Networks, USA, May 2014.

Chung, et al.           Expires May 15, 2018                  [Page 7]
Internet-Draft      Extension of PRoPHET for ICN         November 2017

Authors' Addresses

   Yun Won Chung
   Soongsil University
   369, Sangdo-ro, Dongjak-gu,
   Seoul, 06978, Korea

   Email: ywchung@ssu.ac.kr

   Min Wook Kang
   Soongsil University
   369, Sangdo-ro, Dongjak-gu,
   Seoul, 06978, Korea

   Email: goodlookmw@gmail.com

   Younghan Kim
   Soongsil University
   369, Sangdo-ro, Dongjak-gu,
   Seoul, 06978, Korea

   Email: younghak@ssu.ac.kr

Chung, et al.           Expires May 15, 2018                  [Page 8]