idnits 2.17.1 draft-ietf-p2psip-service-discovery-11.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 314 has weird spacing: '...ExtType type...' -- The document date (May 10, 2014) is 3638 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 281 -- Looks like a reference, but probably isn't: '7' on line 281 -- Looks like a reference, but probably isn't: '8' on line 281 -- Looks like a reference, but probably isn't: '15' on line 281 == Outdated reference: A later version (-09) exists of draft-ietf-p2psip-concepts-05 Summary: 0 errors (**), 0 flaws (~~), 3 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: November 11, 2014 May 10, 2014 7 Service Discovery Usage for REsource LOcation And Discovery (RELOAD) 8 draft-ietf-p2psip-service-discovery-11.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 November 11, 2014. 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 . . . . . . . . . . . . . . 9 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 . . . . . . . . . . . . . . . . . . . . 13 63 6. REDIR Kind Definition . . . . . . . . . . . . . . . . . . . . 13 64 7. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 14 65 7.1. Service Registration . . . . . . . . . . . . . . . . . . 14 66 7.2. Service Lookup . . . . . . . . . . . . . . . . . . . . . 16 67 8. Overlay Configuration Document Extension . . . . . . . . . . 17 68 9. Security Considerations . . . . . . . . . . . . . . . . . . . 17 69 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 17 70 10.1. Access Control Policies . . . . . . . . . . . . . . . . 17 71 10.2. A New IETF XML Registry . . . . . . . . . . . . . . . . 17 72 10.3. Data Kind-ID . . . . . . . . . . . . . . . . . . . . . . 18 73 10.4. ReDiR Namespaces . . . . . . . . . . . . . . . . . . . . 18 74 11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 18 75 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 19 76 12.1. Normative References . . . . . . . . . . . . . . . . . . 19 77 12.2. Informative References . . . . . . . . . . . . . . . . . 19 78 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 19 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 ReDiR implements service discovery by building a tree structure of 119 the service providers that provide a particular service. The tree 120 structure is stored into the RELOAD Overlay Instance using RELOAD 121 Store and Fetch requests. Each service provided in the Overlay 122 Instance has its own tree. The nodes in a ReDiR tree contain 123 pointers to service providers. During service discovery, a peer 124 wishing to use a given service fetches ReDiR tree nodes one-by-one 125 from the RELOAD Overlay Instance until it finds a service provider 126 responsible for its Node-ID. It has been proved that ReDiR can find 127 a service provider using only a constant number of Fetch operations 128 [Redir]. 130 2. Terminology 132 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 133 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 134 document are to be interpreted as described in RFC 2119 [RFC2119]. 136 This document uses the terminology and definitions from the Concepts 137 and Terminology for Peer to Peer SIP [I-D.ietf-p2psip-concepts] 138 draft. 140 DHT: Distributed Hash Tables (DHTs) are a class of decentralized 141 distributed systems that provide a lookup service similar to a 142 regular hash table. Given a key, any peer participating in the 143 system can retrieve the value associated with that key. The 144 responsibility for maintaining the mapping from keys to values is 145 distributed among the peers. 147 H(x): Refers to a hash function (e.g., SHA-1) calculated over the 148 value x. 150 I(lvl,k): An interval at level lvl in the ReDiR tree that encloses 151 key k. As an example, I(5,10) refers to an interval at level 5 in 152 the ReDiR tree within whose range key 10 falls. 154 n.id: Refers to the RELOAD Node-ID of node n. 156 Namespace: An arbitrary identifier that identifies a service 157 provided in the RELOAD Overlay Instance. Examples of potential 158 namespaces include "voice-mail" and "turn-relay". The namespace 159 is an UTF-8 text string. 161 numBitsInNodeId: Refers to the number of bits in a RELOAD Node-ID. 162 This value is used in the equations for calculating the ranges of 163 intervals that ReDiR tree nodes are responsible for. 165 ReDiR tree: A tree structure of the nodes that provide a particular 166 service. The nodes embed the ReDiR tree into the RELOAD Overlay 167 Instance using RELOAD Store and Fetch requests. Each tree node in 168 the ReDiR tree belongs to some level in the tree. The root node 169 of the ReDiR tree is located at level 0 of the ReDiR tree. The 170 child nodes of the root node are located at level 1. The children 171 of the tree nodes at level 1 are located at level 2, and so forth. 172 The ReDiR tree has a branching factor b. At every level lvl in the 173 ReDiR tree, there is room for a maximum of b^lvl tree nodes. Each 174 tree node in the ReDiR tree is uniquely identified by a pair 175 (lvl,j), where lvl is a level in the ReDiR tree and j is the 176 position of the tree node (from the left) at that level. 178 Successor: The successor of identifier k in namespace ns is the node 179 belonging to the namespace ns whose identifier most immediately 180 follows the identifier k. 182 3. Introduction to ReDiR 184 Recursive Distributed Rendezvous (ReDiR) [Redir] does not require new 185 functionality from the RELOAD base protocol. This is possible since 186 ReDiR interacts with the RELOAD Overlay Instance by simply storing 187 and fetching data, that is, using RELOAD Store and Fetch requests. 188 ReDiR creates a tree structure of the service providers of a 189 particular service and stores it into the RELOAD Overlay Instance 190 using the Store and Fetch requests. ReDiR service lookups require a 191 logarithmic number of Fetch operations. Further, if information from 192 past service lookups is used to determine the optimal level in the 193 ReDiR tree from which to start new service lookups, an average 194 service lookup can typically finish after a constant number of Fetch 195 operations assuming that Node-IDs are distributed uniformly at 196 random. 198 In ReDiR, each service provided in the overlay is identified by an 199 identifier, called the namespace. All service providers of a given 200 service store their information under the namespace of that service. 201 Peers wishing to use a service perform lookups within the namespace 202 of the service. The result of a ReDiR lookup for an identifier k in 203 namespace ns is a RedirServiceProvider structure (see Section 4.1) of 204 a service provider that belongs to ns and whose Node-ID is the 205 closest successor of identifier k in the namespace. 207 Each tree node in the ReDiR tree contains a dictionary of 208 RedirServiceProvider entries of peers providing a particular service. 209 Each tree node in the ReDiR tree also belongs to some level in the 210 tree. The root node of the ReDiR tree is located at level 0. The 211 child nodes of the root node are located at level 1 of the ReDiR 212 tree. The children of the tree nodes at level 1 are located at level 213 2, and so forth. The ReDiR tree has a branching factor, whose value 214 is determined by a new element in the RELOAD overlay configuration 215 document, called branching-factor. At every level lvl in the ReDiR 216 tree, there is room for a maximum of branching-factor^lvl tree nodes. 217 As an example, in a tree whose branching-factor is 2, the second 218 level can contain up to 4 tree nodes (note that a given level may 219 contain less than the maximum number of tree nodes since empty tree 220 nodes are not stored). Each tree node in the ReDiR tree is uniquely 221 identified by a pair (lvl,j), where lvl is a level in the ReDiR tree 222 and j is the position of the tree node (from the left) at that level. 224 As an example, the pair (2,3) identifies the 3rd tree node from the 225 left at level 2. 227 The ReDiR tree is stored into the RELOAD Overlay Instance tree node 228 by tree node, by storing the values of tree node (level,j) under a 229 key created by taking a hash over the concatenation of the namespace, 230 level, and j, that is, as H(namespace,level,j). As an example, the 231 root of the tree for a voice mail service is stored at H("voice- 232 mail",0,0). Each node (level,j) in the ReDiR tree contains b 233 intervals of the DHT's identifier space as follows: 235 [2^numBitsInNodeID*b^(-level)*(j+(b'/b)), 236 2^numBitsInNodeID*b^(-level)*(j+((b'+1)/b))), for 0<=b'; 316 opaque namespace<0..2^16-1>; 317 uint16 level; 318 uint16 node; 319 uint16 length; 321 select (type) { 322 /* This type may be extended */ 323 } extension; 325 } RedirServiceProvider; 327 The contents of the RedirServiceProvider Resource Record are as 328 follows: 330 type 332 The type of an extension to the RedirServiceProvider Resource 333 Record. Unknown types are allowed. 335 destination_list 337 A list of IDs through which a message is to be routed to reach the 338 service provider. The destination list consists of a sequence of 339 Destination values. The contents of the Destination structure are 340 as defined in RELOAD base [RFC6940]. 342 namespace 343 An opaque UTF-8 encoded string containing the namespace. 345 level 347 The level in the ReDiR tree. 349 node 351 The position of the node storing this RedirServiceProvider record 352 at the current level in the ReDiR tree. 354 length 356 The length of the rest of the Resource Record. 358 extension 360 An extension value. The RedirServiceProvider Resource Record can 361 be extended to include for instance service or service provider 362 specific information. 364 4.2. Selecting the Starting Level 366 Before registering as a service provider or performing a service 367 lookup, a peer needs to determine the starting level Lstart for the 368 registration or lookup operation in the ReDiR tree. It is 369 RECOMMENDED that Lstart is set to 2. In subsequent registrations, 370 Lstart MAY, as an optimization, be set to the lowest level at which a 371 registration operation has last completed. 373 In the case of subsequent service lookups, nodes MAY, as an 374 optimization, record the levels at which the last 16 service lookups 375 completed and take Lstart to be the mode of those depths. 377 4.3. Service Provider Registration 379 A node MUST use the following procedure to register as a service 380 provider in the RELOAD Overlay Instance: 382 1. A node n with Node-ID n.id wishing to register as a service 383 provider starts from a starting level Lstart (see Section 4.2 for 384 the details on selecting the starting level). Therefore, node n 385 sets the current level to level=Lstart. 387 2. Node n MUST send a RELOAD Fetch request to fetch the contents of 388 the tree node responsible for I(level,n.id). An interval I(l,k) 389 is the interval at level l in the ReDiR tree that includes key k. 390 The fetch MUST be a wildcard fetch. 392 3. Node n MUST send a RELOAD Store request to add its 393 RedirServiceProvider entry to the dictionary stored in the tree 394 node responsible for I(level,n.id). Note that node n always 395 stores its RedirServiceProvider entry, regardless of the contents 396 of the dictionary. 398 4. If node n's Node-ID (n.id) is the lowest or highest Node-ID 399 stored in the tree node responsible for I(Lstart,n.id), node n 400 MUST reduce the current level by one (i.e., set level=level-1) 401 and continue up the ReDiR tree towards the root level (level 0), 402 repeating the steps 2 and 3 above. Node n MUST continue in this 403 way until it reaches either the root of the tree or a level at 404 which n.id is not the lowest or highest Node-ID in the interval 405 I(level,n.id). 407 5. Node n MUST also perform a downward walk in the ReDiR tree, 408 during which it goes through the tree nodes responsible for 409 intervals I(Lstart,n.id), I(Lstart+1,n.id), I(Lstart+2,n.id), 410 etc. At each step, node n MUST fetch the responsible tree node, 411 and store its RedirServiceProvider record in that tree node if 412 n.id is the lowest or highest Node-ID in its interval. Node n 413 MUST end this downward walk as soon as it reaches a level l at 414 which it is the only service provider in its interval I(l,n.id). 416 Note that above, when we refer to 'the tree node responsible for 417 I(l,k)', we mean the entire tree node (that is, all the intervals 418 within the tree node) responsible for interval I(l,k). In contrast, 419 I(l,k) refers to a specific interval within a tree node. 421 4.4. Refreshing Registrations 423 All state in the ReDiR tree is soft. Therefore, a service provider 424 needs to periodically repeat the registration process to refresh its 425 RedirServiceProvider Resource Record. If a record expires, it MUST 426 be dropped from the dictionary by the peer storing the tree node. 427 Deciding an appropriate lifetime for the RedirServiceProvider 428 Resource Records is up to each service provider. Every service 429 provider MUST repeat the entire registration process periodically 430 until it leaves the RELOAD Overlay Instance. 432 Note that no new mechanisms are needed to keep track of the remaining 433 lifetime of RedirServiceProvider records. The 'storage_time' and 434 'lifetime' fields of RELOAD's StoredData structure can be used for 435 this purpose in the usual way. 437 4.5. Service Lookups 439 The purpose of a service lookup for identifier k in namespace ns is 440 to find the node that is a part of ns and whose identifier most 441 immediately follows (i.e., is the closest successor of) the 442 identifier k. 444 A service lookup operation resembles the service registration 445 operation described in Section 4.3. Service lookups start from a 446 given starting level level=Lstart in the ReDiR tree (see Section 4.2 447 for the details on selecting the starting level). At each step, a 448 node n wishing to discover a service provider MUST fetch the tree 449 node responsible for the interval I(level,n.id) that encloses the 450 search key n.id at the current level using a RELOAD Fetch request. 451 Having fetched the tree node, node n MUST determine the next action 452 to carry out as follows: 454 1. If there is no successor of node n present in the just fetched 455 ReDiR tree node (note: within the entire tree and not only within 456 the current interval) responsible for I(level,n.id), then the 457 successor of node n must be present in a larger segment of the 458 identifier space (i.e., further up in the ReDiR tree where each 459 interval and tree node covers a larger range of the identifier 460 space). Therefore, node n MUST reduce the current level by one 461 to level=level-1 and carry out a new Fetch operation for the tree 462 node responsible for n.id at that level. The fetched tree node 463 is then analyzed and the next action determined by checking 464 conditions 1-3. 466 2. If n.id is neither the lowest nor the highest Node-ID within the 467 interval (note: within the interval, not within the entire tree 468 node) I(level,n.id), n MUST next check the tree node responsible 469 for n.id at the next level down the tree. Thus, node n MUST 470 increase the level by one to level=level+1 and carry out a new 471 Fetch operation at that level. The fetched tree node is then 472 analyzed and the next action determined by checking conditions 473 1-3. 475 3. If neither of the conditions above holds, meaning that there is a 476 successor s of n.id present in the just fetched ReDiR tree node 477 and n.id is the highest or lowest Node-ID in its interval, the 478 service lookup has finished successfully and s must be the 479 closest successor of n.id in the ReDiR tree. 481 Note that above, when we refer to 'the tree node responsible for 482 interval I(l,k)', we mean the entire tree node (that is, all the 483 intervals within the tree node) responsible for interval I(l,k). In 484 contrast, I(l,k) refers to a specific interval within a tree node. 486 Note also that there may be some cases in which no successor can be 487 found from the ReDiR tree. An example is a situation in which all of 488 the service providers stored in the ReDiR tree have a Node-ID smaller 489 than identifier k. In this case, the upward walk of the service 490 lookup will reach the root of the tree without encountering a 491 successor. An appropriate strategy in this case is to pick one of 492 the RedirServiceProvider entries stored in the dictionary of the root 493 node at random. 495 Since RedirServiceProvider records are expiring and registrations are 496 being refreshed periodically, there can be certain rare situations in 497 which a service lookup may fail even if there is a valid successor 498 present in the ReDiR tree. An example is a case in which a ReDiR 499 tree node is fetched just after a RedirServiceProvider entry of the 500 only successor of k present in the tree node has expired and just 501 before a Store request that has been sent to refresh the entry 502 reaches the peer storing the tree node. In this rather unlikely 503 scenario, the successor that should have been present in the tree 504 node is temporarily missing. Thus, the service lookup will fail and 505 needs to be carried out again. 507 To recover from the kinds of situations described above, a ReDiR 508 implementation MAY choose to use the optimization described next. 509 The ReDiR implementation MAY implement a local temporary cache that 510 is maintained for the duration of a service lookup operation in a 511 RELOAD node. The temporary cache is used to store all 512 RedirServiceProvider entries that have been fetched during the upward 513 and downward walks of a service lookup operation. Should it happen 514 that a service lookup operation fails due to the downward walk 515 reaching a level that does not contain a successor, the cache is 516 searched for successors of the search key. If there are successors 517 present in the cache, the closest one of them is selected as the 518 service provider. 520 4.6. Removing Registrations 522 Before leaving the RELOAD Overlay Instance, a service provider MUST 523 remove the RedirServiceProvider records it has stored by storing 524 exists=False values in their place, as described in [RFC6940]. 526 5. Access Control Rules 528 As specified in RELOAD base [RFC6940], every kind which is storable 529 in an overlay must be associated with an access control policy. This 530 policy defines whether a request from a given node to operate on a 531 given value should succeed or fail. Usages can define any access 532 control rules they choose, including publicly writable values. 534 ReDiR requires an access control policy that allows multiple nodes in 535 the overlay read and write access to the ReDiR tree nodes stored in 536 the overlay. Therefore, none of the access control policies 537 specified in RELOAD base [RFC6940] is sufficient. 539 This document defines a new access control policy, called NODE-ID- 540 MATCH. In this policy, a given value MUST be written and overwritten 541 only if the the request is signed with a key associated with a 542 certificate whose Node-ID is equal to the dictionary key. In 543 addition, provided that exists=TRUE, the Node-ID MUST belong to one 544 of the intervals associated with the tree node (the number of 545 intervals each tree node has is determined by the branching-factor 546 parameter). Finally, provided that exists=TRUE, 547 H(namespace,level,node), where namespace, level, and node are taken 548 from the RedirServiceProvider structure being stored, MUST be equal 549 to the Resource-ID for the resource. The NODE-ID-MATCH policy may 550 only be used with dictionary types. 552 6. REDIR Kind Definition 554 This section defines the REDIR kind. 556 Name 558 REDIR 560 Kind IDs 561 The Resource Name for the REDIR Kind-ID is created by 562 concatenating three pieces of information: namespace, level, and 563 node number. Namespace is an opaque UTF-8 encoded string 564 identifying a service, such as "turn-server". Level is an integer 565 specifying a level in the ReDiR tree. Node number is an integer 566 identifying a ReDiR tree node at a specific level. The data 567 stored is a RedirServiceProvider structure that was defined in 568 Section 4.1. 570 Data Model 572 The data model for the REDIR Kind-ID is dictionary. The 573 dictionary key is the Node-ID of the service provider. 575 Access Control 577 The access control policy for the REDIR kind is the NODE-ID-MATCH 578 policy that was defined in Section 5. 580 7. Examples 582 7.1. Service Registration 584 Figure 4 shows an example of a ReDiR tree containing information 585 about four different service providers whose Node-IDs are 2, 3, 4, 586 and 7. In the example, numBitsInNodeID=4. Initially, the ReDiR tree 587 is empty; Figure 4 shows the state of the tree at the point when all 588 the service providers have registered. 590 Level 0 ____2_3___4_____7_|__________________ 591 | | 592 Level 1 ____2_3_|_4_____7 ________|________ 593 | | | | 594 Level 2 ___|2_3 4__|__7 ___|___ ___|___ 595 | | | | | | | | 596 Level 3 _|_ _|3 _|_ _|_ _|_ _|_ _|_ _|_ 598 Figure 4: Example of a ReDiR tree 600 First, peer 2 whose Node-ID is 2 joins the namespace. Since this is 601 the first registration peer 2 performs, peer 2 sets the starting 602 level Lstart to 2, as was described in Section 4.2. Also all other 603 peers in this example will start from level 2. First, peer 2 fetches 604 the contents of the tree node associated with interval I(2,2) from 605 the RELOAD Overlay Instance. This tree node is the first tree node 606 from the left at Level 2 since key 2 is associated with the second 607 interval of the first tree node. Peer 2 also stores its 608 RedirServiceProvider record in that tree node. Since peer 2's Node- 609 ID is the only Node-ID stored in the tree node (i.e., peer 2's Node- 610 ID fulfills the condition in Section 4.3 that it is the numerically 611 lowest or highest among the keys stored in the node), peer 2 612 continues up the tree. In fact, peer 2 continues up in the tree all 613 the way to the root inserting its own Node-ID in all levels since the 614 tree is empty (which means that peer 2's Node-ID always fulfills the 615 condition that it is the numerically lowest or highest Node-ID in the 616 interval I(level, 2) during the upward walk). As described in 617 Section 4.3, peer 2 also walks down the tree. The downward walk peer 618 2 does ends at level 2 since peer 2 is the only node in its interval 619 at that level. 621 The next peer to join the namespace is peer 3, whose Node-ID is 3. 622 Peer 3 starts from level 2. At that level, peer 3 stores its 623 RedirServiceProvider entry in the same interval I(2,3) that already 624 contains the RedirServiceProvider entry of peer 2. Interval I(2,3), 625 that is, the interval at Level 2 enclosing key 3, is associated with 626 the right hand side interval of the first tree node. Since peer 3 627 has the numerically highest Node-ID in the tree node associated with 628 I(2,3), peer 3 continues up the tree. Peer 3 stores its 629 RedirServiceProvider record also at levels 1 and 0 since its Node-ID 630 is numerically highest among the Node-IDs stored in the intervals to 631 which its own Node-ID belongs. Peer 3 also does a downward walk 632 which starts from level 2 (i.e., the starting level). Since peer 3 633 is not the only node in interval I(2,3), it continues down the tree 634 to level 3. The downward walk ends at this level since peer 3 is the 635 only service provider in the interval I(3,3). 637 The third peer to join the namespace is peer 7, whose Node-ID is 7. 638 Like the two earlier peers, also peer 7 starts from level 2 because 639 this is the first registration it performs. Peer 7 stores its 640 RedirServiceProvider record at level 2. At level 1, peer 7 has the 641 numerically highest (and lowest) Node-ID in its interval I(1,7) 642 (because it is the only node in interval I(1,7); peers 2 and 3 are 643 stored in the same tree node but in a different interval) and 644 therefore it stores its Node-ID in the tree node associated with that 645 interval. Peer 7 also has the numerically highest Node-ID in the 646 interval I(0,7) associated with its Node-ID at level 0. Finally, 647 peer 7 performs a downward walk, which ends at level 2 because peer 7 648 is the only node in its interval at that level. 650 The final peer to join the ReDiR tree is peer 4, whose Node-ID is 4. 651 Peer 4 starts by storing its RedirServiceProvider record at level 2. 652 Since it has the numerically lowest Node-ID in the tree node 653 associated with interval I(2,4), it continues up in the tree to level 654 1. At level 1, peer 4 stores its record in the tree node associated 655 with interval I(1,4) because it has the numerically lowest Node-ID in 656 that interval. Next, peer 4 continues to the root level, at which it 657 stores its RedirServiceProvider record and finishes the upward walk 658 since the root level was reached. Peer 4 also does a downward walk 659 starting from level 2. The downward walk stops at level 2 because 660 peer 4 is the only peer in the interval I(2,4). 662 7.2. Service Lookup 664 This subsection gives an example of peer 5 whose Node-ID is 5 665 performing a service lookup operation in the ReDiR tree shown in 666 Figure 4. This is the first service lookup peer 5 carries out and 667 thus the service lookup starts from the default starting level 2. As 668 the first action, peer 5 fetches the tree node corresponding to the 669 interval I(2,5) from the starting level. This interval maps to the 670 second tree node from the left at level 2 since that tree node is 671 responsible for the interval (third interval from left) to which 672 Node-ID 5 falls at level 2. Having fetched the tree node, peer 5 673 checks its contents. First, there is a successor, peer 7, present in 674 the tree node. Therefore, condition 1 of Section 4.5 is false and 675 there is no need to perform an upward walk. Second, Node-ID 5 is the 676 highest Node-ID in its interval, so condition 2 of Section 4.5 is 677 also false and there is no need to perform a downward walk. Thus, 678 the service lookup finishes at level 2 since Node-ID 7 is the closest 679 successor of peer 5. 681 Note that the service lookup procedure would be slightly different if 682 peer 5 used level 3 as the starting level. Peer 5 might use this 683 starting level for instance if it has already carried out service 684 lookups in the past and follows the heuristic in Section 4.2 to 685 select the starting level. In this case, peer 5's first action is to 686 fetch the tree node at level 3 that is responsible for I(3,5). Thus, 687 peer 5 fetches the third tree node from the left. Since this tree 688 node is empty, peer 5 decreases the current level by one to 2 and 689 thus continues up in the tree. The next action peer 5 performs is 690 identical to the single action in the previous example of fetching 691 the node associated with I(2,5) from level 2. Thus, the service 692 lookup finishes at level 2. 694 8. Overlay Configuration Document Extension 696 This document extends the RELOAD overlay configuration document by 697 adding a new element "branching-factor" inside the new "REDIR" kind 698 element: 700 redir:branching-factor: The branching factor of the ReDir tree. The 701 default value is 10. 703 The Relax NG Grammar for this element is: 705 namespace redir = "urn:ietf:params:xml:ns:p2p:redir" 707 parameter &= element redir:branching-factor { xsd:unsignedInt }? 709 The 'redir' namespace is added into the element 710 in the overlay configuration file. 712 9. Security Considerations 714 There are no new security considerations introduced in this document. 715 The security considerations of RELOAD [RFC6940] apply. 717 10. IANA Considerations 719 10.1. Access Control Policies 721 This document introduces one additional access control policy to the 722 "RELOAD Access Control Policy" Registry: 724 NODE-ID-MATCH 726 This access control policy was described in Section 5. 728 10.2. A New IETF XML Registry 730 This document registers one new URI for the redir namespace in the 731 IETF XML registry defined in [RFC3688]. 733 URI: urn:ietf:params:xml:ns:p2p:redir 735 Registrant Contact: The IESG 736 XML: N/A, the requested URI is an XML namespace 738 10.3. Data Kind-ID 740 This document introduces one additional data Kind-ID to the "RELOAD 741 Data Kind-ID" Registry: 743 +--------------+------------+----------+ 744 | Kind | Kind-ID | RFC | 745 +--------------+------------+----------+ 746 | REDIR | 104 | RFC-AAAA | 747 +--------------+------------+----------+ 749 This Kind-ID was defined in Section 6. 751 Note to RFC Editor: please replace AAAA with the RFC number for this 752 specification. 754 10.4. ReDiR Namespaces 756 IANA SHALL create a "ReDiR Namespaces" Registry. Entries in this 757 registry are strings denoting ReDiR namespace values. The initial 758 contents of this registry are: 760 +----------------+----------+ 761 | Namespace | RFC | 762 +----------------+----------+ 763 | turn-server | RFC-AAAA | 764 +----------------+----------+ 766 The namespace 'turn-server' is used by nodes that wish to register as 767 providers of a TURN relay service in the RELOAD overlay and by nodes 768 that wish to discover providers of a TURN relay service from the 769 RELOAD overlay. 771 Note to RFC Editor: please replace AAAA with the RFC number for this 772 specification. 774 11. Acknowledgments 776 The authors would like to thank Marc Petit-Huguenin, Joscha 777 Schneider, and Carlos Bernardos for their comments on the document. 779 12. References 781 12.1. Normative References 783 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 784 Requirement Levels", BCP 14, RFC 2119, March 1997. 786 [RFC3688] Mealling, M., "The IETF XML Registry", BCP 81, RFC 3688, 787 January 2004. 789 [RFC6940] Jennings, C., Lowekamp, B., Rescorla, E., Baset, S., and 790 H. Schulzrinne, "REsource LOcation And Discovery (RELOAD) 791 Base Protocol", RFC 6940, January 2014. 793 12.2. Informative References 795 [I-D.ietf-p2psip-concepts] 796 Bryan, D., Matthews, P., Shim, E., Willis, D., and S. 797 Dawkins, "Concepts and Terminology for Peer to Peer SIP", 798 draft-ietf-p2psip-concepts-05 (work in progress), July 799 2013. 801 [Redir] Rhea, S., Godfrey, P., Karp, B., Kubiatowicz, J., 802 Ratnasamy, S., Shenker, S., Stoica, I., and H. Yu, "Open 803 DHT: A Public DHT Service and Its Uses", October 2005. 805 Authors' Addresses 807 Jouni Maenpaa 808 Ericsson 809 Hirsalantie 11 810 Jorvas 02420 811 Finland 813 Email: Jouni.Maenpaa@ericsson.com 815 Gonzalo Camarillo 816 Ericsson 817 Hirsalantie 11 818 Jorvas 02420 819 Finland 821 Email: Gonzalo.Camarillo@ericsson.com