draft-ietf-p2psip-service-discovery-06.txt   draft-ietf-p2psip-service-discovery-07.txt 
P2PSIP Working Group J. Maenpaa P2PSIP Working Group J. Maenpaa
Internet-Draft G. Camarillo Internet-Draft G. Camarillo
Intended status: Standards Track Ericsson Intended status: Standards Track Ericsson
Expires: April 4, 2013 October 1, 2012 Expires: August 20, 2013 February 16, 2013
Service Discovery Usage for REsource LOcation And Discovery (RELOAD) Service Discovery Usage for REsource LOcation And Discovery (RELOAD)
draft-ietf-p2psip-service-discovery-06.txt draft-ietf-p2psip-service-discovery-07.txt
Abstract Abstract
REsource LOcation and Discovery (RELOAD) does not define a generic REsource LOcation and Discovery (RELOAD) does not define a generic
service discovery mechanism as part of the base protocol. This service discovery mechanism as a part of the base protocol. This
document defines how the Recursive Distributed Rendezvous (ReDiR) document defines how the Recursive Distributed Rendezvous (ReDiR)
service discovery mechanism used in OpenDHT can be applied to RELOAD service discovery mechanism used in OpenDHT can be applied to RELOAD
overlays to provide a generic service discovery mechanism. overlays to provide a generic service discovery mechanism.
Status of this Memo Status of this Memo
This Internet-Draft is submitted to IETF in full conformance with the This Internet-Draft is submitted to IETF in full conformance with the
provisions of BCP 78 and BCP 79. provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/. Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on April 4, 2013. This Internet-Draft will expire on August 20, 2013.
Copyright Notice Copyright Notice
Copyright (c) 2012 IETF Trust and the persons identified as the Copyright (c) 2013 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4
3. Introduction to ReDiR . . . . . . . . . . . . . . . . . . . . 4 3. Introduction to ReDiR . . . . . . . . . . . . . . . . . . . . 4
4. Using ReDiR in a RELOAD Overlay Instance . . . . . . . . . . . 6 4. Using ReDiR in a RELOAD Overlay Instance . . . . . . . . . . . 6
4.1. Data Structure . . . . . . . . . . . . . . . . . . . . . . 6 4.1. Data Structure . . . . . . . . . . . . . . . . . . . . . . 6
4.2. Selecting the Starting Level . . . . . . . . . . . . . . . 7 4.2. Selecting the Starting Level . . . . . . . . . . . . . . . 7
4.3. Service Provider Registration . . . . . . . . . . . . . . 7 4.3. Service Provider Registration . . . . . . . . . . . . . . 8
4.4. Refreshing Registrations . . . . . . . . . . . . . . . . . 8 4.4. Refreshing Registrations . . . . . . . . . . . . . . . . . 8
4.5. Service Lookups . . . . . . . . . . . . . . . . . . . . . 9 4.5. Service Lookups . . . . . . . . . . . . . . . . . . . . . 9
4.6. Removing Registrations . . . . . . . . . . . . . . . . . . 9 4.6. Removing Registrations . . . . . . . . . . . . . . . . . . 10
5. Access Control Rules . . . . . . . . . . . . . . . . . . . . . 9 5. Access Control Rules . . . . . . . . . . . . . . . . . . . . . 10
6. REDIR Kind Definition . . . . . . . . . . . . . . . . . . . . 10 6. REDIR Kind Definition . . . . . . . . . . . . . . . . . . . . 11
7. Example . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 7. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
8. Overlay Configuration Document Extension . . . . . . . . . . . 12 7.1. Service Registration . . . . . . . . . . . . . . . . . . . 11
9. Security Considerations . . . . . . . . . . . . . . . . . . . 13 7.2. Service Lookup . . . . . . . . . . . . . . . . . . . . . . 13
10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 13 8. Overlay Configuration Document Extension . . . . . . . . . . . 14
10.1. Access Control Policies . . . . . . . . . . . . . . . . . 13 9. Security Considerations . . . . . . . . . . . . . . . . . . . 14
10.2. Data Kind-ID . . . . . . . . . . . . . . . . . . . . . . . 13 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 14
10.3. ReDiR Namespaces . . . . . . . . . . . . . . . . . . . . . 13 10.1. Access Control Policies . . . . . . . . . . . . . . . . . 14
11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 14 10.2. Data Kind-ID . . . . . . . . . . . . . . . . . . . . . . . 14
12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 14 10.3. ReDiR Namespaces . . . . . . . . . . . . . . . . . . . . . 15
12.1. Normative References . . . . . . . . . . . . . . . . . . . 14 11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 15
12.2. Informative References . . . . . . . . . . . . . . . . . . 14 12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 14 12.1. Normative References . . . . . . . . . . . . . . . . . . . 15
12.2. Informative References . . . . . . . . . . . . . . . . . . 15
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 16
1. Introduction 1. Introduction
REsource LOcation And Discovery (RELOAD) [I-D.ietf-p2psip-base] is a REsource LOcation And Discovery (RELOAD) [I-D.ietf-p2psip-base] is a
peer-to-peer signaling protocol that can be used to maintain an peer-to-peer signaling protocol that can be used to maintain an
overlay network, and to store data in and retrieve data from the overlay network, and to store data in and retrieve data from the
overlay. Although RELOAD defines a Traversal Using Relays around overlay. Although RELOAD defines a Traversal Using Relays around
Network Address Translation (TURN) specific service discovery Network Address Translation (TURN) specific service discovery
mechanism, it does not define a generic service discovery mechanism mechanism, it does not define a generic service discovery mechanism
as part of the base protocol. This document defines how the as a part of the base protocol. This document defines how the
Recursive Distributed Rendezvous (ReDiR) service discovery mechanism Recursive Distributed Rendezvous (ReDiR) service discovery mechanism
[Redir] used in OpenDHT can be applied to RELOAD overlays. [Redir] used in OpenDHT can be applied to RELOAD overlays.
In a Peer-to-Peer (P2P) overlay network such as a RELOAD Overlay In a Peer-to-Peer (P2P) overlay network such as a RELOAD Overlay
Instance, the peers forming the overlay share their resources in Instance, the peers forming the overlay share their resources in
order to provide the service the system has been designed to provide. order to provide the service the system has been designed to provide.
The peers in the overlay both provide services to other peers and The peers in the overlay both provide services to other peers and
request services from other peers. Examples of possible services request services from other peers. Examples of possible services
peers in a RELOAD Overlay Instance can offer to each other include a peers in a RELOAD Overlay Instance can offer to each other include a
TURN relay service, a voice mail service, a gateway location service, TURN relay service, a voice mail service, a gateway location service,
skipping to change at page 4, line 24 skipping to change at page 4, line 24
DHT: Distributed Hash Tables (DHTs) are a class of decentralized DHT: Distributed Hash Tables (DHTs) are a class of decentralized
distributed systems that provide a lookup service similar to a distributed systems that provide a lookup service similar to a
hash table. Given a key, any participating peer can retrieve the hash table. Given a key, any participating peer can retrieve the
value associated with that key. The responsibility for value associated with that key. The responsibility for
maintaining the mapping from keys to values is distributed among maintaining the mapping from keys to values is distributed among
the peers. the peers.
H(x): Hash calculated over x. H(x): Hash calculated over x.
I(l,k): The unique interval at level l in the ReDiR tree that I(l,k): An interval at level l in the ReDiR tree that encloses key
encloses key k. k.
n.id: Node-ID of node n. n.id: Node-ID of node n.
Namespace: An arbitrary identifier that identifies a service Namespace: An arbitrary identifier that identifies a service
provided in the RELOAD Overlay Instance. An example of a provided in the RELOAD Overlay Instance. An example of a
namespace is "voice-mail". The namespace is an UTF-8 text string. namespace is "voice-mail". The namespace is an UTF-8 text string.
numBitsInNodeId: Number of bits in a Node-ID. numBitsInNodeId: Number of bits in a Node-ID.
ReDiR tree: A tree structure of the nodes that provide a particular ReDiR tree: A tree structure of the nodes that provide a particular
service. The nodes embed the ReDiR tree into the RELOAD Overlay service. The nodes embed the ReDiR tree into the RELOAD Overlay
Instance using RELOAD Store and Fetch requests. Instance using RELOAD Store and Fetch requests.
Successor: The successor of identifier k in namespace ns is the node Successor: The successor of identifier k in namespace ns is the node
that has joined ns whose identifier most immediately follows k. belonging to ns whose identifier most immediately follows k.
3. Introduction to ReDiR 3. Introduction to ReDiR
Recursive Distributed Rendezvous (ReDiR) [Redir] does not require new Recursive Distributed Rendezvous (ReDiR) [Redir] does not require new
functionality from the RELOAD base protocol. This is possible since functionality from the RELOAD base protocol. This is possible since
ReDiR interacts with the RELOAD overlay through a put/get API using ReDiR interacts with the RELOAD overlay through a put/get API using
RELOAD Store and Fetch requests. ReDiR builds a tree structure of RELOAD Store and Fetch requests. ReDiR builds a tree structure of
the nodes that provide a particular service and embeds it into the the nodes that provide a particular service and embeds it into the
RELOAD Overlay Instance using the Store and Fetch requests. ReDiR RELOAD Overlay Instance using the Store and Fetch requests. ReDiR
performs lookup in a logarithmic number of Fetch operations with high performs lookup in a logarithmic number of Fetch operations with high
probability. Further, if the tree's height is estimated based on probability. Further, if the height of the ReDiR tree is estimated
past lookups, the average lookup can be reduced to a constant number based on lookups carried out previously, the average lookup can be
of Fetch operations assuming that Node-IDs are distributed uniformly reduced to a constant number of Fetch operations assuming that Node-
at random. IDs are distributed uniformly at random.
In ReDiR, each service provided in the overlay is identified by an In ReDiR, each service provided in the overlay is identified by an
arbitrary identifier, called its namespace. All service providers identifier, called the namespace. All service providers of a given
join a namespace and peers wishing to use a service perform lookups service join the namespace of that service. Peers wishing to use a
within the namespace of the service. A ReDiR lookup for identifier k service perform lookups within the namespace of the service. The
in namespace ns returns a node that has joined ns whose identifier is result of a ReDiR lookup for an identifier k in namespace ns is a
the closest successor of k. RedirServiceProvider structure (see Section 4.1) of a service
provider that belongs to ns and whose Node-ID is the closest
successor of identifier k in the namespace.
Each tree node in the ReDiR tree contains a list of Node-IDs of peers Each tree node in the ReDiR tree contains a dictionary of
providing a particular service. Each node in the tree has a level. RedirServiceProvider entries of peers providing a particular service.
The root is at level 0, the immediate children of the root are at Each tree node in the ReDiR tree also belongs to some level in the
level 1, and so forth. The ReDiR tree has a branching factor, whose tree. The root node of the ReDiR tree is located at level 0. The
value is determined by a new element in the RELOAD overlay child nodes of the root node are located at level 1 of the ReDiR
configuration document, called branching-factor. At every level i in tree. The children of the tree nodes at level 1 are located at level
the tree, there are at most branching-factor^i nodes. The nodes at 2, and so forth. The ReDiR tree has a branching factor, whose value
any level are labeled from left to right, such that a pair (i,j) is determined by a new element in the RELOAD overlay configuration
uniquely identifies the jth node from the left at level i. This tree document, called branching-factor. At every level l in the ReDiR
is embedded into the RELOAD Overlay Instance node by node, by storing tree, there is room for a maximum of branching-factor^l tree nodes.
the values of node (i,j) at key H(namespace,i,j). As an example, the As an example, in a tree whose branching-factor is 2, the second
root of the tree for a voice mail service is stored at H("voice- level can contain up to 4 tree nodes (note that a given level may
mail",0,0). Each node (i,j) in the tree is associated with contain less than the maximum number of tree nodes since empty tree
branching-factor intervals of the DHT keyspace as follows: nodes are not stored). Each tree node in the ReDiR tree is uniquely
identified by a pair (l,j), where l is a level in the ReDiR tree and
j is the position of the tree node (from the left) at that level. As
an example, the pair (2,3) identifies the 3rd tree node from the left
at level 2.
[2^numBitsInNodeID*b^(-i)*(j+(b'/b)), The ReDiR tree is stored into the RELOAD Overlay Instance tree node
2^numBitsInNodeID*b^(-i)*(j+((b'+1)/b))), for 0<=b'<b, by tree node, by storing the values of tree node (level,j) at key
H(namespace,level,j). As an example, the root of the tree for a
voice mail service is stored at H("voice-mail",0,0). Each node
(level,j) in the ReDiR tree contains b intervals of the DHT's
identifier space as follows:
[2^numBitsInNodeID*b^(-level)*(j+(b'/b)),
2^numBitsInNodeID*b^(-level)*(j+((b'+1)/b))), for 0<=b'<b,
where b is the branching-factor. where b is the branching-factor.
Figure 1 shows an example of a ReDiR tree with a branching factor of Figure 1 shows an example of a ReDiR tree whose branching factor is
2. Each node is shown as two horizontal lines separated by a 2. Each tree node is shown as two horizontal lines separated by a
vertical bar. The lines represent the two intervals each node is vertical bar in the middle. The lines represent the two intervals
responsible for. At level 0, there is only one node, (0,0) each node is responsible for. At level 0, there is only one node,
responsible for two intervals that together cover the entire (0,0) responsible for two intervals that together cover the entire
identifier space of the RELOAD Overlay Instance. At level 1, there identifier space of the RELOAD Overlay Instance. At level 1, there
are two nodes, (1,0) and (1,1), each of which is responsible for half are two nodes, (1,0) and (1,1), each of which is responsible for half
of the identifier space. At level 2, there are four nodes. Each of of the identifier space of the RELOAD Overlay Instance. At level 2,
them owns one fourth of the identifier space. At level 3, there are there are four nodes. Each of them owns one fourth of the identifier
eight nodes each of which is responsible for one eight of the space. At level 3, there are eight nodes each of which is
identifier space. responsible for one eight of the identifier space.
Level 0 __________________|__________________ Level 0 __________________|__________________
| | | |
Level 1 ________|________ ________|________ Level 1 ________|________ ________|________
| | | | | | | |
Level 2 ___|___ ___|___ ___|___ ___|___ Level 2 ___|___ ___|___ ___|___ ___|___
| | | | | | | | | | | | | | | |
Level 3 _|_ _|_ _|_ _|_ _|_ _|_ _|_ _|_ Level 3 _|_ _|_ _|_ _|_ _|_ _|_ _|_ _|_
Figure 1: ReDiR tree Figure 1: ReDiR tree
skipping to change at page 7, line 7 skipping to change at page 7, line 12
} RedirServiceProvider; } RedirServiceProvider;
The contents of the RedirServiceProvider Resource Record are as The contents of the RedirServiceProvider Resource Record are as
follows: follows:
type type
The type of an extension to the RedirServiceProvider Resource The type of an extension to the RedirServiceProvider Resource
Record. Unknown types are allowed. Record. Unknown types are allowed.
detination_list destination_list
A list of IDs through which a message is to be routed to reach the A list of IDs through which a message is to be routed to reach the
service provider. The destination list consists of a sequence of service provider. The destination list consists of a sequence of
Destination values. The contents of the Destination structure are Destination values. The contents of the Destination structure are
as defined in RELOAD base [I-D.ietf-p2psip-base]. as defined in RELOAD base [I-D.ietf-p2psip-base].
namespace namespace
An opaque string containing the namespace. An opaque UTF-8 encoded string containing the namespace.
level level
The level in the ReDiR tree. The level in the ReDiR tree.
node node
The position of the node storing this RedirServiceProvider record The position of the node storing this RedirServiceProvider record
at the current level in the ReDiR tree. at the current level in the ReDiR tree.
length length
The length of the rest of the Resource Record. The length of the rest of the Resource Record.
skipping to change at page 7, line 36 skipping to change at page 7, line 41
extension extension
An extension value. The RedirServiceProvider Resource Record can An extension value. The RedirServiceProvider Resource Record can
be extended to include for instance service or service provider be extended to include for instance service or service provider
specific information. specific information.
4.2. Selecting the Starting Level 4.2. Selecting the Starting Level
Before registering as a service provider or performing a service Before registering as a service provider or performing a service
lookup, a peer needs to determine the starting level Lstart for the lookup, a peer needs to determine the starting level Lstart for the
registration or lookup operation in the ReDiR tree. It is registration or lookup operation in the ReDiR tree. It is
RECOMMENDED that Lstart is initially set to 2. In subsequent RECOMMENDED that Lstart is set to 2. In subsequent registrations,
registrations, Lstart MUST be set to the lowest level at which Lstart MAY, as an optimization, be set to the lowest level at which a
registration last completed. registration operation has last completed.
In the case of service lookups, nodes MUST record the levels at which In the case of subsequent service lookups, nodes MAY, as an
the last 16 service lookups completed and take Lstart to be the mode optimization, record the levels at which the last 16 service lookups
of those depths. completed and take Lstart to be the mode of those depths.
4.3. Service Provider Registration 4.3. Service Provider Registration
A node MUST use the following procedure to register as a service A node MUST use the following procedure to register as a service
provider in the RELOAD Overlay Instance: provider in the RELOAD Overlay Instance:
1. A node n with Node-ID n.id wishing to register as a service 1. A node n with Node-ID n.id wishing to register as a service
provider starts from level Lstart (see Section 4.2 for the provider starts from a starting level Lstart (see Section 4.2 for
details on selecting the starting level). Therefore, node n sets the details on selecting the starting level). Therefore, node n
level=Lstart. sets level=Lstart.
2. Node n MUST send a RELOAD Fetch request to fetch the contents of 2. Node n MUST send a RELOAD Fetch request to fetch the contents of
the tree node associated with I(level,n.id). An interval I(l,k) the tree node responsible for I(level,n.id). An interval I(l,k)
is defined as the unique interval at level l in the ReDiR tree is the interval at level l in the ReDiR tree that includes key k.
that encloses key k. The fetch MUST be a wildcard fetch. The fetch MUST be a wildcard fetch.
3. Node n MUST send a RELOAD Store request to add its 3. Node n MUST send a RELOAD Store request to add its
RedirServiceProvider entry to the dictionary stored in the tree RedirServiceProvider entry to the dictionary stored in the tree
node associated with I(level,n.id) node responsible for I(level,n.id)
4. If node n's Node-ID is the numerically lowest or highest among 4. If node n's Node-ID (n.id) is the lowest or highest Node-ID
the Node-IDs stored in the tree node associated with stored in the tree node responsible for I(Lstart,n.id), node n
I(Lstart,n.id), node n MUST continue up the tree towards the root MUST reduce the current level by one (i.e., set level=level-1)
(level 0), repeating steps 2 and 3. Node n MUST continue this and continue up the ReDiR tree towards the root level (level 0),
until it reaches either the root or a level at which n.id is not repeating the steps 2 and 3 above. Node n MUST continue in this
the lowest or highest Node-ID in the interval I(level,n.id). way until it reaches either the root of the tree or a level at
5. Node n MUST also walk down the tree through tree nodes associated which n.id is not the lowest or highest Node-ID in the interval
with the intervals I(Lstart,n.id),I(Lstart+1,n.id),..., at each I(level,n.id).
step fetching the current contents of the tree node, and storing 5. Node n MUST also perform a downward walk in the ReDiR tree,
its RedirServiceProvider record if n.id is the lowest or highest during which it goes through the tree nodes responsible for
Node-ID in the interval. Node n MUST end this downward walk when intervals I(Lstart,n.id), I(Lstart+1,n.id), I(Lstart+2,n.id),
it reaches a level at which it is the only service provider in etc. At each step, node n MUST fetch the responsible tree node,
the interval. and store its RedirServiceProvider record in that tree node if
n.id is the lowest or highest Node-ID in its interval. Node n
MUST end this downward walk as soon as it reaches a level l at
which it is the only service provider in its interval I(l,n.id).
Note that above, when we refer to 'the tree node associated with Note that above, when we refer to 'the tree node responsible for
I(l,k)', we mean the entire tree node (that is, all the intervals I(l,k)', we mean the entire tree node (that is, all the intervals
within the tree node) responsible for interval I(l,k). In contrast, within the tree node) responsible for interval I(l,k). In contrast,
I(l,k) refers to a specific interval within a tree node. I(l,k) refers to a specific interval within a tree node.
4.4. Refreshing Registrations 4.4. Refreshing Registrations
All state in the ReDiR tree is soft. Therefore, a service provider All state in the ReDiR tree is soft. Therefore, a service provider
needs to periodically repeat the registration process to refresh its needs to periodically repeat the registration process to refresh its
RedirServiceProvider Resource Record. If a record expires, it MUST RedirServiceProvider Resource Record. If a record expires, it MUST
be dropped from the dictionary by the peer storing the tree node. be dropped from the dictionary by the peer storing the tree node.
skipping to change at page 9, line 7 skipping to change at page 9, line 12
provider MUST repeat the entire registration process periodically provider MUST repeat the entire registration process periodically
until it leaves the RELOAD Overlay Instance. until it leaves the RELOAD Overlay Instance.
Note that no new mechanisms are needed to keep track of the remaining Note that no new mechanisms are needed to keep track of the remaining
lifetime of RedirServiceProvider records. The 'storage_time' and lifetime of RedirServiceProvider records. The 'storage_time' and
'lifetime' fields of RELOAD's StoredData structure can be used for 'lifetime' fields of RELOAD's StoredData structure can be used for
this purpose in the usual way. this purpose in the usual way.
4.5. Service Lookups 4.5. Service Lookups
The purpose of a service lookup on identifier k in namespace ns is to The purpose of a service lookup for identifier k in namespace ns is
find the node that has joined ns whose identifier most immediately to find the node that is a part of ns and whose identifier most
follows identifier k. immediately follows (i.e., is the closest successor of) the
identifier k.
A service lookup is similar to the registration operation. The A service lookup is similar to the service registration operation
service lookup starts from some level level=Lstart (see Section 4.2 described in Section 4.3. Service lookups start from a given
for the details on selecting the starting level). At each step, the starting level level=Lstart in the ReDiR tree (see Section 4.2 for
node n wishing to discover a service provider MUST fetch the tree the details on selecting the starting level). At each step, a node n
node associated with the current interval I(level,n.id) using a wishing to discover a service provider MUST fetch the tree node
RELOAD Fetch request and MUST determine where to look next as responsible for the interval I(level,n.id) that encloses the search
follows: key n.id at the current level using a RELOAD Fetch request. Having
fetched the tree node, node n MUST determine the next action to carry
out as follows:
1. If the successor of node n is not present in the tree node 1. If there is no successor of node n present in the just fetched
associated with I(level,n.id), then its successor must occur in a ReDiR tree node (note: within the entire tree and not only within
larger range of the keyspace. Node n MUST set level=level-1 and the current interval) responsible for I(level,n.id), then the
try again. successor of node n must be present in a larger segment of the
2. If n.id is sandwiched between two Node-IDs in I(level,n.id), the identifier space (i.e., further up in the ReDiR tree where each
successor must lie somewhere in I(level,n.id). Node n MUST set interval and tree node covers a larger range of the identifier
level=level+1 and repeat. space). Therefore, node n MUST reduce the current level by one
3. Otherwise, there is a Node-ID s stored in the node associated to level=level-1 and carry out a new Fetch operation for the tree
with I(level,n.id) whose identifier succeeds n.id, and there are node responsible for n.id at that level. The fetched tree node
no Node-IDs between n.id and s. Thus, s must be the closest is then analyzed and the next action determined by checking
successor of n.id, and the lookup is done. conditions 1-3.
2. If n.id is neither the lowest nor the highest Node-ID within the
interval (note: within the interval, not within the entire tree
node) I(level,n.id), n MUST next check the tree node responsible
for n.id at the next level down the tree. Thus, node n MUST
increase the level by one to level=level+1 and carry out a new
Fetch operation at that level. The fetched tree node is then
analyzed and the next action determined by checking conditions
1-3.
3. If neither of the conditions above holds, meaning that there is a
successor s of n.id present in the just fetched ReDiR tree node
and n.id is the highest or lowest Node-ID in its interval, the
service lookup has finished successfully and s must be the
closest successor of n.id in the ReDiR tree.
Note that above, when we refer to 'the tree node associated with Note that above, when we refer to 'the tree node responsible for
I(l,k)', we mean the entire tree node (that is, all the intervals interval I(l,k)', we mean the entire tree node (that is, all the
within the tree node) responsible for interval I(l,k). In contrast, intervals within the tree node) responsible for interval I(l,k). In
I(l,k) refers to a specific interval within a tree node. contrast, I(l,k) refers to a specific interval within a tree node.
Note also that there may be some cases in which no successor can be
found from the ReDiR tree. An example is a situation in which all of
the service providers stored in the ReDiR tree have a Node-ID smaller
than identifier k. In this case, the upward walk of the service
lookup will reach the root of the tree without encountering a
successor. An appropriate strategy in this case is to pick one of
the RedirServiceProvider entries stored in the dictionary of the root
node at random.
4.6. Removing Registrations 4.6. Removing Registrations
Before leaving the RELOAD Overlay Instance, a service provider MUST Before leaving the RELOAD Overlay Instance, a service provider MUST
remove the RedirServiceProvider records it has stored by storing remove the RedirServiceProvider records it has stored by storing
exists=False values in their place, as described in exists=False values in their place, as described in
[I-D.ietf-p2psip-base]. [I-D.ietf-p2psip-base].
5. Access Control Rules 5. Access Control Rules
skipping to change at page 10, line 33 skipping to change at page 11, line 15
6. REDIR Kind Definition 6. REDIR Kind Definition
This section defines the REDIR kind. This section defines the REDIR kind.
Name Name
REDIR REDIR
Kind IDs Kind IDs
The Resource Name for the REDIR Kind-ID is created by The Resource Name for the REDIR Kind-ID is created by
concatenating three pieces of information: namespace, level, and concatenating three pieces of information: namespace, level, and
node number. Namespace is a string identifying a service, such as node number. Namespace is an opaque UTF-8 encoded string
"voice-mail". Level is an integer specifying a level in the ReDiR identifying a service, such as "turn-server". Level is an integer
tree. Node number is an integer identifying a ReDiR tree node at specifying a level in the ReDiR tree. Node number is an integer
a specific level. The data stored is a RedirServiceProvider identifying a ReDiR tree node at a specific level. The data
structure that was defined in Section 4.1. stored is a RedirServiceProvider structure that was defined in
Section 4.1.
Data Model Data Model
The data model for the REDIR Kind-ID is dictionary. The The data model for the REDIR Kind-ID is dictionary. The
dictionary key is the Node-ID of the service provider. dictionary key is the Node-ID of the service provider.
Access Control Access Control
The access control policy for the REDIR kind is the NODE-ID-MATCH The access control policy for the REDIR kind is the NODE-ID-MATCH
policy that was defined in Section 5. policy that was defined in Section 5.
7. Example 7. Examples
7.1. Service Registration
Figure 2 shows an example of a ReDiR tree containing information Figure 2 shows an example of a ReDiR tree containing information
about four different service providers whose Node-IDs are 2, 3, 4, about four different service providers whose Node-IDs are 2, 3, 4,
and 7. In the example, numBitsInNodeID=4. Initially, the ReDiR tree and 7. In the example, numBitsInNodeID=4. Initially, the ReDiR tree
is empty. is empty; Figure 2 shows the state of the tree at the point when all
the service providers have registered.
Level 0 ____2_3___4_____7_|__________________ Level 0 ____2_3___4_____7_|__________________
| | | |
Level 1 ____2_3_|_4_____7 ________|________ Level 1 ____2_3_|_4_____7 ________|________
| | | | | | | |
Level 2 ___|2_3 4__|__7 ___|___ ___|___ Level 2 ___|2_3 4__|__7 ___|___ ___|___
| | | | | | | | | | | | | | | |
Level 3 _|_ _|3 _|_ _|_ _|_ _|_ _|_ _|_ Level 3 _|_ _|3 _|_ _|_ _|_ _|_ _|_ _|_
Figure 2: Example of a ReDiR tree Figure 2: Example of a ReDiR tree
First, peer 2 whose Node-ID is 2 joins the namespace. Since this is First, peer 2 whose Node-ID is 2 joins the namespace. Since this is
the first registration peer 2 performs, peer 2 sets the starting the first registration peer 2 performs, peer 2 sets the starting
level Lstart to 2, as was described in Section 4.2. Also all other level Lstart to 2, as was described in Section 4.2. Also all other
peers in this example will start from level 2. First, peer 2 fetches peers in this example will start from level 2. First, peer 2 fetches
the contents of the tree node associated with interval I(2,2) from the contents of the tree node associated with interval I(2,2) from
the overlay. Peer 2 also stores its RedirServiceProvider record in the RELOAD Overlay Instance. This tree node is the first tree node
that tree node. Since peer 2's Node-ID is the only Node-ID stored in from the left at Level 2 since key 2 is associated with the second
the tree node (i.e., peer 2's Node-ID fulfills the condition that it interval of the first tree node. Peer 2 also stores its
is the numerically lowest or highest among the keys stored in the RedirServiceProvider record in that tree node. Since peer 2's
node), peer 2 continues up the tree. In fact, peer 2 continues up in Node-ID is the only Node-ID stored in the tree node (i.e., peer 2's
the tree all the way to the root inserting its own Node-ID in all Node-ID fulfills the condition in Section 4.3 that it is the
levels since the tree is empty (which means that peer 2's Node-ID numerically lowest or highest among the keys stored in the node),
always fulfills the condition that it is the numerically lowest or peer 2 continues up the tree. In fact, peer 2 continues up in the
highest Node-ID in the interval I(level, 2) during the upward walk). tree all the way to the root inserting its own Node-ID in all levels
As described in Section 4.3, peer 2 also walks down the tree. The since the tree is empty (which means that peer 2's Node-ID always
fulfills the condition that it is the numerically lowest or highest
Node-ID in the interval I(level, 2) during the upward walk). As
described in Section 4.3, peer 2 also walks down the tree. The
downward walk peer 2 does ends at level 2 since peer 2 is the only downward walk peer 2 does ends at level 2 since peer 2 is the only
node in its interval at that level. node in its interval at that level.
The next peer to join the namespace is peer 3, whose Node-ID is 3. The next peer to join the namespace is peer 3, whose Node-ID is 3.
Peer 3 starts from level 2. At that level, peer 3 stores its Peer 3 starts from level 2. At that level, peer 3 stores its
RedirServiceProvider record in the same interval I(2,3) that already RedirServiceProvider entry in the same interval I(2,3) that already
contains the Node-ID of peer 2. Since peer 3 has the numerically contains the RedirServiceProvider entry of peer 2. Interval I(2,3),
highest Node-ID in the tree node associated with I(2,3), peer 3 that is, the interval at Level 2 enclosing key 3, is associated with
continues up the tree. Peer 3 stores its RedirServiceProvider record the right hand side interval of the first tree node. Since peer 3
also at levels 1 and 0 since its Node-ID is numerically highest among has the numerically highest Node-ID in the tree node associated with
the Node-IDs stored in the intervals to which its own Node-ID I(2,3), peer 3 continues up the tree. Peer 3 stores its
belongs. Peer 3 also does a downward walk which starts from level 2 RedirServiceProvider record also at levels 1 and 0 since its Node-ID
(i.e., the starting level). Since peer 3 is not the only node in is numerically highest among the Node-IDs stored in the intervals to
interval I(2,3), it continues down the tree to level 3. The downward which its own Node-ID belongs. Peer 3 also does a downward walk
walk ends at this level since peer 3 is the only service provider in which starts from level 2 (i.e., the starting level). Since peer 3
the interval I(3,3). is not the only node in interval I(2,3), it continues down the tree
to level 3. The downward walk ends at this level since peer 3 is the
only service provider in the interval I(3,3).
The third peer to join the namespace is peer 7, whose Node-ID is 7. The third peer to join the namespace is peer 7, whose Node-ID is 7.
Like the two earlier peers, also peer 7 starts from level 2 because Like the two earlier peers, also peer 7 starts from level 2 because
this is the first registration it performs. Peer 7 stores its this is the first registration it performs. Peer 7 stores its
RedirServiceProvider record at level 2. At level 1, peer 7 has the RedirServiceProvider record at level 2. At level 1, peer 7 has the
numerically highest (and lowest) Node-ID in its interval I(1,7) numerically highest (and lowest) Node-ID in its interval I(1,7)
(because it is the only node in interval I(1,7); peers 2 and 3 are (because it is the only node in interval I(1,7); peers 2 and 3 are
stored in the same tree node but in a different interval) and stored in the same tree node but in a different interval) and
therefore it stores its Node-ID in the tree node associated with that therefore it stores its Node-ID in the tree node associated with that
interval. Peer 7 also has the numerically highest Node-ID in the interval. Peer 7 also has the numerically highest Node-ID in the
interval I(0,7) associated with its Node-ID at level 0. Finally, interval I(0,7) associated with its Node-ID at level 0. Finally,
peer 7 performs a downward walk, which ends at level 2 because peer 7 peer 7 performs a downward walk, which ends at level 2 because peer 7
skipping to change at page 12, line 29 skipping to change at page 13, line 18
Since it has the numerically lowest Node-ID in the tree node Since it has the numerically lowest Node-ID in the tree node
associated with interval I(2,4), it continues up in the tree to level associated with interval I(2,4), it continues up in the tree to level
1. At level 1, peer 4 stores its record in the tree node associated 1. At level 1, peer 4 stores its record in the tree node associated
with interval I(1,4) because it has the numerically lowest Node-ID in with interval I(1,4) because it has the numerically lowest Node-ID in
that interval. Next, peer 4 continues to the root level, at which it that interval. Next, peer 4 continues to the root level, at which it
stores its RedirServiceProvider record and finishes the upward walk stores its RedirServiceProvider record and finishes the upward walk
since the root level was reached. Peer 4 also does a downward walk since the root level was reached. Peer 4 also does a downward walk
starting from level 2. The downward walk stops at level 2 because starting from level 2. The downward walk stops at level 2 because
peer 4 is the only peer in the interval I(2,4). peer 4 is the only peer in the interval I(2,4).
7.2. Service Lookup
This subsection gives an example of peer 5 whose Node-ID is 5
performing a service lookup operation in the ReDiR tree shown in
Figure 2. This is the first service lookup peer 5 carries out and
thus the service lookup starts from the default starting level 2. As
the first action, peer 5 fetches the tree node corresponding to the
interval I(2,5) from the starting level. This interval maps to the
second tree node from the left at level 2 since that tree node is
responsible for the interval (third interval from left) to which
Node-ID 5 falls at level 2. Having fetched the tree node, peer 5
checks its contents. First, there is a successor, peer 7, present in
the tree node. Therefore, condition 1 of Section 4.5 is false and
there is no need to perform an upward walk. Second, Node-ID 5 is the
highest Node-ID in its interval, so condition 2 of Section 4.5 is
also false and there is no need to perform a downward walk. Thus,
the service lookup finishes at level 2 since Node-ID 7 is the closest
successor of peer 5.
Note that the service lookup procedure would be slightly different if
peer 5 used level 3 as the starting level. Peer 5 might use this
starting level for instance if it has already carried out service
lookups in the past and follows the heuristic in Section 4.2 to
select the starting level. In this case, peer 5's first action is to
fetch the tree node at level 3 that is responsible for I(3,5). Thus,
peer 5 fetches the third tree node from the left. Since this tree
node is empty, peer 5 decreases the current level by one to 2 and
thus continues up in the tree. The next action peer 5 performs is
identical to the single action in the previous example of fetching
the node associated with I(2,5) from level 2. Thus, the service
lookup finishes at level 2.
8. Overlay Configuration Document Extension 8. Overlay Configuration Document Extension
This document extends the RELOAD overlay configuration document by This document extends the RELOAD overlay configuration document by
adding a new element "branching-factor" inside the new "REDIR" kind adding a new element "branching-factor" inside the new "REDIR" kind
element: element:
redir:branching-factor: The branching factor of the ReDir tree. The redir:branching-factor: The branching factor of the ReDir tree. The
default value is 10. default value is 10.
This new element is formally defined as follows: This new element is formally defined as follows:
skipping to change at page 13, line 45 skipping to change at page 15, line 19
IANA SHALL create a "ReDiR Namespaces" Registry. Entries in this IANA SHALL create a "ReDiR Namespaces" Registry. Entries in this
registry are strings denoting ReDiR namespace values. The initial registry are strings denoting ReDiR namespace values. The initial
contents of this registry are: contents of this registry are:
+----------------+----------+ +----------------+----------+
| Namespace | RFC | | Namespace | RFC |
+----------------+----------+ +----------------+----------+
| turn-server | RFC-AAAA | | turn-server | RFC-AAAA |
+----------------+----------+ +----------------+----------+
| voice-mail | RFC-AAAA |
+----------------+----------+ The namespace 'turn-server' is used by nodes that wish to register as
providers of a TURN relay service in the RELOAD overlay and by nodes
that wish to discover providers of a TURN relay service from the
RELOAD overlay.
11. Acknowledgments 11. Acknowledgments
The authors would like to thank Marc Petit-Huguenin for his comments The authors would like to thank Marc Petit-Huguenin and Joscha
on the draft. Schneider for their comments on the draft.
12. References 12. References
12.1. Normative References 12.1. Normative References
[I-D.ietf-p2psip-base] [I-D.ietf-p2psip-base]
Jennings, C., Lowekamp, B., Rescorla, E., Baset, S., and Jennings, C., Lowekamp, B., Rescorla, E., Baset, S., and
H. Schulzrinne, "REsource LOcation And Discovery (RELOAD) H. Schulzrinne, "REsource LOcation And Discovery (RELOAD)
Base Protocol", draft-ietf-p2psip-base-22 (work in Base Protocol", draft-ietf-p2psip-base-24 (work in
progress), July 2012. progress), January 2013.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997. Requirement Levels", BCP 14, RFC 2119, March 1997.
12.2. Informative References 12.2. Informative References
[I-D.ietf-p2psip-concepts] [I-D.ietf-p2psip-concepts]
Bryan, D., Willis, D., Shim, E., Matthews, P., and S. Bryan, D., Willis, D., Shim, E., Matthews, P., and S.
Dawkins, "Concepts and Terminology for Peer to Peer SIP", Dawkins, "Concepts and Terminology for Peer to Peer SIP",
draft-ietf-p2psip-concepts-04 (work in progress), draft-ietf-p2psip-concepts-04 (work in progress),
 End of changes. 38 change blocks. 
148 lines changed or deleted 234 lines changed or added

This html diff was produced by rfcdiff 1.41. The latest version is available from http://tools.ietf.org/tools/rfcdiff/