TOC 
SIPPING WGD. Bryan
Internet-DraftCollege of William and Mary
Expires: January 16, 2006C. Jennings
 Cisco Systems
 July 15, 2005

A P2P Approach to SIP Registration and Resource Location

draft-bryan-sipping-p2p-01

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 January 16, 2006.

Copyright Notice

Copyright © The Internet Society (2005).

Abstract

This document outlines the motivation and requirements for a Peer-to-Peer (P2P) based approach for SIP registration and resource discovery using distributed hash tables, and presents the architectural design for such a system. This design removes the need for central servers from SIP, while offering full backward compatibility with SIP, allowing reuse of existing clients, and allowing P2P enabled nodes to communicate with conventional SIP entities. A basic introduction to the concepts of P2P is presented, backward compatibility issues addressed, and the security considerations are considered.

This is very early work to explore the characteristics that a P2P system might have. It is less secure in many ways than the traditional approach to SIP but has certain other interesting characteristics that may make it desirable in some situations. This work is being discussed on the sipping@ietf.org mailing list.



Table of Contents

1.  Introduction
2.  Terminology
3.  Background
    3.1  Peer-to-Peer Fundamentals
    3.2  Distributed Hash Table (DHT) Systems
    3.3  Chord
    3.4  Issues for P2P Systems
4.  Overview
    4.1  Node Functions and Behavior
    4.2  P2P Overlay Structure
    4.3  Message Format
    4.4  Node Registration
    4.5  User Registration
    4.6  Session Establishment
5.  Message Syntax
    5.1  Option Tags
    5.2  Hash Algorithms and the alg URI Parameter
    5.3  Node-IDs and the user=node URI Parameter
    5.4  Resource-IDs and the resource-ID URI Parameter
    5.5  Overlay Names and the overlay URI Parameter
    5.6  The DHT-NodeID Header
    5.7  The DHT-Link Header
    5.8  URIs
        5.8.1  P2P Node URIs
        5.8.2  P2P User URIs
6.  Node/DHT Operations
    6.1  Starting a New Overlay
    6.2  Bootstrapping
    6.3  Node Registration
        6.3.1  Constructing a Node Registration
        6.3.2  Processing the Node Registration
    6.4  Resource Location/Search
        6.4.1  Constructing a Node Search Message
        6.4.2  Processing Node Search Message
    6.5  Populating the Joining Node's Finger Table
    6.6  Transfering User Registrations
    6.7  Nodes Leaving the Overlay Gracefully
    6.8  Periodic Stabilization
    6.9  Handling Failed Requests
    6.10  Node Failure
7.  User-level operations
    7.1  User Registration
        7.1.1  User Registrations
        7.1.2  Refreshing User Registrations
        7.1.3  Removing User Registrations
        7.1.4  Querying User Registrations
    7.2  Session Establishment
    7.3  Presence
8.  Examples
    8.1  Example of a Node Registration
    8.2  Example of a User Registration
    8.3  Example of a Session Establishment
    8.4  Example of a Node Leaving the System
    8.5  Example of a Successful User Search
    8.6  Example of an Unsucessful User Search
9.  Security Considerations
    9.1  Threat Model
    9.2  Protecting the Namespace
        9.2.1  Certificate Based Protection
    9.3  Protecting the Routing
    9.4  Protecting the Signaling
    9.5  Protecting the Media
    9.6  Replay Attacks
    9.7  Cut and Paste Attacks
    9.8  Identity Theft Attacks
    9.9  Limitations of the Security
10.  Open Issues
11.  Acknowledgments
12.  Implementations
13.  IANA Considerations
14.  Definitions
15.  References
    15.1  Normative References
    15.2  Informative References
§  Authors' Addresses
§  Intellectual Property and Copyright Statements




 TOC 

1. Introduction

As SIP (Rosenberg, J., Schulzrinne, H., Camarillo, G., Johnston, A., Peterson, J., Sparks, R., Handley, M., and E. Schooler, “SIP: Session Initiation Protocol,” June 2002.)[2] and SIMPLE based Voice over IP (VoIP) Instant Messaging (IM) systems have increased in popularity, situations have emerged where centralized servers are either inconvenient or undesirable. For example, a group of users wishing to communicate between each other, but using machines that are not consistently connected to the network are often forced to use a central server that is outside the control of the group. Similarly, groups wishing to establish ephemeral networks for use in meetings, conferences, or classes often do not wish to configure a centralized server. Organizations may also want to allow their members to communicate with each other without traffic flowing to third parties, but may not have the staff or equipment to maintain a server.

Peer-to-Peer (P2P) computing has emerged as a mechanism for completely decentralized, server-free implementations of various applications. This draft presents a SIP based system that uses P2P mechanisms to remove the need for central servers in SIP and SIMPLE based communications systems. This draft derives from work done on the SoSIMPLE (Bryan, D., Jennings, C., and B. Lowekamp, “SOSIMPLE: A Serverless, Standards-based, P2P SIP Communication System,” June 2005.)[5] P2P SIP project.



 TOC 

2. Terminology

In this document, the key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" are to be interpreted as described in RFC2119 (Bradner, S., “Key words for use in RFCs to Indicate Requirement Levels,” March 1997.)[1].

Terminology defined in RFC 3261 (Rosenberg, J., Schulzrinne, H., Camarillo, G., Johnston, A., Peterson, J., Sparks, R., Handley, M., and E. Schooler, “SIP: Session Initiation Protocol,” June 2002.)[2] is used without definition.

Terms relating to P2P or new to this document are defined when used and are also defined in the Definitions (Definitions) section 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.



 TOC 

3. Background

3.1 Peer-to-Peer Fundamentals

The fundamental principle behind Peer-to-Peer (P2P) Architectures is that each and every member of the network has equal importance in the transactions that take place on the network, and that these nodes communicate with each other to accomplish tasks. Contrast this with the more traditional Client-Server Architecture in which a large number of clients communicate only with a small number of central servers responsible for performing tasks. Each entity that participates in a P2P system, usually called a node or peer, provides server-like functionality and services as well as being a client within the system. In this way, the services or resources that would be provided by a centralized entity are instead available from the nodes of the system. Note that a particular node may or may not provide a particular service, but some node does, ensuring that collectively the nodes can provide that particular service. The logical network connecting the peers to one another is referred to as an overlay network or overlay, as it is in some sense a new, small sub-network at a higher logical level than lower level network connections.

Some P2P networks have certain nodes that provide a higher level of functionality. Often these nodes form a P2P network and connect to each other, then serve a number of true clients. These more powerful nodes are often referred to as super-nodes. This approach is often used to traverse NATs, with nodes residing outside of the NATs serving as super-nodes, and to allow nodes with more bandwidth to serve as concentrators for information.

Many P2P systems further assume that nodes are ephemeral in nature. A node may join or leave the overlay at any time. The design of algorithms for P2P architectures take this into account. Information is often replicated, and the topology of the overlay can be quickly adapted as nodes enter and leave.

Likely the best known (or perhaps infamous) use of P2P technology is file sharing. In these systems, individual users store files, and join the overlay network by connecting to a small number of nodes already in the overlay. When the user wishes to locate a particular file they don't have, they contact these neighbors. Several alternatives exist for this query. In early systems, a node searching for a file would ask their neighbors if they had the file. If one of these nodes had the file, it would respond telling the requester they had the file. If not, they passed the request on to their neighbors. The search was limited to a particular depth using a Time to Live (TTL) mechanism, but since nodes had no idea what other nodes were doing, queries continued until the TTL was reached, even if some node had already replied. This approach, often called the flood search approach, proved inefficient.

3.2 Distributed Hash Table (DHT) Systems

To improve the efficiency, most newer systems locate resources using a Distributed Hash Table, or DHT. Nodes are organized using a Distributed Hash Table (DHT) structure. In such a system, every resource has a Resource-ID, which is obtained by hashing some keyword or value that uniquely identifies the resource. Resources can be thought of as being stored in a hash table at the entry corresponding to their Resource-ID. The nodes that make up the overlay network are also assigned an ID, called a Node-ID, which maps to the same hash space as the Resource-IDs. A node is responsible for storing all resources that have Resource-IDs near the node's Node-ID. The hash space is divided up so that all of the hash space is always the responsibility of some particular node, although as nodes enter and leave the system a particular node's area may change. Messages are exchanged between the nodes in the DHT as the nodes enter and leave to preserve the structure of the DHT and exchange stored entries. Various DHT implementations may visualize the hash space as a grid, circle, or line.

Nodes keep information about the location of other nodes in the hash space and in general know about most nodes nearby in the hash space, and progressively fewer more distant nodes. When a user wishes to search, they consult the list of node they are aware of and contact the node with the Node-ID nearest the desired Resource-ID. If that node does not know how to find the resource, it either suggests the closest node it knows about, or asks that node itself and returns the result. In this fashion, the request eventually reaches the node responsible for the resource, which then replies to the requester.

3.3 Chord

The 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,” .)[6] system is one particular popular DHT algorithm. Chord uses a ring-type structure for the nodes in the overlay. In this structure, a node with a hash of 0 would be located adjacent to a node that hashes to the highest possible hash value. If the hash has 2^n bits in the range, each node will keep a "finger table" of pointers to at most n other nodes. The ith entry in the finger table contains a pointer to a node at least 2^(i) units away in the hash space. These 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 nodes pointed to by these finger table entries are referred to as the neighbors of the node, since they can be reached directly.

Searching in Chord is accomplished by sending messages to the node in the finger table that is closest to the destination address. That neighbor will have finer resolution detail about the area and can route the message closer to the desired node. This process is repeated until the message reaches the node responsible for the destination, which can determine if the resource searched for is present.

3.4 Issues for P2P Systems

All P2P systems need to solve the problem of locating some initial node in the overlay, often called a bootstrap node, in order to join. Some approaches taken to solving this problem include using some set of fixed nodes, requiring that a node be located using an offline mechanism, or using a broadcast/multicast mechanism.

