idnits 2.17.1 draft-chung-dtn-extension-prophet-icn-04.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (July 08, 2019) is 1725 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: 'RFC2119' is mentioned on line 109, but not defined Summary: 0 errors (**), 0 flaws (~~), 3 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Delay-Tolerant Networking Y. W. Chung 2 Internet-Draft M. W. Kang 3 Intended status: Informational D. Y. Seo 4 Expires: January 08, 2020 Y. Kim 5 Soongsil University 6 July 08, 2019 8 Extension of Probabilistic Routing Protocol using History of 9 Encounters and Transitivity for Information Centric Network 10 draft-chung-dtn-extension-prophet-icn-04.txt 12 Abstract 14 This document proposes extension of probabilistic routing protocol 15 using history of encounters and transitivity (PRoPHET) for 16 information centric network. 18 Status of This memo 20 This Internet-Draft is submitted in full conformance with the 21 provisions of BCP 78 and BCP 79. 23 Internet-Drafts are working documents of the Internet Engineering 24 Task Force (IETF). Note that other groups may also distribute 25 working documents as Internet-Drafts. The list of current Internet- 26 Drafts is at http://datatracker.ietf.org/drafts/current/. 28 Internet-Drafts are draft documents valid for a maximum of six 29 months and may be updated, replaced, or obsoleted by other documents 30 at any time. It is inappropriate to use Internet-Drafts as 31 reference material or to cite them other than as "work in progress." 33 This Internet-Draft will expire on January 08, 2020. 35 Copyright Notice 37 Copyright (c) 2019 IETF Trust and the persons identified as the 38 document authors. All rights reserved. 40 This document is subject to BCP 78 and the IETF Trust's Legal 41 Provisions Relating to IETF Documents 42 (http://trustee.ietf.org/license-info) in effect on the date of 43 publication of this document. Please review these documents 44 carefully, as they describe your rights and restrictions with 45 respect to this document. Code Components extracted from this 46 document must include Simplified BSD License text as described in 47 Section 4.e of the Trust Legal Provisions and are provided without 48 warranty as described in the Simplified BSD License. 50 Table of Contents 52 1. Introduction ................................................ 2 53 2. Conventions and Terminology ................................. 3 54 2.1. Conventions ............................................ 3 55 2.2. Terminology ............................................ 3 56 3. Forwarding of Interest and Data for ICN ..................... 3 57 3.1. Delivery predictability of PRoPHET ..................... 3 58 3.2. Extension for Interest forwarding ...................... 4 59 3.3. Extension for Data forwarding .......................... 5 60 3.4. Extension for caching .................................. 6 61 3.5. Operation of the proposed extension .................... 7 62 3.6. Extension for overload control ........................ 13 63 3.7. Overload control based on context information ......... 15 64 4. Security Considerations .................................... 15 65 5. IANA Considerations ........................................ 15 66 6. References ................................................. 16 67 6.1. Normative References .................................. 16 68 6.2. Informative References ................................ 16 70 1. Introduction 72 In Information centric network (ICN), a node requests Data by 73 sending Interest packet and this Interest packet is forwarded 74 through ICN routers. A router with the requested Data replies to the 75 Interest to the requester and the Interest is delivered through a 76 reverse path of the forwarded Interest. ICN router manages content 77 store (CS), pending interest table (PIT), and forwarding information 78 base (FIB) [George2014]. In CS, cached data is stored for future use. 79 In PIT, the information of Interest, the incoming and outgoing faces 80 of the Interest are stored, and this information is used to deliver 81 Data to the requester using the reverse path of forwarded Interest. 82 FIB is used to forward Interest to appropriate faces. 84 ICN is considered important for communication of urgent messages in 85 disaster situations [Edo2014]. In disaster situations, communication 86 infrastructure is destroyed and networks are fragmented. In 87 fragmented networks where connectivity between the nodes at 88 different fragmented networks is not possible, opportunistic network 89 such as delay tolerant networks (DTN) can be used to deliver 90 messages. In DTN, a message is delivered to a destination node via 91 opportunistic contacts between intermediate nodes in a store-carry- 92 forward way. 94 Since forwarding of Interest and Data should be carried out 95 opportunistically using DTN in fragmented networks, forwarding 96 schemes of Interest and Data in connected ICN networks should be 97 extended to accommodate the disruptive characteristics of DTN. In 98 this draft, we consider probabilistic routing protocol using history 99 of encounters and transitivity (PRoPHET)[RFC6693] for extension. 100 Then, we propose forwarding schemes for Interest and Data of ICN. 102 2. Conventions and Terminology 104 2.1. Conventions 106 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 107 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 108 document are to be interpreted as described in RFC 2119 [RFC2119]. 110 2.2. Terminology 112 TBD 114 3. Forwarding of Interest and Data for ICN 116 3.1. Delivery predictability of PRoPHET 118 In PRoPHET, delivery predictability is defined between any two nodes. 119 The delivery predictability between node A and node B i.e., P(A,B), 120 increases whenever node A and node B contact as follows: 122 P(A,B)=P(A,B)_old+(1-delta-P(A,B)_old)*P_encounter,(1) 124 where delta sets an upper bound for P(A,B) and P_encounter is a 125 scaling factor to control the rate of increase [RFC6693]. 127 Also, it decreases as time elapses since the last contact as 128 follows: 130 P(A,B)=P(A,B)_old*gamma^K,(2) 132 where 0<=gamma<=1 is an aging constant and K is the elapsed time. 134 Finally, the delivery predictability has a transitive property i.e., 135 if node A and B encounter frequently, and node B and node C 136 encounter frequently, then node A probably encounters node C as 137 follows: 139 P(A,C)= MAX(P(A,C)_old,P(A,B)*P(B,C)*beta),(3) 141 3.2. Extension for Interest forwarding 143 Conventional DTN routing protocol is based on push model and the 144 destination of a message is a specific node. However, pull model is 145 used in ICN and Interest is forwarded based on content name, rather 146 than node ID. In order to forward Interest to appropriate nodes 147 which have the requested Data in its CS, the delivery predictability 148 of a node A for the Interest i corresponding to the requested Data 149 is defined as P(A,N(d_i)), similar to Eq. (1) as follows: 151 P(A,N(d_i)) 153 =P(A,N(d_i))_old+(1-delta-P(A,N(d_i)_old)*P_encounter,(4) 155 where N(d_i) represents a set of nodes with the Data corresponding 156 to Interest i in its CS. 158 In Eq. (4), P(A,N(d_i)) increases whenever node A contacts another 159 node which has d_i in its CS, where the number of nodes having Data 160 d_i is generally larger than 1, since d_i can be cached in multiple 161 nodes by adopting the ICN approach. Similar to Eq. (2), the delivery 162 predictability of a node to a node set N(d_i) decreases as time 163 elapses since the last contact. We note that if node A has Data d_i, 164 P(A,N(d_i))=1. 166 When node A and node B contact, Interest i stored in node A is 167 forwarded to node B, if P(A,N(d_i)) < P(B,N(d_i)), since node B is a 168 more probable node to deliver Interest i to a node having d_i than 169 node A. In this case, the information of requester nodes for 170 Interest i is also delivered to node B. The information of requester 171 nodes for the same Interest i stored in both node A and node B is 172 shared, irrespective of the comparison of delivery predictabilities. 173 For example, if node A has Interest i with requester R1 and if node 174 B has Interest i with requester R2, both node A and node B have 175 information of requesters R1 and R2 for Interest i after contact. 177 3.3. Extension for Data forwarding 179 For the delivery of Data in DTN, there is no known reverse path like 180 the one using PIT in ICN. Therefore, Data also should be delivered 181 using DTN routing protocol, too. In the proposed extension, the 182 information of requesters for the considered Data is used to forward 183 the Data. If the number of requesters for the Data corresponding to 184 Interest i is only one, the forwarding scheme of conventional 185 PRoPHET can be applied directly since the destination of the Data is 186 a requester node and forwarding is carried out based on node ID. 187 That is, if P(B,R(d_i)) is larger than P(A,R(d_i)), the Data d_i is 188 forwarded to node B, where R(d_i) is defined as the requester node 189 for the Data corresponding to Interest i. 191 If there are multiple requesters for the Data corresponding to 192 Interest i, current forwarding scheme of PRoPHET should be extended, 193 too, based on the delivery predictability relationship of two 194 contact nodes for each requester. In this draft, three forwarding 195 schemes for multiple requesters are presented in as examples. If 196 node A and B contact and node A has Data with multiple requesters, 197 the Data can be forwarded to node B if any of the following 198 condition is met depending on the selected policy: 200 1) if the delivery predictability between node B and a requester is 201 larger than that between node A and the corresponding requester for 202 any requester, 204 2) if the delivery predictability between node B and a requester is 205 larger than that between node A and the corresponding requester for 206 all requesters, 208 3) if the average of the delivery predictabilities of node B and 209 requesters are larger than that between node A and the corresponding 210 requesters. 212 For example, if node A has Data d_i with requesters R1 and R2 and if 213 node B does not have Data d_i already when node A and node B contact, 214 Data d_i in node A will be forwarded to node B depending on a Data 215 forwarding policy as follows: 217 1) if P(A,R1(d_i))
|
336 +------------------------------------------------------------------+
337 Fig 1. Interest Forwarding Procedure (at time t)
339 Each node has a table for delivery predictability to a set of nodes
340 with Data corresponding to Interest in each node, as shown in Tables
341 1 and 2.
343 Table 1. Delivery predictability to a set of nodes with Data
344 corresponding to Interest in node A(at time t)
345 +==============================+
346 | Node | Delivery |
347 | set | Predictability |
348 +========+=====================+
349 | N(d 1) | 0.5 |
350 +--------+---------------------+
351 | N(d_2) | 0.6 |
352 +--------+---------------------+
353 | N(d_4) | 0.8 |
354 +==============================+
356 Table 2. Delivery predictability to a set of nodes with Data
357 corresponding to Interest in node B(at time t)
358 +==============================+
359 | Node | Delivery |
360 | set | Predictability |
361 +========+=====================+
362 | N(d_1) | 0.3 |
363 +--------+---------------------+
364 | N(d_2) | 0.7 |
365 +==============================+
367 After the contact of node A and node B, the requester information
368 for the same Data ID in Interest table is shared and thus requesters
369 R1 and R3 are stored in both node A and node B. Since the delivery
370 predictability of N(d_2) of node B is higher than that of node A,
371 requester information R2 is forwarded to node B.
373 Since node A contacts with node B which has Data d_3 in its cache,
374 delivery predictability of node A is updated, as shown in Table 3.
375 Since node B does not have delivery predictability to a node set
376 N(d_4) before contact, the delivery predictability of node B to a
377 node set is updated using transitivity property.
379 +------------------------------------------------------------------+
380 | +============================+ +============================+ |
381 | | Interest List in Node A | | Interest List in Node B | |
382 | +============================+ +============================+ |
383 | | ID | Data ID | Requester | | ID | Data ID | Requester | |
384 | +======+=========+===========+ +======+=========+===========+ |
385 | | i_1 | d_1 | R1, R3 | | i_3 | d_1 | R1, R3 | |
386 | +------+---------+-----------+ +------+---------+-----------+ |
387 | | i_2 | d_2 | R2 | | i_2 | d_2 | R2 | |
388 | +------+---------+-----------+ +============================+ |
389 | | i_4 | d_4 | R1 | +============================+ |
390 | +============================+ | Data List in B | |
391 | +============================+ |
392 | | ID | Requester | |
393 | +======+=====================+ |
394 | | d_3 | R4 | |
395 | +============================+ |
396 | ___ ___ |
397 | / \ / \ |
398 | ( A ) ( B ) |
399 | \___/ \___/ |
400 | |
401 |