idnits 2.17.1 draft-chung-dtn-extension-prophet-icn-03.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: ---------------------------------------------------------------------------- == The page length should not exceed 58 lines per page, but there was 1 longer page, the longest (page 16) being 60 lines 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 == Line 31 has weird spacing: '...ference mate...' == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (October 22, 2018) is 2007 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: 'George2014' is mentioned on line 78, but not defined == Missing Reference: 'RFC2119' is mentioned on line 109, but not defined == Unused Reference: 'Geroge2014' is defined on line 651, but no explicit reference was found in the text Summary: 0 errors (**), 0 flaws (~~), 7 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: April 22, 2019 Y. Kim 5 Soongsil University 6 October 22, 2018 8 Extension of Probabilistic Routing Protocol using History of 9 Encounters and Transitivity for Information Centric Network 10 draft-chung-dtn-extension-prophet-icn-03.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 32 progress." 34 This Internet-Draft will expire on April 22, 2019. 36 Copyright Notice 38 Copyright (c) 2018 IETF Trust and the persons identified as the 39 document authors. All rights reserved. 41 This document is subject to BCP 78 and the IETF Trust's Legal 42 Provisions Relating to IETF Documents 43 (http://trustee.ietf.org/license-info) in effect on the date of 44 publication of this document. Please review these documents 45 carefully, as they describe your rights and restrictions with 46 respect to this document. Code Components extracted from this 47 document must include Simplified BSD License text as described in 48 Section 4.e of the Trust Legal Provisions and are provided without 49 warranty as described in the Simplified BSD License. 51 Table of Contents 53 1. Introduction ................................................ 2 54 2. Conventions and Terminology ................................. 3 55 2.1. Conventions ............................................ 3 56 2.2. Terminology ............................................ 3 57 3. Forwarding of Interest and Data for ICN ..................... 3 58 3.1. Delivery predictability of PRoPHET ..................... 3 59 3.2. Extension for Interest forwarding ...................... 4 60 3.3. Extension for Data forwarding .......................... 5 61 3.4. Extension for caching .................................. 6 62 3.5. Operation of the proposed extension .................... 7 63 3.6. Extension for overload control ........................ 13 64 4. Security Considerations .................................... 15 65 5. IANA Considerations ........................................ 15 66 6. References ................................................. 15 67 6.1. Normative References .................................. 15 68 6.2. Informative References ................................ 15 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 | | 402 +------------------------------------------------------------------+ 403 Fig 2. Interest Forwarding Procedure (at time t+dt) 405 Table 3. Delivery predictability to a set of nodes with Data 406 corresponding to Interest in node A(at time t+dt) 407 +==============================+ 408 | Node | Delivery | 409 | set | Predictability | 410 +========+=====================+ 411 | N(d_1) | 0.5 | 412 +--------+---------------------+ 413 | N(d_2) | 0.6 | 414 +--------+---------------------+ 415 | N(d_4) | 0.8 | 416 +--------+---------------------| 417 | N(d_3) | 0.5 | 418 +==============================+ 420 Table 4. Delivery predictability to a set of nodes with Data 421 corresponding to Interest in node B(at time t+dt) 422 +==============================+ 423 | Node | Delivery | 424 | set | Predictability | 425 +========+=====================+ 426 | N(d_1) | 0.3 | 427 +--------+---------------------+ 428 | N(d_2) | 0.7 | 429 +--------+---------------------+ 430 | N(d_4) | 0.36 | 431 +==============================+ 433 For Data forwarding, node A checks Data list. If node A has only one 434 requester information for the considered Data, node A forwards Data 435 d_i, which corresponds to Interest i, if node B does not have the 436 Data and P(B,R(d_i)) is larger than P(A,R(d_i)). If node A has 437 multiple requesters information for the considered Data, Data can be 438 forwarded to node B if any of forwarding condition for multiple 439 requesters defined in this draft is met, as proposed in Eqns. (4)- 440 (6). Information on requesters is delivered if Data is forwarded. If 441 both node A and node B have the same Data, the information of 442 requesters is shared between node A and node B after the contact. 444 Figures 3 and 4 show an example of the proposed Data forwarding 445 procedure. Each node has a Data list table, where the information of 446 Data and requester who requested the Data is stored. 448 +------------------------------------------------------------------+ 449 | +============================+ +============================+ | 450 | | Data List in Node C | | Data List in Node D | | 451 | +============================+ +============================+ | 452 | | ID | Requester | | ID | Requester | | 453 | +======+=====================+ +======+=====================+ | 454 | | d_1 | R1, R3 | | d_2 | R4 | | 455 | +------+---------------------+ +============================+ | 456 | | d_2 | R2 | | 457 | +============================+ | 458 | ___ ___ | 459 | / \/ \ | 460 | ( C () D ) | 461 | \___/\___/ | 462 | | 463 | | 464 +------------------------------------------------------------------+ 465 Fig 3. Data Forwarding Procedure (at time t) 467 Table 5 and Table 6 show delivery predictability to requester node 468 for corresponding data in each node. 470 Table 5. Delivery predictability to requester node for corresponding 471 Data in node C (at time t) 472 +==============================+ 473 | Node | Delivery | 474 | ID | Predictability | 475 +========+=====================+ 476 | R1 | 0.9 | 477 +--------+---------------------+ 478 | R2 | 0.6 | 479 +--------+---------------------+ 480 | R3 | 0.2 | 481 +--------+---------------------+ 482 | R4 | 0.7 | 483 +==============================+ 485 Table 6. Delivery predictability to requester node for corresponding 486 Data in node D (at time t) 487 +==============================+ 488 | Node | Delivery | 489 | ID | Predictability | 490 +========+=====================+ 491 | R1 | 0.7 | 492 +--------+---------------------+ 493 | R2 | 0.7 | 494 +--------+---------------------+ 495 | R3 | 0.6 | 496 +--------+---------------------+ 497 | R4 | 0.9 | 498 +==============================+ 500 As shown in Figure 4, requester information is shared between two 501 nodes. Thus requester information for Data d_2 is shared as R2 and 502 R4 and the requester information for Data d_1 of node A is 503 transferred to node B. 505 +------------------------------------------------------------------+ 506 | +============================+ +============================+ | 507 | | Data List in Node C | | Data List in Node D | | 508 | +============================+ +============================+ | 509 | | ID | Requester | | ID | Requester | | 510 | +======+=====================+ +======+=====================+ | 511 | | d_1 | R1, R3 | | d_2 | R4, R2 | | 512 | +------+---------------------+ +------+---------------------+ | 513 | | d_2 | R2, R4 | | d_1 | R1, R3 | | 514 | +============================+ +============================+ | 515 | ___ ___ | 516 | / \ / \ | 517 | ( C ) ( D ) | 518 | \___/ \___/ | 519 | | 520 | | 521 +------------------------------------------------------------------+ 522 Fig 4. Data Forwarding Procedure (at time t+dt) 524 Table 7 and Table 8 show delivery predictability to requester node 525 for corresponding data in node A and node B, respectively after the 526 contact, where the delivery predictability is updated. 528 Table 7. Delivery Predictability to requester node for corresponding 529 data in node C (at time t+dt) 530 +==============================+ 531 | Node | Delivery | 532 | ID | Predictability | 533 +========+=====================+ 534 | R1 | 0.9 | 535 +--------+---------------------+ 536 | R2 | 0.6 | 537 +--------+---------------------+ 538 | R3 | 0.27 | 539 +--------+---------------------+ 540 | R4 | 0.7 | 541 +--------+---------------------+ 542 | D | 0.5 | 543 +==============================+ 545 Table 8. Delivery Predictability to requester node for corresponding 546 data in node D (at time t+dt) 547 +==============================+ 548 | Node | Delivery | 549 | ID | Predictability | 550 +========+=====================+ 551 | R1 | 0.7 | 552 +--------+---------------------+ 553 | R2 | 0.7 | 554 +--------+---------------------+ 555 | R3 | 0.6 | 556 +--------+---------------------+ 557 | R4 | 0.9 | 558 +--------+---------------------+ 559 | C | 0.5 | 560 +==============================+ 562 3.6. Extension for overload control 564 In the proposed forwarding scheme, a requester node which issues an 565 Interest message does not know whether the Interest message has been 566 delivered to a node which has the requested Data until it receives a 567 requested Data. Therefore, unnecessary Interest messages may be 568 forwarded further even though it has been successfully delivered to 569 a node which has the requested Data already. Also, unnecessary Data 570 may be forwarded further even though it has been delivered to a 571 requester node already. Therefore, it is necessary to limit this 572 unnecessary overload of Interest and Data efficiently. In this draft, 573 we propose an extension for overload control, which is basically 574 based on the schemes proposed in the work in [Hass2006]. 576 In the proposed overload control, we manage delivered Interest and 577 Data list in the pending anti-Interest and Data (PAID) table. 578 If node A forwards an Interest message i_1 to a node B which has the 579 requested Data d_1, we can apply one of the following three schemes 580 to limit the forwarding of the satisfied Interest message 581 efficiently as follows: 583 1) Scheme A: the node A removes the delivered Interest i_1 from its 584 Interest list and sets anti-Interest flag for the Interest message 585 i_1 in PAID table. Then, node A does not accept the i_1 again. 587 2) Scheme B: the node A removes the delivered Interest i_1 from its 588 Interest list and sets anti-Interest flag for the Interest message 589 i_1 in PAID table, and does not accept the i_1 again. Further, if 590 node A contacts another node C which has the same Interest i_1, it 591 shares anti-Interest flag with node C. Then, node C removes the 592 Interest i_1 from the Interest list and sets anti-Interest flag for 593 the Interest message i_1 in PAID table. The node C does not accept 594 the i_1 again. 596 3) Scheme C: the node A removes the delivered Interest i_1 from its 597 Interest list and sets anti-Interest flag for the Interest message 598 i_1 in PAID table, and does not accept the i_1 again. Further, if 599 node A contacts any node, it shares anti-Interest flag with the 600 contact node. If the contact node has the Interest i_1 already, 601 it removes the Interest i_1 from the Interest list and sets anti- 602 Interest flag for the Interest message i_1 in PAID table, and does 603 not accept the Interest i_a again. Otherwise, it just sets anti- 604 Interest flag for the Interest message i_1 in PAID table and does 605 not accept the i_1 again. 607 Similar approaches can be applied to delivered Data, too. If Data 608 d_2 is delivered to a node E from a node D, which requested the Data 609 d_2 before, we can apply one of the following three schemes to limit 610 the forwarding of the delivered Data efficiently as follows: 612 1) Scheme D: the node D removes the delivered Data d_2 from its Data 613 list and sets anti-Data flag for the Data d_2 in PAID table. Then, 614 node D does not accept the d_2 again. 616 2) Scheme E: the node D removes the delivered Data d_2 from its Data 617 list and sets anti-Data flag for the Data d_2 in PAID table, and 618 does not accept the d_2 again. Further, if node D contacts another 619 node F which has the same Data d_2, it shares anti-Data flag with 620 node F. Then, node F removes the Data d_2 from the Data list and 621 sets anti-Data flag for the Data d_2 in PAID table. The node F does 622 not accept the d_2 again. 624 3) Scheme F: the node D removes the delivered Data d_2 from its Data 625 list and sets anti-Data flag for the Data d_2 in PAID table, and does 626 not accept the d_2 again. Further, if node D contacts any node, it 627 shares anti-Data flag with the contact node. If the contact node has 628 the Data d_2 already, it removes the Data d_2 from Data list and sets 629 anti-Data flag for the Data d_2 in PAID table, and does not accept 630 the Data d_2 again. Otherwise, it just sets anti-Data flag for the 631 Data d_2 in PAID table and does not accept the d_2 again. 633 4. Security Considerations 635 TBD 637 5. IANA Considerations 639 TBD 641 6. References 643 6.1. Normative References 645 [RFC6693] Lindgren, A., Doria, A., Davies, E., Grasic, S, 646 "Probabilistic routing protocol for intermittently 647 connected networks", RFC 6693, August 2012. 649 6.2. Informative References 651 [Geroge2014] 652 Xylomenos, G. Ververidis, C. N., Siris, V. A., Fotiou, N., 653 Tsilopoulos, C., Vasilakos, X., Katsaros, K. V. Polyzos, G. 654 C., "A Survey of Information-Centric Networking Research", 655 IEEE Communications Surveys and Tutorials, Vol. 16, No. 2, 656 2014. 658 [Edo2014] Monticelli, E., Schubert, B. M., Arumaithurai, M., Fu, X., 659 Ramakrishnan, K. K., "An Information Centric Approach for 660 Communications in Disaster Situations," Proceedings of 661 IEEE Local & Metropolitan Area Networks, USA, May 2014. 663 [Hass2006] 664 Hass, Z. J., Small, T., "A new networking model for 665 biological applications of ad hoc sensor networks", 666 IEEE/ACM Transactions on Networking, Vol. 14, No. 1, 667 pp. 27-40, Feb.,2006. 669 Authors' Addresses 671 Yun Won Chung 672 Soongsil University 673 369, Sangdo-ro, Dongjak-gu, 674 Seoul, 06978, Korea 676 Email: ywchung@ssu.ac.kr 678 Min Wook Kang 679 Soongsil University 680 369, Sangdo-ro, Dongjak-gu, 681 Seoul, 06978, Korea 683 Email: goodlookmw@gmail.com 685 Dong Yeong Seo 686 Soongsil University 687 369, Sangdo-ro, Dongjak-gu, 688 Seoul, 06978, Korea 690 Email: seodong2da@nate.com 692 Younghan Kim 693 Soongsil University 694 369, Sangdo-ro, Dongjak-gu, 695 Seoul, 06978, Korea 697 Email: younghak@ssu.ac.kr