idnits 2.17.1 draft-zangrilli-p2psip-dsip-dhtbamboo-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 15. -- Found old boilerplate from RFC 3978, Section 5.5, updated by RFC 4748 on line 661. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 672. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 679. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 685. 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 : ---------------------------------------------------------------------------- -- The document has examples using IPv4 documentation addresses according to RFC6890, but does not use any IPv6 documentation addresses. Maybe there should be IPv6 examples, too? Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust Copyright Line does not match the current year -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (February 25, 2007) is 6270 days in the past. Is this intentional? 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 (-04) exists of draft-willis-p2psip-concepts-03 ** Downref: Normative reference to an Informational draft: draft-willis-p2psip-concepts (ref. 'I-D.willis-p2psip-concepts') ** Downref: Normative reference to an Informational RFC: RFC 2104 ** Downref: Normative reference to an Informational RFC: RFC 3174 Summary: 4 errors (**), 0 flaws (~~), 2 warnings (==), 8 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 P2PSIP M. Zangrilli 3 Internet-Draft D. Bryan 4 Intended status: Standards Track SIPeerior Technologies 5 Expires: August 29, 2007 February 25, 2007 7 A Bamboo-based DHT for Resource Lookup in P2PSIP 8 draft-zangrilli-p2psip-dsip-dhtbamboo-00 10 Status of this Memo 12 By submitting this Internet-Draft, each author represents that any 13 applicable patent or other IPR claims of which he or she is aware 14 have been or will be disclosed, and any of which he or she becomes 15 aware will be disclosed, in accordance with Section 6 of BCP 79. 17 Internet-Drafts are working documents of the Internet Engineering 18 Task Force (IETF), its areas, and its working groups. Note that 19 other groups may also distribute working documents as Internet- 20 Drafts. 22 Internet-Drafts are draft documents valid for a maximum of six months 23 and may be updated, replaced, or obsoleted by other documents at any 24 time. It is inappropriate to use Internet-Drafts as reference 25 material or to cite them other than as "work in progress." 27 The list of current Internet-Drafts can be accessed at 28 http://www.ietf.org/ietf/1id-abstracts.txt. 30 The list of Internet-Draft Shadow Directories can be accessed at 31 http://www.ietf.org/shadow.html. 33 This Internet-Draft will expire on August 29, 2007. 35 Copyright Notice 37 Copyright (C) The IETF Trust (2007). 39 Abstract 41 This document describes how a structured peer-to-peer algorithm is 42 used for resource lookup by a P2PSIP Peer Protocol. Specifically, 43 this work describes how to integrate a DHT based on Bamboo with dSIP, 44 a proposed P2PSIP Peer Protocol. This document extends the dSIP 45 draft to provide one possible implementation of a pluggable DHT 46 algorithm. 48 This is early work to demonstrate how alternative DHT algorithms can 49 be plugged into the dSIP protocol. Where appropriate, we compare the 50 Bamboo DHT implementation to the Chord DHT implementation. 52 Table of Contents 54 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 55 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 56 2.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 3 57 3. Background . . . . . . . . . . . . . . . . . . . . . . . . . . 4 58 3.1. Bamboo . . . . . . . . . . . . . . . . . . . . . . . . . . 4 59 4. Routing Table and Connection Table . . . . . . . . . . . . . . 4 60 4.1. Leaf Set . . . . . . . . . . . . . . . . . . . . . . . . . 5 61 4.2. Bamboo Routing Table . . . . . . . . . . . . . . . . . . . 5 62 4.3. Message Routing . . . . . . . . . . . . . . . . . . . . . 5 63 5. Message Syntax . . . . . . . . . . . . . . . . . . . . . . . . 6 64 5.1. The DHT-PeerID Header . . . . . . . . . . . . . . . . . . 6 65 5.1.1. Hash Algorithms . . . . . . . . . . . . . . . . . . . 6 66 5.1.2. DHT Name Parameter . . . . . . . . . . . . . . . . . . 6 67 5.2. The DHT-Link Header . . . . . . . . . . . . . . . . . . . 6 68 5.2.1. The linktype and depth values . . . . . . . . . . . . 7 69 6. Bamboo Overlay Algorithm . . . . . . . . . . . . . . . . . . . 7 70 6.1. Bamboo Routing Table and Leaf set . . . . . . . . . . . . 7 71 6.2. Starting a New Overlay . . . . . . . . . . . . . . . . . . 8 72 6.3. Peer Admission . . . . . . . . . . . . . . . . . . . . . . 8 73 6.3.1. Constructing a Peer Registration . . . . . . . . . . . 9 74 6.3.2. Processing and Routing the Peer Registration . . . . . 9 75 6.3.3. Admitting the Joining Peer . . . . . . . . . . . . . . 9 76 6.4. Bamboo Query Processing . . . . . . . . . . . . . . . . . 10 77 6.5. Graceful Leaving . . . . . . . . . . . . . . . . . . . . . 11 78 6.6. DHT Maintenance . . . . . . . . . . . . . . . . . . . . . 11 79 6.6.1. leaf set maintenance . . . . . . . . . . . . . . . . . 11 80 6.6.2. Bamboo routing table maintenance . . . . . . . . . . . 11 81 6.7. Peer Failure . . . . . . . . . . . . . . . . . . . . . . . 12 82 6.8. Resource Replicas . . . . . . . . . . . . . . . . . . . . 12 83 7. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 84 8. Security Considerations . . . . . . . . . . . . . . . . . . . 12 85 9. Open Issues . . . . . . . . . . . . . . . . . . . . . . . . . 12 86 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 13 87 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 13 88 11.1. Normative References . . . . . . . . . . . . . . . . . . . 13 89 11.2. Informative References . . . . . . . . . . . . . . . . . . 14 90 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 14 91 Intellectual Property and Copyright Statements . . . . . . . . . . 15 93 1. Introduction 95 2. Terminology 97 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 98 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 99 document are to be interpreted as described in RFC 2119 [RFC2119]. 101 Terminology defined in RFC 3261 [RFC3261] is used without definition. 103 We use the terminology and definitions from the dSIP: A P2P Approach 104 to SIP Registration and Resource Location [I-D.bryan-p2psip-dsip] and 105 the Concepts and Terminology for Peer to Peer SIP 106 [I-D.willis-p2psip-concepts] drafts extensively in this document. 107 Other terms relating to P2P or new to this document are defined when 108 used and are also defined in Definitions (Section 2.1). We suggest 109 reviewing these drafts and the Definitions (Section 2.1) section 110 before reading the remainder of this document.. 112 In many places in this document, 10 hexadecimal digit values are used 113 in examples as SHA-1 hashes. In reality, these hashes are 40 digit. 114 They are shortened in this document for clarity only. 116 2.1. Definitions 118 Please also see the dSIP: A P2P Approach to SIP Registration and 119 Resource Location [I-D.bryan-p2psip-dsip] draft and the P2PSIP 120 concepts and terminology [I-D.willis-p2psip-concepts] draft for 121 additional terminology. We do not redefine terms from that draft 122 here. 123 Bamboo: A particular algorithm/approach to implementing a DHT that 124 is described by Rhea et al. [Bamboo] Bamboo uses a circular 125 arrangement for the namespace and stores resources with 126 Resource-ID k at the peer with Peer-ID that is numerically closest 127 to k. 128 Bamboo routing table: Tree-based structure containing peer 129 information (Peer-ID and location). Each row of the table, l, 130 contains peers whose Peer-IDs match its own Peer-ID in exactly l 131 digits. The columns in the row represent the values for the (l+1) 132 digit. A peer that has the same digit prefix (l) as its own 133 Peer-ID and whose (l+1) digit is i, will be stored at row l, 134 column i in its routing table. 135 Chord: A particular algorithm/approach to implementing a DHT, 136 described by Stoica et al. [Chord]. Uses a circular arrangement 137 for the namespace. 139 leaf set: A set of peers immediately preceding and following the 140 peer in the circular namespace. 141 Predecessor Peer: Refers to a peer directly before a particular peer 142 in the address space. This does not mean that the predecessor's 143 Peer-ID is one less than the peer, it simply means that there are 144 no other peers in the namespace between the peer and the 145 predecessor peer. 146 Successor Peer: Refers to a peer directly after a particular peer in 147 the address space. This does not mean that the successor peer's 148 Peer-ID is one more that that peer, rather there are no other 149 peers in the namespace between that peer and the successor peer. 150 Note that the first peer in a finger table is typically also the 151 first successor peer. 153 3. Background 155 3.1. Bamboo 157 Bamboo [Bamboo] is one particular DHT algorithm that, like the Chord 158 DHT [Chord], conceptualizes the namespace as a circle, meaning the 159 peer with Peer-ID is located next to the peer with largest possible 160 Peer-ID in the namespace. Unlike Chord, Bamboo uses prefix routing 161 to converge on the peer responsible for the search key. In Bamboo 162 resources are stored by the peer with the closest numerical Peer-ID 163 to their Resource-ID. Note this differs from the Chord [Chord] 164 approach where resources are stored by the first peer with Peer-ID 165 equal or greater than the the Resource-ID. Each Resource-ID is the 166 responsibility of some peer in the overlay, though the responsible 167 peer may change as peers enter and leave the overlay. 169 4. Routing Table and Connection Table 171 Each peer keeps information about how to contact some number of other 172 peers in the overlay. In terms of the overlay network, these are the 173 neighbors of the peer, since they are reachable in one hop. In 174 Bamboo, the peer keep tracks of a leaf set containing one or more of 175 its immediate predecessor peers, as well as one or more successor 176 peers. The peer also keeps a table of information about other 177 neighbors called a Bamboo routing table. 179 Note we use routing table as defined in the dSIP draft and Bamboo 180 routing table as the specific structure of peers stored for routing 181 use in the Bamboo DHT. The routing table, as defined by dSIP, is a 182 union of the leaf set and the Bamboo routing table. 184 4.1. Leaf Set 186 Each peer maintains a leaf set, or set of peers immediately preceding 187 and following the peer in the circular namespace. Half of the leaf 188 set contains the peers with numerically closest Peer-ID that are 189 smaller than this peer's own Peer-ID. The other half of the leaf set 190 contains the peers with numerically closest Peer-IDs that are larger 191 than this peer-s own Peer-ID. 193 The leaf set is a similar concept to Chord's predecessor and 194 successor peers. See Section Definitions (Section 2.1). The peers 195 in the leaf set may be called successors or predecessor in the 196 remainder of this document. 198 4.2. Bamboo Routing Table 200 Each peer also maintains a Bamboo routing table. Bamboo routing 201 tables treat each identifier as a sequence of digits of base 2^b. 202 Each row l of the Bamboo routing table stores peers with Peer-IDs 203 that share the first l digits with its own peer-ID. The columns in 204 each row represent the different values possible for the l+1st digit. 206 More than one peer may be an appropriate fit for each Bamboo routing 207 table entry, and entries may be chosen based on network proximity or 208 other factors. The choice of which peer to use for each entry is 209 left up to each implementation. As an example, the peer with the 210 smallest latency will fill the routing table spot whenever possible. 212 4.3. Message Routing 214 Bamboo uses prefix routing. Messages are routed such that each hop 215 will results in a peer that either shares a larger prefix with the ID 216 being searched for or shares the same length prefix as the previous 217 hop's Peer-ID, but the new peer's Peer-ID is numerically closer to 218 the ID than the previous hop's Peer-ID. 220 To route a message to a particular ID, the peer first looks to see 221 any of the peers in its leaf set are responsible for the ID. If the 222 ID lies within the leaf set, the message is routed to the appropriate 223 leaf set peer. If the ID is not within the leaf set, the searching 224 peer computes the length l of the longest matching prefix between the 225 search ID and it's own peer-ID. The peer then looks in its Bamboo 226 routing table at row l. If there is an entry in that row 227 corresponding to the l length prefix of the ID being searched for, 228 then the message is forwarded on to that peer. If that Bamboo 229 routing table entry is empty, the message is routed to the peer in 230 its leaf set with the peer-ID that is numerically closest to the ID 231 being searched for. 233 5. Message Syntax 235 5.1. The DHT-PeerID Header 237 The routing algorithms used to implement the overlay is specified in 238 the dht-param parameter in the DHT-PeerID header. The format of the 239 DHT-PeerID header is defined in the dSIP [I-D.bryan-p2psip-dsip] 240 draft. 242 5.1.1. Hash Algorithms 244 Implementations MUST support the SHA-1 [RFC3174] algorithm, which 245 produces a 160 bit hash value. An implementation MAY rely on a 246 secret initialization vector, key, or other shared secret to use the 247 identifier as an HMAC, from from RFC 2104 [RFC2104] such that no peer 248 may join the overlay without knowledge of the shared secret, however 249 this technique by itself does not protect the overlay against replay 250 attacks. Security Extensions to dSIP 251 [I-D.lowekamp-p2psip-dsip-security] provides information on how to 252 protect against replay attacks and hash algorithms defined in that 253 draft MAY be used in Chord implementations. 255 5.1.2. DHT Name Parameter 257 For this protocol, the dht-param token MUST be set to "Bamboo1.0". 259 A peer receiving a message with a dht-param other than "Bamboo1.0" 260 SHOULD reject the message and return a 488 Not Acceptable Here 261 response message. 263 Examples: 264 A peer with an SHA-1 hashed Peer-ID of a04d371e24 on IP 192.0.2.1. 265 We include the required algorithm, and overlay as well as the 266 optional expires header parameter. 268 DHT-PeerID: ;algorithm=sha1; 269 dht=Bamboo1.0;overlay=chat;expires=600 271 5.2. The DHT-Link Header 273 The DHT-Link header is used to transfer information about where in 274 the DHT other peers are located. In particular, it is used by peers 275 to pass information about the leaf set peers and Bamboo routing table 276 information stored by a peer. 278 The linktype and depth values are dependent on the DHT routing 279 algorithm employed by the peer. We define a linktype-token and 280 depth-token in the DHT-Link Header to be used by peers implementing 281 the Bamboo1.0 DHT algorithm. 283 link-value = linktype-token depth-token 284 linktype-token = "P" / "S" / "R" / other-token 285 depth-token = 1*DIGIT 287 and an example, the header might look like (using a shortened digit 288 Peer-ID for clarity): 290 DHT-Link: ;link=R1;expires=600 292 5.2.1. The linktype and depth values 294 The linktype MUST be one of three single characters, "S", "P" or "R". 295 "S" MUST be used to indicate that the information provided describes 296 a successor, a peer in the leaf set that immediately follows the 297 sending peer in the circular namespace. "P" MUST be used to indicate 298 that the information provided describes a peer in the leaf set that 299 immediately precedes the sending peer in the circular namespace. "R" 300 MUST indicate that the information describes a peer in the sending 301 peer's routing table. 303 The depth MUST be a non-negative integer representing which leaf set 304 peer or routing table entry is being described. For leaf set peers, 305 this depth value MUST indicate numeric depth. In other words, "S1" 306 indicates the first succeeding peer in the circular namespace, while 307 "P3" would indicate the third preceding peer in the circular 308 namespace. "S0" or "P0" would indicate the sending peer itself. In 309 the case of the routing table entries, the depth MUST indicate the 310 level/row of the routing table. The routing table level is designed 311 so that the level represents the number of digits (digit prefix) the 312 routing table entry has in common with the sending peer. For 313 example, "R1" would correspond to a routing table entry that shares a 314 one-digit prefix with the sending peer, while "R3" would indicate a 315 routing table entry that shares a three-digits prefix with the 316 sending peer. 318 6. Bamboo Overlay Algorithm 320 6.1. Bamboo Routing Table and Leaf set 322 Bamboo routing tables treat each identifier as a sequence of digits 323 of base 2^b. For a namespace of N, there are log_(2^b)(N) rows in a 324 Bamboo routing table and each row should contain 2^b-1 entries. We 325 use "l" to indicate the number of rows. The row number corresponds 326 to the number of digits that match its own identifier ( row 0 would 327 have no matching prefix, row 1 would have peers that have the same 328 first digit...). 330 In order to be compatible with our hashing and security schemes, we 331 use 160 bit identifiers, meaning our namespace N is of size 2^160. 332 Additionally, we choose to use hexadecimal values, meaning our b is 333 4, since 2^b or 2^4=16. Solving for the number rows in the Bamboo 334 routing table, " l", we have the following. Note that in our 335 notation, log_n means log base n, and lg is assumed to be log base 2, 336 or log_2: 338 l = log_(2^b) (N) 340 Using the property that log_n x = lg n / lg x we have: 342 l = [lg N] / [lg 2^b] 344 Plugging in and solving we have: 346 l = [lg (2^160)] / [lg 16] 347 l = 160 / 4 348 l = 40 350 Leaf sets in Bamboo store peers that immediately precede or follow 351 the current peer in the circular namespace. The leaf set MUST 352 contain at least one peer that immediately precedes the current peer 353 and one peer that follows the current peer, but it SHOULD contain 2^b 354 total peers in the leaf set (half for peers preceding and half for 355 peers following the current peer in the namespace). 357 6.2. Starting a New Overlay 359 A peer starting an overlay for the first time need not do anything 360 special in order to construct the overlay. The peer MUST initialize 361 its leaf set and routing table such that all entries are NULL. 363 6.3. Peer Admission 365 A peer that wishes to join an overlay (called the joining peer), 366 constructs a Peer Registration message and sends it to the bootstrap 367 peer. The Peer Registration is routed to the admitting peer, which 368 is the peer that is currently responsible for the joining peer's 369 portion of the overlay. 371 6.3.1. Constructing a Peer Registration 373 To initiate the joining process, the joining peer constructs a Peer 374 Registration and sends it to the bootstrap peer. The joining peer 375 MUST construct the Peer Registration according the rules outlined in 376 the dSIP [I-D.bryan-p2psip-dsip] draft. The registering peer MUST 377 provide a DHT-PeerID header field in the Peer Registration message. 378 It MAY leave the overlay parameter set to "*" for its initial 379 registration message, but MUST set this parameter to the name of the 380 overlay it is joining as soon as it receives a response from the 381 bootstrap peer. The dht-param parameter in the DHT-PeerID header 382 MUST be set to "*" or "Bamboo1.0", as specified in Section DHT Name 383 Parameter (Section 5.1.2). 385 Assume that a peer running on IP address 192.0.2.2 on port 5060 386 attempts to join the network by contacting a bootstrap peer at 387 address 192.0.2.129. Further assume that 192.0.2.2:5060 hashes to 388 463ac4b449 under SHA-1 (using a 10 digit hash for example 389 simplicity), and that the overlay name is chat. An example message 390 would look like this (neglecting tags): 392 REGISTER sip:192.0.2.129 SIP/2.0 393 To: 394 From: 395 Contact: 396 Expires: 600 397 DHT-PeerID: ;algorithm=sha1; 398 dht=Bamboo1.0;overlay=chat;expires=600 399 Require: dht 400 Supported: dht 402 6.3.2. Processing and Routing the Peer Registration 404 The Peer Registration is processed and routed according the rules 405 outlined in the dSIP [I-D.bryan-p2psip-dsip] draft. 407 6.3.3. Admitting the Joining Peer 409 The admitting peer recognizes that it is presently responsible for 410 this region of the hash space -- that is, it is currently the peer 411 storing the information that the joining peer will eventually be 412 responsible for. The admitting peer knows this because the joining 413 peer's Peer-ID is numerically closest to its own Peer-ID; the 414 admitting peer does not have a Bamboo routing table entry or leaf set 415 peer with a longer shared prefix or with a numerically closer Peer-ID 416 than its own Peer-ID. The admitting peer is responsible for helping 417 the joining peer become a member of the overlay. 419 When handling a Peer Registration, the admitting peer MUST reply with 420 a 200 response if the admitting peer's Peer-ID has the longest shared 421 prefix and is numerically closest to the joining peer's peer-ID as 422 compared to all the peers in its leaf set and Bamboo routing table. 424 The admitting peer MUST verify that the joining peer's Peer-ID is 425 valid. If the joining peer's credentials are not valid, the message 426 should be rejected with a response of 493 Undecipherable. In 427 addition to verifying that the joining peer's Peer-ID is valid, the 428 admitting peer MAY require an authentication challenge to the 429 REGISTER message. Once any challenge has been met, the admitting 430 will reply with a 200 OK message to the joining peer. As in a 431 traditional registration, the Contact in the 200 OK will be the same 432 as in the request, and the expiry time MUST be provided. 434 The 200 response that is constructed MUST provide information about 435 the admitting peer's leaf set peers in the DHT-Link headers of the 436 200 response. This enables the joining peer to initialize its own 437 leaf set and fill any appropriate entries in its Bamboo routing 438 table. These MUST be placed in DHT-Link headers, as described in the 439 The DHT-Link Header (Section 5.2) section of this document. If the 440 immediate preceding peer is not NULL, it MUST be transmitted in a 441 DHT-Link header using a type of "P" and a depth of 1. It MUST be 442 omitted if NULL. If the immediate following peer is not NULL, it 443 must be transmitted in a DHT-Link header using a type of "S" and 444 depth of 1. It MUST be omitted if NULL. The 200 or 404 MUST contain 445 the other leaf set peers, again only if they are not NULL. 446 Additionally, the replying peer MUST include its DHT-PeerID header. 448 The admitting peer MUST add the joining peer to its leaf set and the 449 joining peer MUST add the admitting peer to its leaf set. The 450 joining peer MAY use the leaf set information to fill in entries in 451 its Bamboo routing table. 453 [To Do: Add example of 200 response to Peer Registration.] 455 6.4. Bamboo Query Processing 457 A reply that is constructed to a query by the responsible peer MUST 458 provide information about the responding peer's Bamboo routing table 459 entries. These MUST be placed in in the DHT-Link headers of the 200 460 or 404 message. The admitting peer calculates the shared prefix, l, 461 between it's Peer-ID and the joining peer's Peer-ID. The admitting 462 peer MUST place all non NULL Bamboo routing table entries in row l of 463 its Bamboo routing table in DHT-Link headers of type R, as described 464 in the The DHT-Link Header (Section 5.2) section. Additionally, the 465 replying peer MUST include its DHT-PeerID header. 467 6.5. Graceful Leaving 469 Peers MUST send their resource registrations to their successor or 470 predecessor before leaving the overlay. Additionally, peers MUST 471 unregister themselves with their leaf set peers. This unregister 472 message is constructed exactly the same as the Peer Registration 473 message used to join, with the following exceptions. The expires 474 parameter or header MUST be provided, and MUST be set to 0. 476 6.6. DHT Maintenance 478 In order to keep the overlay stable, peers must periodically perform 479 book keeping operations to take into account peer failures. 480 Periodically (we suggest 60-360 seconds), peers MUST perform leaf set 481 and Bamboo routing table maintenance. 483 6.6.1. leaf set maintenance 485 Every maintenance period, a peer must exchange its leaf set 486 information with a randomly chosen peer in the leaf set. After 487 choosing the peer from the leaf set, the peer MUST send a Peer 488 Registration to the selected peer, structured as if the peer had just 489 entered the system. The message MUST include the sending peer's leaf 490 set information transmitted in the DHT-Link headers using a type of 491 "S" and "P", as described above in the The DHT-Link Header 492 (Section 5.2) section. Additionally, the sending peer MUST include 493 its DHT-PeerID header. 495 The response MUST include the responding peer's leaf set information 496 transmitted in the DHT-Link headers using a type of "S" and "P", as 497 described above. The response MUST also include the DHT-PeerID of 498 the responding peer. 500 Both peers should examine the DHT-Link Headers in the response and 501 verify that the leaf set information is consistent with each others 502 leaf set. If there are any inconsistencies, the peers SHOULD attempt 503 to update their leaf sets by contacting the peers in question. 505 6.6.2. Bamboo routing table maintenance 507 Every maintenance period, a peer MUST perform an arbitrary query for 508 to update one of its Bamboo routing entries. Each routing table 509 entry is specified by the l shared prefix with the peer and the 510 unique l+1st digit. During maintenance, the peer performs a peer 511 query for a Peer-ID that contains the l prefix and l+1st digit of the 512 chosen routing table entry with all other digits random. 514 The responding peer MUST provide information about its Bamboo routing 515 table entries in the 200 or 404 response. The responding peer 516 calculates the shared prefix, l, between it's Peer-ID and the sending 517 peer's Peer-ID. The responding peer MUST place all non NULL Bamboo 518 routing table entries in row l of its Bamboo routing table in DHT- 519 Link headers of type R, as described in the The DHT-Link Header 520 (Section 5.2) section. Additionally, the responding peer MUST 521 include its DHT-PeerID header. 523 The sending peer uses the information in the response to update its 524 Bamboo routing table information. If the peer in the DHT-PeerID is a 525 closer peer than the existing entry in the Bamboo routing table, the 526 existing entry MUST be replaced by the peer in the DHT-PeerID. The 527 peers listed in the DHT-Link Headers MAY be used to fill any empty 528 Bamboo routing table holes, but these SHOULD be contacted directly 529 before adding to the table. 531 6.7. Peer Failure 533 Peer failure is handled by the periodic DHT Maintenance and responses 534 to failed requests discussed above. Redundancy prevents against lost 535 registrations. 537 6.8. Resource Replicas 539 When a resource is registered, the registering peer SHOULD create at 540 least 2 redundant replicas to ensure the registry information is 541 secure in the DHT. The registering peer is responsible for 542 maintaining these replicas along with the primary entry. 544 7. Examples 546 [To Do: Add examples here] 548 8. Security Considerations 550 There are no new security considerations introduced in this draft 551 beyond those already mentioned in the dSIP [I-D.bryan-p2psip-dsip] 552 and Security for P2PSIP [I-D.lowekamp-p2psip-dsip-security] drafts. 554 9. Open Issues 556 As this is preliminary work on how to integrate the Bamboo DHT with 557 dSIP, there are many issues that are yet to be resolved. 559 The reliability of the system depends in part on keeping the leaf 560 sets updated and exchanging leaf set information between peers. 561 Peers should be skeptical of information about peer arrival or 562 departures and should verify information by directly contacting 563 peers. However, should it be possible for one peer to trigger 564 another peer to update their information? 566 The number of bits in each Peer-ID is large (160 if using SHA-1) and 567 messages include the Peer-IDs in DHT-PeerID and DHT-Link headers. In 568 Bamboo, each routing table row has the same prefix length (just 569 different digits after the prefix are stored in each row). When 570 routing table information is sent in DHT-Link headers, can we 571 eliminate the prefix of each Peer-ID? This would certainly help 572 reduce the message size, but needs to be explored more. 574 10. IANA Considerations 576 This document defines the valid "link-value" values, and defines the 577 "dht-param" value to be "Bamboo1.0". 579 11. References 581 11.1. Normative References 583 [I-D.bryan-p2psip-dsip] 584 Bryan, D., Lowekamp, B., and C. Jennings, "dSIP: A P2P 585 Approach to SIP Registration and Resource Location", 586 Internet Draft draft-bryan-p2psip-dsip-00, February 2007. 588 [I-D.lowekamp-p2psip-dsip-security] 589 Lowekamp, B. and J. Deverick, "Authenticated Identity 590 Extensions to dSIP", Internet 591 Draft draft-lowekamp-p2psip-dsip-security-00, 592 February 2007. 594 [I-D.willis-p2psip-concepts] 595 Willis, D., "Concepts and Terminology for Peer to Peer 596 SIP", draft-willis-p2psip-concepts-03 (work in progress), 597 October 2006. 599 [RFC2104] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed- 600 Hashing for Message Authentication", RFC 2104, 601 February 1997. 603 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 604 Requirement Levels", BCP 14, RFC 2119, March 1997. 606 [RFC3174] Eastlake, D. and P. Jones, "US Secure Hash Algorithm 1 607 (SHA1)", RFC 3174, September 2001. 609 [RFC3261] Rosenberg, J., Schulzrinne, H., Camarillo, G., Johnston, 610 A., Peterson, J., Sparks, R., Handley, M., and E. 611 Schooler, "SIP: Session Initiation Protocol", RFC 3261, 612 June 2002. 614 11.2. Informative References 616 [Bamboo] Rhea, R., Geels, D., Roscoe, T., and J. Kubiaatowicz, 617 "Handling Churn in a DHT", University of California, 618 Berkeley Technical Report UCB/CSD-03-1299 December 2003, 619 Usenix Annual Technical Conference June 2004. 621 [Chord] Stoica, I., Morris, R., Liben-Nowell, D., Karger, D., 622 Kaashoek, M., Dabek, F., and H. Balakrishnan, "Chord: A 623 Scalable Peer-to-peer Lookup Service for Internet 624 Applications", IEEE/ACM Transactions on Networking Volume 625 11, Issue 1, 17-32, Feb 2003. 627 Authors' Addresses 629 Marcia Zangrilli 630 SIPeerior Technologies 631 3000 Easter Circle 632 Williamsburg, VA 23188 633 USA 635 Phone: +1 757 565 0101 636 Email: marcia@sipeerior.com 638 David A. Bryan 639 SIPeerior Technologies 640 3000 Easter Circle 641 Williamsburg, VA 23188 642 USA 644 Phone: +1 757 565 0101 645 Email: dbryan@sipeerior.com 647 Full Copyright Statement 649 Copyright (C) The IETF Trust (2007). 651 This document is subject to the rights, licenses and restrictions 652 contained in BCP 78, and except as set forth therein, the authors 653 retain all their rights. 655 This document and the information contained herein are provided on an 656 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 657 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND 658 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS 659 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 660 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 661 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 663 Intellectual Property 665 The IETF takes no position regarding the validity or scope of any 666 Intellectual Property Rights or other rights that might be claimed to 667 pertain to the implementation or use of the technology described in 668 this document or the extent to which any license under such rights 669 might or might not be available; nor does it represent that it has 670 made any independent effort to identify any such rights. Information 671 on the procedures with respect to rights in RFC documents can be 672 found in BCP 78 and BCP 79. 674 Copies of IPR disclosures made to the IETF Secretariat and any 675 assurances of licenses to be made available, or the result of an 676 attempt made to obtain a general license or permission for the use of 677 such proprietary rights by implementers or users of this 678 specification can be obtained from the IETF on-line IPR repository at 679 http://www.ietf.org/ipr. 681 The IETF invites any interested party to bring to its attention any 682 copyrights, patents or patent applications, or other proprietary 683 rights that may cover technology that may be required to implement 684 this standard. Please address the information to the IETF at 685 ietf-ipr@ietf.org. 687 Acknowledgment 689 Funding for the RFC Editor function is provided by the IETF 690 Administrative Support Activity (IASA).