idnits 2.17.1 draft-ietf-p2psip-service-discovery-15.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 == Line 324 has weird spacing: '...ExtType type...' -- The document date (August 13, 2014) is 3537 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Looks like a reference, but probably isn't: '0' on line 291 -- Looks like a reference, but probably isn't: '7' on line 291 -- Looks like a reference, but probably isn't: '8' on line 291 -- Looks like a reference, but probably isn't: '15' on line 291 ** Downref: Normative reference to an Informational RFC: RFC 3174 Summary: 1 error (**), 0 flaws (~~), 2 warnings (==), 6 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 P2PSIP Working Group J. Maenpaa 3 Internet-Draft G. Camarillo 4 Intended status: Standards Track Ericsson 5 Expires: February 14, 2015 August 13, 2014 7 Service Discovery Usage for REsource LOcation And Discovery (RELOAD) 8 draft-ietf-p2psip-service-discovery-15.txt 10 Abstract 12 REsource LOcation and Discovery (RELOAD) does not define a generic 13 service discovery mechanism as a part of the base protocol. This 14 document defines how the Recursive Distributed Rendezvous (ReDiR) 15 service discovery mechanism used in OpenDHT can be applied to RELOAD 16 overlays to provide a generic service discovery mechanism. 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 months 29 and may be updated, replaced, or obsoleted by other documents at any 30 time. It is inappropriate to use Internet-Drafts as reference 31 material or to cite them other than as "work in progress." 33 This Internet-Draft will expire on February 14, 2015. 35 Copyright Notice 37 Copyright (c) 2014 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 respect 45 to this document. Code Components extracted from this document must 46 include Simplified BSD License text as described in Section 4.e of 47 the Trust Legal Provisions and are provided without warranty as 48 described in the Simplified BSD License. 50 Table of Contents 52 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 53 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 54 3. Introduction to ReDiR . . . . . . . . . . . . . . . . . . . . 5 55 4. Using ReDiR in a RELOAD Overlay Instance . . . . . . . . . . 8 56 4.1. Data Structure . . . . . . . . . . . . . . . . . . . . . 8 57 4.2. Selecting the Starting Level . . . . . . . . . . . . . . 10 58 4.3. Service Provider Registration . . . . . . . . . . . . . . 10 59 4.4. Refreshing Registrations . . . . . . . . . . . . . . . . 11 60 4.5. Service Lookups . . . . . . . . . . . . . . . . . . . . . 11 61 4.6. Removing Registrations . . . . . . . . . . . . . . . . . 13 62 5. Access Control Rules . . . . . . . . . . . . . . . . . . . . 14 63 6. REDIR Kind Definition . . . . . . . . . . . . . . . . . . . . 14 64 7. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 15 65 7.1. Service Registration . . . . . . . . . . . . . . . . . . 15 66 7.2. Service Lookup . . . . . . . . . . . . . . . . . . . . . 17 67 8. Overlay Configuration Document Extension . . . . . . . . . . 17 68 9. Security Considerations . . . . . . . . . . . . . . . . . . . 18 69 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 18 70 10.1. Access Control Policies . . . . . . . . . . . . . . . . 18 71 10.2. A New IETF XML Registry . . . . . . . . . . . . . . . . 18 72 10.3. Data Kind-ID . . . . . . . . . . . . . . . . . . . . . . 19 73 10.4. RELOAD Services Registry . . . . . . . . . . . . . . . . 19 74 11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 20 75 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 20 76 12.1. Normative References . . . . . . . . . . . . . . . . . . 20 77 12.2. Informative References . . . . . . . . . . . . . . . . . 20 78 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 20 80 1. Introduction 82 REsource LOcation And Discovery (RELOAD) [RFC6940] is a peer-to-peer 83 signaling protocol that can be used to maintain an overlay network, 84 and to store data in and retrieve data from the overlay. Although 85 RELOAD defines a Traversal Using Relays around Network Address 86 Translation (TURN) specific service discovery mechanism, it does not 87 define a generic service discovery mechanism as a part of the base 88 protocol. This document defines how the Recursive Distributed 89 Rendezvous (ReDiR) service discovery mechanism [Redir] used in 90 OpenDHT can be applied to RELOAD overlays. 92 In a Peer-to-Peer (P2P) overlay network such as a RELOAD Overlay 93 Instance, the peers forming the overlay share their resources in 94 order to provide the service the system has been designed to provide. 95 The peers in the overlay both provide services to other peers and 96 request services from other peers. Examples of possible services 97 peers in a RELOAD Overlay Instance can offer to each other include a 98 TURN relay service, a voice mail service, a gateway location service, 99 and a transcoding service. Typically, only a small subset of the 100 peers participating in the system are providers of a given service. 101 A peer that wishes to use a particular service faces the problem of 102 finding peers that are providing that service from the Overlay 103 Instance. 105 A naive way to perform service discovery is to store the Node-IDs of 106 all nodes providing a particular service under a well-known key k. 107 The limitation of this approach is that it scales linearly with the 108 number of nodes that provide the service. The problem is two-fold: 109 the node n that is responsible for service s identified by key k may 110 end up storing a large number of Node-IDs and most importantly, may 111 also become overloaded since all service lookup requests for service 112 s will need to be answered by node n. An efficient service discovery 113 mechanism does not overload the nodes storing pointers to service 114 providers. In addition, the mechanism must ensure that the load of 115 providing a given service is distributed evenly among the nodes 116 providing the service. 118 It should be noted that a simple service discovery mechanism such as 119 the one mentioned in the previous paragraph might be an appropriate 120 solution in a very small overlay network consisting of perhaps tens 121 of nodes. The ReDiR-based service discovery mechanism described in 122 this document is suitable for use even in overlay networks where the 123 number of end-users that may make service discovery requests can be 124 very high (e.g., tens of thousands of nodes or even higher), and 125 where a large fraction of the peers (e.g., on the order of one out of 126 ten or more) can offer the service. 128 ReDiR implements service discovery by building a tree structure of 129 the service providers that provide a particular service. The tree 130 structure is stored into the RELOAD Overlay Instance using RELOAD 131 Store and Fetch requests. Each service provided in the Overlay 132 Instance has its own tree. The nodes in a ReDiR tree contain 133 pointers to service providers. During service discovery, a peer 134 wishing to use a given service fetches ReDiR tree nodes one-by-one 135 from the RELOAD Overlay Instance until it finds a service provider 136 responsible for its Node-ID. It has been proved that ReDiR can find 137 a service provider using only a constant number of Fetch operations 138 [Redir]. 140 2. Terminology 142 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 143 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 144 document are to be interpreted as described in RFC 2119 [RFC2119]. 146 DHT: Distributed Hash Tables (DHTs) are a class of decentralized 147 distributed systems that provide a lookup service similar to a 148 regular hash table. Given a key, any peer participating in the 149 system can retrieve the value associated with that key. The 150 responsibility for maintaining the mapping from keys to values is 151 distributed among the peers. 153 H(x): Refers to a hash function (e.g., SHA-1 [RFC3174]) calculated 154 over the value x. 156 H(x,y,z): Refers to a hash function calculated over a concatenated 157 string consisting of x, y, and z, where x, y, and z can be both 158 strings and integers. The network byte order is used. 160 I(lvl,k): An interval at level lvl in the ReDiR tree that encloses 161 key k. As an example, I(5,10) refers to an interval at level 5 in 162 the ReDiR tree within whose range key 10 falls. 164 n.id: Refers to the RELOAD Node-ID of node n. 166 Namespace: An arbitrary identifier that identifies a service 167 provided in the RELOAD Overlay Instance. Examples of potential 168 namespaces include "voice-mail" and "turn-server". The namespace 169 is an UTF-8 [RFC3629] text string. 171 numBitsInNodeId: Refers to the number of bits in a RELOAD Node-ID. 172 This value is used in the equations for calculating the ranges of 173 intervals that ReDiR tree nodes are responsible for. 175 ReDiR tree: A tree structure of the nodes that provide a particular 176 service. The nodes embed the ReDiR tree into the RELOAD Overlay 177 Instance using RELOAD Store and Fetch requests. Each tree node in 178 the ReDiR tree belongs to some level in the tree. The root node 179 of the ReDiR tree is located at level 0 of the ReDiR tree. The 180 child nodes of the root node are located at level 1. The children 181 of the tree nodes at level 1 are located at level 2, and so forth. 182 The ReDiR tree has a branching factor b. At every level lvl in 183 the ReDiR tree, there is room for a maximum of b^lvl tree nodes. 184 Each tree node in the ReDiR tree is uniquely identified by a pair 185 (lvl,j), where lvl is a level in the ReDiR tree and j is the 186 position of the tree node (from the left) at that level. 188 Successor: The successor of identifier k in namespace ns is the node 189 belonging to the namespace ns whose identifier most immediately 190 follows the identifier k. 192 3. Introduction to ReDiR 194 Recursive Distributed Rendezvous (ReDiR) [Redir] does not require new 195 functionality from the RELOAD base protocol. This is possible since 196 ReDiR interacts with the RELOAD Overlay Instance by simply storing 197 and fetching data, that is, using RELOAD Store and Fetch requests. 198 ReDiR creates a tree structure of the service providers of a 199 particular service and stores it into the RELOAD Overlay Instance 200 using the Store and Fetch requests. ReDiR service lookups require a 201 logarithmic number of Fetch operations. Further, if information from 202 past service lookups is used to determine the optimal level in the 203 ReDiR tree from which to start new service lookups, an average 204 service lookup can typically finish after a constant number of Fetch 205 operations assuming that Node-IDs are distributed uniformly at 206 random. 208 In ReDiR, each service provided in the overlay is identified by an 209 identifier, called the namespace. All service providers of a given 210 service store their information under the namespace of that service. 211 Peers wishing to use a service perform lookups within the namespace 212 of the service. The result of a ReDiR lookup for an identifier k in 213 namespace ns is a RedirServiceProvider structure (see Section 4.1) of 214 a service provider that belongs to ns and whose Node-ID is the 215 closest successor of identifier k in the namespace. 217 Each tree node in the ReDiR tree contains a dictionary of 218 RedirServiceProvider entries of peers providing a particular service. 219 Each tree node in the ReDiR tree also belongs to some level in the 220 tree. The root node of the ReDiR tree is located at level 0. The 221 child nodes of the root node are located at level 1 of the ReDiR 222 tree. The children of the tree nodes at level 1 are located at level 223 2, and so forth. The ReDiR tree has a branching factor, whose value 224 is determined by a new element in the RELOAD overlay configuration 225 document, called branching-factor. At every level lvl in the ReDiR 226 tree, there is room for a maximum of branching-factor^lvl tree nodes. 227 As an example, in a tree whose branching-factor is 2, the second 228 level can contain up to 4 tree nodes (note that a given level may 229 contain less than the maximum number of tree nodes since empty tree 230 nodes are not stored). Each tree node in the ReDiR tree is uniquely 231 identified by a pair (lvl,j), where lvl is a level in the ReDiR tree 232 and j is the position of the tree node (from the left) at that level. 233 As an example, the pair (2,3) identifies the 3rd tree node from the 234 left at level 2. 236 The ReDiR tree is stored into the RELOAD Overlay Instance tree node 237 by tree node, by storing the values of tree node (level,j) under a 238 key created by taking a hash over the concatenation of the namespace, 239 level, and j, that is, as H(namespace,level,j). As an example, the 240 root of the tree for a voice mail service is stored at H("voice- 241 mail",0,0). Each node (level,j) in the ReDiR tree contains b 242 intervals of the DHT's identifier space as follows: 244 [2^numBitsInNodeID*b^(-level)*(j+(b'/b)), 245 2^numBitsInNodeID*b^(-level)*(j+((b'+1)/b))), for 0<=b'; 326 opaque namespace<0..2^16-1>; 327 uint16 level; 328 uint16 node; 329 uint16 length; 331 select (type) { 332 /* This type may be extended */ 333 } extension; 335 } RedirServiceProvider; 337 The contents of the RedirServiceProvider Resource Record are as 338 follows: 340 type 342 The type of an extension to the RedirServiceProvider Resource 343 Record. Unknown types are allowed. 345 destination_list 347 A list of IDs through which a message is to be routed to reach the 348 service provider. The destination list consists of a sequence of 349 Destination values. The contents of the Destination structure are 350 as defined in RELOAD base [RFC6940]. 352 namespace 354 An opaque UTF-8 encoded string containing the namespace. 356 level 358 The level in the ReDiR tree. 360 node 362 The position of the node storing this RedirServiceProvider record 363 at the current level in the ReDiR tree. 365 length 367 The length of the rest of the Resource Record. 369 extension 370 An extension value. The RedirServiceProvider Resource Record can 371 be extended to include for instance service or service provider 372 specific information. 374 4.2. Selecting the Starting Level 376 Before registering as a service provider or performing a service 377 lookup, a peer needs to determine the starting level Lstart for the 378 registration or lookup operation in the ReDiR tree. It is 379 RECOMMENDED that Lstart is set to 2. This recommendation is based on 380 the findings in [Redir], which indicate that this starting level 381 results in good performance. In subsequent registrations, Lstart 382 MAY, as an optimization, be set to the lowest level at which a 383 registration operation has last completed. 385 In the case of subsequent service lookups, nodes MAY, as an 386 optimization, record the levels at which the last 16 service lookups 387 completed and take Lstart to be the mode of those depths (mode, in 388 statistics, is the value that appears most often in a set of data). 390 4.3. Service Provider Registration 392 A node MUST use the following procedure to register as a service 393 provider in the RELOAD Overlay Instance: 395 1. A node n with Node-ID n.id wishing to register as a service 396 provider starts from a starting level Lstart (see Section 4.2 for 397 the details on selecting the starting level). Therefore, node n 398 sets the current level to level=Lstart. 400 2. Node n MUST send a RELOAD Fetch request to fetch the contents of 401 the tree node responsible for I(level,n.id). An interval I(l,k) 402 is the interval at level l in the ReDiR tree that includes key k. 403 The fetch MUST be a wildcard fetch. 405 3. Node n MUST send a RELOAD Store request to add its 406 RedirServiceProvider entry to the dictionary stored in the tree 407 node responsible for I(level,n.id). Note that node n always 408 stores its RedirServiceProvider entry, regardless of the contents 409 of the dictionary. 411 4. If node n's Node-ID (n.id) is the lowest or highest Node-ID 412 stored in the tree node responsible for I(Lstart,n.id), node n 413 MUST reduce the current level by one (i.e., set level=level-1) 414 and continue up the ReDiR tree towards the root level (level 0), 415 repeating the steps 2 and 3 above. Node n MUST continue in this 416 way until it reaches either the root of the tree or a level at 417 which n.id is not the lowest or highest Node-ID in the interval 418 I(level,n.id). 420 5. Node n MUST also perform a downward walk in the ReDiR tree, 421 during which it goes through the tree nodes responsible for 422 intervals I(Lstart,n.id), I(Lstart+1,n.id), I(Lstart+2,n.id), 423 etc. At each step, node n MUST fetch the responsible tree node, 424 and store its RedirServiceProvider record in that tree node if 425 n.id is the lowest or highest Node-ID in its interval. Node n 426 MUST end this downward walk as soon as it reaches a level l at 427 which it is the only service provider in its interval I(l,n.id). 429 Note that above, when we refer to 'the tree node responsible for 430 I(l,k)', we mean the entire tree node (that is, all the intervals 431 within the tree node) responsible for interval I(l,k). In contrast, 432 I(l,k) refers to a specific interval within a tree node. 434 4.4. Refreshing Registrations 436 All state in the ReDiR tree is soft. Therefore, a service provider 437 needs to periodically repeat the registration process to refresh its 438 RedirServiceProvider Resource Record. If a record expires, it MUST 439 be dropped from the dictionary by the peer storing the tree node. 440 Deciding an appropriate lifetime for the RedirServiceProvider 441 Resource Records is up to each service provider. However, a default 442 value of 10 minutes is RECOMMENDED as this is a good tradeoff between 443 keeping the amount of ReDiR traffic in the overlay at a reasonable 444 level and ensuring that stale information is removed quickly enough. 445 Every service provider MUST repeat the entire registration process 446 periodically until it leaves the RELOAD Overlay Instance. The 447 service provider SHOULD initiate each refresh process slightly 448 earlier (e.g., when 90% of the refresh interval has passed) than the 449 expiry time of the Resource Record. 451 Note that no new mechanisms are needed to keep track of the remaining 452 lifetime of RedirServiceProvider records. The 'storage_time' and 453 'lifetime' fields of RELOAD's StoredData structure can be used for 454 this purpose in the usual way. 456 4.5. Service Lookups 458 The purpose of a service lookup for identifier k in namespace ns is 459 to find the node that is a part of ns and whose identifier most 460 immediately follows (i.e., is the closest successor of) the 461 identifier k. 463 A service lookup operation resembles the service registration 464 operation described in Section 4.3. Service lookups start from a 465 given starting level level=Lstart in the ReDiR tree (see Section 4.2 466 for the details on selecting the starting level). At each step, a 467 node n wishing to discover a service provider MUST fetch the tree 468 node responsible for the interval I(level,n.id) that encloses the 469 search key n.id at the current level using a RELOAD Fetch request. 470 Having fetched the tree node, node n MUST determine the next action 471 to carry out as follows: 473 Condition 1 475 If there is no successor of node n present in the just fetched 476 ReDiR tree node (note: within the entire tree node and not only 477 within the current interval) responsible for I(level,n.id), then 478 the successor of node n must be present in a larger segment of the 479 identifier space (i.e., further up in the ReDiR tree where each 480 interval and tree node covers a larger range of the identifier 481 space). Therefore, node n MUST reduce the current level by one to 482 level=level-1 and carry out a new Fetch operation for the tree 483 node responsible for n.id at that level. The fetched tree node is 484 then analyzed and the next action determined by checking 485 Conditions 1-3. 487 Condition 2 489 If n.id is neither the lowest nor the highest Node-ID within the 490 interval (note: within the interval, not within the entire tree 491 node) I(level,n.id), n MUST next check the tree node responsible 492 for n.id at the next level down the tree. Thus, node n MUST 493 increase the level by one to level=level+1 and carry out a new 494 Fetch operation at that level. The fetched tree node is then 495 analyzed and the next action determined by checking the conditions 496 listed here starting at Condition 1. 498 Condition 3 500 If neither of the conditions above holds, meaning that there is a 501 successor s of n.id present in the just fetched ReDiR tree node 502 and n.id is the highest or lowest Node-ID in its interval, the 503 service lookup has finished successfully and s must be the closest 504 successor of n.id in the ReDiR tree. 506 Note that above, when we refer to 'the tree node responsible for 507 interval I(l,k)', we mean the entire tree node (that is, all the 508 intervals within the tree node) responsible for interval I(l,k). In 509 contrast, I(l,k) refers to a specific interval within a tree node. 511 Note also that there may be some cases in which no successor can be 512 found from the ReDiR tree. An example is a situation in which all of 513 the service providers stored in the ReDiR tree have a Node-ID smaller 514 than identifier k. In this case, the upward walk of the service 515 lookup will reach the root of the tree without encountering a 516 successor. An appropriate strategy in this case is to pick one of 517 the RedirServiceProvider entries stored in the dictionary of the root 518 node at random. 520 Since RedirServiceProvider records are expiring and registrations are 521 being refreshed periodically, there can be certain rare situations in 522 which a service lookup may fail even if there is a valid successor 523 present in the ReDiR tree. An example is a case in which a ReDiR 524 tree node is fetched just after a RedirServiceProvider entry of the 525 only successor of k present in the tree node has expired and just 526 before a Store request that has been sent to refresh the entry 527 reaches the peer storing the tree node. In this rather unlikely 528 scenario, the successor that should have been present in the tree 529 node is temporarily missing. Thus, the service lookup will fail and 530 needs to be carried out again. 532 To recover from the kinds of situations described above, a ReDiR 533 implementation MAY choose to use the optimization described next. 534 The ReDiR implementation MAY implement a local temporary cache that 535 is maintained for the duration of a service lookup operation in a 536 RELOAD node. The temporary cache is used to store all 537 RedirServiceProvider entries that have been fetched during the upward 538 and downward walks of a service lookup operation. Should it happen 539 that a service lookup operation fails due to the downward walk 540 reaching a level that does not contain a successor, the cache is 541 searched for successors of the search key. If there are successors 542 present in the cache, the closest one of them is selected as the 543 service provider. 545 4.6. Removing Registrations 547 Before leaving the RELOAD Overlay Instance, a service provider SHOULD 548 remove the RedirServiceProvider records it has stored by storing 549 exists=False values in their place, as described in [RFC6940]. 551 5. Access Control Rules 553 As specified in RELOAD base [RFC6940], every Kind which is storable 554 in an overlay must be associated with an access control policy. This 555 policy defines whether a request from a given node to operate on a 556 given value should succeed or fail. Usages can define any access 557 control rules they choose, including publicly writable values. 559 ReDiR requires an access control policy that allows multiple nodes in 560 the overlay read and write access to the ReDiR tree nodes stored in 561 the overlay. Therefore, none of the access control policies 562 specified in RELOAD base [RFC6940] is sufficient. 564 This document defines a new access control policy, called NODE-ID- 565 MATCH. In this policy, a given value MUST be written and overwritten 566 only if the the request is signed with a key associated with a 567 certificate whose Node-ID is equal to the dictionary key. In 568 addition, provided that exists=TRUE, the Node-ID MUST belong to one 569 of the intervals associated with the tree node (the number of 570 intervals each tree node has is determined by the branching-factor 571 parameter). Finally, provided that exists=TRUE, 572 H(namespace,level,node), where namespace, level, and node are taken 573 from the RedirServiceProvider structure being stored, MUST be equal 574 to the Resource-ID for the resource. The NODE-ID-MATCH policy may 575 only be used with dictionary types. 577 6. REDIR Kind Definition 579 This section defines the REDIR Kind. 581 Name 583 REDIR 585 Kind IDs 587 The Resource Name for the REDIR Kind-ID is created by 588 concatenating three pieces of information: namespace, level, and 589 node number. Namespace is an opaque UTF-8 encoded string 590 identifying a service, such as "turn-server". Level is an integer 591 specifying a level in the ReDiR tree. Node number is an integer 592 identifying a ReDiR tree node at a specific level. The data 593 stored is a RedirServiceProvider structure that was defined in 594 Section 4.1. 596 Data Model 598 The data model for the REDIR Kind-ID is dictionary. The 599 dictionary key is the Node-ID of the service provider. 601 Access Control 603 The access control policy for the REDIR Kind is the NODE-ID-MATCH 604 policy that was defined in Section 5. 606 7. Examples 608 7.1. Service Registration 610 Figure 4 shows an example of a ReDiR tree containing information 611 about four different service providers whose Node-IDs are 2, 3, 4, 612 and 7. In the example, numBitsInNodeID=4. Initially, the ReDiR tree 613 is empty; Figure 4 shows the state of the tree at the point when all 614 the service providers have registered. 616 Level 0 ____2_3___4_____7_|__________________ 617 | | 618 Level 1 ____2_3_|_4_____7 ________|________ 619 | | | | 620 Level 2 ___|2_3 4__|__7 ___|___ ___|___ 621 | | | | | | | | 622 Level 3 _|_ _|3 _|_ _|_ _|_ _|_ _|_ _|_ 624 Figure 4: Example of a ReDiR tree 626 First, peer 2 whose Node-ID is 2 joins the namespace. Since this is 627 the first registration peer 2 performs, peer 2 sets the starting 628 level Lstart to 2, as was described in Section 4.2. Also all other 629 peers in this example will start from level 2. First, peer 2 fetches 630 the contents of the tree node associated with interval I(2,2) from 631 the RELOAD Overlay Instance. This tree node is the first tree node 632 from the left at Level 2 since key 2 is associated with the second 633 interval of the first tree node. Peer 2 also stores its 634 RedirServiceProvider record in that tree node. Since peer 2's Node- 635 ID is the only Node-ID stored in the tree node (i.e., peer 2's Node- 636 ID fulfills the condition in Section 4.3 that it is the numerically 637 lowest or highest among the keys stored in the node), peer 2 638 continues up the tree. In fact, peer 2 continues up in the tree all 639 the way to the root inserting its own Node-ID in all levels since the 640 tree is empty (which means that peer 2's Node-ID always fulfills the 641 condition that it is the numerically lowest or highest Node-ID in the 642 interval I(level, 2) during the upward walk). As described in 643 Section 4.3, peer 2 also walks down the tree. The downward walk peer 644 2 does ends at level 2 since peer 2 is the only node in its interval 645 at that level. 647 The next peer to join the namespace is peer 3, whose Node-ID is 3. 648 Peer 3 starts from level 2. At that level, peer 3 stores its 649 RedirServiceProvider entry in the same interval I(2,3) that already 650 contains the RedirServiceProvider entry of peer 2. Interval I(2,3), 651 that is, the interval at Level 2 enclosing key 3, is associated with 652 the right hand side interval of the first tree node. Since peer 3 653 has the numerically highest Node-ID in the tree node associated with 654 I(2,3), peer 3 continues up the tree. Peer 3 stores its 655 RedirServiceProvider record also at levels 1 and 0 since its Node-ID 656 is numerically highest among the Node-IDs stored in the intervals to 657 which its own Node-ID belongs. Peer 3 also does a downward walk 658 which starts from level 2 (i.e., the starting level). Since peer 3 659 is not the only node in interval I(2,3), it continues down the tree 660 to level 3. The downward walk ends at this level since peer 3 is the 661 only service provider in the interval I(3,3). 663 The third peer to join the namespace is peer 7, whose Node-ID is 7. 664 Like the two earlier peers, also peer 7 starts from level 2 because 665 this is the first registration it performs. Peer 7 stores its 666 RedirServiceProvider record at level 2. At level 1, peer 7 has the 667 numerically highest (and lowest) Node-ID in its interval I(1,7) 668 (because it is the only node in interval I(1,7); peers 2 and 3 are 669 stored in the same tree node but in a different interval) and 670 therefore it stores its Node-ID in the tree node associated with that 671 interval. Peer 7 also has the numerically highest Node-ID in the 672 interval I(0,7) associated with its Node-ID at level 0. Finally, 673 peer 7 performs a downward walk, which ends at level 2 because peer 7 674 is the only node in its interval at that level. 676 The final peer to join the ReDiR tree is peer 4, whose Node-ID is 4. 677 Peer 4 starts by storing its RedirServiceProvider record at level 2. 678 Since it has the numerically lowest Node-ID in the tree node 679 associated with interval I(2,4), it continues up in the tree to level 680 1. At level 1, peer 4 stores its record in the tree node associated 681 with interval I(1,4) because it has the numerically lowest Node-ID in 682 that interval. Next, peer 4 continues to the root level, at which it 683 stores its RedirServiceProvider record and finishes the upward walk 684 since the root level was reached. Peer 4 also does a downward walk 685 starting from level 2. The downward walk stops at level 2 because 686 peer 4 is the only peer in the interval I(2,4). 688 7.2. Service Lookup 690 This subsection gives an example of peer 5 whose Node-ID is 5 691 performing a service lookup operation in the ReDiR tree shown in 692 Figure 4. This is the first service lookup peer 5 carries out and 693 thus the service lookup starts from the default starting level 2. As 694 the first action, peer 5 fetches the tree node corresponding to the 695 interval I(2,5) from the starting level. This interval maps to the 696 second tree node from the left at level 2 since that tree node is 697 responsible for the interval (third interval from left) to which 698 Node-ID 5 falls at level 2. Having fetched the tree node, peer 5 699 checks its contents. First, there is a successor, peer 7, present in 700 the tree node. Therefore, condition 1 of Section 4.5 is false and 701 there is no need to perform an upward walk. Second, Node-ID 5 is the 702 highest Node-ID in its interval, so condition 2 of Section 4.5 is 703 also false and there is no need to perform a downward walk. Thus, 704 the service lookup finishes at level 2 since Node-ID 7 is the closest 705 successor of peer 5. 707 Note that the service lookup procedure would be slightly different if 708 peer 5 used level 3 as the starting level. Peer 5 might use this 709 starting level for instance if it has already carried out service 710 lookups in the past and follows the heuristic in Section 4.2 to 711 select the starting level. In this case, peer 5's first action is to 712 fetch the tree node at level 3 that is responsible for I(3,5). Thus, 713 peer 5 fetches the third tree node from the left. Since this tree 714 node is empty, peer 5 decreases the current level by one to 2 and 715 thus continues up in the tree. The next action peer 5 performs is 716 identical to the single action in the previous example of fetching 717 the node associated with I(2,5) from level 2. Thus, the service 718 lookup finishes at level 2. 720 8. Overlay Configuration Document Extension 722 This document extends the RELOAD overlay configuration document by 723 adding a new element "branching-factor" inside the new "REDIR" kind 724 element: 726 redir:branching-factor: The branching factor of the ReDir tree. The 727 default value is 10. 729 The Relax NG Grammar for this element is: 731 namespace redir = "urn:ietf:params:xml:ns:p2p:redir" 732 parameter &= element redir:branching-factor { xsd:unsignedInt }? 734 The 'redir' namespace is added into the element 735 in the overlay configuration file. 737 9. Security Considerations 739 This document defines a new access control policy called NODE-ID- 740 MATCH (see Section 5) whose purpose is to control which nodes in the 741 overlay are allowed read and write access to the ReDiR tree nodes. 742 The NODE-ID-MATCH access control policy ensures that the only node in 743 the overlay that can store a pointer to a specific service provider 744 in the ReDiR tree is the service provider itself. This prevents 745 attacks where a malicious node is inserting pointers to other nodes 746 in the ReDiR tree. Further, the NODE-ID-MATCH access control policy 747 ensures that a node can only store in locations in the ReDiR tree 748 where it is entitled to store information. In other words, a node 749 can only store one RedirServiceProvider record at any given level in 750 the ReDiR tree. This prevents an attack where a malicious node is 751 trying to insert a high number of pointers to the ReDiR tree. 753 When it comes to attacks such as a malicious node refusing to store a 754 value or denying knowledge of value it has previously accepted, such 755 security concerns are already discussed in the RELOAD base 756 specification [RFC6940]. 758 10. IANA Considerations 760 10.1. Access Control Policies 762 This document introduces one additional access control policy to the 763 "RELOAD Access Control Policy" Registry: 765 NODE-ID-MATCH 767 This access control policy was described in Section 5. 769 10.2. A New IETF XML Registry 771 This document registers one new URI for the redir namespace in the 772 IETF XML registry defined in [RFC3688]. 774 URI: urn:ietf:params:xml:ns:p2p:redir 776 Registrant Contact: The IESG 778 XML: N/A, the requested URI is an XML namespace 780 10.3. Data Kind-ID 782 This document introduces one additional data Kind-ID to the "RELOAD 783 Data Kind-ID" Registry: 785 +--------------+------------+----------+ 786 | Kind | Kind-ID | RFC | 787 +--------------+------------+----------+ 788 | REDIR | 0x104 | RFC-AAAA | 789 +--------------+------------+----------+ 791 This Kind-ID was defined in Section 6. 793 Note to RFC Editor: please replace AAAA with the RFC number for this 794 specification. 796 10.4. RELOAD Services Registry 798 IANA is requested to create a new registry for ReDiR namespaces. 800 Registry Name: RELOAD Services Registry 802 Reference: RFC-AAAA 804 Registration Procedure: Specification Required 806 [TO BE REMOVED: The registry should be located under 807 http://www.iana.org/assignments/reload and be called: RELOAD Services 808 Registry]. 810 Entries in this registry are strings denoting ReDiR namespace values. 811 The initial contents of this registry are: 813 +----------------+----------+ 814 | Namespace | RFC | 815 +----------------+----------+ 816 | turn-server | RFC-AAAA | 817 +----------------+----------+ 818 | voice-mail | RFC-AAAA | 819 +----------------+----------+ 821 The namespace 'turn-server' is used by nodes that wish to register as 822 providers of a TURN relay service in the RELOAD overlay and by nodes 823 that wish to discover providers of a TURN relay service from the 824 RELOAD overlay. In the TURN server discovery use case, the ReDiR- 825 based service discovery and registration mechanism specified in this 826 document can be used as an alternative to the TURN server discovery 827 mechanism specified in the RELOAD base specification [RFC6940]. The 828 namespace 'voice-mail' is intended for a voice mail service 829 implemented on top of a RELOAD overlay. 831 Note to RFC Editor: please replace AAAA with the RFC number for this 832 specification. 834 11. Acknowledgments 836 The authors would like to thank Marc Petit-Huguenin, Joscha 837 Schneider, Carlos Bernardos, Spencer Dawkins, Barry Leiba, Adrian 838 Farrel, Alexey Melnikov, Ted Lemon, and Stephen Farrell for their 839 comments on the document. 841 12. References 843 12.1. Normative References 845 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 846 Requirement Levels", BCP 14, RFC 2119, March 1997. 848 [RFC3174] Eastlake, D. and P. Jones, "US Secure Hash Algorithm 1 849 (SHA1)", RFC 3174, September 2001. 851 [RFC3629] Yergeau, F., "UTF-8, a transformation format of ISO 852 10646", STD 63, RFC 3629, November 2003. 854 [RFC3688] Mealling, M., "The IETF XML Registry", BCP 81, RFC 3688, 855 January 2004. 857 [RFC6940] Jennings, C., Lowekamp, B., Rescorla, E., Baset, S., and 858 H. Schulzrinne, "REsource LOcation And Discovery (RELOAD) 859 Base Protocol", RFC 6940, January 2014. 861 12.2. Informative References 863 [Redir] Rhea, S., Godfrey, P., Karp, B., Kubiatowicz, J., 864 Ratnasamy, S., Shenker, S., Stoica, I., and H. Yu, "Open 865 DHT: A Public DHT Service and Its Uses", October 2005. 867 Authors' Addresses 868 Jouni Maenpaa 869 Ericsson 870 Hirsalantie 11 871 Jorvas 02420 872 Finland 874 Email: Jouni.Maenpaa@ericsson.com 876 Gonzalo Camarillo 877 Ericsson 878 Hirsalantie 11 879 Jorvas 02420 880 Finland 882 Email: Gonzalo.Camarillo@ericsson.com