P2P architectures offer several advantages over centralized architectures. P2P systems distribute resources across multiple machines, greatly reducing the potential of failure due to a single node failing. This results in increased robustness, as well as some measure of protection from Denial-of-Service (DOS) attacks. P2P systems also have the advantage of scaling more easily as the number of nodes increases, since each new node offers additional server-like functionality when it joins. P2P systems have their own class of problems, however. In particular, malicious nodes can provide incorrect information, possibly denying access to resource in the system. Additionally, users can sometimes create many nodes in the system, possibly using this as a mechanism for hijacking the system. These type of attack is often referred to as a Sybil (Douceur, J., “The Sybil Attack,” March 2002.)[7] attack.

When referring to P2P systems in this document, we are referring to what are called true P2P systems in the literature. Some systems, such as the original Napster system, as well as many existing SIP deployments (which are occasionally referred to as P2P), are more properly referred to as hybrid systems. In hybrid systems, nodes communicate with each other to exchange information, but resource location is still handled with a centralized server. Our goal in this document is a system that requires no central server of any type.



 TOC 

4. Overview

In this section we provide an overview of how P2P SIP works. Protocol details are provided in the remainder of the document.

Unlike a conventional SIP architecture, P2P SIP systems require no central servers. In a traditional SIP architecture many UAs connect to a central proxy server. In a P2P SIP network the peers connect directly to a few other peers, forming a virtual overlay network of peers which communicate with each other to provide services in the overlay. The nodes participating in the overlay not only act as traditional SIP UAs, allowing their users to place and receive calls, but, when viewed collectively with the other peers, perform the roles of registrars and proxies in traditional SIP networks. These roles include resource location, maintaining presence information, and call routing. Each participating peer will maintain some fraction of the information that would normally be maintained by the proxy and/or registrar in a conventional SIP network.

4.1 Node Functions and Behavior

P2P SIP nodes provide many functions, more than any single entity in a traditional SIP architecture. Minimally, a participating peer must be an active member of the overlay and must provide some SIP "server-like" behaviors as well. The code that implements the additional server-like and DHT behavior can be located in several places in the network. The simplest is to have nodes that are endpoints directly joining the overlay as peers. In this case, these nodes provide the basic functionality of any SIP endpoint, but additionally implement the operations described in this document to enable self-organization and provide SIP functionality.

The behavior can also be located in an adapter node, which allow one or more non-P2P aware SIP UAs to interact with the P2P overlay network. These adapters perform the additional self-organizing and SIP server-like behavior on behalf of the UA or UAs it supports. In this case, only the adapter node is a peer in the overlay, the UAs are not peers themselves. All interaction with the P2P network is carried out by the adapter node. The adapter essentially acts as a proxy server for the unmodified SIP UAs. The adapter can take the form of a small software shim, or may be code within a traditional RFC 3261 server.

In most places in this document, which type of node we are discussing won't affect the discussion. In those cases where it will, we have noted the differences.

4.2 P2P Overlay Structure

Nodes are organized using a Distributed Hash Table (DHT) P2P structure based on Chord. Like Chord, the system uses consistent hashing to a one dimensional namespace, conceptually in the form of a circle. Unlike Chord, all the messages needed to maintain the DHT are implemented as SIP messages. We use many Chord-like terms, which are defined in the section Definitions and Terminology. (Definitions)

Every resource has a Resource-ID, obtained by hashing some keyword that identifies the resource. In the case of users, the unique keyword is the userid and the resource is the registration -- a mapping between the user name and a contact. Resources can be thought of as being stored in the distributed hash table at a location corresponding to their Resource-ID. The nodes that make up the overlay network are also assigned an ID, called a Node-ID, which maps to the same hash space as the Resource-IDs. Node-IDs are created by hashing the IP address and port of the node providing service. This creates some security issues. See the Open Issues (Open Issues) section of this document for more information. We allow for different algorithms to be used to calculate these hashes, but all members of the overlay must use the same algorithm.

Like Chord, a resource with Resource-ID k will be stored by the first node with Node-ID equal to or greater (mod the size of the namespace) than k, ensuring that every Resource-ID is associated with some node. As nodes enter and leave, resources may be stored on different nodes, so the information related to them is exchanged as nodes enter and leave. Redundancy is used to protect against loss of information in the event of a node failure.

Each node keeps information about how to contact some number of other nodes in the overlay. In terms of the overlay network, these are the neighbors of the node, since they are reachable in one hop. The node keeps track of its immediate predecessor node, as well as one or more successor nodes. The node also keeps a table of information about other neighbors called a finger table. 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 node at least 2^i away from the node, for 0 <= i <= 159, mod 2^160. Essentially, the node divides the overlay hash circle up into segments, the first being the segment from [0-2^0) away from the node, the second being from [2^0-2^1), the third being from [2^1-2^2), etc., all the way to the segment from [2^158-2^159) away from node. It then stores an entry in the finger table for the first node with a Node-ID greater than or equal to the start of this interval. In this way, the node has many entries pointing to nearby nodes, and less and less entries about more remote nodes. These tables are populated when the node joins the overlay, and are kept up to date by periodically updating them.

Messages are routed by taking advantage of a key property of these finger tables. A node has more detailed, fine grained information about nodes near it than further away, but it knows at least a few more distant nodes. When locating a resource with a particular Resource-ID, the node will send the request to the finger table entry with the Node-ID closest to the desired Resource-ID. Since the node receiving the request has many neighbors with similar Node-IDs, it will presumably know of a node with a Node-ID closer to the Resource-ID, and suggests this node to in response. The request is then resent to this closer node. The process is repeated until the node responsible for the Resource-ID is located, which can then determine if it is storing the information.

We recommend that, while using the full SHA-1 hash algorithm, nodes maintain less than the full 160 entries in the finger table, perhaps 16 entries for small networks, 32 for larger networks. As this effects only the efficiency of the client, it is left to the implementor to determine a useful value.

4.3 Message Format

All of the messages that are needed to maintain the DHT, as well as those needed to query for information are implemented using SIP messages. We will briefly discuss the exchange of information in the system. Fundamentally, messages are being exchanged for two purposes. The purpose of the first class of messages is to maintain the DHT, such as the messages needed to join or leave the overlay, and to transfer information between nodes. The second type of messages are those used to allow the users of the overlay to communicate. This second type of message is the type most SIP users will be familiar with -- registering users, inviting other users to a session, etc.

4.4 Node Registration

When a node wishes to join the overlay (the joining node), it hash its IP address and port to create a Node-ID, and will send a REGISTER message to a bootstrap node already in the overlay, requesting to join. The bootstrap node will look up the node it knows nearest the Node-ID of the joining node, and respond with 302 redirect it to this nearer node. The joining node will repeat this process until it reaches the node currently responsible for the space it will occupy. The joining node then exchanges additional REGISTER messages with this node, called the admitting node, to allow the joining node to learn about other nodes in the overlay (neighbors) and to obtain information about resources the joining node will be responsible for maintaining. Other messages will be exchanged later to maintain the overlay as other nodes enter and leave, as well as to periodically verify the information about the overlay, but once the initial set messages are exchanged, a node has joined the overlay.

4.5 User Registration

The REGISTER messages that are exchanged to allow a node to join the overlay make up a node registration, allowing the node to join the overlay and participate in storing and locating information. The node registration does not, however, register the node's user(s) with the P2P SIP network -- it has only allowed the node to join the overlay.

Once a node has joined the overlay, the user that node hosts must be registered with the system. This process is referred to as user registration. This registration is analogous to the traditional SIP registration, in which a message is sent to the registrar creating a mapping between a SIP URI and a user's contact. The only difference is that since there is no central registrar, some node in the overlay will maintain the registration on the users behalf. The user doesn't know this node initially, but will locate the node using a distributed search.

The user's node will hash the user name, resulting in a resource-ID corresponding to that user name. A REGISTER message containing contact information for the user is constructed. The user's node will look up the node it is aware of with a Node-ID nearest the resource-ID calculated from the user's name, and forward the message to this node. If the receiving node is not responsible for the portion of the hash space corresponding to that resource-ID, it will return a 302 Redirect response containing the node nearest in the hash space that it is aware of. The user's node will then resend the request to this nearer node. The process is repeated until the REGISTER message reaches the node responsible for the portion of the hash space that includes the hashed user id. This node then stores the registration for that user, and returns a 200 response. For redundancy, the user should also store the registration at some other nodes immediately following the responsible node, so it will send registrations to these nodes as well, The addresses of these nodes will be provided in the 200 of the responsible node.

4.6 Session Establishment

Establishing a session works very much like user registration. The caller's node constructs an INVITE message, and hashes the name of the called. The caller's node sends the message to the node nearest the hashed name that it is aware of. Again, if the node the message is sent to is not responsible for that ID, a 302 with a closer node is returned, and the caller's node will retry sending the message to this node. The behavior is slightly different when the node storing that registration is finally reached. Rather than returning a 200, as in the registration case, it sends back a 302 where the contact is the actual address of the called's node. When the caller resends the message to that node, the call is completed in the conventional SIP format.



 TOC 

5. Message Syntax

5.1 Option Tags

We create the new option tag "dht" to indicate support for DHT based P2P SIP. As described in RFC 3261. Nodes MUST include a Require and Supported header with the option tag dht for all messages that are intended to processed in a P2P method or include P2P extensions. Clients supporting P2P and contacting another SIP entity using a non-P2P mechanism for a transaction that may or may later be P2P SHOULD include a Supported header with dht.

5.2 Hash Algorithms and the alg URI Parameter

The hash algorithm used for the overlay is included in several places in P2P SIP messages. It may appear in URIs or in P2P specific headers. In all cases, the tokens used to identify the algorithm MUST be the same as those used in other SIP documents such as draft-ietf-sip-identity-05. (Peterson, J. and C. Jennings, “Enhancements for Authenticated Identity Management in the Session Initiation Protocol (SIP),” March 2005.)[4] Currently, those consist of 'rsa-sha1', indicating SHA-1 as defined in RFC 3174. (Eastlake, 3rd, D. and P. Jones, “US Secure Hash Algorithm 1 (SHA1),” September 2001.)[3] Implementations SHOULD use the SHA-1 algorithm for all implementations. We formally define algorithms here as:

