P2PSIP S. Cirani Internet-Draft L. Veltri Expires: April 27, 2008 Department of Information Engineering - University of Parma October 25, 2007 A Kademlia-based DHT for Resource Lookup in P2PSIP draft-cirani-p2psip-dsip-dhtkademlia-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 April 27, 2008. Copyright Notice Copyright (C) The IETF Trust (2007). Cirani & Veltri Expires April 27, 2008 [Page 1] Internet-Draft Kademlia-based dSIP October 2007 Abstract This draft describes a Kademlia-based protocol for Resource Lookup in P2PSIP. The proposed protocol is based on dSIP, a SIP-based protocol proposed by other authors as generic framework for a distributed SIP Location Service. Although the dSIP authors have obsoleted the draft by a newer approach based on a binary protocol named RELOAD, we are still considering this SIP-based approach, due to implementation simplicity, possibility of reuse of already available SIP stack implementations, easy integration into existing UAs, minimization of the number of required protocols for a P2P UA, and widespread support for (and relative maturity of) the SIP standard. Cirani & Veltri Expires April 27, 2008 [Page 2] Internet-Draft Kademlia-based dSIP October 2007 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 5 3. Background . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.1. Kademlia . . . . . . . . . . . . . . . . . . . . . . . . . 6 4. Routing Table and Connection Table . . . . . . . . . . . . . . 7 4.1. The Kademlia protocol . . . . . . . . . . . . . . . . . . 8 4.2. Node lookup procedure . . . . . . . . . . . . . . . . . . 8 5. Message Syntax . . . . . . . . . . . . . . . . . . . . . . . . 10 5.1. The DHT-PeerID Header . . . . . . . . . . . . . . . . . . 10 5.1.1. Hash Algorithms . . . . . . . . . . . . . . . . . . . 10 5.1.2. DHT Name Parameter . . . . . . . . . . . . . . . . . . 10 5.2. The DHT-Link Header . . . . . . . . . . . . . . . . . . . 10 6. Kademlia Overlay Algorithm . . . . . . . . . . . . . . . . . . 11 6.1. Routing Table . . . . . . . . . . . . . . . . . . . . . . 11 6.2. Starting a New Overlay . . . . . . . . . . . . . . . . . . 11 6.3. Peer Admission . . . . . . . . . . . . . . . . . . . . . . 11 6.3.1. Constructing a Peer Registration . . . . . . . . . . . 11 6.3.2. Processing and Routing the Peer Registration . . . . . 12 6.3.3. Admitting the Joining Peer . . . . . . . . . . . . . . 12 6.4. Kademlia query processing . . . . . . . . . . . . . . . . 13 6.5. Kademlia Graceful Leaving . . . . . . . . . . . . . . . . 13 6.6. DHT Maintenance . . . . . . . . . . . . . . . . . . . . . 13 6.7. Peer Failure . . . . . . . . . . . . . . . . . . . . . . . 13 6.8. Resource Replicas . . . . . . . . . . . . . . . . . . . . 13 7. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 7.1. Peer registration . . . . . . . . . . . . . . . . . . . . 15 7.2. Peer query . . . . . . . . . . . . . . . . . . . . . . . . 17 7.3. User registration . . . . . . . . . . . . . . . . . . . . 20 7.4. Session establishment . . . . . . . . . . . . . . . . . . 21 8. Implementation . . . . . . . . . . . . . . . . . . . . . . . . 25 9. Security Considerations . . . . . . . . . . . . . . . . . . . 26 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 27 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 28 11.1. Normative References . . . . . . . . . . . . . . . . . . . 28 11.2. Informative References . . . . . . . . . . . . . . . . . . 29 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 30 Intellectual Property and Copyright Statements . . . . . . . . . . 31 Cirani & Veltri Expires April 27, 2008 [Page 3] Internet-Draft Kademlia-based dSIP October 2007 1. Introduction This draft describes a Kademlia-based protocol for Resource Lookup in P2PSIP. The proposed protocol is based on dSIP [I-D.bryan-p2psip-dsip], a SIP-based protocol proposed by other authors as generic framework for a distributed SIP Location Service. On top of dSIP, different DHTs can be supported in a pluggable module fashion. The dSIP specification for the support of Chord has already been defined in [I-D.zangrilli-p2psip-dsip-dhtchord]. Although the dSIP authors have obsoleted the draft by a newer approach based on a binary protocol named RELOAD [I-D.bryan-p2psip-reload], at this moment we are not sure that a binary protocol should be preferred to a text-based or SIP-based one, and, due to this, we are still considering this approach. A SIP-based solution might have some advantages such as simplicity of the implementation of a text-based approach, the possibility of reuse of already available SIP stack implementations, easy integration into existing UAs, minimization of the number of required protocols for a P2P UA, and widespread support for (and relative maturity of) the SIP standard. Moreover the drawbacks of such an approach do not appear so relevant by now to justify an abrupt change of course. Particularly, in this draft we chose to use dSIP as basis for the specification of a Kademlia-based protocol to be used for Resource Lookup in P2PSIP, due to relative maturity of its specification [I-D.bryan-p2psip-dsip]. Kademlia was selected because of its simplicity, permormance, and widespread use in P2P application such as eMule and BitTorrent. As practical demonstration of the feasibility of our solution we have already provided a dSIP implementation of both Chord and Kademlia, available from based on the MjSip SIP stack [mjSip]. For simplicity of presentation this draft follows the same structure and style of the other proposed draft specifying the use of Chord with dSIP [I-D.zangrilli-p2psip-dsip-dhtchord]. Next versions of this draft may or may not rely on dSIP, which could be replaced by new text-based (SIP-based) or binary protocols. Cirani & Veltri Expires April 27, 2008 [Page 4] Internet-Draft Kademlia-based dSIP October 2007 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. o Kademlia: a DHT for decentralized peer-to-peer networks based on a XOR metric to compute the distance between two nodes on the network that exploits the fact that long-time active nodes are most likely to stay active. o Routing 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. Cirani & Veltri Expires April 27, 2008 [Page 5] Internet-Draft Kademlia-based dSIP October 2007 3. Background 3.1. Kademlia The Kademlia system [Kademlia] is one particular popular DHT algorithm. In Kademlia, resource with Resource-ID r will be stored by the k peers with Peer-ID closest to n, ensuring that every Resource-ID is associated with some peer. Cirani & Veltri Expires April 27, 2008 [Page 6] Internet-Draft Kademlia-based dSIP October 2007 4. Routing Table and Connection Table For each 0 <= i < 160, every node keeps a list of pair for later retrieval. This is a primitive operation, not an iterative one. o FIND NODE: FIND NODE takes a 160-bit ID as an argument. The recipient of the RPC returns triples for the k nodes it knows about closest to the target ID. These triples can come from a single k-bucket, or they may come from multiple k-buckets if the closest k-bucket is not full. In any case, the RPC recipient must return k items (unless there are fewer than k nodes in all its k-buckets combined, in which case it returns every node it knows about). This is a primitive operation, not an iterative one. o FIND VALUE: FIND VALUE behaves like FIND NODE, returning triples, with one exception: if the RPC recipient has received a STORE RPC for the key, it just returns the stored value. This is a primitive operation, not an iterative one. 4.2. Node lookup procedure The most important procedure a Kademlia participant must perform is to locate the k closest nodes to some given node ID. We call this procedure a node lookup. Kademlia employs an iterative algorithm for node lookups (although the paper describes it as recursive). The lookup initiator starts by picking alpha nodes from its closest non- empty k-bucket (or, if that bucket has fewer than alpha entries, it just takes the alpha closest nodes it knows of). The initiator then sends parallel, asynchronous FIND NODE RPCs to the alpha nodes it has chosen. alpha is a system-wide concurrency parameter, such as 3. In the iterative step, the initiator resends the FIND NODE to nodes it has learned about from previous RPCs. This iteration can begin before all alpha of the previous RPCs have returned. Kademlia uses alpha = 3, the degree of parallelism used. It appears that this value is optimal. There are at least three approaches to managing Cirani & Veltri Expires April 27, 2008 [Page 8] Internet-Draft Kademlia-based dSIP October 2007 parallelism. The first is to launch alpha probes and wait until all have succeeded or timed out before iterating. This is termed strict parallelism. The second is to limit the number of probes in flight to alpha; whenever a probe returns a new one is launched. We might call this bounded parallelism. A third is to iterate after what seems to be a reasonable delay (duration unspecifed), so that the number of probes in flight is some low multiple of alpha. This is called loose parallelism. Of the k nodes the initiator has heard of closest to the target, it picks alpha that it has not yet queried and resends the FIND NODE RPC to them. Nodes that fail to respond quickly are removed from consideration until and unless they do respond. If a round of FIND NODEs fails to return a node any closer than the closest already seen, the initiator resends the FIND NODE to all of the k closest nodes it has not already queried. The lookup terminates when the initiator has queried and gotten responses from the k closest nodes it has seen. Most operations are implemented in terms of the above lookup procedure: o iterativeStore: this is the Kademlia store operation. The initiating node does an iterativeFindNode, collecting a set of k closest contacts, and then sends a primitive STORE RPC to each. iterativeStores are used for publishing or replicating data on a Kademlia network. o iterativeFindNode: this is the basic Kademlia node lookup operation. As described above, the initiating node builds a list of k closest contacts using iterative node lookup and the FIND NODE RPC. The list is returned to the caller. o iterativeFindValue: this is the Kademlia search operation. It is conducted as a node lookup, and so builds a list of k closest contacts. However, this is done using the FIND VALUE RPC instead of the FIND NODE RPC. If at any time during the node lookup the value isreturned instead of a set of contacts, the search is abandoned and the value is returned. Otherwise, if no value has been found, the list of k closest contacts is returned to the caller. Cirani & Veltri Expires April 27, 2008 [Page 9] Internet-Draft Kademlia-based dSIP October 2007 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 Kademlia implementations. 5.1.2. DHT Name Parameter For this protocol, the dht-param token MUST be set to "Kademlia1.0". A peer receiving a message with a dht-param other than "Kademlia1.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=Kademlia1.0;overlay=chat;expires=600 5.2. The DHT-Link Header The DHT-Link header is not needed to implement this protocol. Information about other peers is carried in the Contact headers. Therefore there is no need to define the linktype and depth values used in the header. Cirani & Veltri Expires April 27, 2008 [Page 10] Internet-Draft Kademlia-based dSIP October 2007 6. Kademlia Overlay Algorithm Each peer keeps track of a list of up to k peers in its k-buckets. The Kademlia paper recommends keeping a number of k-buckets equal to the size in bits of the identifier, which is 160. However, it is possible to use a smaller number of k-buckets, as this affects only the effciency, that is, node lookups would possibly return more distant contacts than with 160 k-buckets. There is no actual need to this, though, unless to minimize memory usage by the peer. This would be useful for mobile devices, which feature a smaller amount of memory. Other than this case, the full number of k-buckets is recommended to increase performance. This is the choice made in this work. 6.1. Routing Table A peer starting an overlay for the first time needs not to do anything special in order to construct the overlay. Its k-buckets are initialized as empty and will be populated as other peers join the overlay and messages are routed to the peer. 6.2. Starting a New Overlay 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 bootstrap peer is also the admitting peer. After receiving a response from the bootstrap peer, the joining peer performs a node lookup targeting its own id in order to populate its k-buckets. 6.3. Peer Admission 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. 6.3.1. Constructing a Peer Registration 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): Cirani & Veltri Expires April 27, 2008 [Page 11] Internet-Draft Kademlia-based dSIP October 2007 REGISTER sip:192.0.2.129 SIP/2.0 To: From: Contact: Expires: 600 DHT-PeerID: ;algorithm=sha1; dht=Kademlia1.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 When handling a Peer Registration from a joining peer, the admitting peer MUST reply with a 200 response and update the appropriate k-bucket according to the rules outlined in Section 4. 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. After receiving the 200 response the joining peer must populate its routing table. This is done by performing a node lookup targeting its own id. This process will let the joining peer know about the k nodes that are closest to itself, which is the basic information that a node needs in order to be an active node in the Kademlia network, as it needs to be able to reply to a lookup request. As a side effect, other nodes would know about the joining peer. The messages exchanged in this process are peer query messages, which will be shown in Section 6.4. 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 response would look something like: Cirani & Veltri Expires April 27, 2008 [Page 12] Internet-Draft Kademlia-based dSIP October 2007 SIP/2.0 200 OK To: From: Contact: Expires: 600 DHT-PeerID: ;algorithm=sha1; dht=Kademlia1.0;overlay=chat;expires=600 Require: dht Supported: dht *After* the admitting peer sends the 200 response, it MUST update the appropriate k-bucket, and MUST obtain the information about the joining peer from the DHT-Peer header in the register request. It MUST NOT update the k-bucket prior to sending the 200. 6.4. Kademlia query processing If the target node is the receiving node itself, it MUST reply with a 200 message. Otherwise, the receiving peer MUST provide the contacts of the k closest nodes to the target id in the 302 message. These MUST be placed placed in Contact headers. If the receiving node knows less than k nodes it must report all the nodes it knows about. Additionally, the replying peer MUST include its DHT-PeerID header. 6.5. Kademlia Graceful Leaving Peers MUST unregister themselves. 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. 6.6. DHT Maintenance No operations are needed in order to keep the overlay stable, as the Kademlia algorithm is designed to update routing table and resource storing information anytime a message is received. Therefore, the Kademlia DHT needs no Chord-like stabilization procedure. 6.7. Peer Failure Peer failure is discovered through timed-out requests. Redundancy prevents against lost registrations. 6.8. Resource Replicas When a resource is registered, the registering peer MUST create at least 2 redundant replicas to ensure the registry information is Cirani & Veltri Expires April 27, 2008 [Page 13] Internet-Draft Kademlia-based dSIP October 2007 secure in the DHT. The registering peer is responsible for maintaining these replicas along with the primary entry. Moreover, Kademlia provides an inner replication mechanism by storing a registration in the k closest nodes to the resource's id. Cirani & Veltri Expires April 27, 2008 [Page 14] Internet-Draft Kademlia-based dSIP October 2007 7. Examples Instead of the SHA-1 algorithm, which would create a 2^160 nodes network, a simpler network is used. The hash is a 4 bit hash, which yields a namespace of size 16. Moreover, k (the maximum size of the k-buckets) is set to 4. Assume, for the sake of example simplicity, assume the peer Peer-ID 3 has IP address 192.0.2.3, the peer with Peer-ID 5 has IP address 192.0.2.5, and so on. Further assume that peer 1, peer 3, peer 7, peer 10, and peer 12 are currently enrolled in the overlay. In the case that each peer has been previously contacted by all other peer in the overlay, the k-buckets for each peer are shown in Figure 4. |----------|--------|--------|--------|--------|--------| | k-bucket | Peer1 | Peer3 | Peer7 | Peer10 | Peer12 | |----------|--------|--------|--------|--------|--------| | K0 | - | - | - | - | - | |----------|--------|--------|--------|--------|--------| | K1 | Peer3 | Peer1 | - | - | - | | | - | - | - | - | - | |----------|--------|--------|--------|--------|--------| | K2 | Peer7 | Peer7 | Peer1 | Peer12 | Peer10 | | | - | - | Peer3 | - | - | | | - | - | - | - | - | | | - | - | - | - | - | |----------|--------|--------|--------|--------|--------| | K3 | Peer10 | Peer10 | Peer10 | Peer1 | Peer1 | | | Peer12 | Peer12 | Peer12 | Peer3 | Peer3 | | | - | - | - | Peer7 | Peer7 | | | - | - | - | - | - | | | - | - | - | - | - | | | - | - | - | - | - | | | - | - | - | - | - | | | - | - | - | - | - | |----------|--------|--------|--------|--------|--------| Figure 4 7.1. Peer registration Assume peer 5, running on IP 192.0.2.5, port 5060, wants to join the overlay. From an out of band mechanism, peer 5 discovers peer 10 and uses it as a bootstrap. Peer 5 constructs a peer registration request and sends it to peer 10. Peer 10 verifies that the request is valid and executes the following steps: Cirani & Veltri Expires April 27, 2008 [Page 15] Internet-Draft Kademlia-based dSIP October 2007 1. updates its k-buckets: the sending peer's id is 5, that is 0101; the distance between peer 10 and peer 5 is therefore 1010 XOR 0101 = 1111 = 15; the contact of peer 5 should then be stored in the k-bucket of index 3 as d(1010, 0101) belongs to the [2^3, 2^4) interval; 2. replies with a 200 OK response. At this point, peer 5 has joined the overlay and the k-buckets of the peers are shown in Figure 5. |----------|--------|--------|--------|--------|--------|--------| | k-bucket | Peer1 | Peer3 | Peer5 | Peer7 | Peer10 | Peer12 | |----------|--------|--------|--------|--------|--------|--------| | K0 | - | - | - | - | - | - | |----------|--------|--------|--------|--------|--------|--------| | K1 | Peer3 | Peer1 | - | - | - | - | | | - | - | - | - | - | - | |----------|--------|--------|--------|--------|--------|--------| | K2 | Peer7 | Peer7 | - | Peer1 | Peer12 | Peer10 | | | - | - | - | Peer3 | - | - | | | - | - | - | - | - | - | | | - | - | - | - | - | - | |----------|--------|--------|--------|--------|--------|--------| | K3 | Peer10 | Peer10 | Peer10 | Peer10 | Peer1 | Peer1 | | | Peer12 | Peer12 | - | Peer12 | Peer3 | Peer3 | | | - | - | - | - | Peer7 | Peer7 | | | - | - | - | - | - | - | | | - | - | - | - | - | - | | | - | - | - | - | - | - | | | - | - | - | - | - | - | | | - | - | - | - | - | - | |----------|--------|--------|--------|--------|--------|--------| Figure 5 The registration process completes after peer 5 populates its routing table by performing a node lookup targeting its own id. This process is described in Section 7.2. The message flow for the registration is shown in Figure 6. Cirani & Veltri Expires April 27, 2008 [Page 16] Internet-Draft Kademlia-based dSIP October 2007 Peer5 Peer10 | | | REGISTER | |-------------------->| | | | 200 OK | |<--------------------| | | | | Peer5 -> Peer10 REGISTER sip:192.0.2.10 SIP/2.0 To: From: Contact: Expires: 600 DHT-PeerID: ;algorithm=sha1; dht=Kademlia1.0;overlay=p2psip;expires=600 Require: dht Supported: dht Peer10 -> Peer5 SIP/2.0 200 OK To: From: Contact: Expires: 600 DHT-PeerID: ;algorithm=sha1; dht=Kademlia1.0;overlay=p2psip;expires=600 Require: dht Supported: dht Figure 6 7.2. Peer query After joining the overlay, peer 5 needs to populate its routing table. To do so, it performs a node lookup targeting its own id. As peer 10 is the only contact in its routing table, peer 5 sends a peer query to it and sets the closest contacted node to NULL. Peer 10 receives the peer query, updates its k-buckets as a new message was received, and replies with a 302 response, reporting the k closest nodes to the target (peer 5) that is currently aware of. These k contacts will be, in order of proximity to the target node: peer 7, Cirani & Veltri Expires April 27, 2008 [Page 17] Internet-Draft Kademlia-based dSIP October 2007 peer 1, peer 3, and peer 12. Peer 5 receives the reply from peer 10 and retrieves all the contacts from the Contact header. Peer 5 first updates its k-buckets and then sets peer 10 as the closest contacted peer to the target at a distance of 15. Now peer 5 selects alpha = 3 contacts from the k contacts it has received by peer 10 and sends asynchronous peer queries to these contacts. Peer 5 chooses peer 7, peer 1, and peer 3. All these peers receive the request from peer 5, and therefore update their routing table by adding peer 5's contact. The peers then reply with a 302 response reporting the closest nodes to peer 5 they are aware of in the Contact header. When peer 5 receives the responses from each peer it updates its k-buckets and retrieves the contacts reported in the responses. After receiving all the replies, or after they have timed out, peer 5 updates the closest node contacted to be peer 7 at a distance of 2. Now peer 5 need to contact peer 12, as it is the only peer it has not yet queried. Peer 12 receives the request, updates its k-buckets, and replies with 302 response reporting the closest nodes it knows. Peer 5 receives the reply, updates its k-buckets, but it does not update its closest contacted node. At this point, since the round of queries has not yielded an improvement in proximity to the target, the peer query process terminates and peer 5 has populated its routing table. The k-buckets of the peers at this point are shown in Figure 7. |----------|--------|--------|--------|--------|--------|--------| | k-bucket | Peer1 | Peer3 | Peer5 | Peer7 | Peer10 | Peer12 | |----------|--------|--------|--------|--------|--------|--------| | K0 | - | - | - | - | - | - | |----------|--------|--------|--------|--------|--------|--------| | K1 | Peer3 | Peer1 | Peer7 | Peer5 | - | - | | | - | - | - | - | - | - | |----------|--------|--------|--------|--------|--------|--------| | K2 | Peer7 | Peer7 | Peer1 | Peer1 | Peer12 | Peer10 | | | Peer5 | Peer5 | Peer3 | Peer3 | - | - | | | - | - | - | - | - | - | | | - | - | - | - | - | - | |----------|--------|--------|--------|--------|--------|--------| | K3 | Peer10 | Peer10 | Peer10 | Peer10 | Peer1 | Peer1 | | | Peer12 | Peer12 | Peer12 | Peer12 | Peer3 | Peer3 | | | - | - | - | - | Peer7 | Peer7 | | | - | - | - | - | Peer5 | Peer5 | | | - | - | - | - | - | - | | | - | - | - | - | - | - | | | - | - | - | - | - | - | | | - | - | - | - | - | - | |----------|--------|--------|--------|--------|--------|--------| Cirani & Veltri Expires April 27, 2008 [Page 18] Internet-Draft Kademlia-based dSIP October 2007 Figure 7 The message flow for the registration is shown in Figure 8. Peer5 Peer10 Peer7 Peer1 Peer3 Peer12 | | | | | | | REGISTER | | | | | |----------->| | | | | | | | | | | | 302 Moved | | | | | |<-----------| | | | | | | | | | | | REGISTER | | | | | |------------------------>| | | | | | | | | | | REGISTER | | | | | |------------------------------------->| | | | | | | | | | REGISTER | | | | | |-------------------------------------------------->| | | | | | | | | | 302 Moved | | | | |<------------------------| | | | | | | | | | | | | 302 Moved | | | |<-------------------------------------| | | | | | | | | | | | | 302 Moved | | |<--------------------------------------------------| | | | | | | | | REGISTER | | | | | |--------------------------------------------------------------->| | | | | | | | | | | | 302 Moved | |<---------------------------------------------------------------| | | | | | | | | | | | | Peer5 -> Peer10 REGISTER sip:192.0.2.10 SIP/2.0 To: From: Contact: Expires: 600 DHT-PeerID: ;algorithm=sha1; Cirani & Veltri Expires April 27, 2008 [Page 19] Internet-Draft Kademlia-based dSIP October 2007 dht=Kademlia1.0;overlay=p2psip;expires=600 Require: dht Supported: dht Peer10 -> Peer5 SIP/2.0 302 Moved Temporarily To: From: Contact: , , , Expires: 600 DHT-PeerID: ;algorithm=sha1; dht=Kademlia1.0;overlay=p2psip;expires=600 Require: dht Supported: dht Figure 8 7.3. User registration Assume user Carl starts a UA co-located with peer 5. Carl's contact is carl@192.0.2.5 and his user name is carl@p2psip.org. Peer 5 hashes Carl's user name and determines that the corresponding resource-ID is 11. The registration proceeds through the following steps: 1. peer 5 performs a node lookup targeting id 11; 2. when the lookup has terminated, peer 5 has discovered the k peers closest to the id 11; in this case the lookup for id 11 results in peer 10, peer 12, peer 3, and peer 1; 3. peer 5 sends a resource registration request to each of the discovered nodes; 4. peers receive the registration request, store the registration, and reply with a 200 OK response. The dSIP messages for a user registration are (we show only one registration request and its relative response) shown in Figure 9. Cirani & Veltri Expires April 27, 2008 [Page 20] Internet-Draft Kademlia-based dSIP October 2007 Peer5 Peer10 | | | REGISTER | |-------------------->| | | | 200 OK | |<--------------------| | | | | Peer5 -> Peer10 REGISTER sip:192.0.2.10 SIP/2.0 To: From: Contact: Expires: 600 DHT-PeerID: ;algorithm=sha1; dht=Kademlia1.0;overlay=p2psip;expires=1200 Require: dht Supported: dht Peer10 -> Peer5 SIP/2.0 200 OK To: From: Contact: Expires: 600 DHT-PeerID: ;algorithm=sha1; dht=Kademlia1.0;overlay=p2psip;expires=600 Require: dht Supported: dht Figure 9 After the user registration has completed, the registration for Carl is stored by peers 10, 12, 3, and 1. This approach has therefore a built-in replication of registrations. 7.4. Session establishment Assume user Carl wishes to call user Simon. Simon is co-located with peer 10 and Simon's user name (simon@p2psip.org) hashes to 9. Further assume that the registration for Alice is stored by peer 10, Cirani & Veltri Expires April 27, 2008 [Page 21] Internet-Draft Kademlia-based dSIP October 2007 12, 1, and 3. Peer 5 performs a resource query for id 4. First, peer 5 finds k nodes in its k-buckets that are closest to the target id 4. It then selects of these nodes and sends a resource query request to each of these. Assume that peer 5's routing table does not contain peer 12. The k = 4 closest nodes to the target id in peer 5's k- buckets are peer 10, peer 1, peer 3, and peer 7. Since Kademlia does not specify any criteria for choosing the alpha nodes to contacts, suppose peer 5 decides to send the request to peer 7, peer 3, and peer 10. Peer 7 replies with a 302 response indicating the contacts in its routing table that are closest to the resource id, which would be peer 10, peer 12, peer 1, and peer 3. Peer 3, instead, replies with a 200 OK response, as it is currently storing the registration for Simon. When peer 5 receives the 200 OK response, the resource query is completed and the call can complete by Carl sending an INVITE request to Simon. The dSIP message flow for the session establishement is shown in Figure 10. Carl's UA Peer5 Peer7 Peer3 Peer10 Simon's UA | | | | | | | | REGISTER | | | | | |---------->| | | | | | | | | | | | REGISTER | | | | | |---------------------->| | | | | | | | | | | REGISTER | | | | | |---------------------------------->| | | | | | | | | | | | | | | | 302 Moved | | | | | |<----------| | | | | | | | | | | | | 200 OK | | | | |<----------- ----------| | | | | | | | | | INVITE | | | | | |---------------------------------------------------------->| | | | | | | | | | | |180 Ringing| |<----------------------------------------------------------| | | | | | | | | | | | 200 OK | |<----------------------------------------------------------| | | | | | | | ACK | | | | | |---------------------------------------------------------->| | | | | | | Cirani & Veltri Expires April 27, 2008 [Page 22] Internet-Draft Kademlia-based dSIP October 2007 | | | | | | Peer5 -> Peer7; Peer5 -> Peer3; Peer5 -> Peer10; REGISTER sip:192.0.2.7 SIP/2.0 To: From: DHT-PeerID: ;algorithm=sha1; dht=Kademlia1.0;overlay=p2psip;expires=800 Require: dht Supported: dht REGISTER sip:192.0.2.3 SIP/2.0 To: From: DHT-PeerID: ;algorithm=sha1; dht=Kademlia1.0;overlay=p2psip;expires=800 Require: dht Supported: dht REGISTER sip:192.0.2.10 SIP/2.0 To: From: DHT-PeerID: ;algorithm=sha1; dht=Kademlia1.0;overlay=p2psip;expires=800 Require: dht Supported: dht Peer7 -> Peer5 SIP/2.0 302 Moved Temporarily To: From: Contact: , , , DHT-PeerID: ;algorithm=sha1; dht=Kademlia1.0;overlay=p2psip;expires=600 Require: dht Supported: dht Peer10 -> Peer5 Cirani & Veltri Expires April 27, 2008 [Page 23] Internet-Draft Kademlia-based dSIP October 2007 SIP/2.0 200 OK To: From: Contact: DHT-PeerID: ;algorithm=sha1; dht=Kademlia1.0;overlay=p2psip;expires=1200 Require: dht Supported: dht Figure 10 Cirani & Veltri Expires April 27, 2008 [Page 24] Internet-Draft Kademlia-based dSIP October 2007 8. Implementation The dSIP system has already been successfully implemented. The implementation includes support for the Chord DHT, as required in the old dSIP draft [I-D.bryan-p2psip-dsip], and for the Kademlia DHT, following the outline sketched in this document. The implementation relies on the mjSip library [mjSip], developed at the University of Parma (Italy), which is a complete Java-based open source implementation of a SIP stack, and available under the terms of the GNU GPL license as published by the Free Software Foundation. mjSip implements the complete layered stack architecture as defined in [RFC3261] (Transport, Transaction, and Dialog sublayers), and is fully compliant with the standard. Moreover, it includes higher level interfaces for Call Control and User Agent implementations. The complete source code for the implementation of the dSIP architecture, including support for the Chord and Kademlia DHTs, is available at the following location: . Other DHTs can be easily implemented by extending the currently available API. Cirani & Veltri Expires April 27, 2008 [Page 25] Internet-Draft Kademlia-based dSIP October 2007 9. Security Considerations [TO BE INVESTIGATED] Cirani & Veltri Expires April 27, 2008 [Page 26] Internet-Draft Kademlia-based dSIP October 2007 10. IANA Considerations This document defines the "dht-param" value to be "Kademlia1.0". Cirani & Veltri Expires April 27, 2008 [Page 27] Internet-Draft Kademlia-based dSIP October 2007 11. References 11.1. Normative References [I-D.bryan-p2psip-dsip] Bryan, D., "dSIP: A P2P Approach to SIP Registration and Resource Location", draft-bryan-p2psip-dsip-00 (work in progress), February 2007. [I-D.bryan-p2psip-reload] Bryan, D., "REsource LOcation And Discovery (RELOAD)", draft-bryan-p2psip-reload-01 (work in progress), July 2007. [I-D.lowekamp-p2psip-dsip-security] Lowekamp, B. and J. Deverick, "Authenticated Identity Extensions to dSIP", draft-lowekamp-p2psip-dsip-security-00 (work in progress), February 2007. [I-D.willis-p2psip-concepts] Willis, D., "Concepts and Terminology for Peer to Peer SIP", draft-willis-p2psip-concepts-04 (work in progress), March 2007. [I-D.zangrilli-p2psip-dsip-dhtchord] Zangrilli, M. and D. Bryan, "A Chord-based DHT for Resource Lookup in P2PSIP", draft-zangrilli-p2psip-dsip-dhtchord-00 (work in progress), February 2007. [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. Cirani & Veltri Expires April 27, 2008 [Page 28] Internet-Draft Kademlia-based dSIP October 2007 11.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", February 2003. [Kademlia] Maymounkov, P. and D. Mazieres, "Kademlia: A Peer-to-peer Information System Based on the XOR Metric", March 2002. [KademliaSpecification] XLattice, "Kademlia: A Design Specification". [mjSip] Veltri, L., "mjSIP". Cirani & Veltri Expires April 27, 2008 [Page 29] Internet-Draft Kademlia-based dSIP October 2007 Authors' Addresses Simone Cirani Department of Information Engineering - University of Parma Parco Area delle Scienze, 181/A Parma 43100 Italy Email: simone.cirani@gmail.com Luca Veltri Department of Information Engineering - University of Parma Parco Area delle Scienze, 181/A Parma 43100 Italy Email: luca.veltri@unipr.it URI: http://www.mjsip.org Cirani & Veltri Expires April 27, 2008 [Page 30] Internet-Draft Kademlia-based dSIP October 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). Cirani & Veltri Expires April 27, 2008 [Page 31]