draft-ietf-p2psip-service-discovery-11.txt   draft-ietf-p2psip-service-discovery-12.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: November 11, 2014 May 10, 2014 Expires: December 10, 2014 June 8, 2014
Service Discovery Usage for REsource LOcation And Discovery (RELOAD) Service Discovery Usage for REsource LOcation And Discovery (RELOAD)
draft-ietf-p2psip-service-discovery-11.txt draft-ietf-p2psip-service-discovery-12.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 a 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
skipping to change at page 1, line 34 skipping to change at page 1, line 34
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 November 11, 2014. This Internet-Draft will expire on December 10, 2014.
Copyright Notice Copyright Notice
Copyright (c) 2014 IETF Trust and the persons identified as the Copyright (c) 2014 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
skipping to change at page 2, line 26 skipping to change at page 2, line 26
4.6. Removing Registrations . . . . . . . . . . . . . . . . . 13 4.6. Removing Registrations . . . . . . . . . . . . . . . . . 13
5. Access Control Rules . . . . . . . . . . . . . . . . . . . . 13 5. Access Control Rules . . . . . . . . . . . . . . . . . . . . 13
6. REDIR Kind Definition . . . . . . . . . . . . . . . . . . . . 13 6. REDIR Kind Definition . . . . . . . . . . . . . . . . . . . . 13
7. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 14 7. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 14
7.1. Service Registration . . . . . . . . . . . . . . . . . . 14 7.1. Service Registration . . . . . . . . . . . . . . . . . . 14
7.2. Service Lookup . . . . . . . . . . . . . . . . . . . . . 16 7.2. Service Lookup . . . . . . . . . . . . . . . . . . . . . 16
8. Overlay Configuration Document Extension . . . . . . . . . . 17 8. Overlay Configuration Document Extension . . . . . . . . . . 17
9. Security Considerations . . . . . . . . . . . . . . . . . . . 17 9. Security Considerations . . . . . . . . . . . . . . . . . . . 17
10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 17 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 17
10.1. Access Control Policies . . . . . . . . . . . . . . . . 17 10.1. Access Control Policies . . . . . . . . . . . . . . . . 17
10.2. A New IETF XML Registry . . . . . . . . . . . . . . . . 17 10.2. A New IETF XML Registry . . . . . . . . . . . . . . . . 18
10.3. Data Kind-ID . . . . . . . . . . . . . . . . . . . . . . 18 10.3. Data Kind-ID . . . . . . . . . . . . . . . . . . . . . . 18
10.4. ReDiR Namespaces . . . . . . . . . . . . . . . . . . . . 18 10.4. ReDiR Namespaces . . . . . . . . . . . . . . . . . . . . 18
11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 18 11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 19
12. References . . . . . . . . . . . . . . . . . . . . . . . . . 19 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 19
12.1. Normative References . . . . . . . . . . . . . . . . . . 19 12.1. Normative References . . . . . . . . . . . . . . . . . . 19
12.2. Informative References . . . . . . . . . . . . . . . . . 19 12.2. Informative References . . . . . . . . . . . . . . . . . 19
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 19 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 19
1. Introduction 1. Introduction
REsource LOcation And Discovery (RELOAD) [RFC6940] is a peer-to-peer REsource LOcation And Discovery (RELOAD) [RFC6940] is a peer-to-peer
signaling protocol that can be used to maintain an overlay network, signaling protocol that can be used to maintain an overlay network,
and to store data in and retrieve data from the overlay. Although and to store data in and retrieve data from the overlay. Although
skipping to change at page 3, line 18 skipping to change at page 3, line 18
finding peers that are providing that service from the Overlay finding peers that are providing that service from the Overlay
Instance. Instance.
A naive way to perform service discovery is to store the Node-IDs of A naive way to perform service discovery is to store the Node-IDs of
all nodes providing a particular service under a well-known key k. all nodes providing a particular service under a well-known key k.
The limitation of this approach is that it scales linearly with the The limitation of this approach is that it scales linearly with the
number of nodes that provide the service. The problem is two-fold: number of nodes that provide the service. The problem is two-fold:
the node n that is responsible for service s identified by key k may the node n that is responsible for service s identified by key k may
end up storing a large number of Node-IDs and most importantly, may end up storing a large number of Node-IDs and most importantly, may
also become overloaded since all service lookup requests for service also become overloaded since all service lookup requests for service
s will need to be answered by node n. An efficient service discovery s will need to be answered by node n. An efficient service discovery
mechanism does not overload the nodes storing pointers to service mechanism does not overload the nodes storing pointers to service
providers. In addition, the mechanism must ensure that the load of providers. In addition, the mechanism must ensure that the load of
providing a given service is distributed evenly among the nodes providing a given service is distributed evenly among the nodes
providing the service. providing the service.
ReDiR implements service discovery by building a tree structure of ReDiR implements service discovery by building a tree structure of
the service providers that provide a particular service. The tree the service providers that provide a particular service. The tree
structure is stored into the RELOAD Overlay Instance using RELOAD structure is stored into the RELOAD Overlay Instance using RELOAD
Store and Fetch requests. Each service provided in the Overlay Store and Fetch requests. Each service provided in the Overlay
Instance has its own tree. The nodes in a ReDiR tree contain Instance has its own tree. The nodes in a ReDiR tree contain
skipping to change at page 4, line 11 skipping to change at page 4, line 11
distributed systems that provide a lookup service similar to a distributed systems that provide a lookup service similar to a
regular hash table. Given a key, any peer participating in the regular hash table. Given a key, any peer participating in the
system can retrieve the value associated with that key. The system can retrieve the value associated with that key. The
responsibility for maintaining the mapping from keys to values is responsibility for maintaining the mapping from keys to values is
distributed among the peers. distributed among the peers.
H(x): Refers to a hash function (e.g., SHA-1) calculated over the H(x): Refers to a hash function (e.g., SHA-1) calculated over the
value x. value x.
I(lvl,k): An interval at level lvl in the ReDiR tree that encloses I(lvl,k): An interval at level lvl in the ReDiR tree that encloses
key k. As an example, I(5,10) refers to an interval at level 5 in key k. As an example, I(5,10) refers to an interval at level 5 in
the ReDiR tree within whose range key 10 falls. the ReDiR tree within whose range key 10 falls.
n.id: Refers to the RELOAD Node-ID of node n. n.id: Refers to the RELOAD 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. Examples of potential provided in the RELOAD Overlay Instance. Examples of potential
namespaces include "voice-mail" and "turn-relay". The namespace namespaces include "voice-mail" and "turn-server". The namespace
is an UTF-8 text string. is an UTF-8 text string.
numBitsInNodeId: Refers to the number of bits in a RELOAD Node-ID. numBitsInNodeId: Refers to the number of bits in a RELOAD Node-ID.
This value is used in the equations for calculating the ranges of This value is used in the equations for calculating the ranges of
intervals that ReDiR tree nodes are responsible for. intervals that ReDiR tree nodes are responsible for.
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. Each tree node in Instance using RELOAD Store and Fetch requests. Each tree node in
the ReDiR tree belongs to some level in the tree. The root node the ReDiR tree belongs to some level in the tree. The root node
of the ReDiR tree is located at level 0 of the ReDiR tree. The of the ReDiR tree is located at level 0 of the ReDiR tree. The
child nodes of the root node are located at level 1. The children child nodes of the root node are located at level 1. The children
of the tree nodes at level 1 are located at level 2, and so forth. of the tree nodes at level 1 are located at level 2, and so forth.
The ReDiR tree has a branching factor b. At every level lvl in the The ReDiR tree has a branching factor b. At every level lvl in
ReDiR tree, there is room for a maximum of b^lvl tree nodes. Each the ReDiR tree, there is room for a maximum of b^lvl tree nodes.
tree node in the ReDiR tree is uniquely identified by a pair Each tree node in the ReDiR tree is uniquely identified by a pair
(lvl,j), where lvl is a level in the ReDiR tree and j is the (lvl,j), where lvl is a level in the ReDiR tree and j is the
position of the tree node (from the left) at that level. position of the tree node (from the left) at that level.
Successor: The successor of identifier k in namespace ns is the node Successor: The successor of identifier k in namespace ns is the node
belonging to the namespace ns whose identifier most immediately belonging to the namespace ns whose identifier most immediately
follows the identifier k. follows the identifier 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
skipping to change at page 9, line 30 skipping to change at page 9, line 30
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 set to 2. In subsequent registrations, RECOMMENDED that Lstart is set to 2. This recommendation is based on
Lstart MAY, as an optimization, be set to the lowest level at which a the findings in [Redir], which indicate that this starting level
results in good performance. In subsequent registrations, Lstart
MAY, as an optimization, be set to the lowest level at which a
registration operation has last completed. registration operation has last completed.
In the case of subsequent service lookups, nodes MAY, as an In the case of subsequent service lookups, nodes MAY, as an
optimization, record the levels at which the last 16 service lookups optimization, record the levels at which the last 16 service lookups
completed and take Lstart to be the mode 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:
skipping to change at page 11, line 39 skipping to change at page 11, line 39
operation described in Section 4.3. Service lookups start from a operation described in Section 4.3. Service lookups start from a
given starting level level=Lstart in the ReDiR tree (see Section 4.2 given starting level level=Lstart in the ReDiR tree (see Section 4.2
for the details on selecting the starting level). At each step, a for the details on selecting the starting level). At each step, a
node n wishing to discover a service provider MUST fetch the tree node n wishing to discover a service provider MUST fetch the tree
node responsible for the interval I(level,n.id) that encloses the node responsible for the interval I(level,n.id) that encloses the
search key n.id at the current level using a RELOAD Fetch request. search key n.id at the current level using a RELOAD Fetch request.
Having fetched the tree node, node n MUST determine the next action Having fetched the tree node, node n MUST determine the next action
to carry out as follows: to carry out as follows:
1. If there is no successor of node n present in the just fetched 1. If there is no successor of node n present in the just fetched
ReDiR tree node (note: within the entire tree and not only within ReDiR tree node (note: within the entire tree node and not only
the current interval) responsible for I(level,n.id), then the within the current interval) responsible for I(level,n.id), then
successor of node n must be present in a larger segment of the the successor of node n must be present in a larger segment of
identifier space (i.e., further up in the ReDiR tree where each the identifier space (i.e., further up in the ReDiR tree where
interval and tree node covers a larger range of the identifier each interval and tree node covers a larger range of the
space). Therefore, node n MUST reduce the current level by one identifier space). Therefore, node n MUST reduce the current
to level=level-1 and carry out a new Fetch operation for the tree level by one to level=level-1 and carry out a new Fetch operation
node responsible for n.id at that level. The fetched tree node for the tree node responsible for n.id at that level. The
is then analyzed and the next action determined by checking fetched tree node is then analyzed and the next action determined
conditions 1-3. by checking conditions 1-3.
2. If n.id is neither the lowest nor the highest Node-ID within the 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 interval (note: within the interval, not within the entire tree
node) I(level,n.id), n MUST next check the tree node responsible 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 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 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 Fetch operation at that level. The fetched tree node is then
analyzed and the next action determined by checking conditions analyzed and the next action determined by checking conditions
1-3. 1-3.
skipping to change at page 12, line 24 skipping to change at page 12, line 24
closest successor of n.id in the ReDiR tree. closest successor of n.id in the ReDiR tree.
Note that above, when we refer to 'the tree node responsible for Note that above, when we refer to 'the tree node responsible for
interval I(l,k)', we mean the entire tree node (that is, all the interval 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 intervals within the tree node) responsible for interval I(l,k). In
contrast, 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 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 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 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 than identifier k. In this case, the upward walk of the service
lookup will reach the root of the tree without encountering a lookup will reach the root of the tree without encountering a
successor. An appropriate strategy in this case is to pick one of successor. An appropriate strategy in this case is to pick one of
the RedirServiceProvider entries stored in the dictionary of the root the RedirServiceProvider entries stored in the dictionary of the root
node at random. node at random.
Since RedirServiceProvider records are expiring and registrations are Since RedirServiceProvider records are expiring and registrations are
being refreshed periodically, there can be certain rare situations in being refreshed periodically, there can be certain rare situations in
which a service lookup may fail even if there is a valid successor which a service lookup may fail even if there is a valid successor
present in the ReDiR tree. An example is a case in which a ReDiR present in the ReDiR tree. An example is a case in which a ReDiR
tree node is fetched just after a RedirServiceProvider entry of the tree node is fetched just after a RedirServiceProvider entry of the
skipping to change at page 13, line 15 skipping to change at page 13, line 15
service provider. service provider.
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 [RFC6940]. exists=False values in their place, as described in [RFC6940].
5. Access Control Rules 5. Access Control Rules
As specified in RELOAD base [RFC6940], every kind which is storable As specified in RELOAD base [RFC6940], every Kind which is storable
in an overlay must be associated with an access control policy. This in an overlay must be associated with an access control policy. This
policy defines whether a request from a given node to operate on a policy defines whether a request from a given node to operate on a
given value should succeed or fail. Usages can define any access given value should succeed or fail. Usages can define any access
control rules they choose, including publicly writable values. control rules they choose, including publicly writable values.
ReDiR requires an access control policy that allows multiple nodes in ReDiR requires an access control policy that allows multiple nodes in
the overlay read and write access to the ReDiR tree nodes stored in the overlay read and write access to the ReDiR tree nodes stored in
the overlay. Therefore, none of the access control policies the overlay. Therefore, none of the access control policies
specified in RELOAD base [RFC6940] is sufficient. specified in RELOAD base [RFC6940] is sufficient.
skipping to change at page 13, line 41 skipping to change at page 13, line 41
of the intervals associated with the tree node (the number of of the intervals associated with the tree node (the number of
intervals each tree node has is determined by the branching-factor intervals each tree node has is determined by the branching-factor
parameter). Finally, provided that exists=TRUE, parameter). Finally, provided that exists=TRUE,
H(namespace,level,node), where namespace, level, and node are taken H(namespace,level,node), where namespace, level, and node are taken
from the RedirServiceProvider structure being stored, MUST be equal from the RedirServiceProvider structure being stored, MUST be equal
to the Resource-ID for the resource. The NODE-ID-MATCH policy may to the Resource-ID for the resource. The NODE-ID-MATCH policy may
only be used with dictionary types. only be used with dictionary types.
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 an opaque UTF-8 encoded string node number. Namespace is an opaque UTF-8 encoded string
identifying a service, such as "turn-server". Level is an integer identifying a service, such as "turn-server". Level is an integer
skipping to change at page 14, line 20 skipping to change at page 14, line 20
stored is a RedirServiceProvider structure that was defined in stored is a RedirServiceProvider structure that was defined in
Section 4.1. 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. Examples 7. Examples
7.1. Service Registration 7.1. Service Registration
Figure 4 shows an example of a ReDiR tree containing information Figure 4 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; Figure 4 shows the state of the tree at the point when all is empty; Figure 4 shows the state of the tree at the point when all
skipping to change at page 17, line 28 skipping to change at page 17, line 28
parameter &= element redir:branching-factor { xsd:unsignedInt }? parameter &= element redir:branching-factor { xsd:unsignedInt }?
The 'redir' namespace is added into the <mandatory-extension> element The 'redir' namespace is added into the <mandatory-extension> element
in the overlay configuration file. in the overlay configuration file.
9. Security Considerations 9. Security Considerations
There are no new security considerations introduced in this document. There are no new security considerations introduced in this document.
The security considerations of RELOAD [RFC6940] apply. The security considerations of RELOAD [RFC6940] apply.
It should be noted that this document defines a new access control
policy called NODE-ID-MATCH (see Section 5) whose purpose is to
control which nodes in the overlay are allowed read and write access
to the ReDiR tree nodes.
10. IANA Considerations 10. IANA Considerations
10.1. Access Control Policies 10.1. Access Control Policies
This document introduces one additional access control policy to the This document introduces one additional access control policy to the
"RELOAD Access Control Policy" Registry: "RELOAD Access Control Policy" Registry:
NODE-ID-MATCH NODE-ID-MATCH
This access control policy was described in Section 5. This access control policy was described in Section 5.
skipping to change at page 18, line 24 skipping to change at page 18, line 34
| REDIR | 104 | RFC-AAAA | | REDIR | 104 | RFC-AAAA |
+--------------+------------+----------+ +--------------+------------+----------+
This Kind-ID was defined in Section 6. This Kind-ID was defined in Section 6.
Note to RFC Editor: please replace AAAA with the RFC number for this Note to RFC Editor: please replace AAAA with the RFC number for this
specification. specification.
10.4. ReDiR Namespaces 10.4. ReDiR Namespaces
IANA SHALL create a "ReDiR Namespaces" Registry. Entries in this IANA is requested to create a "ReDiR Namespaces" Registry. Entries
registry are strings denoting ReDiR namespace values. The initial in this registry are strings denoting ReDiR namespace values. The
contents of this registry are: initial contents of this registry are:
+----------------+----------+ +----------------+----------+
| Namespace | RFC | | Namespace | RFC |
+----------------+----------+ +----------------+----------+
| turn-server | RFC-AAAA | | turn-server | RFC-AAAA |
+----------------+----------+ +----------------+----------+
The namespace 'turn-server' is used by nodes that wish to register as 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 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 that wish to discover providers of a TURN relay service from the
 End of changes. 17 change blocks. 
30 lines changed or deleted 37 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/