alg-type = "rsa-sha1" / token

Where token represents other algorithms, which may be defined later or defined by the implementor.

URIs in the message containing values or URI parameters encoded with the algorithm MUST include the ident-info-alg URI parameter (alg=<alg name>) as defined in draft-ietf-sip-identity-05. The alg URI parameter is of type other-param as defined in RFC 3261.

5.3 Node-IDs and the user=node URI Parameter

Node-IDs are determined by the algorithm being used. In the case of rsa-sha1, <40 hex digit hash>. The Node-ID MUST be formed by taking the IP address of the node, followed by a colon, followed by the port, and hashing this string with the appropriate algorithm. For rsa-sha1, the resulting Node-ID looks like a04d371e3f4078a7a8c49bb7a4ea6199fc9d5c77. Formally, Node-IDs are defined as follows:

NodeID = token

When using rsa-sha1:

NodeID = 40LHEX

Additionally, the URI parameter "user=node" MUST be used when registering nodes into the overlay, as opposed to registering users to receive calls. Formally, user=node parameter is defined by using the keyword "node" of type token, serving as "other-user" in the definition of user-param from RFC 3261.

5.4 Resource-IDs and the resource-ID URI Parameter

No special restrictions, beyond those imposed by RFC 3261, are imposed on the user IDs in a P2P SIP system. Note that various security schemes, two of which are discussed in Protecting the Namespace (Protecting the Namespace) may place restrictions of their own on the User IDs.

Resource-IDs MUST be formed by hashing the user ID using the appropriate hashing algorithm for this overlay. Formally:

ResourceID = token

When using rsa-sha1:

ResourceID = 40LHEX

Following a user name, the optional URI parameter resource-ID=<Resource-ID> MAY be provided. This is strictly as a courtesy to nodes receiving requests for this user, as it prevents them from having to hash the user name again before routing. This parameter is a courtesy only and MUST NOT be used when making any changes to the data stored in an overlay, as it may be spoofed or incorrect. If the hash parameter is used incorrectly for routing, this only affects the transmitting node's user. If it is used to insert or modify stored information, it can affect the systems integrity. Nodes MUST verify the hash of user names before making changes that affect the overlay. The resource-ID URI parameter is of type other-param as defined in RFC 3261

5.5 Overlay Names and the overlay URI Parameter

Each overlay is named using a string, which SHOULD be unique to a particular deployment environment. Nodes will use this value to identify messages in cases where they may belong to multiple overlays simultaneously. These are defined formally simply as a token:

overlay-name = token

Nodes MUST include a the URI parameter "overlay" following all URIs that are intended to be P2P URIs. This parameter is defined formally as:

overlay-uri-param = "overlay" EQUAL overlay-name

5.6 The DHT-NodeID Header

We introduce a new SIP header called the DHT-NodeID header. This header is used to express the Node-ID of the sending node.

The format of the DHT-NodeID header is as follows. It consists of the header name/colon, followed by a token indicating the hash algorithm followed by a space, a Node-ID, as described above, followed by a space, and finally an address for this node. Thus the header format is:

DHT-NodeID: <algorithm> <Node-ID> <IP address>

Examples:

A node with an SHA-1 hashed Node-ID of a04d371e3f4078a7a8c49bb7a4ea6199fc9d5c77 on IP 192.1.1.1:

DHT-NodeID: rsa-sha1 a04d371e3f4078a7a8c49bb7a4ea6199fc9d5c77 192.1.1.1

The formal syntax of the DHT-NodeID header is:

DHT-NodeID = "DHT-NodeID" HCOLON alg-type SWS NodeID SWS host

NodeID and alg-type are defined above.

5.7 The DHT-Link Header

We introduce a new SIP header called the DHT-Link header. The DHT-Link header is used to transfer information about where in the DHT other nodes are located. In particular, it is used by nodes to pass information about the predecessor, successors, and finger table information stored by a node.

The format of the DHT-Link header is as follows. It consists of the header name/colon, followed by 5 parameters -- type, depth, algorithm,-- Node-ID and IP address, each separated by a space. Thus the header format is:

DHT-Link: <type> <depth> <algorithm> <Node-ID> <IP address>

and an example, the header might look like (using a shortened 10 digit Node-ID for clarity):

DHT-Link: P 1 rsa-sha1 671a65bf22 192.168.0.1

The type parameter MUST have 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 node. S MUST indicate that the information describes a successor node, and F MUST indicate that it is a finger table node from the sending node.

The depth parameter MUST be a non-negative integer representing which predecessor, successor, or finger table entry is being described. For predecessors and successors, this MUST indicate numeric depth. In other words, "P 1" indicates the nodes immediate predecessor, while "S 5" would indicate the fifth successor. "P 0" or "S 0" would indicate the sending node 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 node in the hash space by a power of two. That is, finger table entry i points to a range that begins with a node 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 parameter corresponds to this exponent i. In other words, "F 0" would correspond to a finger table entry pointing to the node for a range starting a distance 2^0 = 1 from the Node-ID in the hash space, while "F 6" would point to node used to search for resources in a range starting 2^6 = 64 away from the Node-ID in the hash space.

Examples (again using shortened Node-ID for clarity):

The sending node's immediate predecessor is 192.168.0.1:
DHT-Link: P 1 rsa-sha1 671a65bf22 192.168.0.1
The sending node's fifth successor is 10.0.1.1:
DHT-Link: S 1 rsa-sha1 23fe841ddd 10.0.1.1
The sending node's 2^3 finger table entry (the range starting 2^3 = 8 away in the hash space) is 192.168.0.3:
DHT-Link: F 3 rsa-sha1 75783b47df 192.168.0.3

The formal syntax of the DHT-Link header is:

DHT-Link = "DHT-Link" HCOLON DHTL-type SWS DHTL-depth SWS alg-type SWS Node-ID SWS host

DHTL-type = "P" / "S" / "F"

DHTL-depth = 1*DIGIT

alg-type and Node-ID are defined above.

5.8 URIs

There are two types of URIs for P2P systems, node URIs and user URIs.

5.8.1 P2P Node URIs

The userinfo (username) portion of P2P node URIs MUST be Node-IDs, constructed by hashing the IP Address and port of the appropriate node. The hostport portion of the URI is constructed using the rules in RFC 3261. P2P node URIs MUST include the user=node URI parameter to indicate that the target of the URI is a node, and MUST NOT include any other user-parameter. P2P node URIs MUST include the alg and overlay URI parameters, which indicate what algorithm is being used for hashing, and what the name of the logical overlay is. P2P node URIs MUST NOT include the resource-ID URI parameter, as it is intended to define information about resources that are stored in the overlay, not information about the nodes making up the overlay. P2P node URIs used in name-addr SHOULD NOT include any display-name information, and nodes receiving name-addrs for nodes with display-name information MUST ignore the information.

Formally, P2P node URIs are constructed like sip or sips headers, and the formal grammar in RFC 3261 for SIP-URI, SIPS-URI, username, hostport, and uri-parameters, and headers are unchanged. The hashed NodeID is used for the username. The URI parameters user=node, alg and overlay are formally defined above.

Examples (again using shortened Node-ID for clarity):

The URI for a node using the rsa-sha1 hash algorithm, with hashed ID 86ff438a32 in an overlay named sipchat, and IP address 192.168.0.7:
sip:86ff438a32@192.168.0.7;user=node;overlay=sipchat;alg=rsa-sha1
The URI for a node using the rsa-sha1 hash algorithm, with hashed ID ed57487add in an overlay named cs101chat, using IP address 10.6.5.5, used in a To header:
To: <sip:ed57487add@10.6.5.5>;user=node;overlay=cs101chat;alg=rsa-sha1

5.8.2 P2P User URIs

The userinfo (username) portion of P2P user URIs MUST be the unhashed username. This value MUST not be hashed to create the username for the URI. The hostport portion of the URI is constructed using the rules in RFC 3261. P2P user URIs MUST NOT include the user=node URI parameter, because this indicate that the target of the URI is a node. P2P user URIs MAY include other user-parameters such as user=phone. P2P node URIs MUST include the alg and overlay URI parameters, which indicate what algorithm is being used for hashing, and what the name of the logical overlay is. P2P user URIs SHOULD include the resource-ID URI parameter, which MUST be the Resource-ID constructed by hashing the username.

Formally, P2P user URIs are constructed like sip or sips headers, and the formal grammar in RFC 3261 for SIP-URI, SIPS-URI, username, hostport, and uri-parameters, and headers are unchanged. The hashed ResourceID is used as the value for the resource-ID parameter. The URI parameters alg and overlay are formally defined above.

Examples (again using shortened Node-ID for clarity):

The URI for a user with username bob using the rsa-sha1 hash algorithm, with hashed Resource-ID 723fedaab1 in an overlay named sipchat. The IP address for the URI is 192.168.13.225, and the optional resource-ID URI parameter is included:
sip:bob@192.168.13.225;overlay=sipchat;alg=rsa-sha1;resource-ID=723fedaab1
The URI, used in a To header for user Alice White, with username alice. Alice's node is using the rsa-sha1 hash algorithm, and is a member of an overlay called techtalk. The URI is for IP address 10.56.222.11.This example omits the optional resource-ID URI parameter:
To: Alice White <sip:alice@10.56.222.11>;alg=rsa-sha1;overlay=techtalk


 TOC 

6. Node/DHT Operations

The SIP REGISTER message is used extensively in this system. REGISTER is used to register users, as in conventional SIP systems, and we discuss this further in the User Registration (User Registration) section of this document. Additionally, SIP REGISTER messages are used to register a new node with the DHT and to transmit the information needed to maintain the DHT. The algorithms used in this system draw extensively from the Chord algorithms. It is node registration -- rather than user registration, that is discussed in this section of the document.

6.1 Starting a New Overlay

