Delay-Tolerant Networking Y. W. Chung Internet-Draft M. W. Kang Intended status: Informational Y. Kim Expires: September 17, 2018 Soongsil University March 18, 2018 Extension of Probabilistic Routing Protocol using History of Encounters and Transitivity for Information Centric Network draft-chung-dtn-extension-prophet-icn-01.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 September 17, 2018. Copyright Notice Copyright (c) 2018 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 17, 2018 [Page 1] Internet-Draft Extension of PRoPHET for ICN March 2018 (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 .................................... 12 5. IANA Considerations ........................................ 12 6. References ................................................. 12 6.1. Normative References .................................. 12 6.2. Informative References ................................ 12 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 17, 2018 [Page 2] Internet-Draft Extension of PRoPHET for ICN March 2018 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 17, 2018 [Page 3] Internet-Draft Extension of PRoPHET for ICN March 2018 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 as follows: P(A,C)= MAX(P(A,C)_old,P(A,B)* P(B,C)_recv * beta),(3) where 0<=beta<=1 is a scaling constant. 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,(4) where N(d_i) represents a set of nodes with the Data corresponding to Interest i in its CS. In Eq. (4), 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. Chung, et al. Expires May 17, 2018 [Page 4] Internet-Draft Extension of PRoPHET for ICN March 2018 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. 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)) | +------------------------------------------------------------------+ Fig 1. Interest Forwarding Procedure (at time t) Chung, et al. Expires May 17, 2018 [Page 6] Internet-Draft Extension of PRoPHET for ICN March 2018 Figures 1 and 2 show an example of the proposed interest forwarding procedure. Each node has an Interest list table, where the information of Interest, corresponding Data, and requester who requested the Data is stored. If a node already caches Data, the Data ID and corresponding requester information who requested the Data is stored in Data list table. Each node has a table for delivery predictability to a set of nodes with Data corresponding to Interest in each node, as shown in Tables 1 and 2. Table 1. Delivery predictability to a set of nodes with Data corresponding to Interest in node A(at time t) +==============================+ | Node | Delivery | | set | Predictability | +========+=====================+ | N(d 1) | 0.5 | +--------+---------------------+ | N(d_2) | 0.6 | +--------+---------------------+ | N(d_4) | 0.8 | +==============================+ Table 2. Delivery predictability to a set of nodes with Data corresponding to Interest in node B(at time t) +==============================+ | Node | Delivery | | set | Predictability | +========+=====================+ | N(d_1) | 0.3 | +--------+---------------------+ | N(d_2) | 0.7 | +==============================+ After the contact of node A and node B, the requester information for the same Data ID in Interest table is shared and thus requesters R1 and R3 are stored in both node A and node B. Since the delivery predictability of N(d_2) of node B is higher than that of node A, requester information R2 is forwarded to node B. Since node A contacts with node B which has Data d_3 in its cache, delivery predictability of node A is updated, as shown in Table 3. Since node B does not have delivery predictability to a node set N(d_4) before contact, the delivery predictability of node B to a node set is updated using transitivity property. Chung, et al. Expires May 17, 2018 [Page 7] Internet-Draft Extension of PRoPHET for ICN March 2018 +------------------------------------------------------------------+ | +============================+ +============================+ | | | Interest List in Node A | | Interest List in Node B | | | +============================+ +============================+ | | | ID | Data ID | Requester | | ID | Data ID | Requester | | | +======+=========+===========+ +======+=========+===========+ | | | i_1 | d_1 | R1, R3 | | i_3 | d_1 | R1, R3 | | | +------+---------+-----------+ +------+---------+-----------+ | | | i_2 | d_2 | R2 | | i_2 | d_2 | R2 | | | +------+---------+-----------+ +============================+ | | | i_4 | d_4 | R1 | +============================+ | | +============================+ | Data List in B | | | +============================+ | | | ID | Requester | | | +======+=====================+ | | | d_3 | R4 | | | +============================+ | | ___ ___ | | / \ / \ | | ( A ) ( B ) | | \___/ \___/ | | | | | +------------------------------------------------------------------+ Fig 2. Interest Forwarding Procedure (at time t+dt) Table 3. Delivery predictability to a set of nodes with Data corresponding to Interest in node A(at time t+dt) +==============================+ | Node | Delivery | | set | Predictability | +========+=====================+ | N(d_1) | 0.5 | +--------+---------------------+ | N(d_2) | 0.6 | +--------+---------------------+ | N(d_4) | 0.8 | +--------+---------------------| | N(d_3) | 0.5 | +==============================+ Chung, et al. Expires May 17, 2018 [Page 8] Internet-Draft Extension of PRoPHET for ICN March 2018 Table 4. Delivery predictability to a set of nodes with Data corresponding to Interest in node B(at time t+dt) +==============================+ | Node | Delivery | | set | Predictability | +========+=====================+ | N(d_1) | 0.3 | +--------+---------------------+ | N(d_2) | 0.7 | +--------+---------------------+ | N(d_4) | 0.36 | +==============================+ 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. Figures 3 and 4 show an example of the proposed Data forwarding procedure. Each node has a Data list table, where the information of Data and requester who requested the Data is stored. +------------------------------------------------------------------+ | +============================+ +============================+ | | | Data List in Node C | | Data List in Node D | | | +============================+ +============================+ | | | ID | Requester | | ID | Requester | | | +======+=====================+ +======+=====================+ | | | d_1 | R1, R3 | | d_2 | R4 | | | +------+---------------------+ +============================+ | | | d_2 | R2 | | | +============================+ | | ___ ___ | | / \/ \ | | ( C () D ) | | \___/\___/ | | | | | +------------------------------------------------------------------+ Fig 3. Data Forwarding Procedure (at time t) Chung, et al. Expires May 17, 2018 [Page 9] Internet-Draft Extension of PRoPHET for ICN March 2018 Table 5 and Table 6 show delivery predictability to requester node for corresponding data in each node. Table 5. Delivery predictability to requester node for corresponding Data in node C (at time t) +==============================+ | Node | Delivery | | ID | Predictability | +========+=====================+ | R1 | 0.9 | +--------+---------------------+ | R2 | 0.6 | +--------+---------------------+ | R3 | 0.2 | +--------+---------------------+ | R4 | 0.7 | +==============================+ Table 6. Delivery predictability to requester node for corresponding Data in node D (at time t) +==============================+ | Node | Delivery | | ID | Predictability | +========+=====================+ | R1 | 0.7 | +--------+---------------------+ | R2 | 0.7 | +--------+---------------------+ | R3 | 0.6 | +--------+---------------------+ | R4 | 0.9 | +==============================+ As shown in Figure 4, requester information is shared between two nodes. Thus requester information for Data d_2 is shared as R2 and R4 and the requester information for Data d_1 of node A is transferred to node B. Chung, et al. Expires May 17, 2018 [Page 10] Internet-Draft Extension of PRoPHET for ICN March 2018 +------------------------------------------------------------------+ | +============================+ +============================+ | | | Data List in Node C | | Data List in Node D | | | +============================+ +============================+ | | | ID | Requester | | ID | Requester | | | +======+=====================+ +======+=====================+ | | | d_1 | R1, R3 | | d_2 | R4, R2 | | | +------+---------------------+ +------+---------------------+ | | | d_2 | R2, R4 | | d_1 | R1, R3 | | | +============================+ +============================+ | | ___ ___ | | / \ / \ | | ( C ) ( D ) | | \___/ \___/ | | | | | +------------------------------------------------------------------+ Fig 4. Data Forwarding Procedure (at time t+dt) Table 7 and Table 8 show delivery predictability to requester node for corresponding data in node A and node B, respectively after the contact, where the delivery predictability is updated. Table 7. Delivery Predictability to requester node for corresponding data in node C (at time t+dt) +==============================+ | Node | Delivery | | ID | Predictability | +========+=====================+ | R1 | 0.9 | +--------+---------------------+ | R2 | 0.6 | +--------+---------------------+ | R3 | 0.27 | +--------+---------------------+ | R4 | 0.7 | +--------+---------------------+ | D | 0.5 | +==============================+ Chung, et al. Expires May 17, 2018 [Page 11] Internet-Draft Extension of PRoPHET for ICN March 2018 Table 8. Delivery Predictability to requester node for corresponding data in node D (at time t+dt) +==============================+ | Node | Delivery | | ID | Predictability | +========+=====================+ | R1 | 0.7 | +--------+---------------------+ | R2 | 0.7 | +--------+---------------------+ | R3 | 0.6 | +--------+---------------------+ | R4 | 0.9 | +--------+---------------------+ | C | 0.5 | +==============================+ 4. Security Considerations TBD 5. IANA Considerations TBD 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 [Geroge2014] 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. Chung, et al. Expires May 17, 2018 [Page 12] Internet-Draft Extension of PRoPHET for ICN March 2018 [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 17, 2018 [Page 13] Internet-Draft Extension of PRoPHET for ICN March 2018 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 17, 2018 [Page 14]