idnits 2.17.1 draft-ietf-p2psip-service-discovery-08.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 298 has weird spacing: '...ExtType type...' -- The document date (February 23, 2013) is 4078 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 265 -- Looks like a reference, but probably isn't: '7' on line 265 -- Looks like a reference, but probably isn't: '8' on line 265 -- Looks like a reference, but probably isn't: '15' on line 265 == Outdated reference: A later version (-26) exists of draft-ietf-p2psip-base-25 == Outdated reference: A later version (-09) exists of draft-ietf-p2psip-concepts-04 Summary: 0 errors (**), 0 flaws (~~), 4 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: August 27, 2013 February 23, 2013 7 Service Discovery Usage for REsource LOcation And Discovery (RELOAD) 8 draft-ietf-p2psip-service-discovery-08.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 to IETF 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 August 27, 2013. 35 Copyright Notice 37 Copyright (c) 2013 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 . . . . . . . . . . . . . . . . . . . . . . . . . 3 53 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 54 3. Introduction to ReDiR . . . . . . . . . . . . . . . . . . . . 4 55 4. Using ReDiR in a RELOAD Overlay Instance . . . . . . . . . . . 7 56 4.1. Data Structure . . . . . . . . . . . . . . . . . . . . . . 7 57 4.2. Selecting the Starting Level . . . . . . . . . . . . . . . 8 58 4.3. Service Provider Registration . . . . . . . . . . . . . . 9 59 4.4. Refreshing Registrations . . . . . . . . . . . . . . . . . 9 60 4.5. Service Lookups . . . . . . . . . . . . . . . . . . . . . 10 61 4.6. Removing Registrations . . . . . . . . . . . . . . . . . . 11 62 5. Access Control Rules . . . . . . . . . . . . . . . . . . . . . 12 63 6. REDIR Kind Definition . . . . . . . . . . . . . . . . . . . . 12 64 7. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 65 7.1. Service Registration . . . . . . . . . . . . . . . . . . . 13 66 7.2. Service Lookup . . . . . . . . . . . . . . . . . . . . . . 15 67 8. Overlay Configuration Document Extension . . . . . . . . . . . 15 68 9. Security Considerations . . . . . . . . . . . . . . . . . . . 16 69 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 16 70 10.1. Access Control Policies . . . . . . . . . . . . . . . . . 16 71 10.2. Data Kind-ID . . . . . . . . . . . . . . . . . . . . . . . 16 72 10.3. ReDiR Namespaces . . . . . . . . . . . . . . . . . . . . . 16 73 11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 17 74 12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 17 75 12.1. Normative References . . . . . . . . . . . . . . . . . . . 17 76 12.2. Informative References . . . . . . . . . . . . . . . . . . 17 77 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 17 79 1. Introduction 81 REsource LOcation And Discovery (RELOAD) [I-D.ietf-p2psip-base] is a 82 peer-to-peer signaling protocol that can be used to maintain an 83 overlay network, and to store data in and retrieve data from the 84 overlay. Although RELOAD defines a Traversal Using Relays around 85 Network Address Translation (TURN) specific service discovery 86 mechanism, it does not define a generic service discovery mechanism 87 as a part of the base protocol. This document defines how the 88 Recursive Distributed Rendezvous (ReDiR) service discovery mechanism 89 [Redir] used in OpenDHT can be applied to RELOAD overlays. 91 In a Peer-to-Peer (P2P) overlay network such as a RELOAD Overlay 92 Instance, the peers forming the overlay share their resources in 93 order to provide the service the system has been designed to provide. 94 The peers in the overlay both provide services to other peers and 95 request services from other peers. Examples of possible services 96 peers in a RELOAD Overlay Instance can offer to each other include a 97 TURN relay service, a voice mail service, a gateway location service, 98 and a transcoding service. Typically, only a small subset of the 99 peers participating in the system are providers of a given service. 100 A peer that wishes to use a particular service faces the problem of 101 finding peers that are providing that service from the Overlay 102 Instance. 104 A naive way to perform service discovery is to store the Node-IDs of 105 all nodes providing a particular service under a well-known key k. 106 The limitation of this approach is that it scales linearly in the 107 number of nodes that provide the service. The problem is two-fold: 108 the node n that is responsible for service s identified by key k may 109 end up storing a large number of Node-IDs and most importantly, may 110 also become overloaded since all service lookup requests for service 111 s will need to be answered by node n. An efficient service discovery 112 mechanism does not overload the nodes storing pointers to service 113 providers. In addition, the mechanism must ensure that the load of 114 providing a given service is distributed evenly among the nodes 115 providing the service. 117 ReDiR implements service discovery by building a tree structure of 118 the service providers that provide a particular service. The tree 119 structure is stored into the RELOAD Overlay Instance using RELOAD 120 Store and Fetch requests. Each service provided in the Overlay 121 Instance has its own tree. The nodes in a ReDiR tree contain 122 pointers to service providers. During service discovery, a peer 123 wishing to use a given service fetches ReDiR tree nodes one-by-one 124 from the RELOAD Overlay Instance until it finds a service provider 125 responsible for its Node-ID. It has been proved that ReDiR can find 126 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 hash table. Given a key, any participating peer can retrieve the 143 value associated with that key. The responsibility for 144 maintaining the mapping from keys to values is distributed among 145 the peers. 147 H(x): Hash calculated over x. 149 I(l,k): An interval at level l in the ReDiR tree that encloses key 150 k. 152 n.id: Node-ID of node n. 154 Namespace: An arbitrary identifier that identifies a service 155 provided in the RELOAD Overlay Instance. An example of a 156 namespace is "voice-mail". The namespace is an UTF-8 text string. 158 numBitsInNodeId: Number of bits in a Node-ID. 160 ReDiR tree: A tree structure of the nodes that provide a particular 161 service. The nodes embed the ReDiR tree into the RELOAD Overlay 162 Instance using RELOAD Store and Fetch requests. 164 Successor: The successor of identifier k in namespace ns is the node 165 belonging to ns whose identifier most immediately follows k. 167 3. Introduction to ReDiR 169 Recursive Distributed Rendezvous (ReDiR) [Redir] does not require new 170 functionality from the RELOAD base protocol. This is possible since 171 ReDiR interacts with the RELOAD Overlay Instance by simply storing 172 and fetching data, that is, using RELOAD Store and Fetch requests. 173 ReDiR creates a tree structure of the service providers of a 174 particular service and stores it into the RELOAD Overlay Instance 175 using the Store and Fetch requests. ReDiR service lookups require a 176 logarithmic number of Fetch operations. Further, if information from 177 past service lookups is used to determine the optimal level in the 178 ReDiR tree from which to start new service lookups, an average 179 service lookup can typically finish after a constant number of Fetch 180 operations assuming that Node-IDs are distributed uniformly at 181 random. 183 In ReDiR, each service provided in the overlay is identified by an 184 identifier, called the namespace. All service providers of a given 185 service store their information under the namespace of that service. 186 Peers wishing to use a service perform lookups within the namespace 187 of the service. The result of a ReDiR lookup for an identifier k in 188 namespace ns is a RedirServiceProvider structure (see Section 4.1) of 189 a service provider that belongs to ns and whose Node-ID is the 190 closest successor of identifier k in the namespace. 192 Each tree node in the ReDiR tree contains a dictionary of 193 RedirServiceProvider entries of peers providing a particular service. 194 Each tree node in the ReDiR tree also belongs to some level in the 195 tree. The root node of the ReDiR tree is located at level 0. The 196 child nodes of the root node are located at level 1 of the ReDiR 197 tree. The children of the tree nodes at level 1 are located at level 198 2, and so forth. The ReDiR tree has a branching factor, whose value 199 is determined by a new element in the RELOAD overlay configuration 200 document, called branching-factor. At every level lvl in the ReDiR 201 tree, there is room for a maximum of branching-factor^lvl tree nodes. 202 As an example, in a tree whose branching-factor is 2, the second 203 level can contain up to 4 tree nodes (note that a given level may 204 contain less than the maximum number of tree nodes since empty tree 205 nodes are not stored). Each tree node in the ReDiR tree is uniquely 206 identified by a pair (lvl,j), where lvl is a level in the ReDiR tree 207 and j is the position of the tree node (from the left) at that level. 208 As an example, the pair (2,3) identifies the 3rd tree node from the 209 left at level 2. 211 The ReDiR tree is stored into the RELOAD Overlay Instance tree node 212 by tree node, by storing the values of tree node (level,j) under a 213 key created by taking a hash over the concatenation of the namespace, 214 level, and j, that is, as H(namespace,level,j). As an example, the 215 root of the tree for a voice mail service is stored at H("voice- 216 mail",0,0). Each node (level,j) in the ReDiR tree contains b 217 intervals of the DHT's identifier space as follows: 219 [2^numBitsInNodeID*b^(-level)*(j+(b'/b)), 220 2^numBitsInNodeID*b^(-level)*(j+((b'+1)/b))), for 0<=b'; 300 opaque namespace<0..2^16-1>; 301 uint16 level; 302 uint16 node; 303 uint16 length; 305 select (type) { 306 /* This type may be extended */ 307 } extension; 309 } RedirServiceProvider; 311 The contents of the RedirServiceProvider Resource Record are as 312 follows: 314 type 315 The type of an extension to the RedirServiceProvider Resource 316 Record. Unknown types are allowed. 318 destination_list 319 A list of IDs through which a message is to be routed to reach the 320 service provider. The destination list consists of a sequence of 321 Destination values. The contents of the Destination structure are 322 as defined in RELOAD base [I-D.ietf-p2psip-base]. 324 namespace 325 An opaque UTF-8 encoded string containing the namespace. 327 level 328 The level in the ReDiR tree. 330 node 331 The position of the node storing this RedirServiceProvider record 332 at the current level in the ReDiR tree. 334 length 335 The length of the rest of the Resource Record. 337 extension 338 An extension value. The RedirServiceProvider Resource Record can 339 be extended to include for instance service or service provider 340 specific information. 342 4.2. Selecting the Starting Level 344 Before registering as a service provider or performing a service 345 lookup, a peer needs to determine the starting level Lstart for the 346 registration or lookup operation in the ReDiR tree. It is 347 RECOMMENDED that Lstart is set to 2. In subsequent registrations, 348 Lstart MAY, as an optimization, be set to the lowest level at which a 349 registration operation has last completed. 351 In the case of subsequent service lookups, nodes MAY, as an 352 optimization, record the levels at which the last 16 service lookups 353 completed and take Lstart to be the mode of those depths. 355 4.3. Service Provider Registration 357 A node MUST use the following procedure to register as a service 358 provider in the RELOAD Overlay Instance: 360 1. A node n with Node-ID n.id wishing to register as a service 361 provider starts from a starting level Lstart (see Section 4.2 for 362 the details on selecting the starting level). Therefore, node n 363 sets the current level to level=Lstart. 364 2. Node n MUST send a RELOAD Fetch request to fetch the contents of 365 the tree node responsible for I(level,n.id). An interval I(l,k) 366 is the interval at level l in the ReDiR tree that includes key k. 367 The fetch MUST be a wildcard fetch. 368 3. Node n MUST send a RELOAD Store request to add its 369 RedirServiceProvider entry to the dictionary stored in the tree 370 node responsible for I(level,n.id). Note that node n always 371 stores its RedirServiceProvider entry, regardless of the contents 372 of the dictionary. 373 4. If node n's Node-ID (n.id) is the lowest or highest Node-ID 374 stored in the tree node responsible for I(Lstart,n.id), node n 375 MUST reduce the current level by one (i.e., set level=level-1) 376 and continue up the ReDiR tree towards the root level (level 0), 377 repeating the steps 2 and 3 above. Node n MUST continue in this 378 way until it reaches either the root of the tree or a level at 379 which n.id is not the lowest or highest Node-ID in the interval 380 I(level,n.id). 381 5. Node n MUST also perform a downward walk in the ReDiR tree, 382 during which it goes through the tree nodes responsible for 383 intervals I(Lstart,n.id), I(Lstart+1,n.id), I(Lstart+2,n.id), 384 etc. At each step, node n MUST fetch the responsible tree node, 385 and store its RedirServiceProvider record in that tree node if 386 n.id is the lowest or highest Node-ID in its interval. Node n 387 MUST end this downward walk as soon as it reaches a level l at 388 which it is the only service provider in its interval I(l,n.id). 390 Note that above, when we refer to 'the tree node responsible for 391 I(l,k)', we mean the entire tree node (that is, all the intervals 392 within the tree node) responsible for interval I(l,k). In contrast, 393 I(l,k) refers to a specific interval within a tree node. 395 4.4. Refreshing Registrations 397 All state in the ReDiR tree is soft. Therefore, a service provider 398 needs to periodically repeat the registration process to refresh its 399 RedirServiceProvider Resource Record. If a record expires, it MUST 400 be dropped from the dictionary by the peer storing the tree node. 401 Deciding an appropriate lifetime for the RedirServiceProvider 402 Resource Records is up to each service provider. Every service 403 provider MUST repeat the entire registration process periodically 404 until it leaves the RELOAD Overlay Instance. 406 Note that no new mechanisms are needed to keep track of the remaining 407 lifetime of RedirServiceProvider records. The 'storage_time' and 408 'lifetime' fields of RELOAD's StoredData structure can be used for 409 this purpose in the usual way. 411 4.5. Service Lookups 413 The purpose of a service lookup for identifier k in namespace ns is 414 to find the node that is a part of ns and whose identifier most 415 immediately follows (i.e., is the closest successor of) the 416 identifier k. 418 A service lookup operation resembles the service registration 419 operation described in Section 4.3. Service lookups start from a 420 given starting level level=Lstart in the ReDiR tree (see Section 4.2 421 for the details on selecting the starting level). At each step, a 422 node n wishing to discover a service provider MUST fetch the tree 423 node responsible for the interval I(level,n.id) that encloses the 424 search key n.id at the current level using a RELOAD Fetch request. 425 Having fetched the tree node, node n MUST determine the next action 426 to carry out as follows: 428 1. If there is no successor of node n present in the just fetched 429 ReDiR tree node (note: within the entire tree and not only within 430 the current interval) responsible for I(level,n.id), then the 431 successor of node n must be present in a larger segment of the 432 identifier space (i.e., further up in the ReDiR tree where each 433 interval and tree node covers a larger range of the identifier 434 space). Therefore, node n MUST reduce the current level by one 435 to level=level-1 and carry out a new Fetch operation for the tree 436 node responsible for n.id at that level. The fetched tree node 437 is then analyzed and the next action determined by checking 438 conditions 1-3. 439 2. If n.id is neither the lowest nor the highest Node-ID within the 440 interval (note: within the interval, not within the entire tree 441 node) I(level,n.id), n MUST next check the tree node responsible 442 for n.id at the next level down the tree. Thus, node n MUST 443 increase the level by one to level=level+1 and carry out a new 444 Fetch operation at that level. The fetched tree node is then 445 analyzed and the next action determined by checking conditions 446 1-3. 447 3. If neither of the conditions above holds, meaning that there is a 448 successor s of n.id present in the just fetched ReDiR tree node 449 and n.id is the highest or lowest Node-ID in its interval, the 450 service lookup has finished successfully and s must be the 451 closest successor of n.id in the ReDiR tree. 453 Note that above, when we refer to 'the tree node responsible for 454 interval I(l,k)', we mean the entire tree node (that is, all the 455 intervals within the tree node) responsible for interval I(l,k). In 456 contrast, I(l,k) refers to a specific interval within a tree node. 458 Note also that there may be some cases in which no successor can be 459 found from the ReDiR tree. An example is a situation in which all of 460 the service providers stored in the ReDiR tree have a Node-ID smaller 461 than identifier k. In this case, the upward walk of the service 462 lookup will reach the root of the tree without encountering a 463 successor. An appropriate strategy in this case is to pick one of 464 the RedirServiceProvider entries stored in the dictionary of the root 465 node at random. 467 Since RedirServiceProvider records are expiring and registrations are 468 being refreshed periodically, there can be certain rare situations in 469 which a service lookup may fail even if there is a valid successor 470 present in the ReDiR tree. An example is a case in which a ReDiR 471 tree node is fetched just after a RedirServiceProvider entry of the 472 only successor of k present in the tree node has expired and just 473 before a Store request that has been sent to refresh the entry 474 reaches the peer storing the tree node. In this rather unlikely 475 scenario, the successor that should have been present in the tree 476 node is temporarily missing. Thus, the service lookup will fail and 477 needs to be carried out again. 479 To recover from the kinds of situations described above, a ReDiR 480 implementation MAY choose to use the optimization described next. 481 The ReDiR implementation MAY implement a local temporary cache that 482 is maintained for the duration of a service lookup operation in a 483 RELOAD node. The temporary cache is used to store all 484 RedirServiceProvider entries that have been fetched during the upward 485 and downward walks of a service lookup operation. Should it happen 486 that a service lookup operation fails due to the downward walk 487 reaching a level that does not contain a successor, the cache is 488 searched for successors of the search key. If there are successors 489 present in the cache, the closest one of them is selected as the 490 service provider. 492 4.6. Removing Registrations 494 Before leaving the RELOAD Overlay Instance, a service provider MUST 495 remove the RedirServiceProvider records it has stored by storing 496 exists=False values in their place, as described in 497 [I-D.ietf-p2psip-base]. 499 5. Access Control Rules 501 As specified in RELOAD base [I-D.ietf-p2psip-base], every kind which 502 is storable in an overlay must be associated with an access control 503 policy. This policy defines whether a request from a given node to 504 operate on a given value should succeed or fail. Usages can define 505 any access control rules they choose, including publicly writable 506 values. 508 ReDiR requires an access control policy that allows multiple nodes in 509 the overlay read and write access to the ReDiR tree nodes stored in 510 the overlay. Therefore, none of the access control policies 511 specified in RELOAD base [I-D.ietf-p2psip-base] is sufficient. 513 This document defines a new access control policy, called NODE-ID- 514 MATCH. In this policy, a given value MUST be written and overwritten 515 only if the the request is signed with a key associated with a 516 certificate whose Node-ID is equal to the dictionary key. In 517 addition, provided that exists=TRUE, the Node-ID MUST belong to one 518 of the intervals associated with the tree node (the number of 519 intervals each tree node has is determined by the branching-factor 520 parameter). Finally, provided that exists=TRUE, 521 H(namespace,level,node), where namespace, level, and node are taken 522 from the RedirServiceProvider structure being stored, MUST be equal 523 to the Resource-ID for the resource. The NODE-ID-MATCH policy may 524 only be used with dictionary types. 526 6. REDIR Kind Definition 528 This section defines the REDIR kind. 530 Name 531 REDIR 533 Kind IDs 534 The Resource Name for the REDIR Kind-ID is created by 535 concatenating three pieces of information: namespace, level, and 536 node number. Namespace is an opaque UTF-8 encoded string 537 identifying a service, such as "turn-server". Level is an integer 538 specifying a level in the ReDiR tree. Node number is an integer 539 identifying a ReDiR tree node at a specific level. The data 540 stored is a RedirServiceProvider structure that was defined in 541 Section 4.1. 543 Data Model 544 The data model for the REDIR Kind-ID is dictionary. The 545 dictionary key is the Node-ID of the service provider. 547 Access Control 548 The access control policy for the REDIR kind is the NODE-ID-MATCH 549 policy that was defined in Section 5. 551 7. Examples 553 7.1. Service Registration 555 Figure 4 shows an example of a ReDiR tree containing information 556 about four different service providers whose Node-IDs are 2, 3, 4, 557 and 7. In the example, numBitsInNodeID=4. Initially, the ReDiR tree 558 is empty; Figure 4 shows the state of the tree at the point when all 559 the service providers have registered. 561 Level 0 ____2_3___4_____7_|__________________ 562 | | 563 Level 1 ____2_3_|_4_____7 ________|________ 564 | | | | 565 Level 2 ___|2_3 4__|__7 ___|___ ___|___ 566 | | | | | | | | 567 Level 3 _|_ _|3 _|_ _|_ _|_ _|_ _|_ _|_ 569 Figure 4: Example of a ReDiR tree 571 First, peer 2 whose Node-ID is 2 joins the namespace. Since this is 572 the first registration peer 2 performs, peer 2 sets the starting 573 level Lstart to 2, as was described in Section 4.2. Also all other 574 peers in this example will start from level 2. First, peer 2 fetches 575 the contents of the tree node associated with interval I(2,2) from 576 the RELOAD Overlay Instance. This tree node is the first tree node 577 from the left at Level 2 since key 2 is associated with the second 578 interval of the first tree node. Peer 2 also stores its 579 RedirServiceProvider record in that tree node. Since peer 2's 580 Node-ID is the only Node-ID stored in the tree node (i.e., peer 2's 581 Node-ID fulfills the condition in Section 4.3 that it is the 582 numerically lowest or highest among the keys stored in the node), 583 peer 2 continues up the tree. In fact, peer 2 continues up in the 584 tree all the way to the root inserting its own Node-ID in all levels 585 since the tree is empty (which means that peer 2's Node-ID always 586 fulfills the condition that it is the numerically lowest or highest 587 Node-ID in the interval I(level, 2) during the upward walk). As 588 described in Section 4.3, peer 2 also walks down the tree. The 589 downward walk peer 2 does ends at level 2 since peer 2 is the only 590 node in its interval at that level. 592 The next peer to join the namespace is peer 3, whose Node-ID is 3. 593 Peer 3 starts from level 2. At that level, peer 3 stores its 594 RedirServiceProvider entry in the same interval I(2,3) that already 595 contains the RedirServiceProvider entry of peer 2. Interval I(2,3), 596 that is, the interval at Level 2 enclosing key 3, is associated with 597 the right hand side interval of the first tree node. Since peer 3 598 has the numerically highest Node-ID in the tree node associated with 599 I(2,3), peer 3 continues up the tree. Peer 3 stores its 600 RedirServiceProvider record also at levels 1 and 0 since its Node-ID 601 is numerically highest among the Node-IDs stored in the intervals to 602 which its own Node-ID belongs. Peer 3 also does a downward walk 603 which starts from level 2 (i.e., the starting level). Since peer 3 604 is not the only node in interval I(2,3), it continues down the tree 605 to level 3. The downward walk ends at this level since peer 3 is the 606 only service provider in the interval I(3,3). 608 The third peer to join the namespace is peer 7, whose Node-ID is 7. 609 Like the two earlier peers, also peer 7 starts from level 2 because 610 this is the first registration it performs. Peer 7 stores its 611 RedirServiceProvider record at level 2. At level 1, peer 7 has the 612 numerically highest (and lowest) Node-ID in its interval I(1,7) 613 (because it is the only node in interval I(1,7); peers 2 and 3 are 614 stored in the same tree node but in a different interval) and 615 therefore it stores its Node-ID in the tree node associated with that 616 interval. Peer 7 also has the numerically highest Node-ID in the 617 interval I(0,7) associated with its Node-ID at level 0. Finally, 618 peer 7 performs a downward walk, which ends at level 2 because peer 7 619 is the only node in its interval at that level. 621 The final peer to join the ReDiR tree is peer 4, whose Node-ID is 4. 622 Peer 4 starts by storing its RedirServiceProvider record at level 2. 623 Since it has the numerically lowest Node-ID in the tree node 624 associated with interval I(2,4), it continues up in the tree to level 625 1. At level 1, peer 4 stores its record in the tree node associated 626 with interval I(1,4) because it has the numerically lowest Node-ID in 627 that interval. Next, peer 4 continues to the root level, at which it 628 stores its RedirServiceProvider record and finishes the upward walk 629 since the root level was reached. Peer 4 also does a downward walk 630 starting from level 2. The downward walk stops at level 2 because 631 peer 4 is the only peer in the interval I(2,4). 633 7.2. Service Lookup 635 This subsection gives an example of peer 5 whose Node-ID is 5 636 performing a service lookup operation in the ReDiR tree shown in 637 Figure 4. This is the first service lookup peer 5 carries out and 638 thus the service lookup starts from the default starting level 2. As 639 the first action, peer 5 fetches the tree node corresponding to the 640 interval I(2,5) from the starting level. This interval maps to the 641 second tree node from the left at level 2 since that tree node is 642 responsible for the interval (third interval from left) to which 643 Node-ID 5 falls at level 2. Having fetched the tree node, peer 5 644 checks its contents. First, there is a successor, peer 7, present in 645 the tree node. Therefore, condition 1 of Section 4.5 is false and 646 there is no need to perform an upward walk. Second, Node-ID 5 is the 647 highest Node-ID in its interval, so condition 2 of Section 4.5 is 648 also false and there is no need to perform a downward walk. Thus, 649 the service lookup finishes at level 2 since Node-ID 7 is the closest 650 successor of peer 5. 652 Note that the service lookup procedure would be slightly different if 653 peer 5 used level 3 as the starting level. Peer 5 might use this 654 starting level for instance if it has already carried out service 655 lookups in the past and follows the heuristic in Section 4.2 to 656 select the starting level. In this case, peer 5's first action is to 657 fetch the tree node at level 3 that is responsible for I(3,5). Thus, 658 peer 5 fetches the third tree node from the left. Since this tree 659 node is empty, peer 5 decreases the current level by one to 2 and 660 thus continues up in the tree. The next action peer 5 performs is 661 identical to the single action in the previous example of fetching 662 the node associated with I(2,5) from level 2. Thus, the service 663 lookup finishes at level 2. 665 8. Overlay Configuration Document Extension 667 This document extends the RELOAD overlay configuration document by 668 adding a new element "branching-factor" inside the new "REDIR" kind 669 element: 671 redir:branching-factor: The branching factor of the ReDir tree. The 672 default value is 10. 674 This new element is formally defined as follows: 676 namespace redir = "urn:ietf:params:xml:ns:p2p:service-discovery" 677 parameter &= element redir:branching-factor { xsd:unsignedInt } 679 The 'redir' namespace is added into the element 680 in the overlay configuration file. 682 9. Security Considerations 684 There are no new security considerations introduced in this document. 685 The security considerations of RELOAD [I-D.ietf-p2psip-base] apply. 687 10. IANA Considerations 689 10.1. Access Control Policies 691 This document introduces one additional access control policy to the 692 "RELOAD Access Control Policy" Registry: 694 NODE-ID-MATCH 696 This access control policy was described in Section 5. 698 10.2. Data Kind-ID 700 This document introduces one additional data Kind-ID to the "RELOAD 701 Data Kind-ID" Registry: 703 +--------------+------------+----------+ 704 | Kind | Kind-ID | RFC | 705 +--------------+------------+----------+ 706 | REDIR | 104 | RFC-AAAA | 707 +--------------+------------+----------+ 709 This Kind-ID was defined in Section 6. 711 10.3. ReDiR Namespaces 713 IANA SHALL create a "ReDiR Namespaces" Registry. Entries in this 714 registry are strings denoting ReDiR namespace values. The initial 715 contents of this registry are: 717 +----------------+----------+ 718 | Namespace | RFC | 719 +----------------+----------+ 720 | turn-server | RFC-AAAA | 721 +----------------+----------+ 723 The namespace 'turn-server' is used by nodes that wish to register as 724 providers of a TURN relay service in the RELOAD overlay and by nodes 725 that wish to discover providers of a TURN relay service from the 726 RELOAD overlay. 728 11. Acknowledgments 730 The authors would like to thank Marc Petit-Huguenin and Joscha 731 Schneider for their comments on the draft. 733 12. References 735 12.1. Normative References 737 [I-D.ietf-p2psip-base] 738 Jennings, C., Lowekamp, B., Rescorla, E., Baset, S., and 739 H. Schulzrinne, "REsource LOcation And Discovery (RELOAD) 740 Base Protocol", draft-ietf-p2psip-base-25 (work in 741 progress), February 2013. 743 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 744 Requirement Levels", BCP 14, RFC 2119, March 1997. 746 12.2. Informative References 748 [I-D.ietf-p2psip-concepts] 749 Bryan, D., Willis, D., Shim, E., Matthews, P., and S. 750 Dawkins, "Concepts and Terminology for Peer to Peer SIP", 751 draft-ietf-p2psip-concepts-04 (work in progress), 752 October 2011. 754 [Redir] Rhea, S., Godfrey, P., Karp, B., Kubiatowicz, J., 755 Ratnasamy, S., Shenker, S., Stoica, I., and H. Yu, "Open 756 DHT: A Public DHT Service and Its Uses". 758 Authors' Addresses 760 Jouni Maenpaa 761 Ericsson 762 Hirsalantie 11 763 Jorvas 02420 764 Finland 766 Email: Jouni.Maenpaa@ericsson.com 768 Gonzalo Camarillo 769 Ericsson 770 Hirsalantie 11 771 Jorvas 02420 772 Finland 774 Email: Gonzalo.Camarillo@ericsson.com