A node starting an overlay for the first time need not do anything special in order to construct the overlay. The node MUST initalize its finger table such that all entries point to itself. The node MUST set its successor (which is also the first entry of the finger table) to itself, and MUST set its predecessor to NULL.

6.2 Bootstrapping

When a node wishes to join an existing overlay, it must first locate some node that is already participating in the overlay. referred to as the bootstrap node. Nodes MAY use any method they choose to locate the initial bootstrap node. The following are a few of many methods that may be used:

Static Locations:
Some number of nodes in the overlay may be persistent, and have well know addresses. These address could be configured into the node application, or obtained using an out-of-band mechanism such as a web page.
Cached Nodes:
While this mechanism cannot be used the first time that a node runs, on subsequent attempts to join the overlay, a node might attempt to use a previously contacted peer as a bootstrap node.
Broadcast mechanisms:
Nodes can use a broadcast mechanism to locate the initial peer, for example by sending the first REGISTER message to the SIP multicast address.

In the rest of this section, we assume that the joining node is not the first node, and that a bootstrap node has been located.

6.3 Node Registration

After a node has located an initial bootstrap node, the process of joining the overlay is started by constructing a REGISTER message and sending it to the bootstrap node. Third party registration MAY NOT be used for registering nodes into the overlay, and attempts to do so MUST be rejected by the node receiving such a request. (although third party registrations are used for other purposes, as described below) The node first calculates their Node-ID. Nodes MUST calculate the Node-ID using the appropriate algorithm to hash the IP address and port of the node. This done by concatenating the IP address, a colon, and the port, and then hashing this. Once the Node-ID has been calculated, the node MUST construct a SIP REGISTER message following the instructions in RFC3261, section 10, with the exceptions/rules outlined below.

6.3.1 Constructing a Node Registration

The Request-URI SHOULD include only the IP address of the node that is being contacted (initially the bootstrap node). This URI SHOULD NOT include any of the P2P defined parameters. For example, a request intended for node 10.3.44.2 should look like: "REGISTER sip:10.3.44.2 SIP/2.0".

The To and From fields of the REGISTER message MUST contain a valid P2P Node URI constructed according to the rules in the subsection P2P node URIs (P2P Node URIs) in the Message Syntax section. The URIs MUST used the node's hashed User-ID as the username, and MUST contain the alg, overlay, and user=node URI parameters. The address for both the To and From fields MUST be the IP address of the sending node.

While using the IP address of the sender for To and From is different than traditional SIP registers, there are two reasons for this. First, in a P2P network, which node the request is sent to, and thus the domain for which the registration is intended, is not important. Any node can process the information, and the user name is not associated with a particular IP address or DNS domain, but rather with the overlay name, which is encoded elsewhere. In that sense, the IP address used is irrelevant. Choosing the domain of the sender ensures that if a request is sent to a non-P2P aware registrar RFC 3261 compliant registrar, it will be rejected. RFC 3261 (section 10.3) states that a registrar should examine the To header to determine if it presents a valid address-of-record for the domain it serves. Since the IP address of the sending node is unlikely to be a valid address for a non-P2P aware registrar, the message will be rejected, eliminating possibly erroneous handling by the registrar.

The node MUST provide a contact field when registering so that this may be identified as a registration/update, rather than a query. This URI in the contact must be a valid P2P node URI. The node MUST provide an expires parameter or expires header with a non-zero value. As in standard SIP registrations, Expire headers with a value of zero will be used to remove registrations. The contact URI MUST use the hashed User-ID as the username, and MUST contain the alg, overlay, and user=node parameters.

The node MUST provide a DHT-NodeID header field containing their calculated Node-ID and IP.

The node MUST include Require and Supported headers with the option tag "dht".

Assume that a node running on IP address 10.4.1.2 on port 5060 attempts to join the network by contacting a bootstrap node at address 10.7.8.129. Further assume that 10.4.5.23:5060 hashes to 463ac4b449 under rsa-sha1 (using a 10 digit hash for example simplicity), and that the overlay name is chat. An example message would look like this (neglecting tags):

REGISTER sip:10.7.8.129 SIP/2.0
To: sip:463ac4b449@10.4.1.2;user=node;alg=rsa-sha1;overlay=chat
From: sip:463ac4b449@10.4.1.2;user=node;alg=rsa-sha1;overlay=chat
Contact: sip:463ac4b449@10.4.1.2;user=node;alg=rsa-sha1;overlay=chat
Expires: 600
DHT-NodeID: rsa-sha1 463av4b449 10.4.1.2
Require: dht
Supported: dht

6.3.2 Processing the Node Registration

The receiving node determines that this is a P2P SIP message based on the presence of the dht Require and Supported fields. In the event that the node does not support P2P extensions, it MUST reply with a 5xx class response such as 501 Not Implemented. If the node examines the overlay parameters and determines that this is not an overlay the node participates in, the node MUST reject the message with a 488 Not Acceptable Here response. In the event a P2P node receives a non-P2P request, it SHOULD reject it with a message such as 421 Extension Required.

The presence of user=node URI parameter and a valid expiration time indicate that this message is a node registration and the receiving node MUST process this as a DHT level request. The bootstrap node SHOULD verify that the hashed Node-ID corresponds to the IP address specified in the URI by hashing the IP address and port and comparing it to the Node-ID. If these do not match, the message should be rejected with a response of 493 Undecipherable. The bootstrap node examines the Node-ID to determine if it corresponds to the portion of the overlay the bootstrap node is responsible for. If it does, the node will handle the REGISTER request itself, if not, it will provide the joining node with information about a node closer to the area of the overlay where the joining nodes Node-ID is stored.

If the bootstrap node is not responsible for the area of the hash table where Node-ID should be stored, the node MUST generate a 302 message. Nodes SHOULD NOT proxy the request, as described in RFC3261:10.3, item1. (although they could, it would place undue burden on a peer to ask it to do so, so we advise against it) The 302 is constructed following the rules of RFC 3261 with the following rules. The bootstrap node MUST look up the node in its finger table nearest the joining node's Node-ID, and use it to create a contact field in the form of a node URI, as specified in the P2P Node URIs (P2P Node URIs) section of this document, including appropriate URI parameters. The response MUST contain a valid DHT-NodeID header. This response is sent to the joining node.

Using our example register from the previous section, assume that bootstrap node 10.7.8.129 receives the message, determines it is not responsible for that area of the overlay, and redirects the joining node to a node with Node-ID 47e46fa2cd at IP address 10.3.1.7. The 302 response, again neglecting tags, is shown below. Note that the node creating response uses its information to construct the DHT-NodeID header.

SIP/2.0 302 Moved Temporarily
To: sip:463ac4b449@10.4.1.2;user=node;alg=rsa-sha1;overlay=chat
From: sip:463ac4b449@10.4.1.2;user=node;alg=rsa-sha1;overlay=chat
Contact: sip:47e46fa2cd@10.3.1.7;user=node;alg=rsa-sha1;overlay=chat
Expires: 600
DHT-NodeID: rsa-sha1 837dd9321a 10.7.8.129
Require: dht
Supported: dht

Upon receiving the 302, the joining node uses the contact address as the new bootstrap node. The process is repeated until the node contacted is currently responsible for the area of the DHT in which the new node will reside. The receiving node that is responsible for that portion of the overlay is referred to as the admitting node.

The admitting node MUST verify that the Node-ID hash of the IP address is valid, as described above. If these do not match, the message should be rejected with a response of 493 Undecipherable. The admitting node recognizes that it is presently responsible for this region of the hash space -- that is, it is currently the node storing the information that this Node-Id will eventually be responsible for. The admitting node knows this because the joining node's Node-ID falls between the Node-ID of the admitting node and its predecessor. The admitting node is responsible for helping the joining node become a member of the overlay. In addition to verifying that the Node-ID was properly calculated, the admitting node 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 node. 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 admitting node MUST reply with a 200 response if the joining node has a Node-ID between the admitting node's Node-ID and the admitting node's predecessor's Node-ID. The admitting node MUST provide the joining node with its current predecessor and successor in the 200. These MUST be placed placed in DHT-Link headers, as described in The DHT-Link Header (The DHT-Link Header) 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 200 SHOULD contain the next 4 successor nodes, for use in redundancy. All nodes SHOULD maintain 4 successors at all times for redundancy. Additionally, the admitting node MUST include a DHT-NodeID header containing the admitting node's Node-ID and IP.

The joining node obtains the Node-ID and address of the admitting node from the DHT-Node header, and the information about the admitting node's predecessor from the DHT-Link P 1 header. The joining node MUST set its successor to be the admitting node, and its predecessor to be the admitting node's predecessor. The admitting node MUST set its predecessor to be the joining node, and MUST obtain the information from the DHT-Node header in the register request. The admitting node's successor is unchanged.

The admitting node MAY optionally send a copy of the entries in their finger table to the joining node, using DHT-Link headers of the F type. As the joining node will likely be nearby the admitting node in the hash space (at least for an overlay with a reasonable number of nodes), this finger table information can likely improve the performance of the queries required to obtain a correct finger table information. It is the responsibility of the joining node to calculate and reconstruct the intervals that the admitting would have based on the F parameters and the Node-ID supplied in the 200. Node that providing the first finger is optional, as it is (by definition) identical to the required successor field.

Continuing the example register from the previous sections, assume now that the node with Node-ID 47e46fa2cd and IP address 10.3.1.7 is currently responsible for 463ac4b449 in the namespace. The admitting node here does send the fingertable, 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: sip:463ac4b449@10.4.1.2;user=node;alg=rsa-sha1;overlay=chat
From: sip:463ac4b449@10.4.1.2;user=node;alg=rsa-sha1;overlay=chat
Contact: sip:463ac4b449@10.4.1.2;user=node;alg=rsa-sha1;overlay=chat
Expires: 600
DHT-NodeID: rsa-sha1 47e46fa2cd 10.3.1.7
DHT-Link: P 1 rsa-sha1 4201034a89 10.233.4.1
DHT-Link: S 1 rsa-sha1 574fb2d34a 10.0.233.227
DHT-Link: F 2 rsa-sha1 5f8dd34100 10.44.76.67
Require: dht
Supported: dht

