idnits 2.17.1 draft-ietf-p2psip-service-discovery-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** You're using the IETF Trust Provisions' Section 6.b License Notice from 12 Sep 2009 rather than the newer Notice from 28 Dec 2009. (See https://trustee.ietf.org/license-info/) 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 (January 19, 2010) is 5209 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-06 == Outdated reference: A later version (-09) exists of draft-ietf-p2psip-concepts-02 Summary: 1 error (**), 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: July 23, 2010 January 19, 2010 7 Service Discovery Usage for REsource LOcation And Discovery (RELOAD) 8 draft-ietf-p2psip-service-discovery-00.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), its areas, and its working groups. Note that 25 other groups may also distribute working documents as Internet- 26 Drafts. 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 The list of current Internet-Drafts can be accessed at 34 http://www.ietf.org/ietf/1id-abstracts.txt. 36 The list of Internet-Draft Shadow Directories can be accessed at 37 http://www.ietf.org/shadow.html. 39 This Internet-Draft will expire on July 23, 2010. 41 Copyright Notice 43 Copyright (c) 2010 IETF Trust and the persons identified as the 44 document authors. All rights reserved. 46 This document is subject to BCP 78 and the IETF Trust's Legal 47 Provisions Relating to IETF Documents 48 (http://trustee.ietf.org/license-info) in effect on the date of 49 publication of this document. Please review these documents 50 carefully, as they describe your rights and restrictions with respect 51 to this document. Code Components extracted from this document must 52 include Simplified BSD License text as described in Section 4.e of 53 the Trust Legal Provisions and are provided without warranty as 54 described in the BSD License. 56 Table of Contents 58 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 59 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 60 3. Introduction to ReDiR . . . . . . . . . . . . . . . . . . . . 4 61 4. Using ReDiR in a RELOAD Overlay Instance . . . . . . . . . . . 6 62 4.1. Data Structure . . . . . . . . . . . . . . . . . . . . . . 6 63 4.2. Selecting the Starting Level . . . . . . . . . . . . . . . 7 64 4.3. Service Provider Registration . . . . . . . . . . . . . . 7 65 4.4. Refreshing Registrations . . . . . . . . . . . . . . . . . 8 66 4.5. Service Lookups . . . . . . . . . . . . . . . . . . . . . 8 67 4.6. Removing Registrations . . . . . . . . . . . . . . . . . . 9 68 5. Access Control Rules . . . . . . . . . . . . . . . . . . . . . 9 69 6. REDIR Kind Definition . . . . . . . . . . . . . . . . . . . . 9 70 7. Example . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 71 8. Overlay Configuration Document Extension . . . . . . . . . . . 11 72 9. Security Considerations . . . . . . . . . . . . . . . . . . . 12 73 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 12 74 10.1. Access Control Policies . . . . . . . . . . . . . . . . . 12 75 10.2. Data Kind-ID . . . . . . . . . . . . . . . . . . . . . . . 12 76 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 12 77 11.1. Normative References . . . . . . . . . . . . . . . . . . . 12 78 11.2. Informative References . . . . . . . . . . . . . . . . . . 13 79 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 13 81 1. Introduction 83 REsource LOcation And Discovery (RELOAD) [I-D.ietf-p2psip-base] is a 84 peer-to-peer signaling protocol that can be used to maintain an 85 overlay network, and to store data in and retrieve data from the 86 overlay. Although RELOAD defines a Traversal Using Relays around 87 Network Address Translation (TURN) specific service discovery 88 mechanism, it does not define a generic service discovery mechanism 89 as part of the base protocol. This document defines how the 90 Recursive Distributed Rendezvous (ReDiR) service discovery mechanism 91 [Redir] used in OpenDHT can be applied to RELOAD overlays. 93 In a Peer-to-Peer (P2P) overlay network such as a RELOAD Overlay 94 Instance, the peers forming the overlay share their resources in 95 order to provide the service the system has been designed to provide. 96 The peers in the overlay both provide services to other peers and 97 request services from other peers. Examples of possible services 98 peers in a RELOAD Overlay Instance can offer to each other include a 99 TURN relay service, a voice mail service, a gateway location service, 100 and a transcoding service. Typically, only a small subset of the 101 peers participating in the system are providers of a given service. 102 A peer that wishes to use a particular service faces the problem of 103 finding peers that are providing that service from the Overlay 104 Instance. 106 A naive way to perform service discovery is to store the Node-IDs of 107 all nodes providing a particular service under a well-known key k. 108 The limitation of this approach is that it scales linearly in the 109 number of nodes that provide the service. The problem is two-fold: 110 the node n that is responsible for service s identified by key k may 111 end up storing a large number of Node-IDs and most importantly, may 112 also become overloaded since all service lookup requests for service 113 s will need to be answered by node n. An efficient service discovery 114 mechanism does not overload the nodes storing pointers to service 115 providers. In addition, the mechanism must ensure that the load of 116 providing a given service is distributed evenly among the nodes 117 providing the service. 119 ReDiR implements service discovery by building a tree structure of 120 the nodes that provide a particular service and embedding it into the 121 RELOAD Overlay Instance using RELOAD Store and Fetch requests. Each 122 service provided in the Overlay Instance has its own tree. The nodes 123 in a ReDiR tree contain pointers to service providers. During 124 service discovery, a peer wishing to use a given service fetches 125 ReDiR tree nodes one-by-one from the RELOAD Overlay Instance until it 126 finds a service provider responsible for its Node-ID. It has been 127 proved that ReDiR can find a service provider using only a constant 128 number of fetch operations [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): The unique interval at level l in the ReDiR tree that 150 encloses key 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". 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 that has joined 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 through a put/get API using 172 RELOAD Store and Fetch requests. ReDiR builds a tree structure of 173 the nodes that provide a particular service and embeds it into the 174 RELOAD Overlay Instance using the Store and Fetch requests. ReDiR 175 performs lookup in a logarithmic number of Fetch operations with high 176 probability. Further, if the tree's height is estimated based on 177 past lookups, the average lookup can be reduced to a constant number 178 of fetch operations assuming that Node-IDs are distributed uniformly 179 at random. 181 In ReDiR, each service provided in the overlay is identified by an 182 arbitrary identifier, called its namespace. All service providers 183 join a namespace and peers wishing to use a service perform lookups 184 within the namespace of the service. A ReDiR lookup for identifier k 185 in namespace ns returns a node that has joined ns whose identifier is 186 the closest successor of k. 188 Each tree node in the ReDiR tree contains a list of Node-IDs of peers 189 providing a particular service. Each node in the tree has a level. 190 The root is at level 0, the immediate children of the root are at 191 level 1, and so forth. The ReDiR tree has a branching factor, whose 192 value is determined by a new element in the RELOAD overlay 193 configuration document, called redirBranchingFactor. At every level 194 i in the tree, there are at most redirBranchingFactor^i nodes. The 195 nodes at any level are labeled from left to right, such that a pair 196 (i,j) uniquely identifies the jth node from the left at level i. 197 This tree is embedded into the RELOAD Overlay Instance node by node, 198 by storing the values of node (i,j) at key H(namespace,i,j). As an 199 example, the root of the tree for a voice mail service is stored at 200 H("voice-mail",0,0). Each node (i,j) in the tree is associated with 201 redirBranchingFactor intervals of the DHT keyspace as follows: 203 [2^numBitsInNodeID*b^(-i)*(j+(b'/b)), 204 2^numBitsInNodeID*b^(-i)*(j+((b'+1)/b))], for 0<=b'; 241 uint16 level; 242 uint16 node; 244 /* This type can be extended */ 246 } RedirServiceProviderData; 248 struct { 249 uint16 length; 250 RedirServiceProviderData data; 251 } RedirServiceProvider; 253 The contents of the RedirServiceProvider structure are as follows: 255 length 256 The length of the rest of the structure. 258 data 259 The service provider data. 261 The contents of the RedirServiceProviderData structure are as 262 follows: 264 serviceProvider 265 The Node-ID of a service provider. 267 namespace 268 An opaque string containing the namespace. 270 level 271 The level in the ReDiR tree. 273 node 274 The position of the node storing this RedirServiceProvider record 275 at the current level in the ReDiR tree. 277 The RedirServiceProviderData structure can be extended to include for 278 instance service or service provider specific information. 280 4.2. Selecting the Starting Level 282 Before registering as a service provider or performing a service 283 lookup, a peer needs to determine the starting level Lstart for the 284 registration or lookup operation in the ReDiR tree. It is 285 RECOMMENDED that Lstart is initially set to 2. In subsequent 286 registrations, Lstart MUST be set to the lowest level at which 287 registration last completed. 289 In the case of service lookups, nodes MUST record the levels at which 290 the last 16 service lookups completed and take Lstart to be the mode 291 of those depths. 293 4.3. Service Provider Registration 295 A node MUST use the following procedure to register as a service 296 provider in the RELOAD Overlay Instance: 298 1. A node n with Node-ID n.id wishing to register as a service 299 provider starts from level Lstart (see Section 4.2 for the 300 details on selecting the starting level). First, node n MUST 301 send a RELOAD Store request to add its RedirServiceProvider entry 302 to the dictionary stored in the tree node associated with 303 I(Lstart,n.id). An interval I(l,k) is defined as the unique 304 interval at level l in the ReDiR tree that encloses key k 305 2. Node n MUST send a RELOAD Fetch request to obtain the contents of 306 the tree node associated with I(Lstart,n.id). The fetch MUST be 307 a wildcard fetch. 308 3. If node n's Node-ID is the numerically lowest or highest among 309 the Node-IDs stored in the tree node, node n MUST continue up the 310 tree towards the root (level 0), repeating steps 1 and 2. Node n 311 MUST continue this until it reaches either the root or a level at 312 which n.id is not the lowest or highest Node-ID in the interval. 313 4. Node n MUST also walk down the tree through tree nodes associated 314 with the intervals I(Lstart,n.id),I(Lstart+1,n.id),..., at each 315 step fetching the current contents of the tree node, and storing 316 its redirServiceProvider record if n.id is the lowest or highest 317 Node-ID in the interval. Node n MUST end this downward walk when 318 it reaches a level at which it is the only service provider in 319 the interval. 321 4.4. Refreshing Registrations 323 All state in the ReDiR tree is soft. If an entry (Node-ID) is not 324 refreshed for redirRefreshPeriod seconds, it MUST be dropped from the 325 dictionary by the peer storing the tree node. redirRefreshPeriod is a 326 new element in the RELOAD overlay configuration document (see 327 Section 8). Every service provider MUST repeat the entire 328 registration process periodically until it leaves the RELOAD Overlay 329 Instance. 331 Note that no new mechanisms are needed to keep track of the remaining 332 lifetime of RedirServiceProvider records. The 'storage_time' and 333 'lifetime' fields of RELOAD's StoredData structure can be used for 334 this purpose in the usual way. 336 4.5. Service Lookups 338 The purpose of a service lookup on identifier k in namespace ns is to 339 find the node that has joined ns whose identifier most immediately 340 follows identifier k. 342 A service lookup is similar to the registration operation. The 343 service lookup starts from some level level=Lstart (see Section 4.2 344 for the details on selecting the starting level). At each step, the 345 node n wishing to discover a service provider MUST fetch the current 346 interval I(level,n.id) using a RELOAD Fetch request and MUST 347 determine where to look next as follows: 349 1. If the successor of node n is not present in the tree node 350 associated with I(level,n.id), then its successor must occur in a 351 larger range of the keyspace. Node n MUST set level=level-1 and 352 try again. 353 2. If n.id is sandwiched between two Node-IDs in I(level,n.id), the 354 successor must lie somewhere in I(level,n.id). Node n MUST set 355 level=level+1 and repeat. 356 3. Otherwise, there is a Node-ID s stored in the node associated 357 with I(level,n.id) whose identifier succeeds n.id, and there are 358 no Node-IDs between n.id and s. Thus, s must be the closest 359 successor of n.id, and the lookup is done. 361 4.6. Removing Registrations 363 Before leaving the RELOAD Overlay Instance, a service provider MUST 364 remove the redirServiceProvider records it has stored by storing 365 "nonexistent" values in their place, as described in 366 [I-D.ietf-p2psip-base]. 368 5. Access Control Rules 370 As specified in RELOAD base [I-D.ietf-p2psip-base], every kind which 371 is storable in an overlay must be associated with an access control 372 policy. This policy defines whether a request from a given node to 373 operate on a given value should succeed or fail. Usages can define 374 any access control rules they choose, including publicly writable 375 values. 377 ReDiR requires an access control policy that allows multiple nodes in 378 the overlay read and write access to the ReDiR tree nodes stored in 379 the overlay. Therefore, none of the access control policies 380 specified in RELOAD base [I-D.ietf-p2psip-base] is sufficient. 382 This document defines a new access control policy, called NODE-ID- 383 MATCH. In this policy, a given value MUST be written and overwritten 384 only if the the request is signed with a key associated with a 385 certificate whose Node-ID is equal to the dictionary key. In 386 addition, the Node-ID MUST belong to one of the two intervals 387 associated with the tree node. Finally, H(namespace,level,node), 388 where namespace, level, and node are taken from the 389 RedirServiceProvider structure being stored, MUST be equal to the 390 Resource-ID for the resource. The NODE-ID-MATCH policy may only be 391 used with dictionary types. 393 6. REDIR Kind Definition 395 This section defines the REDIR kind. 397 Name 398 REDIR 400 Kind IDs 401 The Resource Name for the REDIR Kind-ID is created by 402 concatenating three pieces of information: service name, level, 403 and node number. Service name is a string identifying a service, 404 such as "voice-mail". Level is an integer specifying a level in 405 the ReDiR tree. Node number is an integer identifying a ReDiR 406 tree node at a specific level. The data stored is a 407 RedirServiceProvider structure that was defined in Section 4.1. 409 Data Model 410 The data model for the REDIR Kind-ID is dictionary. The 411 dictionary key is the Node-ID of the service provider. 413 Access Control 414 The access control policy for the REDIR kind is the NODE-ID-MATCH 415 policy that was defined in Section 5. 417 7. Example 419 Figure 2 shows an example of a ReDiR tree containing information 420 about four different service providers whose Node-IDs are 2, 3, 4, 421 and 7. Initially, the ReDiR tree is empty. 423 Level 0 ____2_3_________7_|__________________ 424 | | 425 Level 1 ____2_3_|_4_____7 ________|________ 426 | | | | 427 Level 2 ___|2_3 4__|__7 ___|___ ___|___ 428 | | | | | | | | 429 Level 3 _|_ _|3 4|_ _|_ _|_ _|_ _|_ _|_ 431 Figure 2: Example of a ReDiR tree 433 First, peer 2 whose Node-ID is 2 joins the namespace. Since this is 434 the first registration peer 2 performs, peer 2 sets the starting 435 level Lstart to 2, as was described in Section 4.2. Also all other 436 peers in this example will start from level 2. Peer 2 stores a 437 RedirServiceProvider record containing its Node-ID in the tree node 438 associated with interval I(2,2). Peer 2 also fetches the contents of 439 that tree node from the overlay. Since peer 2's Node-ID is the only 440 Node-ID stored in the interval, peer 2 continues up the tree. In 441 fact, peer 2 continues up in the tree all the way to the root 442 inserting its own Node-ID in all levels since the tree is empty. As 443 described in Section 4.3, peer 2 also walks down the tree. The 444 downward walk peer 2 does ends at level 2 since peer 2 is the only 445 node in its interval at that level. 447 The next peer to join the namespace is peer 3, whose Node-ID is 3. 448 Peer 3 starts from level 2. At that level, peer 3 stores its Node-ID 449 in the same interval I(2,3) that already contains the Node-ID of peer 450 2. Since peer 3 has the numerically highest Node-ID in the interval, 451 it continues up the tree. Peer 3 stores its node-ID also at levels 1 452 and 0 since its Node-ID is numerically highest among the Node-IDs 453 stored in the tree nodes it fetches. Peer 3 also does a downward 454 walk which starts from level 2 (i.e., the starting level). Since 455 peer 3 is not the only node in interval I(2,3), it continues down the 456 tree to level 3. The downward walk ends at this level since peer 3 457 is the only entry in the interval I(3,3). 459 The third peer to join the namespace is peer 7, whose Node-ID is 7. 460 Like the two earlier peers, also peer 7 starts from level 2 because 461 this is the first registration it performs. Peer 7 stores its 462 RedirServiceProvider record at level 2. At level 1, peer 7 has the 463 numerically highest Node-ID (because it is the only node in interval 464 I(1,7); peers 2 and 3 are stored in the same tree node but in a 465 different interval) and therefore it stores its Node-ID in the tree 466 node associated with interval I(1,7). Peer 7 also has the 467 numerically highest Node-ID in the interval I(0,7) associated with 468 its Node-ID at level 0. Peer 7 also does a downward walk, which ends 469 at level 2 because peer 7 is the only node in its interval at that 470 level. 472 The final peer to join the ReDiR tree is peer 4, whose Node-ID is 4. 473 Peer 4 starts by storing its RedirServiceProvider record at level 2. 474 Since it is the only peer associated with interval I(2,4), it 475 continues up in the tree to level 1. At level 1, peer 4 stores its 476 record in the tree node associated with interval I(1,4) because it 477 has the numerically lowest Node-ID in that interval. Next, peer 4 478 continues to the root level. At the root level, there are other 479 peers having higher and lower Node-IDs than peer 4 in interval 480 I(0,4). Therefore, peer 4 does not store a RedirServiceProvider 481 record at the tree node associated with the interval I(0,4). Peer 4 482 also does a downward walk starting from level 2. The downward walk 483 stops at level 3 because peer 4 is the only peer in the interval 484 I(3,4). 486 8. Overlay Configuration Document Extension 488 This document extends the RELOAD overlay configuration document by 489 adding two new elements inside each "configuration" element. 491 redirBranchingFactor: The branching factor of the ReDir tree. The 492 default value is 10. 494 redirRefreshPeriod: The interval at which a service provider needs 495 to repeat the ReDiR registration process. 497 9. Security Considerations 499 There are no new security considerations introduced in this document. 500 The security considerations of RELOAD [I-D.ietf-p2psip-base] apply. 502 10. IANA Considerations 504 10.1. Access Control Policies 506 This document introduces one additional access control policy to the 507 "RELOAD Access Control Policy" Registry: 509 NODE-ID-MATCH 511 This access control policy was described in Section 5. 513 10.2. Data Kind-ID 515 This document introduces one additional data kind-ID to the "RELOAD 516 Data Kind-ID" Registry: 518 +--------------+------------+----------+ 519 | Kind | Kind-ID | RFC | 520 +--------------+------------+----------+ 521 | REDIR | 104 | RFC-AAAA | 522 +--------------+------------+----------+ 524 This kind-ID was defined in Section 6. 526 11. References 528 11.1. Normative References 530 [I-D.ietf-p2psip-base] 531 Jennings, C., Lowekamp, B., Rescorla, E., Baset, S., and 532 H. Schulzrinne, "REsource LOcation And Discovery (RELOAD) 533 Base Protocol", draft-ietf-p2psip-base-06 (work in 534 progress), November 2009. 536 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 537 Requirement Levels", BCP 14, RFC 2119, March 1997. 539 11.2. Informative References 541 [I-D.ietf-p2psip-concepts] 542 Bryan, D., Matthews, P., Shim, E., Willis, D., and S. 543 Dawkins, "Concepts and Terminology for Peer to Peer SIP", 544 draft-ietf-p2psip-concepts-02 (work in progress), 545 July 2008. 547 [Redir] Rhea, S., Godfrey, P., Karp, B., Kubiatowicz, J., 548 Ratnasamy, S., Shenker, S., Stoica, I., and H. Yu, "Open 549 DHT: A Public DHT Service and Its Uses". 551 Authors' Addresses 553 Jouni Maenpaa 554 Ericsson 555 Hirsalantie 11 556 Jorvas 02420 557 Finland 559 Email: Jouni.Maenpaa@ericsson.com 561 Gonzalo Camarillo 562 Ericsson 563 Hirsalantie 11 564 Jorvas 02420 565 Finland 567 Email: Gonzalo.Camarillo@ericsson.com