P2PSIP M. Zangrilli Internet-Draft D. Bryan Intended status: Standards Track SIPeerior Technologies Expires: August 29, 2007 February 25, 2007 A Chord-based DHT for Resource Lookup in P2PSIP draft-zangrilli-p2psip-dsip-dhtchord-00 Status of this Memo By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This Internet-Draft will expire on August 29, 2007. Copyright Notice Copyright (C) The IETF Trust (2007). Abstract This document describes how a structured peer-to-peer algorithm is used for resource lookup by a P2PSIP Peer Protocol. Specifically, this work describes how to integrate a DHT based on Chord with dSIP, a proposed P2PSIP Peer Protocol. This document extends the dSIP draft to provide one possible implementation of a pluggable DHT algorithm. Zangrilli & Bryan Expires August 29, 2007 [Page 1] Internet-Draft P2PSIP February 2007 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 4 3. Background . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.1. Chord . . . . . . . . . . . . . . . . . . . . . . . . . . 5 4. Routing Table and Connection Table . . . . . . . . . . . . . . 5 4.1. Finger Table . . . . . . . . . . . . . . . . . . . . . . . 5 4.2. Message Routing . . . . . . . . . . . . . . . . . . . . . 6 5. Message Syntax . . . . . . . . . . . . . . . . . . . . . . . . 6 5.1. The DHT-PeerID Header . . . . . . . . . . . . . . . . . . 6 5.1.1. Hash Algorithms . . . . . . . . . . . . . . . . . . . 6 5.1.2. DHT Name Parameter . . . . . . . . . . . . . . . . . . 7 5.2. The DHT-Link Header . . . . . . . . . . . . . . . . . . . 7 5.2.1. The linktype and depth values . . . . . . . . . . . . 7 6. Chord Overlay Algorithm . . . . . . . . . . . . . . . . . . . 8 6.1. Finger Table, Successors, and Predecessors . . . . . . . . 8 6.2. Starting a New Overlay . . . . . . . . . . . . . . . . . . 9 6.3. Peer Admission . . . . . . . . . . . . . . . . . . . . . . 9 6.3.1. Constructing a Peer Registration . . . . . . . . . . . 9 6.3.2. Processing and Routing the Peer Registration . . . . . 10 6.3.3. Admitting the Joining Peer . . . . . . . . . . . . . . 10 6.4. Chord Query Processing . . . . . . . . . . . . . . . . . . 12 6.5. Chord Graceful Leaving . . . . . . . . . . . . . . . . . . 12 6.6. DHT Maintenance . . . . . . . . . . . . . . . . . . . . . 13 6.6.1. Chord Finger Table Updates . . . . . . . . . . . . . . 13 6.6.2. Chord Periodic Stabilization . . . . . . . . . . . . . 13 6.7. Peer Failure . . . . . . . . . . . . . . . . . . . . . . . 13 6.8. Resource Replicas . . . . . . . . . . . . . . . . . . . . 14 7. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 7.1. Example of a Peer Registration . . . . . . . . . . . . . . 16 7.2. Example of a User Registration . . . . . . . . . . . . . . 19 7.3. Example of a Session Establishment . . . . . . . . . . . . 21 7.4. Example of Moving From Empty Overlay to Stable 3 Peer System . . . . . . . . . . . . . . . . . . . . . . . . . . 23 7.5. Example of a Peer Leaving the System . . . . . . . . . . . 44 7.6. Example of a Successful User Search . . . . . . . . . . . 44 7.7. Example of an Unsucessful User Search . . . . . . . . . . 45 8. Security Considerations . . . . . . . . . . . . . . . . . . . 45 9. Open Issues . . . . . . . . . . . . . . . . . . . . . . . . . 45 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 45 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 45 12. Changes to this Version . . . . . . . . . . . . . . . . . . . 46 13. References . . . . . . . . . . . . . . . . . . . . . . . . . . 46 13.1. Normative References . . . . . . . . . . . . . . . . . . . 46 13.2. Informative References . . . . . . . . . . . . . . . . . . 46 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 47 Zangrilli & Bryan Expires August 29, 2007 [Page 2] Internet-Draft P2PSIP February 2007 Intellectual Property and Copyright Statements . . . . . . . . . . 48 Zangrilli & Bryan Expires August 29, 2007 [Page 3] Internet-Draft P2PSIP February 2007 1. Introduction This draft describes an overlay algorithm for use by dSIP [I-D.bryan-p2psip-dsip], a proposed P2PSIP Peer Protocol. This overlay algorithm is derived from the Chord algorithm [Chord], but has been adapted to use SIP messages, as specified by dSIP, to communicate between peers in the overlay. Chord is selected because of its simplicity, convergence properties, and general familiarity within the P2P community. This work reflects experience gained in actually building a full commercially available P2PSIP product based on using a Chord-like DHT for resource location in the dSIP protocol, as well as from work/insight gleaned from the P2PSIP mailing list. 2. Terminology The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119]. Terminology defined in RFC 3261 [RFC3261] is used without definition. We use the terminology and definitions from the dSIP: A P2P Approach to SIP Registration and Resource Location [I-D.bryan-p2psip-dsip] and the Concepts and Terminology for Peer to Peer SIP [I-D.willis-p2psip-concepts] drafts extensively in this document. Other terms relating to P2P or new to this document are defined when used and are also defined in Definitions (Section 2.1). We suggest reviewing these drafts and the Definitions (Section 2.1) section before reading the remainder of this document.. In many places in this document, 10 hexadecimal digit values are used in examples as SHA-1 hashes. In reality, these hashes are 40 digit. They are shortened in this document for clarity only. 2.1. Definitions Please also see the dSIP: A P2P Approach to SIP Registration and Resource Location [I-D.bryan-p2psip-dsip] draft and the P2PSIP concepts and terminology [I-D.willis-p2psip-concepts] draft for additional terminology. We do not redefine terms from that draft here. Chord: A particular algorithm/approach to implementing a DHT, described by Stoica et al. [Chord]. Uses a circular arrangement for the namespace. Zangrilli & Bryan Expires August 29, 2007 [Page 4] Internet-Draft P2PSIP February 2007 Finger Table: The list of peers that a peer uses to send messages to. The finger table contains many entries about peers with similar IDs, and fewer entries about more remote IDs. Predecessor Peer: Refers to a peer directly before a particular peer in the address space. This does not mean that the predecessor's Peer-ID is one less than the peer, it simply means that there are no other peers in the namespace between the peer and the predecessor peer. Successor Peer: Refers to a peer directly after a particular peer in the address space. This does not mean that the successor peer's Peer-ID is one more that that peer, rather there are no other peers in the namespace between that peer and the successor peer. Note that the first peer in a finger table is typically also the first successor peer. 3. Background 3.1. Chord The Chord [Chord] system is one particular popular DHT algorithm. Chord uses a ring-type structure for the peers in the overlay. In this structure, a peer with a hash of 0 would be located adjacent to a peer that hashes to the highest possible hash value. In Chord, resource with Resource-ID k will be stored by the first peer with Peer-ID equal to or greater (mod the size of the namespace) than k, ensuring that every Resource-ID is associated with some peer. 4. Routing Table and Connection Table Each peer keeps information about how to contact some number of other peers in the overlay. In terms of the overlay network, these are the neighbors of the peer, since they are reachable in one hop. In Chord the peer keeps track of one or more of its immediate predecessor peers, as well as one or more successor peers. The peer also keeps a table of information about other neighbors called a finger table, consisting of peers distributed around the overlay. Note that dSIP defines a routing table as the set of peers that a peer knows about and uses to send messages to when routing. The routing table is the combination of the predecessor, successor and finger table. 4.1. Finger Table If the hash has 2^n bits in the range, each peer will keep a "finger table" of pointers to at most n other peers. The ith entry in the Zangrilli & Bryan Expires August 29, 2007 [Page 5] Internet-Draft P2PSIP February 2007 finger table contains a pointer to a peer at least 2^(i) units away in the hash space. The highest finger table entry thus point to a range 1/2 of the way across the hash space, the next highest 1/4, the next 1/8, and the smallest entry points to a range only 1 away in the hash space. The set of peers pointed to by these finger table entries are referred to as the neighbors of the peer, since they can be reached directly. 4.2. Message Routing Messages are routed by taking advantage of a key property of these finger tables. A peer has more detailed, fine grained information about peers near it than further away, but it knows at least a few more distant peers. When locating a a particular ID (either Resource-ID or Peer-ID), the peer will send the request to the finger table entry with the Peer-ID closest to the desired ID. Because the peer receiving the request has many neighbors with similar Peer-IDs, it will presumably know of a peer with a Peer-ID closer to the ID, and suggests this peer to in response. The request is then resent to this closer peer. The process is repeated until the peer responsible for the ID is located, which can then determine if it is storing the information. 5. Message Syntax 5.1. The DHT-PeerID Header The routing algorithms used to implement the overlay is specified in the dht-param parameter in the DHT-PeerID header. The format of the DHT-PeerID header is defined in the dSIP [I-D.bryan-p2psip-dsip] draft. 5.1.1. Hash Algorithms Implementations MUST support the SHA-1 [RFC3174] algorithm, which produces a 160 bit hash value. An implementation MAY rely on a secret initialization vector, key, or other shared secret to use the identifier as an HMAC, from from RFC 2104 [RFC2104] such that no peer may join the overlay without knowledge of the shared secret, however this technique by itself does not protect the overlay against replay attacks. Security Extensions to dSIP [I-D.lowekamp-p2psip-dsip-security] provides information on how to protect against replay attacks and hash algorithms defined in that draft MAY be used in Chord implementations. Zangrilli & Bryan Expires August 29, 2007 [Page 6] Internet-Draft P2PSIP February 2007 5.1.2. DHT Name Parameter For this protocol, the dht-param token MUST be set to "Chord1.0". A peer receiving a message with a dht-param other than "Chord1.0" SHOULD reject the message and return a 488 Not Acceptable Here response message. Examples: A peer with an SHA-1 hashed Peer-ID of a04d371e24 on IP 192.0.2.1. We include the required algorithm, and overlay as well as the optional expires header parameter. DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=600 5.2. The DHT-Link Header The DHT-Link header is used to transfer information about where in the DHT other peers are located. In particular, it is used by peers to pass information about the predecessor, successors, and finger table information stored by a peer. The linktype and depth values are dependent on the DHT routing algorithm employed by the peer. We define a linktype-token and depth-token in the DHT-Link Header to be used by peers implementing the Chord1.0 DHT algorithm. link-value = linktype-token depth-token linktype-token = "P" / "F" / "S" / other-token depth-token = 1*DIGIT and an example, the header might look like (using a shortened digit Peer-ID for clarity): DHT-Link: ;link=S1;expires=600 5.2.1. The linktype and depth values The linktype MUST be one of three single characters, P, S, or F. P MUST be used to indicate that the information provided describes a predecessor of the sending peer. S MUST indicate that the information describes a successor peer, and F MUST indicate that it is a finger table peer from the sending peer. The depth MUST be a non-negative integer representing which predecessor, successor, or finger table entry is being described. Zangrilli & Bryan Expires August 29, 2007 [Page 7] Internet-Draft P2PSIP February 2007 For predecessors and successors, this MUST indicate numeric depth. In other words, "P1" indicates the peers immediate predecessor, while "S5" would indicate the fifth successor. "P0" or "S0" would indicate the sending peer itself. In the case of finger table entries, the depth MUST indicate the exponent of the offset. Since finger tables point to ranges in the hash table that are offset from the current peer in the hash space by a power of two. That is, finger table entry i points to a range that begins with a peer 2^i away in the hash space, and there are a maximum of k finger table entries, where k is the size of the hash result in bits. For an finger table entry, the depth corresponds to this exponent i. In other words, "F0" would correspond to a finger table entry pointing to the peer for a range starting a distance 2^0 = 1 from the Peer-ID in the hash space, while "F6" would point to peer used to search for resources in a range starting 2^6 = 64 away from the Peer-ID in the hash space. 6. Chord Overlay Algorithm 6.1. Finger Table, Successors, and Predecessors Each peer MUST have keep track of at least one predecessor peer in its routing table. This predecessor peer CANNOT be set to itself, but CAN be NULL if the current peer is the only peer in the overlay. Each peer MUST also have at least one successor peer in its routing table. This successor peer can be set to itself. Peers MAY keep additional successor and predecessor information in their routing tables for reliability. Chord recommends keeping a number of finger table entries equal to the size in bits of the hash space, for example 160 for SHA-1. These entries point to the first peer at least 2^i away from the peer, for 0 <= i <= 159, mod 2^160. Essentially, the peer divides the overlay hash circle up into segments, the first being the segment from [2^0-2^1) away from the peer, the second being from [2^1-2^2), the third being from [2^2-2^3), etc., all the way to the segment from [2^158-2^159) away from peer. It then stores an entry in the finger table for the first peer with a Peer-ID greater than or equal to the start of this interval. In this way, the peer has many entries pointing to nearby peers, and less and less entries about more remote peers. These tables are populated when the peer joins the overlay, and are kept up to date by periodically updating them. We recommend that, while using the full SHA-1 hash algorithm, peers maintain less than the full 160 entries in the finger table, perhaps 16 entries for small networks, 32 for larger networks. As this affects only the efficiency of the client, it is left to the implementer to determine a useful value. Note that a client can Zangrilli & Bryan Expires August 29, 2007 [Page 8] Internet-Draft P2PSIP February 2007 easily store enough finger table entries to exceed the maximum MTU size when transmitting the full finger table. In this case, a client may need to reduce the number of finger table entries reported in DHT-Link headers. 6.2. Starting a New Overlay A peer starting an overlay for the first time need not do anything special in order to construct the overlay. The peer MUST initialize its finger table. To create the finger table, a peer MUST take its Peer-ID and, by applying the exponential offsets for each finger, calculate the Resource-IDs corresponding to the start of each finger interval. See Finger Table, Successors and Predecessors (Section 6.1) for more details. After the finger table is created, the peer MUST initialize the finger table entries such that all entries point to itself. The peer MUST set its successor to itself, and MUST set its predecessor to NULL. 6.3. Peer Admission A peer that wishes to join an overlay (called the joining peer), constructs a Peer Registration message and sends it to the bootstrap peer. The Peer Registration is routed to the admitting peer, which is the peer that is currently responsible for the joining peer's portion of the overlay. 6.3.1. Constructing a Peer Registration To initiate the joining process, the joining peer constructs a Peer Registration and sends it to the bootstrap peer. The joining peer MUST construct the Peer Registration according the rules outlined in the dSIP [I-D.bryan-p2psip-dsip] draft. The joining peer MUST provide a DHT-PeerID header field in the Peer Registration and the dht-param part of the DHT-PeerID MUST be set to "*" or the token specified in the DHT Name Parameter (Section 5.1.2) section of this document. Assume that a peer running on IP address 192.0.2.2 on port 5060 attempts to join the network by contacting a bootstrap peer at address 192.0.2.129. Further assume that 192.0.2.2 hashes to 463ac4b449 under SHA-1 (using a 10 digit hash for example simplicity), and that the overlay name is chat. An example message would look like this (neglecting tags): Zangrilli & Bryan Expires August 29, 2007 [Page 9] Internet-Draft P2PSIP February 2007 REGISTER sip:192.0.2.129 SIP/2.0 To: From: Contact: Expires: 600 DHT-PeerID: ;algorithm=sha1; dht-param=Chord1.0;overlay=chat;expires=600 Require: dht Supported: dht 6.3.2. Processing and Routing the Peer Registration The Peer Registration is processed and routed according the rules outlined in the dSIP [I-D.bryan-p2psip-dsip] draft. 6.3.3. Admitting the Joining Peer The admitting peer recognizes that it is presently responsible for this region of the hash space -- that is, it is currently the peer storing the information that the joining peer will eventually be responsible for. The admitting peer knows this because the joining peer's Peer-ID falls between the admitting peer's predecessor's Peer-ID and the admitting peer's Peer-ID. The admitting peer is responsible for helping the joining peer become a member of the overlay. When handling a Peer Registration from a joining peer, the admitting peer MUST reply with a 200 response if the joining peer has a Peer-ID between the admitting peer's predecessor's Peer-ID and the admitting Peer-ID, or the admitting peer's predecessor is NULL. In the special case where the admitting peer's predecessor is NULL (as can happen if the admitting peer is the peer that started the overlay), that peer MUST reply with a 200 response to any peer validly attempting to join the system, regardless of Peer-ID. The admitting peer MUST verify that the joining peer's Peer-ID is valid. If the joining peer's credentials are not valid, the message should be rejected with a response of 493 Undecipherable. In addition to verifying that the joining peer's Peer-ID is valid, the admitting peer MAY require an authentication challenge to the REGISTER message. Once any challenge has been met, the admitting will reply with a 200 OK message to the joining peer. As in a traditional registration, the Contact in the 200 OK will be the same as in the request, and the expiry time MUST be provided. The 200 response that is constructed MUST provide information about the admitting peer's neighbors and finger table entries in the DHT- Link headers of the 200 response. This enables the joining peer to Zangrilli & Bryan Expires August 29, 2007 [Page 10] Internet-Draft P2PSIP February 2007 initialize its neighbors and finger table entries. Additionally, the admitting peer MUST include its DHT-PeerID header containing the admitting peer's Peer-ID and IP. If the admitting peer's predecessor is not NULL, it MUST provide the joining peer with its current predecessor and successor in the 200. If the predecessor is NULL, the 200 MUST NOT include a value for the predecessor but MUST include a value for the successor. These MUST be placed placed in DHT-Link headers, as described in The DHT-Link Header (Section 5.2) section of this document. The predecessor MUST be transmitted in a DHT-Link header using a type of P and a depth of 1. The successor MUST be transmitted in a DHT-Link header using a type of S and a depth of 1. The admitting peer SHOULD send a copy of the entries in their finger table to the joining peer, using DHT-Link headers of the F type. As the joining peer will likely be nearby the admitting peer in the hash space (at least for an overlay with a reasonable number of peers), this finger table information can likely improve the performance of the queries required to obtain a correct finger table information. Continuing the example Peer Registration from the section above, assume now that the peer with Peer-ID 47e46fa2cd and IP address 192.0.2.7 is currently responsible for 463ac4b449 in the namespace. The admitting peer here does send the finger table, but we show only the first entry entry for clarity. We also omit the additional successors used to support redundancy for clarity. The response would look something like: SIP/2.0 200 OK To: From: Contact: Expires: 600 DHT-PeerID: ;algorithm=sha1; dht-param=Chord1.0;overlay=chat;expires=600 DHT-Link: ;link=P1;expires=412 DHT-Link: ;link=S1;expires=816 DHT-Link: ;link=F2;expires=121 Require: dht Supported: dht The joining peer obtains the Peer-ID and address of the admitting peer from the DHT-Peer header, and the information about the admitting peer's predecessor from the DHT-Link P 1 header. The joining peer MUST set its successor to be the admitting peer and its predecessor to be the admitting peer's predecessor. If the admitting peer did not provide a predecessor (which MUST only occur if the admitting peer's predecessor is NULL), the joining peer should leave their predecessor as NULL. Zangrilli & Bryan Expires August 29, 2007 [Page 11] Internet-Draft P2PSIP February 2007 *After* the admitting peer sends the 200 response, it MUST set its predecessor to be the joining peer, and MUST obtain the information from the DHT-Peer header in the register request. It MUST NOT change the value of the predecessor prior to sending the 200. The admitting peer's successor is unchanged. Note that at this point the joining can also set all fingers pointing to intervals before the successor in the finger table to point to the successor. Following the admission, the joining peer MUST run periodic stabilization as described in DHT Maintenance (Section 6.6). The admitting peer should perform periodic stabilization as well. 6.4. Chord Query Processing A reply that is constructed to a query by the responsible peer MUST provide the current predecessor (if not NULL) and successor in the 200 or 404 message. These MUST be placed placed in DHT-Link headers, as described in The DHT-Link Header (Section 5.2) section of this document. If the predecessor is not NULL it MUST be transmitted in a DHT-Link header using a type of P and a depth of 1. It must be omitted if NULL. The successor MUST be transmitted in a DHT-Link header using a type of S and a depth of 1. The 200 or 404 SHOULD contain a copy of entries in their finger table, using DHT-Link headers with type F. Additionally, the replying peer MUST include its DHT-PeerID header. 6.5. Chord Graceful Leaving Peers MUST send their resource registrations to their successor before leaving the overlay. Additionally, peers MUST unregister themselves with both their successor and predecessor. This unregister is constructed exactly the same as the Peer Registration message used to join, with the following exceptions. The expires parameter or header MUST be provided, and MUST be set to 0. When a peer sends its unregister message to its successor and predecessor, it MUST include DHT-Link headers listing its predecessor and successor peers. This allows the peers receiving the requests to obtain the information needed to correct their predecessor and successor peers, as well as keep their successor lists needed for redundancy current. OPEN ISSUE: should it be possible to trigger another peer to check its predecessor? Zangrilli & Bryan Expires August 29, 2007 [Page 12] Internet-Draft P2PSIP February 2007 6.6. DHT Maintenance In order to keep the overlay stable, peers must periodically perform book keeping operations to take into account peer failures. Periodically (we suggest 60-360 seconds), peers MUST perform finger table updates and periodic stabilization. 6.6.1. Chord Finger Table Updates To update the finger table, a peer performs a Peer Query search for ID corresponding to the start of each of its finger intervals. These intervals are described in Finger Table, Successors and Predecessors (Section 6.1) and Peer Queries are described in the dSIP [I-D.bryan-p2psip-dsip] draft. The 200 response to each Peer Query will contain the peer responsible for that ID in the DHT-PeerID header. The peer information in the DHT-PeerID header is entered into the corresponding finger table entry. 6.6.2. Chord Periodic Stabilization In periodic stabilization, peers MUST perform an arbitrary query for their current successor's Peer-ID. The peer should examine the response from their successor. The predecessor reported should be the peer that made the request. If it is not, the peer MUST update their own successor with the predecessor returned, and additionally MUST send a REGISTER to this peer, structured as if the stabilizing peer had just entered the system. However, the peer sending this message MUST not process the response, but simply discard it, as this is intended only to pass information. This will serve to properly update the overlay. This is analogous to the notify procedure in Chord. OPEN ISSUE: this operation is identical to the original chord operation, but it seems like we can pay attention to the response and observe if there have been multiple peers inserted and the peer we sent the REGISTER to knows a better successor peer, but this goes away with the next stabilize, anyway. 6.7. Peer Failure Peer failure is handled by the periodic stabilization and responses to failed requests discussed above. Redundancy prevents against lost registrations. Zangrilli & Bryan Expires August 29, 2007 [Page 13] Internet-Draft P2PSIP February 2007 6.8. Resource Replicas When a resource is registered, the registering peer SHOULD create at least 2 redundant replicas to ensure the registry information is secure in the DHT. The registering peer is responsible for maintaining these replicas along with the primary entry. 7. Examples For our examples, we use a simplified network. Rather than use a full SHA-1 hash, and the resulting 2^160 namespace, we instead use a smaller 4 bit hash, leading to a namespace of size 16. All hash results in our examples are contrived. We list the Peer-ID and Resource-IDs as xx, where xx is a number between 0 and 15 (2^4 namespace). In a real situation, the full 40 hex chars would be used. Additionally, because the number of finger table entries is so small in this case, we use the full 4 entries, where in a real case we suggest that one uses less than the number of bits in the namespace. The empty overlay can be visualized as a circle with 16 possible vacant points, each corresponding to one possible location in the hash space. On the left, we have labeled these locations in the hash space as 0-15, starting in the upper left, and have used 0s to indicate vacant spaces in the hash space. On the right, we show the same network with 3 operating peers, denoted by capital Ns, with Peer-IDs of 3, 5, and 10. We will use this sample network state as the starting point for all our networks: 0 1 2 0 1 2 0----0----0 0----0----0 / \ / \ 15 0 0 3 15 0 N 3 / \ / \ 14 0 0 4 14 0 0 4 | | | | 13 0 0 5 13 0 N 5 | | | | 12 0 0 6 12 0 0 6 \ / \ / 11 0 0 7 11 0 0 7 \ / \ / 0----0----0 N----0----0 10 9 8 10 9 8 Zangrilli & Bryan Expires August 29, 2007 [Page 14] Internet-Draft P2PSIP February 2007 Further, for the sake of example simplicity, assume the peer Peer-ID 3 has IP address 192.0.2.3, the peer peer with Peer-ID 5 has IP address 192.0.2.5, etc. Data that hashes to a Resource-ID is stored by the next peer whose Peer-ID is equal to or larger than the Resource-ID, mod the size of the hash. As such, Peer 3 is responsible for any resources hashing from 11-15, as well as 0-3. Peer 5 is responsible for resources with Resource-IDs from 4-5, and Peer 10 is responsible for resources with Resource-IDs from 6-10. From this illustration, you follow a location clockwise until you encounter a peer, and this is the peer responsible for storing the information. This is illustrated below: 0 1 2 0----0----0 / \ 15 0 N 3 / 14 0 0 4 | | 13 0 N 5 | 12 0 0 6 \ / 11 0 0 7 / N----0----0 10 9 8 Finger tables give pointers to nearby peers. For our system, with 4 bit identifiers, we have 4 finger table entries. These finger tables point to the peer nearest to Peer-ID + 2^0, Peer-ID + 2^1, Peer-ID + 2^2 and Peer-ID + 2^3. If no peer is present at that location, the next available peer will be used. Thus, for our 3 peers, the finger tables look like the following, with ranges (indicated in traditional mathematical form) mapping to the peer those requests will be sent to: Peer 3 Peer 5 Peer 10 2^0 Entry [4,5) -> 5 [6,7) -> 10 [11,12) -> 3 2^1 Entry [5,7) -> 5 [7,9) -> 10 [12,14) -> 3 2^2 Entry [7,11) -> 10 [9,13) -> 10 [14,2) -> 3 2^3 Entry [11,3) -> 3 [13,5) -> 3 [2,10) -> 3 Zangrilli & Bryan Expires August 29, 2007 [Page 15] Internet-Draft P2PSIP February 2007 Assume further our sample network is called sipchat, and that 2 users are currently registered. User alice has a Resource-ID of 5, so her registration information is stored at peer 5. User bob is also registered, and has a Resource-ID of 12, so his registration information is stored by peer 3. Assume further that bob's UA is co- located with Peer 10, so his contact is sipchat/bob@192.0.2.10, and that alice is running a UA on a completely separate IP of 192.0.2.99, but is using an adapter peer running on Peer 3, therefore Peer 3 will send messages on alice's behalf, but alice's contact is sipchat/alice@192.0.2.99. In each of the examples below, we assume we start from the network described above. Changes to the example network from previous examples are discarded. Note that for simplicity we do not show user registration redundancy in any examples. This includes responses -- we only send predecessor and successor, as well as finger table -- not redundant successors. 7.1. Example of a Peer Registration Assume a new peer wishes to join the system. The peer has an IP address of 192.0.2.14, which we shall assume hashes to a Peer-ID of 14. From an out of band mechanism, this peer discovers peer 5. This peer constructs a REGISTER and sends it to peer 5. Peer 5 verifies that 192.0.2.14 hashes to 14, then checks to see if it controls that portion of the namespace. Since it does not, it looks up in its finger table where it would route a search for 14, and determines it would send it to peer 3. The peer then sends a 302 back to peer 14, with a contact of peer 3. Peer 14 the constructs a new REGISTER and sends it to Peer 3. Again, Peer 3 verifies the hash, and determines it is currently responsible for 14 in the hash space. After an optional challenge, it replies with a 200 OK message to admit the peer to the system. Finally, Peer 3 sends a third party registration on behalf of bob to Peer 14, transferring bob's registration to the new peer. Peer 14 Peer 5 Peer 3 | | | |(1) REGISTER | | |------------------>| | | | | |(2) 302 | | |<------------------| | | | | |(3) REGISTER | | Zangrilli & Bryan Expires August 29, 2007 [Page 16] Internet-Draft P2PSIP February 2007 |-------------------------------------->| | | | |(4) 200 | | |<--------------------------------------| | | | |(5) REGISTER | | |<--------------------------------------| | | | |(6) 200 | | |-------------------------------------->| | | | Peer 14 -> Peer 5 REGISTER sip:192.0.2.5 SIP/2.0 To: From: Contact: Expires: 600 DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=600 Require: dht Supported: dht Peer 5 -> Peer 14 SIP/2.0 302 Moved Temporarily To: From: Contact: DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=1200 DHT-Link: ;link=P1;expires=427 DHT-Link: ;link=S1;expires=387 Require: dht Supported: dht Peer 14 -> Peer 3 REGISTER sip:192.0.2.3 SIP/2.0 To: From: Contact: Expires: 600 DHT-PeerID: ;algorithm=sha1; Zangrilli & Bryan Expires August 29, 2007 [Page 17] Internet-Draft P2PSIP February 2007 dht=Chord1.0;overlay=chat;expires=600 Require: dht Supported: dht Peer 3 -> Peer 14 SIP/2.0 200 OK To: From: Contact: Expires: 600 DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=600 DHT-Link: ;link=P1;expires=125 DHT-Link: ;link=S1;expires=919 DHT-Link: ;link=F0;expires=919 DHT-Link: ;link=F1;expires=919 DHT-Link: ;link=F2;expires=125 DHT-Link: ;link=F3;expires=600 Require: dht Supported: dht Peer 3 -> Peer 14 REGISTER sip:192.0.2.14 SIP/2.0 To: From: Contact: Expires: 201 DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=600 Require: dht Supported: dht Peer 14 -> Peer 3 SIP/2.0 200 OK To: From: Contact: Expires: 201 DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=600 Require: dht Supported: dht Zangrilli & Bryan Expires August 29, 2007 [Page 18] Internet-Draft P2PSIP February 2007 7.2. Example of a User Registration Assume user Carl starts a UA co-located with peer 5. Carl's contact will be carl@192.0.2.5, and his user name will be carl@p2psip.org. Carl's Peer hashes his user id and determines that the corresponding Resource-ID will be 11 -- that is, Carl's registration will be stored by the peer responsible for Resource-ID 11 -- ultimately Peer 3 in our example. Carl's UA begins by constructing a SIP REGISTER message. Carl's UA consults its finger table, and determines that it should route requests pertaining to a Resource-ID of 11 to Peer 10. The REGISTER is sent to Peer 10, which observes that it is not responsible for that portion of the namespace, and consults the finger table, finding Peer 3 in the appropriate entry. Peer 10 sends a 302 containing Peer 3 as a contact. Peer 5 constructs a new REGISTER on behalf of carl, and sends it to Peer 3. Peer 3 recognizes that it is responsible for storing this registration, and replies with a 200 OK (although in reality it might challenge in some way). The 200 contains some number of successor peers -- in this case 2 (although in our contrived example, one is peer 5 itself) that Carl's peer could send redundant registrations to. In our example, we do not show these. The 200 also (like 302s) must contain successors/predecessors in case the request is being used for stabilization. Again, in the tiny contrived example it looks odd since the second successor is the same as the predecessor. In a larger example this would not be the case. [To Do: Maybe use a bigger example to fix these problems? That might be to big and ugly. Need a good way to show this] Peer 5 Peer 10 Peer 3 | | | |(1) REGISTER | | |------------------>| | | | | |(2) 302 | | |<------------------| | | | | |(3) REGISTER | | |-------------------------------------->| | | | |(4) 200 | | |<--------------------------------------| | | | Zangrilli & Bryan Expires August 29, 2007 [Page 19] Internet-Draft P2PSIP February 2007 Peer 5 -> Peer 10 REGISTER sip:192.0.2.10 SIP/2.0 To: From: Contact: Expires: 600 DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=1200 Require: dht Supported: dht Peer 10 -> Peer 5 SIP/2.0 302 Moved Temporarily Contact: DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=800 DHT-Link: ;link=P1;expires=1200 DHT-Link: ;link=S1;expires=412 Require: dht Supported: dht Peer 5 -> Peer 3 REGISTER sip:192.0.2.3 SIP/2.0 To: From: Contact: Expires: 600 DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=1200 Require: dht Supported: dht Peer 3 -> Peer 5 SIP/2.0 200 OK To: From: Contact: Expires: 600 DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=600 DHT-Link: ;link=P1;expires=405 Zangrilli & Bryan Expires August 29, 2007 [Page 20] Internet-Draft P2PSIP February 2007 DHT-Link: ;link=S1;expires=1200 DHT-Link: ;link=S2;expires=405 Require: dht Supported: dht 7.3. Example of a Session Establishment Assume user Bob wishes to call user Alice. Bob's peer hashes Alice's user id, resulting in a Resource-ID of 5. Bob's peer (recall that Bob's UA is co-located with peer 10) consults its finger table, and determines that a request for Resource-ID 5 should be routed to Peer 3. A REGISTER query message is constructed and routed to Peer 3. Peer 3 determines it is not responsible for a Resource-ID of 5, looks up the ID in its finger table and determines it should be routed to Peer 5, so it returns a 302 referring to Peer 5. Bob's peer resends the REGISTER to Peer 5, which stores Alice's information. It sends a 200 with Alice's contact -- sipchat/alice@192.0.2.99. Bob finally sends an INVITE to Alice's UA, and session establishment is completed as normal. Peer 10 Peer 3 Peer 5 Alice UA | | | | |(1) REGISTER | | | |------------------>| | | | | | | |(2) 302 | | | |<------------------| | | | | | | |(3) REGISTER | | | |----------------------------------->| | | | | | |(4) 200 | | | |<-----------------------------------| | | | | | |(5) INVITE | | | |------------------------------------------------------>| | | | | |(6) 180 | | | |<------------------------------------------------------| | | | | |(7) 200 | | | |<------------------------------------------------------| | | | | |(8) ACK | | | |------------------------------------------------------>| Zangrilli & Bryan Expires August 29, 2007 [Page 21] Internet-Draft P2PSIP February 2007 | | | | Peer 10 -> Peer 3 REGISTER sip:192.0.2.3 SIP/2.0 To: From: DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=800 Require: dht Supported: dht Peer 3 -> Peer 10 SIP/2.0 302 Moved Temporarily To: From: Contact: DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=600 DHT-Link: ;link=P1;expires=421 DHT-Link: ;link=S1;expires=1004 Require: dht Supported: dht Peer 10 -> Peer 5 REGISTER sip:192.0.2.5 SIP/2.0 To: From: DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=800 Require: dht Supported: dht Peer 5 -> Peer 10 SIP/2.0 200 OK To: From: Contact: DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=1200 DHT-Link: ;link=P1;expires=108 Zangrilli & Bryan Expires August 29, 2007 [Page 22] Internet-Draft P2PSIP February 2007 DHT-Link: ;link=S1;expires=492 Require: dht Supported: dht Peer 10 -> Alice UA INVITE sip:alice@p2psip.org SIP/2.0 To: From: Contact: DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=800 Supported: dht The remainder of the call is completed as any other SIP call. Note that if Alice's UA is DHT-compliant, then it will recognize the Supported field and DHT-PeerID header, and may respond with similar fields. However, if it does not support DHT extensions, it will simply ignore those values and complete the call as any normal non- P2P SIP UA. 7.4. Example of Moving From Empty Overlay to Stable 3 Peer System In this example, we track the system state from overlay creation to a stable 3 peer overlay with 2 resources (user registrations) registered and stored in the system. This example will show how successor, predecessor, and finger table entries are updated during each step as well as show the P2P SIP messages exchanged. Assume we start with an empty overlay with a namespace of 16. Each peer in the system will have one successor, one predecessor and 4 finger table entries (2^4 namespace). Peer state will be shown in the following way: Zangrilli & Bryan Expires August 29, 2007 [Page 23] Internet-Draft P2PSIP February 2007 PeerID Successor Predecessor 2^0 Entry 2^1 Entry 2^2 Entry 2^3 Entry Resources 0 1 2 0----0----0 / \ 15 0 0 3 / \ 14 0 0 4 | | 13 0 0 5 | | 12 0 0 6 \ / 11 0 0 7 \ / 0----0----0 10 9 8 Additionally, we will track the location of resources with a resource map. A peer with PeerID 3, IP address 192.0.2.3, and port 5060 starts the overlay called chat. When a peer starts a new overlay, it sets its successor to be its PeerID and sets its predecessor to be NULL. Additionally, the peer initializes its finger table and sets all fingers to be its PeerID. The resulting state of the system is: Zangrilli & Bryan Expires August 29, 2007 [Page 24] Internet-Draft P2PSIP February 2007 0 1 2 0----0----0 / \ 15 0 P 3 / \ 14 0 0 4 | | 13 0 0 5 | | 12 0 0 6 \ / 11 0 0 7 \ / 0----0----0 10 9 8 Peer 3 Successor 3 Predecessor NULL 2^0 Entry [4,5) -> 3 2^1 Entry [5,7) -> 3 2^2 Entry [7,11) -> 3 2^3 Entry [11,3) -> 3 Resources Resource Map For peer 3, there is a resource called alice that must be registered with the system. alice's peer hashes her user id and determines that the corresponding resource will be 8. alice's contact will be sipchat/alice@192.0.2.3 and her user name will be alice@p2psip.org. Because there are no other peers in the system, peer 3 is responsible for all resources including alice's registration. Note that we use "resID" as a short form for "resource-ID" to save room in the figure only -- resource-ID is used in the actual messages. As a result the system state changes to: Zangrilli & Bryan Expires August 29, 2007 [Page 25] Internet-Draft P2PSIP February 2007 0 1 2 0----0----0 / \ 15 0 P 3 / \ 14 0 0 4 | | 13 0 0 5 | | 12 0 0 6 \ / 11 0 0 7 \ / 0----0----0 10 9 8 Peer 3 Successor 3 Predecessor NULL 2^0 Entry [4,5) -> 3 2^1 Entry [5,7) -> 3 2^2 Entry [7,11) -> 3 2^3 Entry [11,3) -> 3 Resources alice;resID=8 -> 3 Resource Map Resource name ResID ResLocation ResStorage Location alice 8 3 3 Next a peer with PeerID 10, IP address 192.0.2.10, and port 5060 decides to join the overlay called chat. From an out of band mechanism, such as one of the ones listed in the Bootstrapping section of this document, this peer discovers peer 3. This new peer 10, constructs a REGISTER and sends it to peer 3. Peer 3 verifies that 192.0.2.10 hashes to 10, then checks to see if it controls that portion of the namespace. Since Peer 3's predecessor is NULL and no other peers are in the system, Peer 3 determines that is currently responsible for peer 10 in the hash space. After an optional challenge, peer 3 replies with a 200 OK message to admit peer 10 into the system. Peer 3 then sets its predecessor to be Peer 10. When Peer 10 receives the 200 OK message, it will set its successor to be Peer 3 and keeps its predecessor set to NULL (because no predecessor was in the 200 response). Finally, Peer 3 sends a third party registration on behalf of alice Zangrilli & Bryan Expires August 29, 2007 [Page 26] Internet-Draft P2PSIP February 2007 to Peer 10, transferring alice's registration to the new peer. Peer 10 Peer 3 | | |(1) REGISTER | |------------------>| | | |(2) 200 | |<------------------| | | |(3) REGISTER | |<------------------| | | |(4) 200 | |------------------>| | | Peer 10 -> Peer 3 REGISTER sip:192.0.2.3 SIP/2.0 To: From: Contact: Expires: 600 DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=600 Require: dht Supported: dht Peer 3 -> Peer 10 SIP/2.0 200 OK To: From: Contact: Expires: 600 DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=600 DHT-Link: ;link=S1;expires=919 DHT-Link: ;link=F0;expires=919 DHT-Link: ;link=F1;expires=919 DHT-Link: ;link=F2;expires=125 DHT-Link: ;link=F3;expires=600 Zangrilli & Bryan Expires August 29, 2007 [Page 27] Internet-Draft P2PSIP February 2007 Require: dht Supported: dht Peer 3 -> Peer 10 REGISTER sip:192.0.2.10 SIP/2.0 To: From: Contact: Expires: 201 DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=600 Require: dht Supported: dht Peer 10 -> Peer 3 SIP/2.0 200 OK To: From: Contact: Expires: 201 DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=600 DHT-Link: ;link=S1;expires=919 DHT-Link: ;link=F0;expires=919 DHT-Link: ;link=F1;expires=919 DHT-Link: ;link=F2;expires=125 DHT-Link: ;link=F3;expires=600 Require: dht Supported: dht The system state is now: Zangrilli & Bryan Expires August 29, 2007 [Page 28] Internet-Draft P2PSIP February 2007 0 1 2 0----0----0 / \ 15 0 P 3 / \ 14 0 0 4 | | 13 0 0 5 | | 12 0 0 6 \ / 11 0 0 7 \ / P----0----0 10 9 8 Peer 3 Peer 10 Successor 3 3 Predecessor 10 NULL 2^0 Entry [4,5) -> 3 [11,12) -> 3 2^1 Entry [5,7) -> 3 [12,14) -> 3 2^2 Entry [7,11) -> 3 [14, 2) -> 3 2^3 Entry [11,3) -> 3 [2, 10) -> 3 Resources alice;resID=8 -> 3 Resource Map Resource name ResID ResLocation ResStorage Location alice 8 3 10 Peer 10 runs its periodic stabilization. It constructs a REGISTER as described in the Peer Query section, and sends it to its successor, Peer 3, querying for its successor's PeerID. Peer 3 checks the query to determine if it is responsible for the region the search key lies within. Because Peer 3's PeerID directly matches the search key, it sends a 200 OK response message with its current successor and predecessor specified in the DHT-Link headers. Peer 10 examines the response from Peer 3. Because the predecessor in the response from Peer 3 is the same as Peer 10, the stabilizing peer, Peer 10 is not required to do any more work. Peer 10 should perform searches to update its finger table, but these are omitted for clarity. Zangrilli & Bryan Expires August 29, 2007 [Page 29] Internet-Draft P2PSIP February 2007 Peer 10 Peer 3 | | |(1) REGISTER | |------------------>| | | |(2) 200 | |<------------------| Peer 10 -> Peer 3 REGISTER sip:192.0.2.3 SIP/2.0 To: From: DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=600 Require: dht Supported: dht Peer 3 -> Peer 10 SIP/2.0 200 OK To: From: Contact: Expires: 600 DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=600 DHT-Link: ;link=P1;expires=0 DHT-Link: ;link=S1;expires=919 DHT-Link: ;link=F0;expires=919 DHT-Link: ;link=F1;expires=919 DHT-Link: ;link=F2;expires=125 DHT-Link: ;link=F3;expires=600 Require: dht Supported: dht The state stays unchanged after Peer 10's periodic stabilization. Zangrilli & Bryan Expires August 29, 2007 [Page 30] Internet-Draft P2PSIP February 2007 0 1 2 0----0----0 / \ 15 0 P 3 / \ 14 0 0 4 | | 13 0 0 5 | | 12 0 0 6 \ / 11 0 0 7 \ / P----0----0 10 9 8 Peer 3 Peer 10 Successor 3 3 Predecessor 10 NULL 2^0 Entry [4,5) -> 3 [11,12) -> 3 2^1 Entry [5,7) -> 3 [12,14) -> 3 2^2 Entry [7,11) -> 3 [14, 2) -> 3 2^3 Entry [11,3) -> 3 [2, 10) -> 3 Resources alice;resID=8 -> 3 Resource Map Resource name ResID ResLocation ResStorage Location alice 8 3 10 For peer 10, there is a resource called bob that must be registered with the system. bob's contact will be sipchat/bob@192.0.2.10 and his user name will be bob@p2psip.org. bob's peer hashes his user id and determines that the corresponding resource will be 11. Bob's UA begins by constructing a SIP REGISTER message as described in Resource Registrations (Resource Registrations). Bob's UA consults its finger table, and determines that it should route requests pertaining to a Resource-ID of 5 to Peer 3. The REGISTER is sent to Peer 3, which observes that it is responsible for that portion of the namespace and replies with a 200 OK containing Peer 3's predecessor and successor information in the DHT-Link headers. Zangrilli & Bryan Expires August 29, 2007 [Page 31] Internet-Draft P2PSIP February 2007 Peer 10 Peer 3 | | |(1) REGISTER | |------------------>| | | |(2) 200 | |<------------------| | | Peer 10 -> Peer 3 REGISTER sip:192.0.2.3 SIP/2.0 To: From: Contact: Expires: 231 DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=600 Require: dht Supported: dht Peer 3 -> Peer 10 SIP/2.0 200 OK To: From: Contact: Expires: 231 DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=600 DHT-Link: ;link=P1;expires=600 DHT-Link: ;link=S1;expires=919 DHT-Link: ;link=F0;expires=919 DHT-Link: ;link=F1;expires=919 DHT-Link: ;link=F2;expires=125 DHT-Link: ;link=F3;expires=600 Require: dht Supported: dht After bob's registration, the system state is: Zangrilli & Bryan Expires August 29, 2007 [Page 32] Internet-Draft P2PSIP February 2007 0 1 2 0----0----0 / \ 15 0 P 3 / \ 14 0 0 4 | | 13 0 0 5 | | 12 0 0 6 \ / 11 0 0 7 \ / P----0----0 10 9 8 Peer 3 Peer 10 Successor 3 3 Predecessor 10 NULL 2^0 Entry [4,5) -> 3 [11,12) -> 3 2^1 Entry [5,7) -> 3 [12,14) -> 3 2^2 Entry [7,11) -> 3 [14, 2) -> 3 2^3 Entry [11,3) -> 3 [2, 10) -> 3 Resources bob;resID=11 -> 10 alice;resID=8 -> 3 Resource Map Resource name ResID ResLocation ResStorage Location alice 8 3 10 bob 11 10 3 Peer 3 now runs its periodic stabilization. It constructs a REGISTER as described in the Peer Query section, and sends it to its successor, Peer 3, querying for its successor's PeerID. Peer 3 checks the query to determine if it is responsible for the region the search key lies within. Because Peer 3's PeerID directly matches the search key, it sends a 200 OK response message with its current successor and predecessor specified in the DHT-Link headers. Peer 3 examines the response from itself. Because the predecessor in the response from Peer 3 is Peer 10, Peer 3 updates its successor to be Peer 10 and sends a REGISTER to Peer 10, structured as if Peer 3 had just entered the system. When Peer 10 receives the message, it then sends a 200 OK response to Peer 3. Then, Peer 10 sets its predecessor to be Peer 3 because Peer 10's predecessor was NULL. Zangrilli & Bryan Expires August 29, 2007 [Page 33] Internet-Draft P2PSIP February 2007 Then Peer 3 should perform searches to update its finger table, but these are simple peer queries and are omitted in this example. We show the finger table as though these searches were performed. Note that because Peer 3's successor is Peer 3, we do not show such a REGISTER message being sent because implementations may choose to remove this step for efficiency. Rather we show the message sent from Peer 3 to Peer 10 that notifies Peer 10 that Peer 3 is its predecessor. Peer 3 Peer 10 | | |(1) REGISTER | |------------------>| | | |(2) 200 | |<------------------| | | Peer 3 -> Peer 10 REGISTER sip:192.0.2.10 SIP/2.0 To: From: Contact: Expires: 600 DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=600 Require: dht Supported: dht Peer 10 -> Peer 3 SIP/2.0 200 OK To: From: Contact: Expires: 600 DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=600 DHT-Link: ;link=S1;expires=919 DHT-Link: ;link=F0;expires=919 DHT-Link: ;link=F1;expires=919 DHT-Link: ;link=F2;expires=125 Zangrilli & Bryan Expires August 29, 2007 [Page 34] Internet-Draft P2PSIP February 2007 DHT-Link: ;link=F3;expires=600 Require: dht Supported: dht After Peer 3's stabilization, the system state is: 0 1 2 0----0----0 / \ 15 0 P 3 / \ 14 0 0 4 | | 13 0 0 5 | | 12 0 0 6 \ / 11 0 0 7 \ / P----0----0 10 9 8 Peer 3 Peer 10 Successor 10 3 Predecessor 10 3 2^0 Entry [4,5) -> 10 [11,12) -> 3 2^1 Entry [5,7) -> 10 [12,14) -> 3 2^2 Entry [7,11) -> 10 [14, 2) -> 3 2^3 Entry [11,3) -> 3 [2, 10) -> 3 Resources bob;resID=11 -> 10 alice;resID=8 -> 3 Resource Map Resource name ResID ResLocation ResStorage Location alice 8 3 10 bob 11 10 3 Next a peer with PeerID 2, IP address 192.0.2.2, and port 5060 decides to join the overlay called chat. From an out of band mechanism, such as one of the ones listed in the Bootstrapping section of this document, this peer discovers peer 10. This new peer 2, constructs a REGISTER and sends it to peer 10. Peer 10 verifies that 192.0.2.2 hashes to 2, then checks to see if it controls that portion of the namespace. Since it does not, it looks Zangrilli & Bryan Expires August 29, 2007 [Page 35] Internet-Draft P2PSIP February 2007 up in its finger table where it would route a search for 2, and determines it would send it to peer 3. The peer then sends a 302 back to peer 2, with a contact of peer 3. Peer 2 then constructs a new REGISTER and sends it to Peer 3. Again, Peer 3 verifies the hash, and determines it is currently responsible for 2 in the hash space. After an optional challenge, it replies with a 200 OK message to admit the peer to the system. After sending the 200 response, Peer 3 then sets its predecessor to be Peer 2. When Peer 2 receives the 200 OK message, it will set its successor to be Peer 3 and set its predecessor to be Peer 10 (because that was the predecessor in the 200 response). Peer 2 should also perform searches to ensure that the finger table is up to date. These searches are omitted, but we update the finger table. Finally, Peer 3 sends a third party registration on behalf of bob to Peer 2, transferring bob's registration to the new peer. Peer 2 Peer 10 Peer 3 | | | |(1) REGISTER | | |------------------>| | | | | |(2) 302 | | |<------------------| | | | | |(3) REGISTER | | |-------------------------------------->| | | | |(4) 200 | | |<--------------------------------------| | | | |(5) REGISTER | | |<--------------------------------------| | | | |(6) 200 | | |-------------------------------------->| | | | Peer 2 -> Peer 10 REGISTER sip:192.0.2.10 SIP/2.0 To: From: Zangrilli & Bryan Expires August 29, 2007 [Page 36] Internet-Draft P2PSIP February 2007 Contact: Expires: 600 DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=600 Require: dht Supported: dht Peer 10 -> Peer 2 SIP/2.0 302 Moved Temporarily To: From: Contact: Expires: 600 DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=600 DHT-Link: ;link=P1;expires=919 DHT-Link: ;link=S1;expires=919 Require: dht Supported: dht Peer 2 -> Peer 3 REGISTER sip:192.0.2.3 SIP/2.0 To: From: Contact: Expires: 600 DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=600 Require: dht Supported: dht Peer 3 -> Peer 2 SIP/2.0 200 OK To: From: Contact: Expires: 600 DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=600 DHT-Link: ;link=P1;expires=419 DHT-Link: ;link=S1;expires=419 DHT-Link: ;link=F0;expires=919 Zangrilli & Bryan Expires August 29, 2007 [Page 37] Internet-Draft P2PSIP February 2007 DHT-Link: ;link=F1;expires=919 DHT-Link: ;link=F2;expires=125 DHT-Link: ;link=F3;expires=600 Require: dht Supported: dht Peer 3 -> Peer 2 REGISTER sip:2.0.0.2 SIP/2.0 To: From: Contact: Expires: 201 DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=600 Require: dht Supported: dht Peer 2 -> Peer 3 SIP/2.0 200 OK To: From: Contact: Expires: 201 DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=600 DHT-Link: ;link=S1;expires=919 DHT-Link: link=P1;expires=800 DHT-Link: ;link=F0;expires=919 DHT-Link: ;link=F1;expires=919 DHT-Link: ;link=F2;expires=125 DHT-Link: ;link=F3;expires=600 Require: dht Supported: dht After Peer 2's insertion, the system state is: Zangrilli & Bryan Expires August 29, 2007 [Page 38] Internet-Draft P2PSIP February 2007 0 1 2 0----0----P / \ 15 0 P 3 / \ 14 0 0 4 | | 13 0 0 5 | | 12 0 0 6 \ / 11 0 0 7 \ / P----0----0 10 9 8 Peer 2 Peer 3 Peer 10 Successor 3 10 3 Predecessor 10 2 3 2^0 Entry [3,4) -> 3 [4,5) -> 10 [11,12) -> 3 2^1 Entry [4,6) -> 10 [5,7) -> 10 [12,14) -> 3 2^2 Entry [6,10) -> 10 [7,11) -> 10 [14, 2) -> 3 2^3 Entry [10,2) -> 10 [11, 3) -> 3 [2, 10) -> 3 Resources bob;resID=11 -> 10 alice;resID=8 -> 3 Resource Map Resource name ResID ResLocation ResStorage Location alice 8 3 10 bob 11 10 2 Peer 3 now runs its periodic stabilization. It constructs a REGISTER as described in the Peer Query section, and sends it to its successor, Peer 10, querying for its successor's PeerID. Peer 10 checks the query to determine if it is responsible for the region the search key lies within. Because Peer 10's PeerID directly matches the search key, it sends a 200 OK response message with its current successor and predecessor specified in the DHT-Link headers. Peer 3 examines the response from itself. Because the predecessor in the response form Peer 10 is the same as Peer3, the stabilizing peer, Peer 3 does not need to send any messages to the predecessor. At this point Peer 3 should send queries to ensure that the finger table is up to date. We do not show the SIP messages for this process, but do show the resulting changes in Peer 3's finger table. Zangrilli & Bryan Expires August 29, 2007 [Page 39] Internet-Draft P2PSIP February 2007 Peer 3 Peer 10 | | |(1) REGISTER | |------------------>| | | |(2) 200 | |<------------------| Peer 10 -> Peer 3 REGISTER sip:192.0.2.10 SIP/2.0 To: From: DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=600 Require: dht Supported: dht Peer 10 -> Peer 3 SIP/2.0 200 OK To: From: Contact: Expires: 600 DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=600 DHT-Link: ;link=P1;expires=0 DHT-Link: ;link=S1;expires=919 DHT-Link: ;link=F0;expires=919 DHT-Link: ;link=F1;expires=919 DHT-Link: ;link=F2;expires=125 DHT-Link: ;link=F3;expires=600 Require: dht Supported: dht The state after Peer 3's periodic stabilization: Zangrilli & Bryan Expires August 29, 2007 [Page 40] Internet-Draft P2PSIP February 2007 0 1 2 0----0----P / \ 15 0 P 3 / \ 14 0 0 4 | | 13 0 0 5 | | 12 0 0 6 \ / 11 0 0 7 \ / P----0----0 10 9 8 Peer 2 Peer 3 Peer 10 Successor 3 10 3 Predecessor 10 2 3 2^0 Entry [3,4) -> 3 [4,5) -> 10 [11,12) -> 3 2^1 Entry [4,6) -> 10 [5,7) -> 10 [12,14) -> 3 2^2 Entry [6,10) -> 10 [7,11) -> 10 [14, 2) -> 3 2^3 Entry [10,2) -> 10 [11, 3) -> 2 [2, 10) -> 3 Resources bob;resID=11->10 alice;resID=8 -> 3 Resource Map Resource name ResID ResLocation ResStorage Location alice 8 3 10 bob 11 10 2 Peer 10 now runs its periodic stabilization. It constructs a REGISTER as described in the Peer Query section, and sends it to its successor, Peer 3, querying for its successor's PeerID. Peer 3 checks the query to determine if it is responsible for the region the search key lies within. Because Peer 3's PeerID directly matches the search key, it sends a 200 OK response with its current successor and predecessor in the response. Because the predecessor in the response from Peer 3 is Peer 2, Peer 10 updates its successor to be Peer 2 and sends a REGISTER to Peer 2, structured as if Peer 10 had just entered the system. When Peer 2 receives the message, it then sends a 200 OK response to Peer 10. Then, Peer 2 updates its predecessor to be Peer 10. Then Peer 10 should perform searches to update its finger table. Zangrilli & Bryan Expires August 29, 2007 [Page 41] Internet-Draft P2PSIP February 2007 These are simple peer queries and are omitted in this example, but we have updated the finger table. Peer 10 Peer 3 Peer 2 | | | |(1) REGISTER | | |------------------>| | | | | |(2) 200 | | |<------------------| | | | | |(3) REGISTER | | |-------------------------------------->| | | | |(4) 200 | | |<--------------------------------------| | | | Peer 10 -> Peer 3 REGISTER sip:3.0.0.3 SIP/2.0 To: From: DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=600 Require: dht Supported: dht Peer 3 -> Peer 10 SIP/2.0 200 OK To: From: Contact: Expires: 600 DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=600 DHT-Link: ;link=P1;expires=0 DHT-Link: ;link=S1;expires=919 DHT-Link: ;link=F0;expires=919 DHT-Link: ;link=F1;expires=919 DHT-Link: ;link=F2;expires=125 DHT-Link: ;link=F3;expires=600 Require: dht Supported: dht Zangrilli & Bryan Expires August 29, 2007 [Page 42] Internet-Draft P2PSIP February 2007 Peer 10 -> Peer 2 REGISTER sip:192.0.2.2 SIP/2.0 To: From: Contact: Expires: 600 DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=600 Require: dht Supported: dht Peer 2 -> Peer 10 SIP/2.0 200 OK To: From: Contact: Expires: 600 DHT-PeerID: ;algorithm=sha1; dht=Chord1.0;overlay=chat;expires=600 DHT-Link: ;link=P1;expires=419 DHT-Link: ;link=S1;expires=419 DHT-Link: ;link=F0;expires=919 DHT-Link: ;link=F1;expires=919 DHT-Link: ;link=F2;expires=125 DHT-Link: ;link=F3;expires=600 Require: dht Supported: dht After Peer 10's stabilization, the system state is: Zangrilli & Bryan Expires August 29, 2007 [Page 43] Internet-Draft P2PSIP February 2007 0 1 2 0----0----P / \ 15 0 P 3 / \ 14 0 0 4 | | 13 0 0 5 | | 12 0 0 6 \ / 11 0 0 7 \ / P----0----0 10 9 8 Peer 2 Peer 3 Peer 10 Successor 3 10 2 Predecessor 10 2 3 2^0 Entry [3,4) -> 3 [4,5) -> 10 [11,12) -> 3 2^1 Entry [4,6) -> 10 [5,7) -> 10 [12,14) -> 3 2^2 Entry [6,10) -> 10 [7,11) -> 10 [14, 2) -> 3 2^3 Entry [10,2) -> 10 [11, 3) -> 2 [2, 10) -> 2 Resources bob;resID=11 -> 10 alice;resID=8 -> 3 Resource Map Resource name ResID ResLocation ResStorage Location alice 8 3 10 bob 11 10 2 This system now has 3 peers in a stable state, such that all predecessor and successor information is correct, and two user resources are stored in the overlay. 7.5. Example of a Peer Leaving the System [To Do: Add an example here] 7.6. Example of a Successful User Search [To Do: Add an example here] Zangrilli & Bryan Expires August 29, 2007 [Page 44] Internet-Draft P2PSIP February 2007 7.7. Example of an Unsucessful User Search [To Do: Add an example here] 8. Security Considerations There are no new security considerations introduced in this draft beyond those already mentioned in the dSIP [I-D.bryan-p2psip-dsip] and Security for P2PSIP [I-D.lowekamp-p2psip-dsip-security] drafts. 9. Open Issues There are certainly many open issues. Here are a few. Should it be possible to trigger a node to recheck a finger table entry after it 302s to a node that appears to be down? Presumably this can be integrated together with the loose routing NAT traversal. During graceful exit, should it be possible to trigger another peer to check its predecessor? The periodic stabilization operation is identical to the original chord operation, but it seems like we can pay attention to the response and observe if there have been multiple peers inserted and the peer we sent the REGISTER to knows a better successor peer, but this goes away with the next stabilize, anyway. 10. Acknowledgements A team of people have worked on the various drafts related to the dSIP protocol and extensions thereof. The team consists of: David Bryan, Eric Cooper, James Deverick, Cullen Jennings, Bruce Lowekamp, Philip Matthews, and Marcia Zangrilli. Thanks to all who have been actively participating in the P2PSIP efforts. Special thanks to Spencer Dawkins, Enrico Marocco, and Jean-Francois Wauthy for providing editorial feedback, and Henry Sinnreich, Eric Rescorla, and Alan Johnston for various discussions related to this work. 11. IANA Considerations This document defines the valid "link-value" values, and defines the "dht-param" value to be "Chord1.0". Zangrilli & Bryan Expires August 29, 2007 [Page 45] Internet-Draft P2PSIP February 2007 12. Changes to this Version While this is a -00 document, it has grown from sections of the earlier draft-bryan-sipping-p2p-xx. 13. References 13.1. Normative References [I-D.bryan-p2psip-dsip] Bryan, D., Lowekamp, B., and C. Jennings, "dSIP: A P2P Approach to SIP Registration and Resource Location", Internet Draft draft-bryan-p2psip-dsip-00, February 2007. [I-D.lowekamp-p2psip-dsip-security] Lowekamp, B. and J. Deverick, "Authenticated Identity Extensions to dSIP", Internet Draft draft-lowekamp-p2psip-dsip-security-00, February 2007. [I-D.willis-p2psip-concepts] Willis, D., "Concepts and Terminology for Peer to Peer SIP", draft-willis-p2psip-concepts-03 (work in progress), October 2006. [RFC2104] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed- Hashing for Message Authentication", RFC 2104, February 1997. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [RFC3174] Eastlake, D. and P. Jones, "US Secure Hash Algorithm 1 (SHA1)", RFC 3174, September 2001. [RFC3261] Rosenberg, J., Schulzrinne, H., Camarillo, G., Johnston, A., Peterson, J., Sparks, R., Handley, M., and E. Schooler, "SIP: Session Initiation Protocol", RFC 3261, June 2002. 13.2. Informative References [Chord] Stoica, I., Morris, R., Liben-Nowell, D., Karger, D., Kaashoek, M., Dabek, F., and H. Balakrishnan, "Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications", IEEE/ACM Transactions on Networking Volume 11, Issue 1, 17-32, Feb 2003. Zangrilli & Bryan Expires August 29, 2007 [Page 46] Internet-Draft P2PSIP February 2007 Authors' Addresses Marcia Zangrilli SIPeerior Technologies 3000 Easter Circle Williamsburg, VA 23188 USA Phone: +1 757 565 0101 Email: marcia@sipeerior.com David A. Bryan SIPeerior Technologies 3000 Easter Circle Williamsburg, VA 23188 USA Phone: +1 757 565 0101 Email: dbryan@sipeerior.com Zangrilli & Bryan Expires August 29, 2007 [Page 47] Internet-Draft P2PSIP February 2007 Full Copyright Statement Copyright (C) The IETF Trust (2007). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Intellectual Property The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. Acknowledgment Funding for the RFC Editor function is provided by the IETF Administrative Support Activity (IASA). Zangrilli & Bryan Expires August 29, 2007 [Page 48]