Both the admitting node and joining node SHOULD immediately perform both a stabilize and fix fingers operation, as described below, to stabilize the overlay.

6.4 Resource Location/Search

Finding the node responsible for a particular hash space works as follows. This corresponds to the find_successor operation in Chord.

As with traditional SIP, REGISTER messages that are sent without a Contact: header are assumed to be queries. If a user wishes to know if a particular resource exists, or what node would be responsible for it if it did exist, a register with no Contact is used.

6.4.1 Constructing a Node Search Message

The node looks for the finger table entry that covers the range they wish to search. If the finger table entry has not yet been filled (and the node was not provided another finger table to use to get started), then the node may send the request to any node it has available, including their successor, predecessor, or even some boot strap node. While these initial searches may be less efficient, they will succeed. The Request-URI SHOULD include only the IP address of the node that the search is intended for. This URI SHOULD NOT include any of the P2P defined parameters. For example, a request intended for node 10.3.44.2 should look like: "REGISTER sip:10.3.44.2 SIP/2.0".

Because this is a query, the sending node MUST NOT include a contact header. The sender MUST NOT include an expires header.

The node MUST provide a DHT-NodeID header field containing their calculated Node-ID and IP.

The node MUST include Require and Supported headers with the option tag "dht".

Assume that a node running on IP address 10.4.1.2 on port 5060 wants to determine who is responsible for Node-ID 4823affe45, and asks the node with IP address 10.5.6.211 Further assume that the node uses rsa-sha1 (using a 10 digit hash for example simplicity), and that the overlay name is chat. An example message would look like this (neglecting tags):

REGISTER sip:10.5.6.211 SIP/2.0
To: sip:4823affe45@10.4.1.2;user=node;alg=rsa-sha1;overlay=chat
From: sip:463ac4b449@10.4.1.2;user=node;alg=rsa-sha1;overlay=chat
DHT-NodeID: rsa-sha1 463av4b449 10.4.1.2
Require: dht
Supported: dht

The To and From fields of the REGISTER message MUST contain a valid P2P Node URI constructed according to the rules in the subsection P2P node URIs (P2P Node URIs) in the Message Syntax section. The From URI MUST used the node's hashed User-ID as the username and the sending Nodes IP address. The To URI MUST have a userid set to the Node-ID we are searching for, and MUST use the IP address of the sending node. Both the To and From MUST contain the alg, overlay, and user=node URI parameters.

6.4.2 Processing Node Search Message

The receiving node determines that this is a P2P SIP message based on the presence of the dht Require and Supported fields. In the event that the node does not support P2P extensions, it MUST reply with a 5xx class response such as 501 Not Implemented. If the node examines the overlay parameters and determines that this is not an overlay the node participates in, the node MUST reject the message with a 488 Not Acceptable Here response. In the event a P2P node receives a non-P2P request, it SHOULD reject it with a message such as 421 Extension Required.

The presence of user=node URI parameter and lack of an expiration time indicate that this message is a node query and the receiving node MUST process this as a DHT level request. The receiving node MUST NOT alter any of its internal values such as successor or predecessor in response to this message, since it is a query. The node SHOULD verify that the hashed Node-ID corresponds to the IP address specified in the URI by hashing the IP address and port and comparing it to the Node-ID. If these do not match, the message should be rejected with a response of 493 Undecipherable. The receiving node examines the Node-ID in the To field and determines if it corresponds to the portion of the overlay the bootstrap node is responsible for. If it does, the node will handle the query itself, if not, it will provide the node with information about a node closer to the area the query applies to

If the receiving node is not responsible for the area of the hash table where the query Node-ID should be stored, the node MUST generate a 302 message. Nodes SHOULD NOT proxy the request, as described in RFC3261:10.3, item1. (although they could, it would place undue burden on a peer to ask it to do so, so we advise against it) The 302 is constructed following the rules of RFC 3261 with the following rules. The receiving node MUST look up the node in its finger table nearest the joining node's Node-ID, and use it to create a contact field in the form of a node URI, as specified in the P2P Node URIs (P2P Node URIs) section of this document, including appropriate URI parameters. The response MUST contain a valid DHT-NodeID header. This response is sent to the querying node.

Upon receiving the 302, the querying node uses the contact address as the new query node. The process is repeated until the node contacted is currently responsible for the area of the DHT in which the new node will reside.

If the receiving node is responsible for the region that the search key lies within, it MUST respond to the query. The admitting node knows this because the joining node's Node-ID falls between the Node-ID of the admitting node and its predecessor. If the receiving node's Node-ID exactly matches the search key, it MUST respond with a 200 OK message. If it is responsible for that region, but its Node-ID is not the search key, it MUST respond with a 404 Not Found message. The node MAY verify that the Node-ID and IP address presented by the querying node in the message. If these do not match, the message should be rejected with a response of 493 Undecipherable.

The reply that is constructed MUST provide the current predecessor and successor in the 200 or 404 message. These MUST be placed placed in DHT-Link headers, as described in The DHT-Link Header (The DHT-Link Header) 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 200 or 404 SHOULD contain the next 4 successor nodes, for use in redundancy. Additionally, the replying node MUST include a DHT-NodeID header containing the admitting node's Node-ID and IP.

6.5 Populating the Joining Node's Finger Table

Once admitted, the joining node MUST populate its finger table. If the admitting node provided finger table information, the joining node MAY use this information to construct a temporary finger table, and use this temporary table in the queries to populate the table, but MAY NOT simply use the provided finger table information. To populate the finger table, the node must take its Node-ID and, by applying the offsets, for each finger, as described in calculate the Resource-IDs corresponding to the start of each finger interval. See the P2P Overlay Structure (P2P Overlay Structure) subsection in the Overview section of this document. The joining node then performs a search for each of these start intervals, as described above. The resulting Node-IDs/IPs are entered into the corresponding finger table entries. This is analogous to the fix_fingers procedure in Chord.

6.6 Transfering User Registrations

Because the joining node has split the area in the hash space that the admitting node was responsible for, some portion of these user registrations are now the responsibility of the joining node, and these user registrations are handed to the joining node by means of these user registrations. These are third party registration. Third part registrations are allowed for user registrations and arbitrary searches, but are not allowed for node registrations. These registrations are exactly the same as those discussed in Registering and Removing User Registrations (User Registration), except that as they are third party registration from a node, the From field should be constructed as described in the sections above.

6.7 Nodes Leaving the Overlay Gracefully

Nodes MUST send their registrations to their successor before leaving the overlay, as described in the section above. Additionally, nodes MUST unregister themselves with both their successor and predecessor. This REGISTER is constructed exactly the same as one used to connect, with the following exceptions. The expires parameter or header MUST be provided, and MUST be set to 0. The nodes MUST include DHT-Link headers listing their predecessor and 4 successor nodes. This allows the nodes receiving the requests to obtain the information needed to correct their predecessor and successor nodes, as well as keep their successor lists needed for redundancy current.

6.8 Periodic Stabilization

In order to keep the overlay stable, nodes must periodically perform book keeping operations to take into account node failures. Periodically (we suggest 60-360 seconds), nodes MUST perform an arbitrary query for their current successor's Node-ID. The node should examine the response from their successor. The predecessor reported should be the node that made the request. If it is not, the node MUST update their own successor with the predecessor returned, and additionally MUST send a REGISTER to this node, structured as if the stabilizing node had just entered the system. This will serve to properly update the overlay. This is analogous to the notify procedure in Chord.

Additionally, when this periodic stabilization takes place, the node should perform searches as discussed in Populating the Joining Node's Finger Table (Populating the Joining Node's Finger Table) to ensure that the finger table is up to date.

6.9 Handling Failed Requests

When a request sent to any node fails, the user MUST perform searches to update their pointers. If the failed request was sent to a node in the finger table, than the searches discussed in Populating the Joining Node's Finger Table (Populating the Joining Node's Finger Table) should be performed for all intervals that rely on the failed node. If the predecessor or successor node fails, a search for the predecessor or successor's ID should be performed, and requests should should be repeated, based on the predecessors and successors returned by these, until the correct successor or predecessors are determined.

6.10 Node Failure

Node failures is handled by the periodic stabilization and responses to failed requests discussed above. 4-way redundancy registrations ensures that unless 4 sequential nodes fail, registrations will not be lost.



 TOC 

7. User-level operations

7.1 User Registration

User registrations are maintained, collectively, by the nodes of the overlay. Registrations SHOULD be stored redundantly in some number of nodes succeeding the node responsible for the registration, and we describe how to do this in these sections.

7.1.1 User Registrations

When a node is in the overlay, it must register the contacts for users for which it is responsible into the overlay as data. This differs from the registrations described above in that these registrations are responsible for entering a URI->IP address mapping into the overlay as data, rather than joining a node into the overlay. These registrations are very similar to those outlined in section 10 of RFC3261. As with node registrations, the user's full user id should be hashed using SHA-1, resulting in a Resource-ID corresponding to the user's user id. The node will route the message to the node listed in the finger table covering the interval containing the Resource-ID of the hashed user id. The user name itself is not hashed, however. The node constructs the register message as follows:

The Request-URI that is constructed for the REGISTER MUST be addressed to the node the request is sent to. The To and From fields of the REGISTER message MUST contain a P2P user URI as defined in the section P2P User URIs (P2P User URIs). The username should be the unhashed username. The To and From fields MUST contain the IP address of the node participating in the overlay. These URIs MUST include the alg and overlay URI parameter, and SHOULD include the Resource-ID URI parameter containing the hashed value of the username. These MUST NOT include the user=node parameter, as these are user registrations.

The node MUST provide a contact field when registering, so that this may be identified as a registration/update, rather than a query. The node MUST provide an expires parameter with a non-zero value or an Expire header. As in standard SIP registrations, Expires parameters with a value of zero will be used to remove registrations. The username for the contact should be the username of the unhashed user name of the user, and the address should be the address of the user's UA (which may or may not be the IP address of the node, since the node could be an adaptor node). The contact header MUST include the alg and overlay URI parameters, and SHOULD include a resource-ID parameter as well.

