SIPPING WG D. Bryan
Internet-Draft College of William and Mary
Expires: January 16, 2006 C. 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 (C) 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
Bryan & Jennings Expires January 16, 2006 [Page 1]
Internet-Draft P2P SIP July 2005
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 . . . . . . . . . . . . . . . . . . . . . . . . . 4
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4
3. Background . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.1 Peer-to-Peer Fundamentals . . . . . . . . . . . . . . . . 4
3.2 Distributed Hash Table (DHT) Systems . . . . . . . . . . . 5
3.3 Chord . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.4 Issues for P2P Systems . . . . . . . . . . . . . . . . . . 7
4. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.1 Node Functions and Behavior . . . . . . . . . . . . . . . 8
4.2 P2P Overlay Structure . . . . . . . . . . . . . . . . . . 8
4.3 Message Format . . . . . . . . . . . . . . . . . . . . . . 10
4.4 Node Registration . . . . . . . . . . . . . . . . . . . . 10
4.5 User Registration . . . . . . . . . . . . . . . . . . . . 10
4.6 Session Establishment . . . . . . . . . . . . . . . . . . 11
5. Message Syntax . . . . . . . . . . . . . . . . . . . . . . . . 11
5.1 Option Tags . . . . . . . . . . . . . . . . . . . . . . . 11
5.2 Hash Algorithms and the alg URI Parameter . . . . . . . . 12
5.3 Node-IDs and the user=node URI Parameter . . . . . . . . . 12
5.4 Resource-IDs and the resource-ID URI Parameter . . . . . . 12
5.5 Overlay Names and the overlay URI Parameter . . . . . . . 13
5.6 The DHT-NodeID Header . . . . . . . . . . . . . . . . . . 13
5.7 The DHT-Link Header . . . . . . . . . . . . . . . . . . . 14
5.8 URIs . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
5.8.1 P2P Node URIs . . . . . . . . . . . . . . . . . . . . 15
5.8.2 P2P User URIs . . . . . . . . . . . . . . . . . . . . 16
6. Node/DHT Operations . . . . . . . . . . . . . . . . . . . . . 16
6.1 Starting a New Overlay . . . . . . . . . . . . . . . . . . 17
6.2 Bootstrapping . . . . . . . . . . . . . . . . . . . . . . 17
6.3 Node Registration . . . . . . . . . . . . . . . . . . . . 17
6.3.1 Constructing a Node Registration . . . . . . . . . . . 18
6.3.2 Processing the Node Registration . . . . . . . . . . . 19
6.4 Resource Location/Search . . . . . . . . . . . . . . . . . 22
6.4.1 Constructing a Node Search Message . . . . . . . . . . 22
6.4.2 Processing Node Search Message . . . . . . . . . . . . 23
6.5 Populating the Joining Node's Finger Table . . . . . . . . 24
6.6 Transfering User Registrations . . . . . . . . . . . . . . 25
6.7 Nodes Leaving the Overlay Gracefully . . . . . . . . . . . 25
Bryan & Jennings Expires January 16, 2006 [Page 2]
Internet-Draft P2P SIP July 2005
6.8 Periodic Stabilization . . . . . . . . . . . . . . . . . . 25
6.9 Handling Failed Requests . . . . . . . . . . . . . . . . . 26
6.10 Node Failure . . . . . . . . . . . . . . . . . . . . . . . 26
7. User-level operations . . . . . . . . . . . . . . . . . . . . 26
7.1 User Registration . . . . . . . . . . . . . . . . . . . . 26
7.1.1 User Registrations . . . . . . . . . . . . . . . . . . 26
7.1.2 Refreshing User Registrations . . . . . . . . . . . . 28
7.1.3 Removing User Registrations . . . . . . . . . . . . . 28
7.1.4 Querying User Registrations . . . . . . . . . . . . . 28
7.2 Session Establishment . . . . . . . . . . . . . . . . . . 29
7.3 Presence . . . . . . . . . . . . . . . . . . . . . . . . . 29
8. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
8.1 Example of a Node Registration . . . . . . . . . . . . . . 32
8.2 Example of a User Registration . . . . . . . . . . . . . . 34
8.3 Example of a Session Establishment . . . . . . . . . . . . 36
8.4 Example of a Node Leaving the System . . . . . . . . . . . 38
8.5 Example of a Successful User Search . . . . . . . . . . . 38
8.6 Example of an Unsucessful User Search . . . . . . . . . . 38
9. Security Considerations . . . . . . . . . . . . . . . . . . . 39
9.1 Threat Model . . . . . . . . . . . . . . . . . . . . . . . 39
9.2 Protecting the Namespace . . . . . . . . . . . . . . . . . 39
9.2.1 Certificate Based Protection . . . . . . . . . . . . . 39
9.3 Protecting the Routing . . . . . . . . . . . . . . . . . . 40
9.4 Protecting the Signaling . . . . . . . . . . . . . . . . . 40
9.5 Protecting the Media . . . . . . . . . . . . . . . . . . . 40
9.6 Replay Attacks . . . . . . . . . . . . . . . . . . . . . . 40
9.7 Cut and Paste Attacks . . . . . . . . . . . . . . . . . . 41
9.8 Identity Theft Attacks . . . . . . . . . . . . . . . . . . 41
9.9 Limitations of the Security . . . . . . . . . . . . . . . 41
10. Open Issues . . . . . . . . . . . . . . . . . . . . . . . . 41
11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . 42
12. Implementations . . . . . . . . . . . . . . . . . . . . . . 42
13. IANA Considerations . . . . . . . . . . . . . . . . . . . . 42
14. Definitions . . . . . . . . . . . . . . . . . . . . . . . . 43
15. References . . . . . . . . . . . . . . . . . . . . . . . . . 45
15.1 Normative References . . . . . . . . . . . . . . . . . . . 45
15.2 Informative References . . . . . . . . . . . . . . . . . . 45
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 46
Intellectual Property and Copyright Statements . . . . . . . . 47
Bryan & Jennings Expires January 16, 2006 [Page 3]
Internet-Draft P2P SIP July 2005
1. Introduction
As SIP [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 [5] P2P SIP project.
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 [1].
Terminology defined in RFC 3261 [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 (Section 14) 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.
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
Bryan & Jennings Expires January 16, 2006 [Page 4]
Internet-Draft P2P SIP July 2005
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
Bryan & Jennings Expires January 16, 2006 [Page 5]
Internet-Draft P2P SIP July 2005
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 [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.
Bryan & Jennings Expires January 16, 2006 [Page 6]
Internet-Draft P2P SIP July 2005
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 [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.
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
Bryan & Jennings Expires January 16, 2006 [Page 7]
Internet-Draft P2P SIP July 2005
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. (Section 14)
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
Bryan & Jennings Expires January 16, 2006 [Page 8]
Internet-Draft P2P SIP July 2005
created by hashing the IP address and port of the node providing
service. This creates some security issues. See the Open Issues
(Section 10) 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
Bryan & Jennings Expires January 16, 2006 [Page 9]
Internet-Draft P2P SIP July 2005
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
Bryan & Jennings Expires January 16, 2006 [Page 10]
Internet-Draft P2P SIP July 2005
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.
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
Bryan & Jennings Expires January 16, 2006 [Page 11]
Internet-Draft P2P SIP July 2005
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. [4] Currently, those consist of 'rsa-
sha1', indicating SHA-1 as defined in RFC 3174. [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
Bryan & Jennings Expires January 16, 2006 [Page 12]
Internet-Draft P2P SIP July 2005
imposed on the user IDs in a P2P SIP system. Note that various
security schemes, two of which are discussed in Protecting the
Namespace (Section 9.2) 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:
Bryan & Jennings Expires January 16, 2006 [Page 13]
Internet-Draft P2P SIP July 2005
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
Bryan & Jennings Expires January 16, 2006 [Page 14]
Internet-Draft P2P SIP July 2005
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
Bryan & Jennings Expires January 16, 2006 [Page 15]
Internet-Draft P2P SIP July 2005
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
6. Node/DHT Operations
The SIP REGISTER message is used extensively in this system.
Bryan & Jennings Expires January 16, 2006 [Page 16]
Internet-Draft P2P SIP July 2005
REGISTER is used to register users, as in conventional SIP systems,
and we discuss this further in the User Registration (Section 7.1)
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
Bryan & Jennings Expires January 16, 2006 [Page 17]
Internet-Draft P2P SIP July 2005
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 (Section 5.8.1) 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
Bryan & Jennings Expires January 16, 2006 [Page 18]
Internet-Draft P2P SIP July 2005
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
Bryan & Jennings Expires January 16, 2006 [Page 19]
Internet-Draft P2P SIP July 2005
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
(Section 5.8.1) 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
Bryan & Jennings Expires January 16, 2006 [Page 20]
Internet-Draft P2P SIP July 2005
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 (Section 5.7) 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:
Bryan & Jennings Expires January 16, 2006 [Page 21]
Internet-Draft P2P SIP July 2005
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".
Bryan & Jennings Expires January 16, 2006 [Page 22]
Internet-Draft P2P SIP July 2005
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 (Section 5.8.1) 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
Bryan & Jennings Expires January 16, 2006 [Page 23]
Internet-Draft P2P SIP July 2005
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 (Section 5.8.1) 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
(Section 5.7) 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,
Bryan & Jennings Expires January 16, 2006 [Page 24]
Internet-Draft P2P SIP July 2005
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 (Section 4.2) 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 (Section 7.1), 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
Bryan & Jennings Expires January 16, 2006 [Page 25]
Internet-Draft P2P SIP July 2005
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 (Section 6.5) 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 (Section 6.5) 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.
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
Bryan & Jennings Expires January 16, 2006 [Page 26]
Internet-Draft P2P SIP July 2005
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 (Section 5.8.2). 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 (Section 6.3). 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.
Bryan & Jennings Expires January 16, 2006 [Page 27]
Internet-Draft P2P SIP July 2005
[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 (Section 6.4), this mechanism
can also be used to locate the node responsible for a particular
Bryan & Jennings Expires January 16, 2006 [Page 28]
Internet-Draft P2P SIP July 2005
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. (Section 6.4)
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 (Section 6.8)
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.
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
Bryan & Jennings Expires January 16, 2006 [Page 29]
Internet-Draft P2P SIP July 2005
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:
Bryan & Jennings Expires January 16, 2006 [Page 30]
Internet-Draft P2P SIP July 2005
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.
Bryan & Jennings Expires January 16, 2006 [Page 31]
Internet-Draft P2P SIP July 2005
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
(Section 4.4), 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
Bryan & Jennings Expires January 16, 2006 [Page 32]
Internet-Draft P2P SIP July 2005
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
Bryan & Jennings Expires January 16, 2006 [Page 33]
Internet-Draft P2P SIP July 2005
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 (Section 7.1.1). 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
Bryan & Jennings Expires January 16, 2006 [Page 34]
Internet-Draft P2P SIP July 2005
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
Bryan & Jennings Expires January 16, 2006 [Page 35]
Internet-Draft P2P SIP July 2005
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.
Bryan & Jennings Expires January 16, 2006 [Page 36]
Internet-Draft P2P SIP July 2005
[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
Bryan & Jennings Expires January 16, 2006 [Page 37]
Internet-Draft P2P SIP July 2005
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]
Bryan & Jennings Expires January 16, 2006 [Page 38]
Internet-Draft P2P SIP July 2005
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
Bryan & Jennings Expires January 16, 2006 [Page 39]
Internet-Draft P2P SIP July 2005
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
Bryan & Jennings Expires January 16, 2006 [Page 40]
Internet-Draft P2P SIP July 2005
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.
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.
Bryan & Jennings Expires January 16, 2006 [Page 41]
Internet-Draft P2P SIP July 2005
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.
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!
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 [9] 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 [10] is being
developed at Columbia University by Kundan Singh and Henning
Schulzrinne. This project implements an alternate [8]proposal for
a P2P SIP implementation.
13. IANA Considerations
This document would require registering the following:
o Option tag "DHT"
Bryan & Jennings Expires January 16, 2006 [Page 42]
Internet-Draft P2P SIP July 2005
o "DHT-Link" as a Header Field
o "DHT-NodeID" as a Header Field
o "node" as a valid value for parameter user (?)
o "Resource-ID" as a valid URI parameter (?)
[ToDo: Not sure if that is all the things that would need to be
registered]
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.
Bryan & Jennings Expires January 16, 2006 [Page 43]
Internet-Draft P2P SIP July 2005
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.
Bryan & Jennings Expires January 16, 2006 [Page 44]
Internet-Draft P2P SIP July 2005
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.
15. References
15.1 Normative References
[1] Bradner, S., "Key words for use in RFCs to Indicate Requirement
Levels", BCP 14, RFC 2119, March 1997.
[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.
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.
URIs
[9] <http://www.p2psip.org>
Bryan & Jennings Expires January 16, 2006 [Page 45]
Internet-Draft P2P SIP July 2005
[10] <http://www1.cs.columbia.edu/~kns10/research/p2p-sip/>
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
Bryan & Jennings Expires January 16, 2006 [Page 46]
Internet-Draft P2P SIP July 2005
Intellectual Property Statement
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.
Disclaimer of Validity
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 Statement
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.
Acknowledgment
Funding for the RFC Editor function is currently provided by the
Internet Society.
Bryan & Jennings Expires January 16, 2006 [Page 47]