idnits 2.17.1 draft-ietf-p2psip-service-discovery-03.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (July 5, 2011) is 4651 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) == Outdated reference: A later version (-26) exists of draft-ietf-p2psip-base-15 == Outdated reference: A later version (-09) exists of draft-ietf-p2psip-concepts-03 Summary: 0 errors (**), 0 flaws (~~), 3 warnings (==), 2 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: January 6, 2012 July 5, 2011 7 Service Discovery Usage for REsource LOcation And Discovery (RELOAD) 8 draft-ietf-p2psip-service-discovery-03.txt 10 Abstract 12 REsource LOcation and Discovery (RELOAD) does not define a generic 13 service discovery mechanism as 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 January 6, 2012. 35 Copyright Notice 37 Copyright (c) 2011 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 . . . . . . . . . . . 6 56 4.1. Data Structure . . . . . . . . . . . . . . . . . . . . . . 6 57 4.2. Selecting the Starting Level . . . . . . . . . . . . . . . 7 58 4.3. Service Provider Registration . . . . . . . . . . . . . . 7 59 4.4. Refreshing Registrations . . . . . . . . . . . . . . . . . 8 60 4.5. Service Lookups . . . . . . . . . . . . . . . . . . . . . 8 61 4.6. Removing Registrations . . . . . . . . . . . . . . . . . . 9 62 5. Access Control Rules . . . . . . . . . . . . . . . . . . . . . 9 63 6. REDIR Kind Definition . . . . . . . . . . . . . . . . . . . . 10 64 7. Example . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 65 8. Overlay Configuration Document Extension . . . . . . . . . . . 12 66 9. Security Considerations . . . . . . . . . . . . . . . . . . . 12 67 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 12 68 10.1. Access Control Policies . . . . . . . . . . . . . . . . . 12 69 10.2. Data Kind-ID . . . . . . . . . . . . . . . . . . . . . . . 12 70 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 13 71 11.1. Normative References . . . . . . . . . . . . . . . . . . . 13 72 11.2. Informative References . . . . . . . . . . . . . . . . . . 13 73 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 13 75 1. Introduction 77 REsource LOcation And Discovery (RELOAD) [I-D.ietf-p2psip-base] is a 78 peer-to-peer signaling protocol that can be used to maintain an 79 overlay network, and to store data in and retrieve data from the 80 overlay. Although RELOAD defines a Traversal Using Relays around 81 Network Address Translation (TURN) specific service discovery 82 mechanism, it does not define a generic service discovery mechanism 83 as part of the base protocol. This document defines how the 84 Recursive Distributed Rendezvous (ReDiR) service discovery mechanism 85 [Redir] used in OpenDHT can be applied to RELOAD overlays. 87 In a Peer-to-Peer (P2P) overlay network such as a RELOAD Overlay 88 Instance, the peers forming the overlay share their resources in 89 order to provide the service the system has been designed to provide. 90 The peers in the overlay both provide services to other peers and 91 request services from other peers. Examples of possible services 92 peers in a RELOAD Overlay Instance can offer to each other include a 93 TURN relay service, a voice mail service, a gateway location service, 94 and a transcoding service. Typically, only a small subset of the 95 peers participating in the system are providers of a given service. 96 A peer that wishes to use a particular service faces the problem of 97 finding peers that are providing that service from the Overlay 98 Instance. 100 A naive way to perform service discovery is to store the Node-IDs of 101 all nodes providing a particular service under a well-known key k. 102 The limitation of this approach is that it scales linearly in the 103 number of nodes that provide the service. The problem is two-fold: 104 the node n that is responsible for service s identified by key k may 105 end up storing a large number of Node-IDs and most importantly, may 106 also become overloaded since all service lookup requests for service 107 s will need to be answered by node n. An efficient service discovery 108 mechanism does not overload the nodes storing pointers to service 109 providers. In addition, the mechanism must ensure that the load of 110 providing a given service is distributed evenly among the nodes 111 providing the service. 113 ReDiR implements service discovery by building a tree structure of 114 the nodes that provide a particular service and embedding it into the 115 RELOAD Overlay Instance using RELOAD Store and Fetch requests. Each 116 service provided in the Overlay Instance has its own tree. The nodes 117 in a ReDiR tree contain pointers to service providers. During 118 service discovery, a peer wishing to use a given service fetches 119 ReDiR tree nodes one-by-one from the RELOAD Overlay Instance until it 120 finds a service provider responsible for its Node-ID. It has been 121 proved that ReDiR can find a service provider using only a constant 122 number of fetch operations [Redir]. 124 2. Terminology 126 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 127 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 128 document are to be interpreted as described in RFC 2119 [RFC2119]. 130 This document uses the terminology and definitions from the Concepts 131 and Terminology for Peer to Peer SIP [I-D.ietf-p2psip-concepts] 132 draft. 134 DHT: Distributed Hash Tables (DHTs) are a class of decentralized 135 distributed systems that provide a lookup service similar to a 136 hash table. Given a key, any participating peer can retrieve the 137 value associated with that key. The responsibility for 138 maintaining the mapping from keys to values is distributed among 139 the peers. 141 H(x): Hash calculated over x. 143 I(l,k): The unique interval at level l in the ReDiR tree that 144 encloses key k. 146 n.id: Node-ID of node n. 148 Namespace: An arbitrary identifier that identifies a service 149 provided in the RELOAD Overlay Instance. An example of a 150 namespace is "voice-mail". 152 numBitsInNodeId: Number of bits in a Node-ID. 154 ReDiR tree: A tree structure of the nodes that provide a particular 155 service. The nodes embed the ReDiR tree into the RELOAD Overlay 156 Instance using RELOAD Store and Fetch requests. 158 Successor: The successor of identifier k in namespace ns is the node 159 that has joined ns whose identifier most immediately follows k. 161 3. Introduction to ReDiR 163 Recursive Distributed Rendezvous (ReDiR) [Redir] does not require new 164 functionality from the RELOAD base protocol. This is possible since 165 ReDiR interacts with the RELOAD overlay through a put/get API using 166 RELOAD Store and Fetch requests. ReDiR builds a tree structure of 167 the nodes that provide a particular service and embeds it into the 168 RELOAD Overlay Instance using the Store and Fetch requests. ReDiR 169 performs lookup in a logarithmic number of Fetch operations with high 170 probability. Further, if the tree's height is estimated based on 171 past lookups, the average lookup can be reduced to a constant number 172 of fetch operations assuming that Node-IDs are distributed uniformly 173 at random. 175 In ReDiR, each service provided in the overlay is identified by an 176 arbitrary identifier, called its namespace. All service providers 177 join a namespace and peers wishing to use a service perform lookups 178 within the namespace of the service. A ReDiR lookup for identifier k 179 in namespace ns returns a node that has joined ns whose identifier is 180 the closest successor of k. 182 Each tree node in the ReDiR tree contains a list of Node-IDs of peers 183 providing a particular service. Each node in the tree has a level. 184 The root is at level 0, the immediate children of the root are at 185 level 1, and so forth. The ReDiR tree has a branching factor, whose 186 value is determined by a new element in the RELOAD overlay 187 configuration document, called branching-factor. At every level i in 188 the tree, there are at most branching-factor^i nodes. The nodes at 189 any level are labeled from left to right, such that a pair (i,j) 190 uniquely identifies the jth node from the left at level i. This tree 191 is embedded into the RELOAD Overlay Instance node by node, by storing 192 the values of node (i,j) at key H(namespace,i,j). As an example, the 193 root of the tree for a voice mail service is stored at H("voice- 194 mail",0,0). Each node (i,j) in the tree is associated with 195 branching-factor intervals of the DHT keyspace as follows: 197 [2^numBitsInNodeID*b^(-i)*(j+(b'/b)), 198 2^numBitsInNodeID*b^(-i)*(j+((b'+1)/b))], for 0<=b'; 235 uint16 level; 236 uint16 node; 238 /* This type can be extended */ 240 } RedirServiceProviderData; 242 struct { 243 uint16 length; 244 RedirServiceProviderData data; 245 } RedirServiceProvider; 247 The contents of the RedirServiceProvider structure are as follows: 249 length 250 The length of the rest of the structure. 252 data 253 The service provider data. 255 The contents of the RedirServiceProviderData structure are as 256 follows: 258 serviceProvider 259 The Node-ID of a service provider. 261 namespace 262 An opaque string containing the namespace. 264 level 265 The level in the ReDiR tree. 267 node 268 The position of the node storing this RedirServiceProvider record 269 at the current level in the ReDiR tree. 271 The RedirServiceProviderData structure can be extended to include for 272 instance service or service provider specific information. 274 4.2. Selecting the Starting Level 276 Before registering as a service provider or performing a service 277 lookup, a peer needs to determine the starting level Lstart for the 278 registration or lookup operation in the ReDiR tree. It is 279 RECOMMENDED that Lstart is initially set to 2. In subsequent 280 registrations, Lstart MUST be set to the lowest level at which 281 registration last completed. 283 In the case of service lookups, nodes MUST record the levels at which 284 the last 16 service lookups completed and take Lstart to be the mode 285 of those depths. 287 4.3. Service Provider Registration 289 A node MUST use the following procedure to register as a service 290 provider in the RELOAD Overlay Instance: 292 1. A node n with Node-ID n.id wishing to register as a service 293 provider starts from level Lstart (see Section 4.2 for the 294 details on selecting the starting level). Therefore, node n sets 295 level=Lstart. 296 2. Node n MUST send a RELOAD Fetch request to fetch the contents of 297 the tree node associated with I(level,n.id). An interval I(l,k) 298 is defined as the unique interval at level l in the ReDiR tree 299 that encloses key k. The fetch MUST be a wildcard fetch. 300 3. Node n MUST send a RELOAD Store request to add its 301 RedirServiceProvider entry to the dictionary stored in the tree 302 node associated with I(level,n.id) 304 4. If node n's Node-ID is the numerically lowest or highest among 305 the Node-IDs stored in the tree node associated with 306 I(Lstart,n.id), node n MUST continue up the tree towards the root 307 (level 0), repeating steps 2 and 3. Node n MUST continue this 308 until it reaches either the root or a level at which n.id is not 309 the lowest or highest Node-ID in the interval I(level,n.id). 310 5. Node n MUST also walk down the tree through tree nodes associated 311 with the intervals I(Lstart,n.id),I(Lstart+1,n.id),..., at each 312 step fetching the current contents of the tree node, and storing 313 its redirServiceProvider record if n.id is the lowest or highest 314 Node-ID in the interval. Node n MUST end this downward walk when 315 it reaches a level at which it is the only service provider in 316 the interval. 318 Note that above, when we refer to 'the tree node associated with 319 I(l,k)', we mean the entire tree node (that is, all the intervals 320 within the tree node) responsible for interval I(l,k). In contrast, 321 I(l,k) refers to a specific interval within a tree node. 323 4.4. Refreshing Registrations 325 All state in the ReDiR tree is soft. If an entry (Node-ID) is not 326 refreshed for refresh-period seconds, it MUST be dropped from the 327 dictionary by the peer storing the tree node. refresh-period is a new 328 element in the RELOAD overlay configuration document (see Section 8). 329 Every service provider MUST repeat the entire registration process 330 periodically until it leaves the RELOAD Overlay Instance. 332 Note that no new mechanisms are needed to keep track of the remaining 333 lifetime of RedirServiceProvider records. The 'storage_time' and 334 'lifetime' fields of RELOAD's StoredData structure can be used for 335 this purpose in the usual way. 337 4.5. Service Lookups 339 The purpose of a service lookup on identifier k in namespace ns is to 340 find the node that has joined ns whose identifier most immediately 341 follows identifier k. 343 A service lookup is similar to the registration operation. The 344 service lookup starts from some level level=Lstart (see Section 4.2 345 for the details on selecting the starting level). At each step, the 346 node n wishing to discover a service provider MUST fetch the tree 347 node associated with the current interval I(level,n.id) using a 348 RELOAD Fetch request and MUST determine where to look next as 349 follows: 351 1. If the successor of node n is not present in the tree node 352 associated with I(level,n.id), then its successor must occur in a 353 larger range of the keyspace. Node n MUST set level=level-1 and 354 try again. 355 2. If n.id is sandwiched between two Node-IDs in I(level,n.id), the 356 successor must lie somewhere in I(level,n.id). Node n MUST set 357 level=level+1 and repeat. 358 3. Otherwise, there is a Node-ID s stored in the node associated 359 with I(level,n.id) whose identifier succeeds n.id, and there are 360 no Node-IDs between n.id and s. Thus, s must be the closest 361 successor of n.id, and the lookup is done. 363 Note that above, when we refer to 'the tree node associated with 364 I(l,k)', we mean the entire tree node (that is, all the intervals 365 within the tree node) responsible for interval I(l,k). In contrast, 366 I(l,k) refers to a specific interval within a tree node. 368 4.6. Removing Registrations 370 Before leaving the RELOAD Overlay Instance, a service provider MUST 371 remove the redirServiceProvider records it has stored by storing 372 "nonexistent" values in their place, as described in 373 [I-D.ietf-p2psip-base]. 375 5. Access Control Rules 377 As specified in RELOAD base [I-D.ietf-p2psip-base], every kind which 378 is storable in an overlay must be associated with an access control 379 policy. This policy defines whether a request from a given node to 380 operate on a given value should succeed or fail. Usages can define 381 any access control rules they choose, including publicly writable 382 values. 384 ReDiR requires an access control policy that allows multiple nodes in 385 the overlay read and write access to the ReDiR tree nodes stored in 386 the overlay. Therefore, none of the access control policies 387 specified in RELOAD base [I-D.ietf-p2psip-base] is sufficient. 389 This document defines a new access control policy, called NODE-ID- 390 MATCH. In this policy, a given value MUST be written and overwritten 391 only if the the request is signed with a key associated with a 392 certificate whose Node-ID is equal to the dictionary key. In 393 addition, the Node-ID MUST belong to one of the intervals associated 394 with the tree node (the number of intervals each tree node has is 395 determined by the branching-factor parameter). Finally, 396 H(namespace,level,node), where namespace, level, and node are taken 397 from the RedirServiceProvider structure being stored, MUST be equal 398 to the Resource-ID for the resource. The NODE-ID-MATCH policy may 399 only be used with dictionary types. 401 6. REDIR Kind Definition 403 This section defines the REDIR kind. 405 Name 406 REDIR 408 Kind IDs 409 The Resource Name for the REDIR Kind-ID is created by 410 concatenating three pieces of information: service name, level, 411 and node number. Service name is a string identifying a service, 412 such as "voice-mail". Level is an integer specifying a level in 413 the ReDiR tree. Node number is an integer identifying a ReDiR 414 tree node at a specific level. The data stored is a 415 RedirServiceProvider structure that was defined in Section 4.1. 417 Data Model 418 The data model for the REDIR Kind-ID is dictionary. The 419 dictionary key is the Node-ID of the service provider. 421 Access Control 422 The access control policy for the REDIR kind is the NODE-ID-MATCH 423 policy that was defined in Section 5. 425 7. Example 427 Figure 2 shows an example of a ReDiR tree containing information 428 about four different service providers whose Node-IDs are 2, 3, 4, 429 and 7. Initially, the ReDiR tree is empty. 431 Level 0 ____2_3___4_____7_|__________________ 432 | | 433 Level 1 ____2_3_|_4_____7 ________|________ 434 | | | | 435 Level 2 ___|2_3 4__|__7 ___|___ ___|___ 436 | | | | | | | | 437 Level 3 _|_ _|3 _|_ _|_ _|_ _|_ _|_ _|_ 439 Figure 2: Example of a ReDiR tree 441 First, peer 2 whose Node-ID is 2 joins the namespace. Since this is 442 the first registration peer 2 performs, peer 2 sets the starting 443 level Lstart to 2, as was described in Section 4.2. Also all other 444 peers in this example will start from level 2. First, peer 2 fetches 445 the contents of the tree node associated with interval I(2,2) from 446 the overlay. Peer 2 also stores its RedirServiceProvider record in 447 that tree node. Since peer 2's Node-ID is the only Node-ID stored in 448 the tree node (i.e., peer 2's Node-ID fulfills the condition that it 449 is the numerically lowest or highest among the keys stored in the 450 node), peer 2 continues up the tree. In fact, peer 2 continues up in 451 the tree all the way to the root inserting its own Node-ID in all 452 levels since the tree is empty (which means that peer 2's Node-ID 453 always fulfills the condition that it is the numerically lowest or 454 highest Node-ID in the interval I(level, 2) during the upward walk). 455 As described in Section 4.3, peer 2 also walks down the tree. The 456 downward walk peer 2 does ends at level 2 since peer 2 is the only 457 node in its interval at that level. 459 The next peer to join the namespace is peer 3, whose Node-ID is 3. 460 Peer 3 starts from level 2. At that level, peer 3 stores its 461 RedirServiceProvider record in the same interval I(2,3) that already 462 contains the Node-ID of peer 2. Since peer 3 has the numerically 463 highest Node-ID in the tree node associated with I(2,3), peer 3 464 continues up the tree. Peer 3 stores its RedirServiceProvider record 465 also at levels 1 and 0 since its Node-ID is numerically highest among 466 the Node-IDs stored in the intervals to which its own Node-ID 467 belongs. Peer 3 also does a downward walk which starts from level 2 468 (i.e., the starting level). Since peer 3 is not the only node in 469 interval I(2,3), it continues down the tree to level 3. The downward 470 walk ends at this level since peer 3 is the only service provider in 471 the interval I(3,3). 473 The third peer to join the namespace is peer 7, whose Node-ID is 7. 474 Like the two earlier peers, also peer 7 starts from level 2 because 475 this is the first registration it performs. Peer 7 stores its 476 RedirServiceProvider record at level 2. At level 1, peer 7 has the 477 numerically highest (and lowest) Node-ID in its interval I(1,7) 478 (because it is the only node in interval I(1,7); peers 2 and 3 are 479 stored in the same tree node but in a different interval) and 480 therefore it stores its Node-ID in the tree node associated with that 481 interval. Peer 7 also has the numerically highest Node-ID in the 482 interval I(0,7) associated with its Node-ID at level 0. Finally, 483 peer 7 performs a downward walk, which ends at level 2 because peer 7 484 is the only node in its interval at that level. 486 The final peer to join the ReDiR tree is peer 4, whose Node-ID is 4. 487 Peer 4 starts by storing its RedirServiceProvider record at level 2. 488 Since it has the numerically lowest Node-ID in the tree node 489 associated with interval I(2,4), it continues up in the tree to level 490 1. At level 1, peer 4 stores its record in the tree node associated 491 with interval I(1,4) because it has the numerically lowest Node-ID in 492 that interval. Next, peer 4 continues to the root level, at which it 493 stores its RedirServiceProvider record and finishes the upward walk 494 since the root level was reached. Peer 4 also does a downward walk 495 starting from level 2. The downward walk stops at level 2 because 496 peer 4 is the only peer in the interval I(2,4). 498 8. Overlay Configuration Document Extension 500 This document extends the RELOAD overlay configuration document by 501 adding two new elements inside the new "REDIR" kind element. 503 redir:branching-factor: The branching factor of the ReDir tree. The 504 default value is 10. 506 redir:refresh-period: The interval at which a service provider needs 507 to repeat the ReDiR registration process. 509 9. Security Considerations 511 There are no new security considerations introduced in this document. 512 The security considerations of RELOAD [I-D.ietf-p2psip-base] apply. 514 10. IANA Considerations 516 10.1. Access Control Policies 518 This document introduces one additional access control policy to the 519 "RELOAD Access Control Policy" Registry: 521 NODE-ID-MATCH 523 This access control policy was described in Section 5. 525 10.2. Data Kind-ID 527 This document introduces one additional data kind-ID to the "RELOAD 528 Data Kind-ID" Registry: 530 +--------------+------------+----------+ 531 | Kind | Kind-ID | RFC | 532 +--------------+------------+----------+ 533 | REDIR | 104 | RFC-AAAA | 534 +--------------+------------+----------+ 536 This kind-ID was defined in Section 6. 538 11. References 540 11.1. Normative References 542 [I-D.ietf-p2psip-base] 543 Jennings, C., Lowekamp, B., Rescorla, E., Baset, S., and 544 H. Schulzrinne, "REsource LOcation And Discovery (RELOAD) 545 Base Protocol", draft-ietf-p2psip-base-15 (work in 546 progress), May 2011. 548 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 549 Requirement Levels", BCP 14, RFC 2119, March 1997. 551 11.2. Informative References 553 [I-D.ietf-p2psip-concepts] 554 Bryan, D., Matthews, P., Shim, E., Willis, D., and S. 555 Dawkins, "Concepts and Terminology for Peer to Peer SIP", 556 draft-ietf-p2psip-concepts-03 (work in progress), 557 October 2010. 559 [Redir] Rhea, S., Godfrey, P., Karp, B., Kubiatowicz, J., 560 Ratnasamy, S., Shenker, S., Stoica, I., and H. Yu, "Open 561 DHT: A Public DHT Service and Its Uses". 563 Authors' Addresses 565 Jouni Maenpaa 566 Ericsson 567 Hirsalantie 11 568 Jorvas 02420 569 Finland 571 Email: Jouni.Maenpaa@ericsson.com 572 Gonzalo Camarillo 573 Ericsson 574 Hirsalantie 11 575 Jorvas 02420 576 Finland 578 Email: Gonzalo.Camarillo@ericsson.com