The request MUST include the value dht in Require and Supported headers. The request MUST include a DHT-NodeID header and MAY include one or more DHT-Link headers passing information about predecessor and successor nodes. The message SHOULD NOT include information about finger table entries.

The message is routed in a fashion exactly analogous to that described in the section on node registration (Node Registration). 302 messages are sent to indicate that the message is to be redirected to another node (this contact should contain the URI parameter user=node). Once the message arrives at a destination that is responsible for that portion of the hash namespace, the node recognizes it as a user registration, rather than a node wishing to join the system, based upon the fact that the To and From fields do not contain user=node parameters. The node responds with a 200, and SHOULD include at least one successor node that can be used by the registering node to send redundant registrations to. These responses MUST NOT include user=node URI parameters, but are otherwise constructed in the same way as node registrations.

[TO DO: explicitly define this behavior, even if it is mostly cut and paste from the node registration section, to prevent any misunderstanding.]

The registering node SHOULD use the successor nodes provided in the 200, and construct registrations to send to these nodes as well for redundancy purposes.

[To Do: Need to have some way of letting these nodes know these are redundant registrations so they don't 302 them as "that isn't an interval I am responsible for" Currently, there is nothing in the protocol to allow it. Perhaps yet another URI parameter?]

7.1.2 Refreshing User Registrations

User registrations are refreshed exactly as described in RFC 3261, Section 10. Users should send a new registration with a valid expiration time prior to the time that the registration is set to expire.

Agents MAY cache the address where they previously registered and attempt to send refreshes to this node, but they are not guaranteed success, as a new node may have registered and may now be responsible for this are of the space. In such a case, the node will receive a 302 from the node with which they previously registered, and should follow the same procedure for locating the node they used in the initial registration.

As with initial registrations, the sending node should use the successors provided in the 200 to send these updates to the redundant nodes as well.

7.1.3 Removing User Registrations

User registrations are removed exactly as described in RFC 3261, Section 10. Users MUST send a registration with expiration time of zero.

As with initial registrations, the sending node SHOULD use the successors provided in the 200 to send these registration removals to the redundant nodes as well.

7.1.4 Querying User Registrations

User registrations are constructed as described in RFC 3261, Section 10. Users should send a registration with no contact header. As described in Resource Location/Search (Resource Location/Search), this mechanism can also be used to locate the node responsible for a particular Resource-ID.

7.2 Session Establishment

When a caller wishes to send a SIP message (such as an INVITE or MESSAGE message to start a conversation, or a subscribe message to create a presence relationship with another user), the user must locate the node where this called's information resides.

The caller hashes the name of the called and obtains a Resource-ID in the DHT for that user. The user then searches for this Resource-ID as described in the section titled Resource Location. (Resource Location/Search)

Once the node responsible for the Resource-ID is located, it will provide either a 302, providing a contact for the users UA, or will provide a 404 if the user is not registered. If a 302 with a valid contact is received, the call will complete in the standard RFC 3261 fashion. If a 404 is received, the user is not registered and the call will not complete. This is analogous to the responses from node level queries.

7.3 Presence

We use SUBSCRIBE/NOTIFY for this. We subscribe to every node on our buddy list when we come online. If the user's are online, that means that we know exactly where they are. Nodes SHOULD use their buddies as additional "finger table" entries (essentially, cached values), consulting these first, as connections are likely to be made to people on the users buddy list. These should also be periodically checked, as described in the Periodic Stabilization (Periodic Stabilization) section.

If buddies are offline, one should periodically try to make the connection. Alternately, we use the same register mechanism that is used at node-join time to let nodes we are here, rather than forcing them to do periodic subscribes. If a UA receives a SUBSCRIBE from some buddy that is currently offline, it SHOULD attempt to subscribe to that buddy. This will allow people that are reciprocally on each others buddy lists to rapidly be notified when one or the other comes online.



 TOC 

8. 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 Node-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 nodes, denoted by capital Ns, with Node-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

Further, for the sake of example simplicity, assume the node Node-ID 3 has IP address 10.0.0.3, the node node with Node-ID 5 has IP address 10.0.0.5, etc.

Data that hashes to a Resource-ID is stored by the next node whose Node-ID is equal to or larger than the Resource-ID, mod the size of the hash. As such, Node 3 is responsible for any resources hashing from 11-15, as well as 0-3. Node 5 is responsible for resources with Resource-IDs from 4-5, and Node 10 is responsible for resources with Resource-IDs from 6-10. From this illustration, you follow a location clockwise until you encounter a node, and this is the node 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 nodes. For our system, with 4 bit identifiers, we have 4 finger table entries. These finger tables point to the node nearest to Node-ID + 2^0, Node-ID + 2^1, Node-ID + 2^2 and Node-ID + 2^3. If no node is present at that location, the next available node will be used. Thus, for our 3 nodes, the finger tables look like the following, with ranges (indicated in traditional mathematical form) mapping to the node those requests will be sent to:


                  Node 3         Node 5         Node 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

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 node 5. User bob is also registered, and has a Resource-ID of 12, so his registration information is stored by node 3. Assume further that bob's UA is co-located with Node 10, so his contact is sipchat/bob@10.10.10.10, and that alice is running a UA on a completely separate IP of 10.99.99.99, but is using an adapter node running on Node 3, therefore Node 3 will send messages on alice's behalf, but alice's contact is sipchat/alice@10.99.99.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.

8.1 Example of a Node Registration

Assume a new node wishes to join the system. The node has an IP address of 10.0.0.14, which we shall assume hashes to a Node-ID of 14. From an out of band mechanism, this node discovers node 5. This node constructs a REGISTER as described in Node Registration (Node Registration), and sends it to node 5. Node 5 verifies that 10.0.0.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 node 3. The node then sends a 302 back to node 14, with a contact of node 3.

Node 14 the constructs a new REGISTER and sends it to Node 3. Again, Node 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 node to the system. Finally, Node 3 sends a third party registration on behalf of bob to Node 14, transferring bob's registration to the new node.


  Node 14             Node 5              Node 3
     |                   |                   |
     |(1) REGISTER       |                   |
     |------------------>|                   |
     |                   |                   |
     |(2) 302            |                   |
     |<------------------|                   |
     |                   |                   |
     |(3) REGISTER       |                   |
     |-------------------------------------->|
     |                   |                   |
     |(4) 200            |                   |
     |<--------------------------------------|
     |                   |                   |
     |(5) REGISTER       |                   |
     |<--------------------------------------|
     |                   |                   |
     |(6) 200            |                   |
     |-------------------------------------->|
     |                   |                   |


Node 14 -> Node 5

REGISTER sip:10.0.0.5 SIP/2.0
To: sip:14@10.0.0.14;user=node;alg=rsa-sha1;overlay=chat
From: sip:14@10.0.0.14;user=node;alg=rsa-sha1;overlay=chat
Contact: sip:14@10.0.0.14;user=node;alg=rsa-sha1;overlay=chat
Expires: 600
DHT-NodeID: rsa-sha1 14 10.0.0.14
Require: dht
Supported: dht


Node 5 -> Node 14

SIP/2.0 302 Moved Temporarily
Contact: sip:3@10.0.0.3;user=node;alg=rsa-sha1;overlay=chat
DHT-NodeID: rsa-sha1 5 10.0.0.5
DHT-Link: P 1 rsa-sha1 3 10.0.0.3
DHT-Link: S 1 rsa-sha1 10 10.0.0.10
Require: dht
Supported: dht


Node 14 -> Node 3

REGISTER sip:10.0.0.3 SIP/2.0
To: sip:14@10.0.0.14;user=node;alg=rsa-sha1;overlay=chat
From: sip:14@10.0.0.14;user=node;alg=rsa-sha1;overlay=chat
Contact: sip:14@14.0.0.14.14;user=node;alg=rsa-sha1;overlay=chat
Expires: 600
DHT-NodeID: rsa-sha1 14 10.0.0.14
Require: dht
Supported: dht


Node 3 -> Node 14

SIP/2.0 200 OK
To: sip:14@10.0.0.14;user=node;alg=rsa-sha1;overlay=chat
From: sip:14@10.0.0.14;user=node;alg=rsa-sha1;overay=chat
Contact: sip:14@10.0.0.14;user=node;alg=rsa-sha1;overlay=chat
Expires: 600
DHT-NodeID: rsa-sha1 3 10.0.0.3
DHT-Link: P 1 rsa-sha1 10 10.0.0.10
DHT-Link: S 1 rsa-sha1 5 10.0.0.5
DHT-Link: F 0 rsa-sha1 5 10.0.0.5
DHT-Link: F 1 rsa-sha1 5 10.0.0.5
DHT-Link: F 2 rsa-sha1 10 10.0.0.10
DHT-Link: F 3 rsa-sha1 3 10.0.0.3
Require: dht
Supported: dht


Node 3 -> Node 14

REGISTER sip:10.0.0.14 SIP/2.0
To: sip:bob@p2psip.org;user=node;alg=rsa-sha1;overlay=chat
From: sip:3@10.0.0.3;user=node;rsa-sha1;overlay=chat
Contact: sip:bob@10.0.0.10;user=node;alg=rsa-sha1;overlay=chat
Expires: 201
DHT-NodeID: rsa-sha1 3 3.3.3.3
Require: dht
Supported: dht


Node 14 -> Node 3

SIP/2.0 200 OK
To: sip:bob@p2psip.org;user=node;alg=rsa-sha1;overlay=chat
From: sip:3@10.0.0.3;user=node;alg=rsa-sha1;overlay=chat
Contact: sip:bob@10.0.0.10;user=node;alg=rsa-sha1;overlay=chat
Expires: 201
DHT-NodeID: rsa-sha1 14 10.0.0.14
Require: dht
Supported: dht

8.2 Example of a User Registration

Assume user Carl starts a UA co-located with node 5. Carl's contact will be carl@10.0.0.5, and his user name will be carl@p2psip.org. Carl's Node hashes his user id and determines that the corresponding Resource-ID will be 11 -- that is, Carl's registration will be stored by by the node responsible for Resource-ID 11 -- ultimately Node 3 in our example.

Carl's UA begins by constructing a SIP REGISTER message as described in Registering User Registrations (User Registrations). Carl's UA consults its finger table, and determines that it should route requests pertaining to a Resource-ID of 11 to Node 10. The REGISTER is sent to Node 10, which observes that it is not responsible for that portion of the namespace, and consults the finger table, finding Node 3 in the appropriate entry. Node 10 sends a 302 containing Node 3 as a contact.

Node 5 constructs a new REGISTER on behalf of carl, and sends it to Node 3. Node 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 nodes -- in this case 2 (although in our contrived example, one is node 5 itself) that Carl's node 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]


  Node 5              Node 10             Node 3
     |                   |                   |
     |(1) REGISTER       |                   |
     |------------------>|                   |
     |                   |                   |
     |(2) 302            |                   |
     |<------------------|                   |
     |                   |                   |
     |(3) REGISTER       |                   |
     |-------------------------------------->|
     |                   |                   |
     |(4) 200            |                   |
     |<--------------------------------------|
     |                   |                   |


Node 5 -> Node 10

REGISTER sip:10.0.0.10 SIP/2.0
To: sip:carl@p2psip.org;resource-ID=11;alg=rsa-sha1;overlay=chat
From: sip:carl@p2psip.org;resource-ID=11;alg=rsa-sha1;overlay=chat
Contact: sip:carl@10.0.0.5;resource-ID=11;alg=rsa-sha1;overlay=chat
Expires: 600
DHT-NodeID: rsa-sha1 5 10.0.0.5
Require: dht
Supported: dht


Node 10 -> Node 5

SIP/2.0 302 Moved Temporarily
Contact: sip:3@10.0.0.3;user=node;alg=rsa-sha1;overlay=chat
DHT-NodeID: rsa-sha1 10 10.0.0.10
DHT-Link: P 1 rsa-sha1 5 10.0.0.5
DHT-Link: S 1 rsa-sha1 3 10.0.0.3
Require: dht
Supported: dht


Node 5 -> Node 3

REGISTER sip:10.0.0.3 SIP/2.0
To: sip:carl@p2psip.org;resource-ID=11;alg=rsa-sha1;overlay=chat
From: sip:carl@p2psip.org;resource-ID=11;alg=rsa-sha1;overlay=chat
Contact: sip:carl@5.5.5.5;resource-ID=:11;alg=rsa-sha1;overlay=chat
Expires: 600
DHT-NodeID: rsa-sha1 5 10.0.0.5
Require: dht
Supported: dht


Node 3 -> Node 5

SIP/2.0 200 OK
To: sip:carl@p2psip.org;resource-ID=11;alg=rsa-sha1;overlay=chat
From: sip:carl@p2psip.org;resource-ID=11;alg=rsa-sha1;overlay=chat
Contact: sip:carl@10.0.0.5;resource-ID=11;alg=rsa-sha1;overlay=chat
Expires: 600
DHT-NodeID: rsa-sha1 3 10.0.0.3
DHT-Link: P 1 rsa-sha1 10 10.0.0.10
DHT-Link: S 1 rsa-sha1 5 10.0.0.5
DHT-Link: S 2 rsa-sha1 10 10.0.0.10
Require: dht
Supported: dht

8.3 Example of a Session Establishment

Assume user bob wishes to call user Alice. Bob's node hashes Alice's user id, resulting in a Resource-ID of 5. Bob's node (recall that Bob's UA is co-located with node 10) consults it's finger table, and determines that a request for Resource-ID 5 should be routed to Node 3. An INVITE message is constructed and routed to Node 3. Node 3 determines it is not responsible for a Resource-ID of 5, looks up the ID in it's finger table and determines it should be routed to Node 5, so it returns a 302 referring to Node 5. Bob's node resends the INVITE to Node 5, which stores Alice's information. It sends a 302 with Alice's contact -- sipchat/alice@10.99.99.99. Bob finally sends an invite to Alice's UA, and session establishment is completed as normal.

