| TOC |
|
This document is an Internet-Draft and is subject to all provisions of Section 3 of RFC 3667. 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 become aware will be disclosed, in accordance with RFC 3668.
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 July 24, 2005.
Copyright (C) The Internet Society (2005).
This document outlines the motivation and requirements for a Peer-to-Peer (P2P) based approach to building a SIP registrar 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.
1.
Conventions
2.
Introduction
3.
Definitions and Terminology
4.
Peer-to-Peer Background
5.
P2P SIP Overview
5.1
P2P Overlay Structure
5.2
Message Format
5.3
Node Registration
5.4
User Registration
5.5
Session Establishment
6.
Architecture
6.1
P2P Overlay Structure
7.
Headers and Parameters
7.1
Option Tags
7.2
Node-IDs and the user=node Parameter
7.3
User IDs and the resource-ID= Parameter
7.4
The DHT-NodeID Header
7.5
The DHT-Link Header
7.6
URIs
8.
DHT Operations
8.1
Node Registration
8.1.1
Bootstrapping
8.1.2
Nodes Joining the Overlay
8.1.3
Nodes Leaving the Overlay Gracefully
8.2
Periodic Stabilization
8.3
Handling Failed Requests
8.4
Node Failure
9.
User-level operations
9.1
User Registration
9.1.1
Registering User Registrations
9.1.2
Refreshing User Registrations
9.1.3
Removing User Registrations
9.1.4
Querying User Registrations
9.2
Session Establishment
9.3
Presence
10.
Examples
10.1
Example of a Node Registration
10.2
Example of a User Registration
10.3
Example of a Session Establishment
10.4
Example of a Node Leaving the System
10.5
Example of a Successful User Search
10.6
Example of an Unsucessful User Search
11.
Security Considerations
11.1
Threat Model
11.2
Protecting the Namespace
11.2.1
Email Based Protection
11.2.2
Certificate Based Protection
11.3
Protecting the Routing
11.4
Protecting the Signaling
11.5
Protecting the Media
11.6
Replay Attacks
11.7
Cut and Paste Attacks
11.8
Identify Theft Attacks
11.9
Limitations of the Security
12.
Open Issues
13.
Acknowledgements
14.
Implementations
15.
IANA Considerations
16.
References
16.1
Normative References
16.2
Informative References
§
Authors' Addresses
§
Intellectual Property and Copyright Statements
| TOC |
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC-2119Bradner, S., Key words for use in RFCs to Indicate Requirement Levels, March 1997.[1].
| TOC |
As SIPRosenberg, 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.
| TOC |
This document uses the terminology defined in RFC 3261Rosenberg, J., Schulzrinne, H., Camarillo, G., Johnston, A., Peterson, J., Sparks, R., Handley, M. and E. Schooler, SIP: Session Initiation Protocol, June 2002.[2], as well as the following terms:
- 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.
- 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".
- 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. Compare these to the term "super node" in the P2P community.
- 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.
- Admiting Node:
- During the process of node registration, this is the node that is currently responsible for the portion of the name space the new node will eventually reside in. This node is responsible for generating many of the messages exchanged during node registration.
- Node-ID:
- The address, in the SHA-1 hashspace, 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 hashspace.
- Resource-ID:
- The address, in the SHA-1 hashspace, resulting from hashing the resource's resource name or keyword. Any information about this resource will then be stored at that location in the name space, and maintained by a node with a Node-ID with a value numerically similar to the Resource-ID.
- 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.
- 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.
- 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.
- Namespace or hashspace:
- That range of numbers that valid results from the hash algorithm fall into. For example, for SHA-1, all results are 40 hex digits, resulting in a namespace ranging from 0000000000000000000000000000000000000000 to ffffffffffffffffffffffffffffffffffffffff. These are the valid values for Node-IDs and Resource-IDs.
| TOC |
The fundamental principle behind Peer-to-Peer (P2P) networks is that each and every node has equal importance in the network that is formed. Rather than a large number of client machines contacting one or more central servers, nodes interact directly with each other. Each node that participates in the P2P system 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 all nodes within the system. P2P networks form logical networks connecting the peers to one another. This logical network is referred to as an overlay network, as it is in some sense a new, small sub-network at a higher logical level than the one that actually connects the nodes. Some P2P networks also have certain nodes which 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
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 these P2P networks takes this fact into account. Information is often replicated, and the topology of the overlay can be quickly adapted as nodes enter and leave.
Perhaps the most famous (or perhaps infamous) purpose to which P2P technology has been applied is file swapping. In these systems, individual users stored files, and joined the overlay network by connecting to a small number of nodes already in the overlay. When the user wanted to locate a particular file they did not have, they would locate it by contacting these neighbors. Several alternatives existed 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.
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) P2P structure. In such a system, every resource has a Resource-ID, which is obtained by hashing some keyword that identifies the resource. Resources can be thought of as being stored in the distributed 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 that has a Node-ID near a particular Resource-ID will be responsible for storing the information about that resource. The hash space is divided up so that all of the hash space is the responsibility of some particular node, although as nodes enter and leave the system, the hash area that any particular node is responsible for my shrink or grow. Messages are exchanged between the nodes in the DHT as the nodes enter and leave to preserve the structure of the DHT. The hash space is often visualized as a grid, circle or line.
When a user wishes to search, they contact a node they know that is nearest to the ID of the file. If that node does not know how to find the resource, it asks the node with the ID nearest the request that it knows about. In this fashion, the request eventually reaches the node responsible for the resource, which then replies to the requester.
The ChordStoica, I., Morris, R., Karger, D., Kaashoek, M. and H. Balakrishnan, Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications, August 2001.[4] system is one particular popular DHT implementation. Chord uses a ring type structure for the nodes in the overlay. In this structure, a node with a hash of 0 would be a neighbor of 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. Searching is accomplished by sending messages to the node in the table that is closest to the destination address. That neighbor should have more finer resolution detail about the area and can route the message closer to the area in question. This process is repeated until the message reaches the node responsible for the destination, which can determine if the resource searched for is present.
Not all systems advertised as P2P are truly P2P. Many systems, such as the original Napster system, many existing SIP deployments, and Skype, are what are 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. We do not consider these type of systems to be P2P in this document. Our goal is design a system that requires no central server of any type.
All P2P systems need to solve the problem of bootstrapping, which is locating some initial node in the overlay. This problem is solved by different P2P systems in different ways, including using some set of fixed nodes, requiring that a node be located using an offline mechanism, or using a broadcast/multicast mechanism.
P2P systems offer several advantages over centralized architectures such as client-server architecture. P2P systems distribute resources across multiple machines, greatly reducing the potential of failure due to a single node, resulting in increased robustness, as well 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 nodes offer server-like functionality, and so additional servers do not need to be added.
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 high-jacking the system. These type of attack is often referred to as a SybilDouceur, J., The Sybil Attack, March 2002.[5] attack.
| TOC |
In this section we provide an overview of how P2P SIP works. Details are provided in the remainder of the document. Details such as URL format, headers, and specific call flows are not presented in this section. Instead, a top level, simplified picture is presented.
Unlike a conventional SIP architecture, P2P SIP systems require no central servers. P2P enabled SIP nodes communicate with other P2P enabled SIP nodes, or peers, to establish sessions. Rather than a traditional architecture where many SIP UAs connect to a central proxy server, in a P2P SIP network, the peers connect directly to a few other peers, forming a virtual network of peers referred to as an overlay network. The nodes participating in this 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.
Nodes are organized using a Distributed Hash Table (DHT) P2P structure. In such a system, every resource has a Resource-ID, which is obtained by hashing some keyword that identifies the resource. Resources can be thought of as being stored in the distributed 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 that has a Node-ID near a particular Resource-ID will be responsible for storing the information about that resource. The hash space is divided up so that all of the hash space is the responsibility of some particular node, although as nodes enter and leave the system, the hash area that any particular node is responsible for may shrink or grow. Messages are exchanged between the nodes in the DHT as the nodes enter and leave. Additionally, redundancy is implemented to protect against a node failing.
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. The node will have a small number of neighbors with Node-IDs very different than its own, and more neighbors with similar Node-IDs -- it knows more about nodes located nearby in hash space, but also has access to some nodes with different Node-IDs. When locating a resource with a particular Resource-ID, the node will send the request to the neighbor with the Node-ID closest in the hash space 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. The request is then forwarded to this closer node. The process is repeated until the node responsible for the Resource-ID is located and the requested information is obtained.
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 first type of messages are those needed to maintain the DHT, such as the messages needed to join or leave the overlay, and to transfer information as a result. 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.
When a node wishes to join the overlay, it will send a REGISTER message to a bootstrap node already in the overlay, requesting to join. In response, additional REGISTER messages are exchanged to allow the joining node to learn about other nodes in the overlay (neighbors) and to obtain the 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, but once the initial set messages are exchanged, a node has joined the overlay.
The REGISTER messages that are exchanged to allow a node to join the overlay make up a node registration. The node registration does not, however, register the user 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 represents 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'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, and also report 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.
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 |
P2P SIP nodes must implement some "server-like" behaviors, as well as DHT behaviors. 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. These nodes have the basic functionality of any SIP endpoint, but additionally implement the operations described in this document to enable self-organization.
The behavior can also be located in an adapter node, which allow one or more conventional SIP UAs to interact with the P2P overlay network. These adapters perform the additional server-like behavior on behalf of the UAs it supports. In this case, these UAs are not peers in the overlay, only the adapter node is, and all the 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. A full featured SIP proxy, implementing not only the limited proxy-like functions described here, but other services as outlined in RFC 3261, may also implement the functions of an adapter node, allowing the UAs it supports to communicate with nodes in the overlay.
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.
The P2P system uses a distributed hash table (DHT) similar to Chord. Like Chord, the system uses consistent hashing to a one dimensional name space, conceptually in the form of a circle. Unlike Chord, all the messages needed to maintain the DHT are strictly SIP messages, although this requires extensions to conventional SIP implementations. We use many Chord-like terms, which are defined in the section Definitions and Terminology.Definitions and Terminology
Implementations MUST use the SHA-1 hash algorithm. Each node in the overlay network is identified by a unique Node-ID. The Node-ID MUST be calculated at the time the node joins the network using the SHA-1Eastlake, 3rd, D. and P. Jones, US Secure Hash Algorithm 1 (SHA1), September 2001.[3] algorithm to hash the IP address of the node (please see the open issues section of this document). A node is placed into the space of the overlay using this hashed value. The IP address is chosen to remove the ability of the node to select its own placement in the overlay network, or to create multiple identities in the overlay -- both of which are popular attacks against a P2P network.
Information stored in the overlay is mapped by a key called a Resource-ID. The Resource-ID MUST be generated by hashing the identifying string using the SHA-1 algorithm. The key is associated with (stored by) first node in the network with a Node-ID that is equal to or greater (mod the size of the namespace) than the Resource-ID.
Each node keeps information about a number of other nodes in the overlay. In addition to keeping track of the predecessor and some number of successor nodes (the nodes directly before or after the node in the hash space), we keep track of several additional entries that point to ranges in the hash space away from the node. These additional entries make up the finger table.
Chord recommends keeping a number of finger table entries equal to the size in bits of the hash space -- 160 for SHA-1. These entries point to the first node greater than equal to a distance 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. When the node wants to find a resource in that interval, it uses the node listed in the corresponding finger table as the first node to send the request to. As the distance between a node and an entry in the finger table increases, the granularity of information about that portion of the overlay increases -- a node knows about more nodes near and just after it than it does nodes that far away. The details of the messages that exchanged to populate this table, as well as the algorithms used to keep this current (derived from Chord) are discussed below.
We recommend that, while using the full SHA-1 hash algorithm, nodes SHOULD NOT maintain the full 160 entries in the finger table, but rather some more manageable subset -- 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.
| TOC |
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. Clients supporting P2P and contacting another SIP entity for a transaction that may or may not be P2P SHOULD include a Supported header with dht.
Node-IDs are of the form SHA-1:<40 hex digit hash>, with the hash being the result of using SHA-1 to hash the IP address. The resulting Node-ID looks like SHA-1:a04d371e3f4078a7a8c49bb7a4ea6199fc9d5c77. Formally, Node-IDs are defined as follows:
NodeID = "SHA-1" HCOLON 40LHEX
Additionally, we use the parameter "user=node" when we are 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.
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 NamespaceProtecting the Namespace may place restrictions of their own on the User IDs.
Following a user name, the optional parameter resource-ID=<40 hex digit hash> 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 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.
Formally, the resource-ID= parameter is defined as a uri-parameter of type other-param as defined by RFC 3261. The pname in this case is defined as "resource-ID", and the pvalue as a ResourceID, as defined below
ResourceID = "SHA-1" HCOLON 40LHEX
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 Node-ID, as described above, followed by a space, and finally an address for this node. Thus the header format is:
DHT-NodeID: <Node-ID> <IP address>
Examples:
- A node with an SHA-1 hashed Node-ID of a04d371e3f4078a7a8c49bb7a4ea6199fc9d5c77 on IP 192.1.1.1:
DHT-NodeID: SHA-1:a04d371e3f4078a7a8c49bb7a4ea6199fc9d5c77 192.1.1.1
The formal syntax of the DHT-Link header is:
DHT-NodeID = "DHT-NodeID" HCOLON NodeID SWS host
NodeID = "SHA-1" HCOLON 40LHEX ;as defined above
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 4 parameters -- type, depth, Node-ID and IP address, each separated by a space. Thus the header format is:
DHT-Link: <type> <depth> <Node-ID> <IP address>
and an example, the header might look like (using a shortened 10 digit Node-ID for simplicity):
DHT-Link: P 1 SHA-1:671a65bf22 192.168.0.1
The type parameter can take on 3 values, and consists of a single letter. That letter can be P, S, or F. P indicates that the information provided describes a predecessor of the sending node. S indicates that the information describes a successor node, and F indicates that it is a finger table node from the sending node.
The depth parameter is a non-negative integer representing which predecessor, successor, or finger table entry is being described. For predecessors and successors, this indicates strictly 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 indicates 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:
- The sending node's immediate predecessor is 192.168.0.1:
- DHT-Link: P 1 SHA-1:671a65bf22 192.168.0.1
- The sending node's fifth successor is 10.0.1.1:
- DHT-Link: S 1 SHA-1: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 SHA-1: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 Node-ID SWS host
DHTL-type = "P" / "S" / "F"
DHTL-depth = 1*DIGIT
[To Do: Have quite a few URIs in here, but no section really defining them. Need a good section that describes them and nails things down]
| TOC |
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 RegistrationUser Registration section of this document. Additionally, SIP REGISTER messages are used to register a new node with the DHT and to register 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.
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 some 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 choose to use peers it connected to the last time it was connected.
- 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 a bootstrap node has been located.
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 creates their Node-ID. This MUST be constructed using the SHA-1 algorithm to hash the IP address of the node. 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 outlined below.
The Request-URI that is constructed for the REGISTER MUST be prepended with the name of the overlay the node wishes to join, followed by a slash. For example, if the node wishes to join a an overlay called "sipchat", and the IP address of the bootstrap node is 11.22.33.44, the resulting Request-URI would be of the form "REGISTER sip:sipchat/11.22.33.44 SIP/2.0".
The To and From fields of the REGISTER message MUST contain a URI constructed by using the hashed Node-ID as the user name, and the IP address of the node. The URI MUST be prepended with the name of the overlay the node wishes to join. The REGISTER message MUST contain a Require header field value of dht. Additionally, both the to and from field MUST include the user=node parameter. A To field might look like the following (the node ID has been shortened to 10 hex characters here for formatting reasons) :
To: sip:sipchat/SHA-1:a542b3ef98@11.22.33.44;user=node
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 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 node MUST provide a DHT-NodeID header field containing their calculated Node-ID and IP.
Once the REGISTER message is constructed, the node sends it to the bootstrap node. The bootstrap determines that this is a node registration because of the presence of the user=node parameter and presence of an expires header/parameter. The bootstrap node SHOULD verify that the hashed Node-ID corresponds to the IP address specified in the URI. 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) To construct the 302, the bootstrap node MUST look up the node in its finger table nearest the joining node's Node-ID, and uses it to create a contact field. The contact field is placed in the 302, with a user=node parameter and this response is sent to the joining node. The responding node MUST include a DHT-NodeID header.
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, but the admitting node differs in that it 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 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 MUST send a 200 OK message to the joining node.
The admitting node MUST provide the joining node with its current predecessor in the 200. This is placed in a DHT-Link header, using a type of P and a depth of 1. For example, if the admitting node's predecessor has an IP address of 192.1.1.1, they would include a header of the following form in their 200 (again, hashed value is shortened for editorial reasons):
DHT-Link: P 1 SHA-1:53ed23f67a 192.168.1.1
Additionally, the node MUST provide the successor node, and SHOULD provide 4 successor node (if that many are present), as these will are used to redundantly store user registrations. Nodes SHOULD maintain 4 successors to allow user registrations to be stored redundantly.
Additionally, the admitting node must include a DHT-NodeID header containing the admitting node's Node-ID and IP. Note that the admitting node's predecessor will become the joining node's predecessor, while the admitting node will become the joining node's successor. This information was transmitted in the 200 in the DHT-Link P 1 header and the DHT-Node headers respectively. Similarly, the joining node will become the admitting node's predecessor. This information was contained in the REGISTER requests DHT-Node parameter. 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. The user must calculate and reconstruct the intervals that the admitting would have based on the F parameters and the Node-ID supplied in the 200.
Before turning to populating the joining node's finger table, we must show how to search to find the node responsible for an arbitrary location in the hash space.
One may find the node responsible for a particular space in the hash table as follows. Note that this corresponds to the find_successor operation in the Chord literature.
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.
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 MUST be constructed using the node selected in the paragraph as the destination, as discussed in the section Registering with the Overlay.Registering with the Overlay The To field MUST be constructed providing a Node-ID corresponding to the arbitrary hash address we are searching for, and MUST NOT include the user=node parameter. It MAY include the resource-ID parameter, described later in the User Registration section. The From field MUST be be constructed as described in the section Registering with the Overlay.Registering with the Overlay with the searching node's URI. The DHT-NodeID header MUST be included. The request MUST NOT contain a Contact header. Note that these are third party registrations. Once constructed, the message is sent to the node in the Request-URI.
If that node is not responsible, it will return a 302 message providing a closer contact, and the searching node will construct and send a new REGISTER to the node provided in the contact. Eventually, the REGISTER will reach the node responsible for that space in the overlay. If that node is storing a resource with that key, it MUST return a 200 with a Contact header corresponding to that resource. Additionally, the 200 MUST include a DHT-NodeID header containing the Node-ID of the responding node. If the data is not present, the node MUST return a 404, which MUST include a DHT-NodeID header containing the Node-ID of the responding node. In either case, the responding node MUST also provide DHT-Link headers providing both the predecessor and successor, as these are required in stabilization algorithms.
The searching node, in addition to determining if there is some data in the overlay associated with the arbitrary key we searched for now knows the Node-ID and IP address of the node responsible for that data. It is contained in the Node-ID field of the reply.
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, calculate the Resource-IDs corresponding to the start of each finger interval. See the P2P Overlay StructureP2P Overlay Structure subsection in the Architecture 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.
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 RegistrationsUser Registration, except that as they are third party registration from a node, the From field should be constructed as described in the sections above.
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.
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 should update their own successor with the predecessor returned, and additionally should send a REGISTER to this node, as if the stabilizing node had just entered the system. This will serve to properly update the overlay.
Additionally, when this periodic stabilization takes place, the node should perform searches as discussed in Populating the Joining Node's Finger TablePopulating the Joining Node's Finger Table to ensure that the finger table is up to date.
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 TablePopulating 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.
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 |
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.
When a node is in the overlay, it must register the 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 node constructs the register message as follows:
The Request-URI that is constructed for the REGISTER MUST be prepended with the name of the overlay the user wishes to join. For example, assume the user wishes to join the overlay "sipchat", and the node in the finger table with Node-ID closest to but equal to or greater than the Resource-ID calculated by hashing the user name is 11.22.33.44. The Request-URI would be of the form: "REGISTER sip:sipchat/11.22.33.44 SIP/2.0".
The To and From fields of the REGISTER message MUST contain a URI constructed using the user's user-id and IP address. For example, if the user is alice@p2psip.org, the To field would look like:
To: sip:sipchat/alice@p2psip.org
The node MAY append the resource-ID parameter to the To and From. For example, if we assume alice@p2psip.org hashes to a671b93eff (shortening the 40 hex digit hash to 10 digits to conserve space), the To field would look like:
To: sip:sipchat/alice@p2psip.org;resource-ID=sha1:a671b93eff
The From field should be constructed in a similar fashion.
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. As in standard SIP registrations, Expires parameters with a value of zero will be used to remove registrations. The node MAY append a resource-ID to the Contact as well.
The node MUST include the value dht in Require and Supported headers.
The message is routed in a fashion exactly analogous to that described in the section on node registrationNode Registration. 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 MUST include successor nodes that can be used by the registering node to send redundant registrations to.
The registering node SHOULD use the successor nodes provided in the 200, and construct registrations to send to these nodes as well.
[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"]
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.
User registrations are removed exactly as described in RFC 3261, Section 10. Users should 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.
User registrations are queried exactly as described in RFC 3261, Section 10. Users should send a registration with no contact header. As described in Resource Location/SearchResource Location/Search, this mechanism can also be used to locate the node responsible for a particular Resource-ID.
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.
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 StabilizationPeriodic 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 |
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 SHA-1: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 SHA-1:3, SHA-1:5, and SHA-1: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 3.3.3.3, the node node with Node-ID 5 has IP address 5.5.5.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 collocated 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 99.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@99.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.
Assume a new node wishes to join the system. The node has an IP address of 14.14.14.14, which we shall assume hashes to a Node-ID of SHA-1:14. From an out of band mechanism, this node discovers node 5. This node constructs a REGISTER as described in Registering with the OverlayRegistering with the Overlay, and sends it to node 5. Node 5 verifies that 14.14.14.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:sipchat/5.5.5.5 SIP/2.0
To: sip:sipchate/SHA-1:14@14.14.14.14;user=node
From: sip:sipchat/SHA-1:14@14.14.14.14;user=node
Contact: sip:sipchat/14@14.14.14.14;user=node
Expires: 600
DHT-NodeID: SHA-1:14 14.14.14.14
Require: dht
Supported: dht
Node 5 -> Node 14
SIP/2.0 302 Moved Temporarily
Contact: sip:sipchat/3@3.3.3.3;user=node
DHT-NodeID: SHA-1:5 5.5.5.5
DHT-Link: P 1 SHA-1:3 3.3.3.3
DHT-Link: S 1 SHA-1:10 10.10.10.10
Require: dht
Supported: dht
Node 14 -> Node 3
REGISTER sip:sipchat/3.3.3.3 SIP/2.0
To: sip:sipchat/14@14.14.14.14;user=node
From: sip:sipchat/14@14.14.14.14;user=node
Contact: sip:sipchat/14@14.14.14.14;user=node
Expires: 600
DHT-NodeID: SHA-1:14 14.14.14.14
Require: dht
Supported: dht
Node 3 -> Node 14
SIP/2.0 200 OK
To: sip:sipchat/14@14.14.14.14;user=node
From: sip:sipchat/14@14.14.14.14;user=node
Contact: sip:sipchat/14@14.14.14.14;user=node
Expires: 600
DHT-NodeID: SHA-1:3 3.3.3.3
DHT-Link: P 1 SHA-1:10 10.10.10.10
DHT-Link: S 1 SHA-1:5 5.5.5.5
DHT-Link: F 0 SHA-1:5 5.5.5.5
DHT-Link: F 1 SHA-1:5 5.5.5.5
DHT-Link: F 2 SHA-1:10 10.10.10.10
DHT-Link: F 3 SHA-1:3 3.3.3.3
Require: dht
Supported: dht
Node 3 -> Node 14
REGISTER sip:sipchat/14.14.14.14 SIP/2.0
To: sip:sipchat/bob@p2psip.org
From: sip:sipchat/3@3.3.3.3;user=node
Contact: sip:sipchat/bob@10.10.10.10;expires=201
DHT-NodeID: SHA-1:3 3.3.3.3
Require: dht
Supported: dht
Node 14 -> Node 3
SIP/2.0 200 OK
To: sip:sipchat/bob@p2psip.org
From: sip:sipchat/3@3.3.3.3;user=node
Contact: sip:sipchat/bob@10.10.10.10;expires=201
DHT-NodeID: SHA-1:14 14.14.14.14
Require: dht
Supported: dht
Assume user carl starts a UA collocated with node 5. Carl's contact will be carl@5.5.5.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 RegistrationsRegistering 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:sipchat/10.10.10.10 SIP/2.0
To: sip:sipchat/carl@p2psip.org;resource-ID=SHA-1:11
From: sip:sipchat/carl@p2psip.org;resource-ID=SHA-1:11
Contact: sip:sipchat/carl@5.5.5.5;resource-ID=SHA-1:11
Expires: 600
DHT-NodeID: SHA-1:5 5.5.5.5
Require: dht
Supported: dht
Node 10 -> Node 5
SIP/2.0 302 Moved Temporarily
Contact: sip:sipchat/3@3.3.3.3;user=node
DHT-NodeID: SHA-1:10 10.10.10.10
DHT-Link: P 1 SHA-1:5 5.5.5.5
DHT-Link: S 1 SHA-1:3 3.3.3.3
Require: dht
Supported: dht
Node 5 -> Node 3
REGISTER sip:sipchat/3.3.3.3 SIP/2.0
To: sip:sipchat/carl@p2psip.org;resource-ID=SHA-1:11
From: sip:sipchat/carl@p2psip.org;resource-ID=SHA-1:11
Contact: sip:sipchat/carl@5.5.5.5;resource-ID=SHA-1:11
Expires: 600
DHT-NodeID: SHA-1:5 5.5.5.5
Require: dht
Supported: dht
Node 3 -> Node 5
SIP/2.0 200 OK
To: sip:sipchat/carl@p2psip.org;resource-ID=SHA-1:11
From: sip:sipchat/carl@p2psip.org;resource-ID=SHA-1:11
Contact: sip:sipchat/carl@5.5.5.5;resource-ID=SHA-1:11
Expires: 600
DHT-NodeID: SHA-1:3 3.3.3.3
DHT-Link: P 1 SHA-1:10 10.10.10.10
DHT-Link: S 1 SHA-1:5 5.5.5.5
DHT-Link: S 2 SHA-1:10 10.10.10.10
Require: dht
Supported: dht
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 collocated 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@99.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:sipchat/alice@p2psip.org SIP/2.0
To: sip:sipchat/alice@p2psip.org;resource-ID=SHA-1:5
From: sip:sipchat/bob@p2psip.org;resource-ID=SHA-1:12
Contact: sip:sipchat/bob@10.10.10.10
DHT-NodeID: SHA-1:10 10.10.10.10.10
Require: dht
Supported: dht
Node 3 -> Node 10
SIP/2.0 302 Moved Temporarily
Contact: sip:sipchat/5@5.5.5.5;user=node
DHT-NodeID: SHA-1:3 3.3.3.3
DHT-Link: P 1 SHA-1:10 10.10.10.10
DHT-Link: S 1 SHA-1:5 5.5.5.5
Require: dht
Supported: dht
Node 10 -> Node 5
INVITE sip:sipchat/alice@p2psip.org SIP/2.0
To: sip:sipchat:alice@p2psip.org;resource-ID=SHA-1:5
From: sip:sipchat:bob@p2psip.org;resource-ID=SHA-1:12
Contact: sip:sipchat:bob@10.10.10.10
DHT-NodeID: SHA-1:10 10.10.10.10.10
Require: dht
Supported: dht
Node 5 -> Node 10
SIP/2.0 302 Moved Temporarily
Contact: sip:sipchat:alice@99.99.99.99
DHT-NodeID: SHA-1:5 5.5.5.5
DHT-Link: P 1 SHA-1:3 3.3.3.3
DHT-Link: S 1 SHA-1:10 10.10.10.10
Require: dht
Supported: dht
[To Do: Rest of call flow, with correct handling of fact
Alice's UA is not DHT compliant]
[To Do: Add an example here]
[To Do: Add an example here]
[To Do: Add an example here]
| TOC |
[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. However, it does trade off some security for certain other properties such as no centralized server or owner of the name space.
The attacker is assumed to be able to generate and identity and become a valid node in the system. They can see other nodes and process certain queries. Attackers may wish to receive communications for another participant. Stop another user from receiving their messages. Stop large portions of the users from receiving messages. Send messages that appear to be from others. Users would like to know they are communicating with the same person they previously talked 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 to get a name that is meaningful to them. Attackers may have computers that are many times faster than the average user. Attackers may be able to DOS other particular nodes and make them fail. To make a robust DHT, many nodes needs to store information on behalf of the community. Nodes may lie about this and not store the information. Attackers may which to see who is communicating with whom and how much data they are communicating.
A key requirement of the system is that there is no centralized naming authority and users can pick names. This means that two users could pick the same name and the system needs a way to arbitrate between which one of them should be allowed to use that name. We present two schemes for protecting the namespace. Implementations SHOULD use some scheme to ensure that users are who they say they are.
Users MUST use a valid email address as their user id. At the time the user registers with the system, the responsible node looks to see if any previous registrations have been entered for this user. If they have not, the node generates an email and sends it to the email being used as a user id. Included in this email is a password. This password may either be a conventional password, or a portion of a key system, in which case other nodes that might replicate the information would have only the public portion of the key.
After receiving this email, the user will re-register. The node receiving the registration MUST challenge the registration, expecting the user to provide the password sent in email. If the user successfully meets the challenge, the password is stored along with the users registration, as well as an expiration. The expiration SHOULD be for a period of between 30 and 90 days. This registration, like a normal user registration SHOULD be replicated to other nodes, so that they can preserve the password.
When a node re-registers at a later date, the node must check if the password is still valid. If it is not, a new email must be sent. If it is, the registering user should be challenged, and if the registration is successful, the expiration SHOULD be advanced to 30 or 90 days from the date of re-registration. In such a way, registrations will only expire if the user ids are unused for an extended portion of time.
The DHT forms a complex routing table. When a node joins, nodes it contacts could like about finger information to try and send all the traffic from that done through themselves.
The goal here is to stop the attacker from know who is signaling what to who.
The interactive systems mans that nodes only see the queries. Clients can randomly generate these to obfuscate who they are tying to connect too. Cached results localize the area in the DHT where an attackers node would have to be located to see a attempted connection to a given node.
All the media needs to be S/MIME encrypted. This reduces the value of intercepting someone else communication to a fairly low value because you can't see the media in the message. This is critical.
| TOC |
There are certainly many open issues. Here are a few.
Still working on the 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, and that clearly won't work, since they will all hash to the same ID. I used IP address 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 of using them.
Among the thoughts we have had on this issue. First, require the use of mechanisms such as STUN, and require that actual IP addresses be placed in the messages. This works well, but causes the problem that only one node can be behind a 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.
Not sure what the correct delimiter between the overlay and username in URIs is. We have used / for now (sip:sipchat/user@address), but perhaps this isn't the right choice. Need to ensure that we have a legal character and that there won't be any issues with parsing.
This draft needs to be changed to use all non-routable IP addresses in the examples.
| TOC |
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 |
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.
- Columbia University
- Another project on P2P-SIP is being developed at Columbia University by Kundan Singh and Henning Schulzrinne.
| TOC |
This document would require registering the following:
[ToDo: Not sure if that is all the things that would need to be registered]
| TOC |
| TOC |
| [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. |
| TOC |
| [4] | Stoica, I., Morris, R., Karger, D., Kaashoek, M. and H. Balakrishnan, "Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications", SIGCOMM '01, August 2001. |
| [5] | Douceur, J., "The Sybil Attack", IPTPS '02, March 2002. |
| TOC |
| 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 |
The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org.
This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Copyright (C) The Internet Society (2005). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights.
Funding for the RFC Editor function is currently provided by the Internet Society.