[To Do: Need to get the messages right. Alice's UA doesn't support dht, so need to tweak the messages a bit as far as supported and such. May need to figure out if sipchat/ belongs in her contact]


  Node 10             Node 3            Node 5           Alice UA
     |                   |                |                  |
     |(1) INVITE         |                |                  |
     |------------------>|                |                  |
     |                   |                |                  |
     |(2) 302            |                |                  |
     |<------------------|                |                  |
     |                   |                |                  |
     |(3) INVITE         |                |                  |
     |----------------------------------->|                  |
     |                   |                |                  |
     |(4) 302            |                |                  |
     |<-----------------------------------|                  |
     |                   |                |                  |
     |(5) INVITE         |                |                  |
     |------------------------------------------------------>|
     |                   |                |                  |
     |(6) 180            |                |                  |
     |<------------------------------------------------------|
     |                   |                |                  |
     |(7) 200            |                |                  |
     |<------------------------------------------------------|
     |                   |                |                  |
     |(8) ACK            |                |                  |
     |------------------------------------------------------>|
     |                   |                |                  |


Node 10 -> Node 3
INVITE sip:alice@p2psip.org SIP/2.0
To: sip:alice@p2psip.org;resource-ID=5;alg=rsa-sha1;overlay=chat
From: sip:bob@p2psip.org;resource-ID=12;alg=rsa-sha1;overlay=chat
Contact: sip:bob@10.0.0.10;alg=rsa-sha1;overlay=chat
DHT-NodeID: rsa-sha1 10 10.0.0.10
Require: dht
Supported: dht


Node 3 -> Node 10

SIP/2.0 302 Moved Temporarily
Contact: sip:5@10.0.0.5;user=node;alg=rsa-sha1;overlay=chat
DHT-NodeID: rsa-sha1 3 10.0.0.3
DHT-Link: P 1 rsa-sha1 10 10.0.0.10
DHT-Link: S 1 rsa-sha1 5 10.0.0.5
Require: dht
Supported: dht


Node 10 -> Node 5

INVITE sip:alice@p2psip.org SIP/2.0
To: sip:alice@p2psip.org;resource-ID=5;alg=rsa-sha1;overlay=chat
From: sip:bob@p2psip.org;resource-ID=12;alg=rsa-sha1;overlay=chat
Contact: sip:bob@10.0.0.10;alg=rsa-sha1;overlay=chat
DHT-NodeID: rsa-sha1 10 10.0.0.10
Require: dht
Supported: dht


Node 5 -> Node 10

SIP/2.0 302 Moved Temporarily
Contact: sip:alice@10.99.99.99;alg=rsa-sha1;overlay=chat
DHT-NodeID: rsa-sha1 5 10.0.0.5
DHT-Link: P 1 rsa-sha1 3 10.0.0.3
DHT-Link: S 1 rsa-sha1 10 10.0.0.10
Require: dht
Supported: dht


[To Do: Rest of call flow, with correct handling of fact
Alice's UA is not DHT compliant]


8.4 Example of a Node Leaving the System

[To Do: Add an example here]

8.5 Example of a Successful User Search

[To Do: Add an example here]

8.6 Example of an Unsucessful User Search

[To Do: Add an example here]



 TOC 

9. Security Considerations

To Do: Still a lots of work to be done here.

There are many inherent security issues in a system such as this, and it is clearly not the solution for everyone. It trades off some security for certain other properties such as functioning without a centralized server or owner of the namespace.

9.1 Threat Model

The attacker is assumed to be able to generate an identity and become a valid node in the system. They can see other nodes and process certain queries. Attackers may wish to receive communications intended for other participants, prevent other users from receiving their messages, prevent large portions of the users from receiving messages, or send messages that appear to be from others. Users would like to be sure they are communicating with the same person they have previously talked to, to be able to verify identity via some out of band mechanism. Attackers may try to squat on all the good names. Users would like names that are meaningful to them. Attackers may have computers that are many times faster than the average user's. Attackers may be able to DOS other particular nodes and make them fail. To make a robust DHT, many nodes need to store information on behalf of the community. Nodes may lie about this and not store the information. Attackers may wish to see who is communicating with whom and how much data is getting communicated.

9.2 Protecting the Namespace

Key requirements of the system are that there is no centralized naming authority and users can pick names. If two users pick the same name, the system must be able to determine which of them should be allowed to use the name. At some level this is tricky, because different clients could pick the same new name at the same time on opposite sides of the ring. Any local mechanism would let that happen, whereas a global mechanism is very difficult to implement efficiently on a P2P network that is dynamically changing.

9.2.1 Certificate Based Protection

The goal of this approach is to end up with a security environment comparable to ssh, which in the opinion of the authors is excellent even though it is less than perfect. This approach tries to limit the damage produced by the theft of a person's identity instead of directly stopping the theft in the first place. The system requires each user to have a self signed certificate and use S/MIME and AIBs for signing the messages. When users first contact each other, they can store the certificates, and each user can warn the other user if they change on future communications. UAs SHOULD be able to display the sha1 hash of the certificate to the user for out of band verification. Address books SHOULD store these certificates, and UAs should trust the information in users' address books at a higher level than information contained in messages they receive over the wire.

9.3 Protecting the Routing

The DHT forms a complex routing table. When a node joins, it may accidentally contact a subversive node that lies about the finger table information it provides. The subversive node could do this to try to trick the joining node to route all the traffic to a subversive group of nodes.

9.4 Protecting the Signaling

The goal here is to stop the attacker from knowing who is signaling what to whom. Ultimately this will be impossible if a large percentage of the ring is compromised. It it possible to make it statistically hard for a user to figure out what some specific other user is doing. This is done by forcing the hash locations to be bound to the contact information via the crypto hash. In many cases, the attacker does not have wide control over the range and number of IPs available to them to attempt these attacks. IPv6 will expand this and this work will have to look at perhaps hashing the upper bits separately from the lower bits to again force the attacker into a position where it is harder to control their IP address and thus the hash function result that determines where they are inserted into the DHT.

Interactive systems mean that nodes only see the queries. Clients can randomly generate these to obfuscate who they are tying to connect to. Cached results localize the area in the DHT where an attacker's node would have to be located to see an attempted connection to a given node.

9.5 Protecting the Media

All the media needs to be S/MIME encrypted. Doing so reduces the value of intercepting others' communications, because the media cannot be seen in the message. This is critical.

9.6 Replay Attacks

Very loosely synchronized time is fairly easy to maintain on modern devices using only the internal clock. This is used in the SIP Date header field value along with random Call-ID and to and from tags, resulting in a fair amount of protection against replay attacks.

9.7 Cut and Paste Attacks

Using the AIB to protect the message with S/MIME makes cut and paste attacks on of fields other than the VIA headers very difficult.

A node can always re-sign the whole thing using a different self sided certificate but new certificate would likely be caused by the receiver if a previous communication had been made.

9.8 Identity Theft Attacks

The lack of central authority to resolve name disputes in the namespace means that at some level this problem is unsolved. The approach has tended to be to allow everyone to call themselves Wally then let the certificates sort them out. Users with names that are often "stolen" by others will learn that theirs is a poor choice of name because it is too valuable, and they will select a less valuable name. Equilibrium will prevail, or chaos.

9.9 Limitations of the Security

The limitations of the security revolve around the intrinsic characteristic that anyone can create a name - names are not unique and routing to a particular name does not guarantee reaching a unique user.



 TOC 

10. Open Issues

There are certainly many open issues. Here are a few.

Still to be worked out are details of what names look like, how they are allocated and protected, and how they are disambiguated from traditional names that use DNS based routing.

Using routable IP addresses for the Node-ID is problematic. Using them solves a big problem with preventing the Sybil attack and preventing people from simply making tons of nodes that join the network and pollute the space; but on the other hand, this will be a BIG problem with NATs. If home users' machines are used, some large fraction probably have IP addresses in the 192.168.0.x and 192.168.1.x families. These addresses will all hash to the same ID. I used IP addresses for now in the draft, but we need a better way to generate Node-IDs that works for NATs and preserves all the protection against P2P attacks that comes from using them.

We have had various thoughts on this issue. One thought is to require the use of mechanisms such as STUN and require that actual IP addresses be placed in the messages. This works well but permits only one node to be behind each NAT. Appending a port does NOT solve the problem, as users then, by selecting arbitrary port numbers can create a very large number of Node-IDs, and in a network with a small number of nodes, could likely find a Node-ID that would place them between any pair of nodes they desired, causing disruption to the network. One possibility we have considered is to append the port number -- unmodified -- to the hash. This would still allow users behind a NAT to have different Node-IDs, but the range of addresses within the hash would be very limited -- the user would only be able to insert themselves between other nodes behind the same NAT they are behind. There would still be issues with being able to control an arbitrary number of successors, but they seem less serious than the other alternative. This issue needs to be explored.



 TOC 

11. Acknowledgments

The following people provided useful feedback, commentary, advice, design ideas, criticism, or proofreading during the course of writing this draft:

Adam Roach, Bruce B. Lowekamp, Robert Sparks, Kundan Singh, Henning Schulzrinne, Marcia Zangrilli.

Thank you for your help!



 TOC 

12. Implementations

Currently, two groups involved in this area of research have P2P SIP implementations:

College of William and Mary:
One P2P SIP implementation is called SoSIMPLE and is being developed at the College of William and Mary. This project is being developed by David A. Bryan and Bruce B. Lowekamp. This is an implementation of the protocol defined in this document.
Columbia University
Another project on P2P-SIP is being developed at Columbia University by Kundan Singh and Henning Schulzrinne. This project implements an alternate (Singh, K. and H. Schulzrinne, “Peer-to-peer Internet Telephony using SIP,” June 2005.)[8]proposal for a P2P SIP implementation.


 TOC 

13. IANA Considerations

This document would require registering the following:

[ToDo: Not sure if that is all the things that would need to be registered]



 TOC 

14. Definitions

Peer-to-Peer (P2P) Architecture:
An architecture in which nodes cooperate together to perform tasks. Each node has essentially equal importance and performs the same tasks within the network. Additionally, nodes communicate directly with one another to perform tasks. Contrast this to a Client-Server architecture.
Client-Server Architecture:
An architecture in which some small number of nodes (servers) provide services to a larger number of nodes (clients). Client nodes connect to servers, but typically do not communicate among themselves.
Node or Peer:
Any entity that participates in the overlay network, understanding the p2p extensions described in this in document, is a "node" or "peer".
Overlay or Overlay Network:
This document refers to the virtual network created by the interconnection between the nodes participating in the P2P SIP network as the "overlay network", in keeping with the terminology used in the P2P community.
Distributed Hash Table (DHT):
A mechanism in which resources are given a unique key produced by hashing some attribute of the resource, locating them in a hash space (see below). Nodes located in this hash space also have a unique id within the hash space. Nodes store information about resources with keys that are numerically similar to the node's ID in the hash space.
Namespace or hash space:
The range of values that valid results from the hash algorithm fall into. For example, using the SHA-1 algorithm, the namespace is all 40 digit hexadecimal identifiers. This namespace forms the set of valid values for Node-IDs and Resource-IDs (see below).
Resource-ID:
The value resulting from hashing the a resource's unique name or keyword. Any information about this resource will then be stored at that location in the namespace, and maintained by a node with a Node-ID with a value numerically similar to the Resource-ID. In P2P SIP, User names are hashed to Resource-IDs to determine where in hash space they should be stored.
Node-ID:
The value resulting from hashing the unique ID of a particular node. A node with particular Node-ID will be responsible for maintaining information about resources with Resource-IDs that are nearby in the hash space.
Chord:
A particular algorithm/approach to implementing a DHT. Uses a circular arrangement for the namespace.
Finger Table:
The list of nodes that a node uses to send messages to. The finger table contains many entries about nodes with similar IDs, and fewer entries about more remote IDs.
Neighbors:
A collection of nodes that a particular node can reach in one hop. In general, note that a node's set of neighbors is equivalent to the entries in that node's finger table. In our DHT structure, neighbor relations are NOT symmetric.
Adapter Node:
An adapter node is a node in the overlay that acts as an adapter for other non-P2P enabled SIP entities, allowing them to access the resources of the overlay. The adapter node participates actively in the overlay network, while the non-P2P enabled SIP entities it provides service to DO NOT participate directly in the overlay. Compare these to the term "super node" in the P2P community, although adapter nodes may be thin software shims intended for only one client.
Successor Node and Predecessor Node:
A term borrowed from Chord. These terms refer to the node directly after (before) a particular node in the address space. This does not mean the successor/predecessor node's ID is one greater/less than the node, it simply means that there are no other nodes in the namespace between the node and the successor/predecessor. Note that the first node in a finger table is typically also the first successor node.
Node Registration:
The act of a peer joining the overlay. Registration allows a peer to communicate with other peers, and requires (allows?) it to take on some server-like responsibilities such as maintaining resource location information. It DOES NOT register the user so that they can receive phone calls, which is the traditional SIP use of the word registration. We refer to traditional SIP registration as "user registration".
User Registration:
The act of a user registering themselves with a SIP network. User registration creates a mapping between a SIP URI and a contact for a user to be created. This is the traditional meaning of registration in SIP. For a P2P SIP node, this action MUST occur after node registration.
Joining Node:
During the node registration process, this is the node that is attempting to register -- that is, the node that is attempting to join the overlay network.
Bootstrap Node:
During the process of node registration, the bootstrap node is the node that the joining node contacts. This node may be a well-known node, a node located using a broadcast method, a node that the joining node previously knew about, or a node that another bootstrap node referred the joining node to. Often, the only role the bootstrap node plays in the node registration is to direct the joining node to the admitting node.
Admitting Node:
During the process of node registration, this is the node that is currently responsible for the portion of the namespace the new node will eventually reside in. This node is responsible for generating many of the messages exchanged during node registration.


 TOC 

15. References



 TOC 

15.1 Normative References

[1] Bradner, S., “Key words for use in RFCs to Indicate Requirement Levels,” BCP 14, RFC 2119, March 1997 (TXT, HTML, XML).
[2] 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.
[3] Eastlake, 3rd, D. and P. Jones, “US Secure Hash Algorithm 1 (SHA1),” RFC 3174, September 2001.
[4] Peterson, J. and C. Jennings, “Enhancements for Authenticated Identity Management in the Session Initiation Protocol (SIP),” Internet Draft draft-ietf-sip-identity-05, March 2005.


 TOC 

15.2 Informative References

[5] Bryan, D., Jennings, C., and B. Lowekamp, “SOSIMPLE: A Serverless, Standards-based, P2P SIP Communication System,” Proceedings of the 2005 International Workshop on Advanced Architectures and Algorithms for Internet Delivery and Applications (AAA-IDEA) '05, June 2005.
[6] 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 (To appear) .
[7] Douceur, J., “The Sybil Attack,” IPTPS '02, March 2002.
[8] Singh, K. and H. Schulzrinne, “Peer-to-peer Internet Telephony using SIP,” Proceedings of the 2005 Network and Operating Systems Support for Digital Audio and Video Workshop (NOSSDAV) '05, June 2005.


 TOC 

Authors' Addresses

  David A. Bryan
  College of William and Mary
  Department of Computer Science
  P.O. Box 8795
  Williamsburg, VA 23187
  USA
Phone:  +1 757 784 5601
Email:  bryan@ethernot.org
  
  Cullen Jennings
  Cisco Systems
  170 West Tasman Drive
  MS: SJC-21/3
  San Jose, CA 95134
  USA
Phone:  +1 408 421 9990
Email:  fluffy@cisco.com


 TOC 

Intellectual Property Statement

Disclaimer of Validity

Copyright Statement

Acknowledgment