draft-ietf-p2psip-service-discovery-15.txt   rfc7374.txt 
P2PSIP Working Group J. Maenpaa Internet Engineering Task Force (IETF) J. Maenpaa
Internet-Draft G. Camarillo Request for Comments: 7374 G. Camarillo
Intended status: Standards Track Ericsson Category: Standards Track Ericsson
Expires: February 14, 2015 August 13, 2014 ISSN: 2070-1721 October 2014
Service Discovery Usage for REsource LOcation And Discovery (RELOAD) Service Discovery Usage for REsource LOcation And Discovery (RELOAD)
draft-ietf-p2psip-service-discovery-15.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 (RFC
document defines how the Recursive Distributed Rendezvous (ReDiR) 6940). This document defines how the Recursive Distributed
service discovery mechanism used in OpenDHT can be applied to RELOAD Rendezvous (ReDiR) service discovery mechanism can be applied to
overlays to provide a generic service discovery mechanism. RELOAD overlays to provide a generic service discovery mechanism.
Status of This Memo Status of This Memo
This Internet-Draft is submitted in full conformance with the This is an Internet Standards Track document.
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months This document is a product of the Internet Engineering Task Force
and may be updated, replaced, or obsoleted by other documents at any (IETF). It represents the consensus of the IETF community. It has
time. It is inappropriate to use Internet-Drafts as reference received public review and has been approved for publication by the
material or to cite them other than as "work in progress." Internet Engineering Steering Group (IESG). Further information on
Internet Standards is available in Section 2 of RFC 5741.
This Internet-Draft will expire on February 14, 2015. Information about the current status of this document, any errata,
and how to provide feedback on it may be obtained at
http://www.rfc-editor.org/info/rfc7374.
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
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 . . . . . . . . . . . . . . . . . . . . . . . . 2 1. Introduction ....................................................3
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology .....................................................4
3. Introduction to ReDiR . . . . . . . . . . . . . . . . . . . . 5 3. Introduction to ReDiR ...........................................5
4. Using ReDiR in a RELOAD Overlay Instance . . . . . . . . . . 8 4. Using ReDiR in a RELOAD Overlay Instance ........................8
4.1. Data Structure . . . . . . . . . . . . . . . . . . . . . 8 4.1. Data Structure .............................................8
4.2. Selecting the Starting Level . . . . . . . . . . . . . . 10 4.2. Selecting the Starting Level ...............................9
4.3. Service Provider Registration . . . . . . . . . . . . . . 10 4.3. Service Provider Registration ..............................9
4.4. Refreshing Registrations . . . . . . . . . . . . . . . . 11 4.4. Refreshing Registrations ..................................10
4.5. Service Lookups . . . . . . . . . . . . . . . . . . . . . 11 4.5. Service Lookups ...........................................11
4.6. Removing Registrations . . . . . . . . . . . . . . . . . 13 4.6. Removing Registrations ....................................13
5. Access Control Rules . . . . . . . . . . . . . . . . . . . . 14 5. Access Control Rules ...........................................13
6. REDIR Kind Definition . . . . . . . . . . . . . . . . . . . . 14 6. REDIR Kind Definition ..........................................13
7. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 15 7. Examples .......................................................14
7.1. Service Registration . . . . . . . . . . . . . . . . . . 15 7.1. Service Registration ......................................14
7.2. Service Lookup . . . . . . . . . . . . . . . . . . . . . 17 7.2. Service Lookup ............................................16
8. Overlay Configuration Document Extension . . . . . . . . . . 17 8. Overlay Configuration Document Extension .......................16
9. Security Considerations . . . . . . . . . . . . . . . . . . . 18 9. Security Considerations ........................................17
10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 18 10. IANA Considerations ...........................................17
10.1. Access Control Policies . . . . . . . . . . . . . . . . 18 10.1. Access Control Policies ..................................17
10.2. A New IETF XML Registry . . . . . . . . . . . . . . . . 18 10.2. A New IETF XML Registry ..................................17
10.3. Data Kind-ID . . . . . . . . . . . . . . . . . . . . . . 19 10.3. Data Kind-ID .............................................18
10.4. RELOAD Services Registry . . . . . . . . . . . . . . . . 19 10.4. RELOAD Services Registry .................................18
11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 20 11. References ....................................................19
12. References . . . . . . . . . . . . . . . . . . . . . . . . . 20 11.1. Normative References .....................................19
12.1. Normative References . . . . . . . . . . . . . . . . . . 20 11.2. Informative Reference ....................................19
12.2. Informative References . . . . . . . . . . . . . . . . . 20 Acknowledgments ...................................................19
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 20 Authors' Addresses ................................................20
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
RELOAD defines a Traversal Using Relays around Network Address RELOAD defines a service discovery mechanism specific to Traversal
Translation (TURN) specific service discovery mechanism, it does not Using Relays around Network Address Translation (TURN), it does not
define a generic service discovery mechanism as a part of the base define a generic service discovery mechanism as a part of the base
protocol. This document defines how the Recursive Distributed protocol. This document defines how the Recursive Distributed
Rendezvous (ReDiR) service discovery mechanism [Redir] used in Rendezvous (ReDiR) service discovery mechanism specified in [Redir]
OpenDHT can be applied to RELOAD overlays. 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,
and a transcoding service. Typically, only a small subset of the and a transcoding service. Typically, only a small subset of the
peers participating in the system are providers of a given service. peers participating in the system are providers of a given service.
A peer that wishes to use a particular service faces the problem of A peer that wishes to use a particular service faces the problem of
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
providing a given service is distributed evenly among the nodes associated with providing a given service is distributed evenly among
providing the service. the nodes providing the service.
It should be noted that a simple service discovery mechanism such as It should be noted that a simple service discovery mechanism such as
the one mentioned in the previous paragraph might be an appropriate the one mentioned in the previous paragraph might be an appropriate
solution in a very small overlay network consisting of perhaps tens solution in a very small overlay network consisting of perhaps tens
of nodes. The ReDiR-based service discovery mechanism described in of nodes. The ReDiR-based service discovery mechanism described in
this document is suitable for use even in overlay networks where the this document is suitable for use even in overlay networks where the
number of end-users that may make service discovery requests can be number of end users that may make service discovery requests can be
very high (e.g., tens of thousands of nodes or even higher), and very high (e.g., tens of thousands of nodes or even higher) and where
where a large fraction of the peers (e.g., on the order of one out of a large fraction of the peers (e.g., on the order of one out of ten
ten or more) can offer the service. or more) can offer 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
pointers to service providers. During service discovery, a peer pointers to service providers. During service discovery, a peer
wishing to use a given service fetches ReDiR tree nodes one-by-one wishing to use a given service fetches ReDiR tree nodes one-by-one
from the RELOAD Overlay Instance until it finds a service provider from the RELOAD Overlay Instance until it finds a service provider
responsible for its Node-ID. It has been proved that ReDiR can find responsible for its Node-ID. It has been proved that ReDiR can find
skipping to change at page 4, line 27 skipping to change at page 4, line 45
strings and integers. The network byte order is used. strings and integers. The network byte order is used.
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-server". The namespace namespaces include 'voice-mail' and 'turn-server'. The namespace
is an UTF-8 [RFC3629] text string. is a UTF-8-encoded [RFC3629] 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
skipping to change at page 5, line 19 skipping to change at page 5, line 25
(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
functionality from the RELOAD base protocol. This is possible since functionality from the RELOAD base protocol [RFC6940]. This is
ReDiR interacts with the RELOAD Overlay Instance by simply storing possible since ReDiR interacts with the RELOAD Overlay Instance by
and fetching data, that is, using RELOAD Store and Fetch requests. simply storing and fetching data, that is, using RELOAD Store and
ReDiR creates a tree structure of the service providers of a Fetch requests. ReDiR creates a tree structure of the service
particular service and stores it into the RELOAD Overlay Instance providers of a particular service and stores it into the RELOAD
using the Store and Fetch requests. ReDiR service lookups require a Overlay Instance using the Store and Fetch requests. ReDiR service
logarithmic number of Fetch operations. Further, if information from lookups require a logarithmic number of Fetch operations. Further,
past service lookups is used to determine the optimal level in the if information from past service lookups is used to determine the
ReDiR tree from which to start new service lookups, an average optimal level in the ReDiR tree from which to start new service
service lookup can typically finish after a constant number of Fetch lookups, an average service lookup can typically finish after a
operations assuming that Node-IDs are distributed uniformly at constant number of Fetch operations, assuming that Node-IDs are
random. 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
identifier, called the namespace. All service providers of a given identifier, called the namespace. All service providers of a given
service store their information under the namespace of that service. service store their information under the namespace of that service.
Peers wishing to use a service perform lookups within the namespace Peers wishing to use a service perform lookups within the namespace
of the service. The result of a ReDiR lookup for an identifier k in of the service. The result of a ReDiR lookup for an identifier k in
namespace ns is a RedirServiceProvider structure (see Section 4.1) of namespace ns is a RedirServiceProvider structure (see Section 4.1) of
a service provider that belongs to ns and whose Node-ID is the a service provider that belongs to ns and whose Node-ID is the
closest successor of identifier k in the namespace. closest successor of identifier k in the namespace.
Each tree node in the ReDiR tree contains a dictionary of Each tree node in the ReDiR tree contains a dictionary of
RedirServiceProvider entries of peers providing a particular service. RedirServiceProvider entries of peers providing a particular service.
Each tree node in the ReDiR tree also belongs to some level in the Each tree node in the ReDiR tree also belongs to some level in the
tree. The root node of the ReDiR tree is located at level 0. The tree. The root node of the ReDiR tree is located at level 0. The
child nodes of the root node are located at level 1 of the ReDiR child nodes of the root node are located at level 1 of the ReDiR
tree. The children of the tree nodes at level 1 are located at level tree. The children of the tree nodes at level 1 are located at
2, and so forth. The ReDiR tree has a branching factor, whose value level 2, and so forth. The ReDiR tree has a branching factor, whose
is determined by a new element in the RELOAD overlay configuration value is determined by a new element in the RELOAD overlay
document, called branching-factor. At every level lvl in the ReDiR configuration document, called branching-factor. The RELOAD overlay
tree, there is room for a maximum of branching-factor^lvl tree nodes. configuration document is defined in the RELOAD base protocol
As an example, in a tree whose branching-factor is 2, the second [RFC6940]. At every level lvl in the ReDiR tree, there is room for a
level can contain up to 4 tree nodes (note that a given level may maximum of branching-factor^lvl tree nodes. As an example, in a tree
contain less than the maximum number of tree nodes since empty tree whose branching-factor is 2, the second level can contain up to four
nodes are not stored). Each tree node in the ReDiR tree is uniquely tree nodes (note that a given level may contain less than the maximum
identified by a pair (lvl,j), where lvl is a level in the ReDiR tree number of tree nodes since empty tree nodes are not stored). Each
and j is the position of the tree node (from the left) at that level. tree node in the ReDiR tree is uniquely identified by a pair (lvl,j),
As an example, the pair (2,3) identifies the 3rd tree node from the where lvl is a level in the ReDiR tree and j is the position of the
left at level 2. tree node (from the left) at that level. As an example, the pair
(2,3) identifies the third tree node from the left at level 2.
The ReDiR tree is stored into the RELOAD Overlay Instance tree node The ReDiR tree is stored into the RELOAD Overlay Instance tree node
by tree node, by storing the values of tree node (level,j) under a by tree node, by storing the values of tree node (level,j) under a
key created by taking a hash over the concatenation of the namespace, key created by taking a hash over the concatenation of the namespace,
level, and j, that is, as H(namespace,level,j). As an example, the level, and j, that is, as H(namespace,level,j). As an example, the
root of the tree for a voice mail service is stored at H("voice- 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 mail",0,0). Each node (level,j) in the ReDiR tree contains b
intervals of the DHT's identifier space as follows: intervals of the DHT's identifier space as follows:
[2^numBitsInNodeID*b^(-level)*(j+(b'/b)), [2^numBitsInNodeId*b^(-level)*(j+(b'/b)),
2^numBitsInNodeID*b^(-level)*(j+((b'+1)/b))), for 0<=b'<b, 2^numBitsInNodeId*b^(-level)*(j+((b'+1)/b))), for 0<=b'<b,
where b is the branching-factor and b' refers to the number of an where b is the branching-factor and b' refers to the number of an
interval within the ReDiR tree node j. interval within the ReDiR tree node j.
Figure 1 shows an example of a ReDiR tree whose branching factor is Figure 1 shows an example of a ReDiR tree whose branching factor
2. In the figure, the size of the identifier space of the overlay is is 2. In the figure, the size of the identifier space of the overlay
16. Each tree node in the ReDiR tree is shown as two horizontal is 16. Each tree node in the ReDiR tree is shown as two horizontal
lines separated by a vertical bar ('|') in the middle. The lines separated by a vertical bar ('|') in the middle. The
horizontal lines represent the two intervals each node is responsible horizontal lines represent the two intervals each node is responsible
for. At level 0, there is only one node, (0,0) responsible for two for. At level 0, there is only one node, (0,0), responsible for two
intervals that together cover the entire identifier space of the intervals that together cover the entire identifier space of the
RELOAD Overlay Instance. At level 1, there are two nodes, (1,0) and RELOAD Overlay Instance. At level 1, there are two nodes, (1,0) and
(1,1), each of which is responsible for half of the identifier space (1,1), each of which is responsible for half of the identifier space
of the RELOAD Overlay Instance. At level 2, there are four nodes. of the RELOAD Overlay Instance. At level 2, there are four nodes.
Each of them owns one fourth of the identifier space. At level 3, Each of them owns one fourth of the identifier space. At level 3,
there are eight nodes each of which is responsible for one eight of there are eight nodes, each of which is responsible for one eighth of
the identifier space. 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
Figure 2 illustrates how tree nodes are numbered in the ReDiR tree at Figure 2 illustrates how tree nodes are numbered in the ReDiR tree at
levels 0-2. levels 0-2.
Level 0 ________________(0,0)________________ Level 0 ________________(0,0)________________
| | | |
Level 1 ______(1,0)______ ______(1,1)______ Level 1 ______(1,0)______ ______(1,1)______
| | | | | | | |
Level 2 _(2,0)_ _(2,1)_ _(2,2)_ _(2,3)_ Level 2 _(2,0)_ _(2,1)_ _(2,2)_ _(2,3)_
| | | | | | | | | | | | | | | |
Level 3 _|_ _|_ _|_ _|_ _|_ _|_ _|_ _|_ Level 3 _|_ _|_ _|_ _|_ _|_ _|_ _|_ _|_
Figure 2: ReDiR tree nodes Figure 2: ReDiR Tree Nodes
Figure 3 illustrates how intervals are assigned to tree nodes in the Figure 3 illustrates how intervals are assigned to tree nodes in the
ReDiR tree at levels 0 and 1. As an example, the single tree node ReDiR tree at levels 0 and 1. As an example, the single tree node
(0,0) at level 0 is divided into two intervals, each of which covers (0,0) at level 0 is divided into two intervals, each of which covers
half of the identifier space of the overlay. These two intervals are half of the identifier space of the overlay. These two intervals are
[0,7] and [8,15]. [0,7] and [8,15].
Level 0 ______[0,7]_______|_______[8,15]_____ Level 0 ______[0,7]_______|_______[8,15]_____
| | | |
Level 1 _[0,3]__|__[4,7]_ _[8,11]_|_[12,15] Level 1 _[0,3]__|__[4,7]_ _[8,11]_|_[12,15]
| | | | | | | |
Level 2 ___|___ ___|___ ___|___ ___|___ Level 2 ___|___ ___|___ ___|___ ___|___
| | | | | | | | | | | | | | | |
Level 3 _|_ _|_ _|_ _|_ _|_ _|_ _|_ _|_ Level 3 _|_ _|_ _|_ _|_ _|_ _|_ _|_ _|_
Figure 3: Intervals in ReDiR tree Figure 3: Intervals in ReDiR Tree
Note that all of the examples above are simplified. In a real ReDiR Note that all of the examples above are simplified. In a real ReDiR
tree, the default ReDiR branching factor is 10, meaning that each tree, the default ReDiR branching factor is 10, meaning that each
tree node is split into 10 intervals and that each tree node has 10 tree node is split into 10 intervals and that each tree node has 10
children. In such a tree, level 1 contains 10 nodes and 100 children. In such a tree, level 1 contains 10 nodes and 100
intervals. Level 2 contains 100 nodes and 1000 intervals, level 3 intervals. Level 2 contains 100 nodes and 1000 intervals, level 3
1000 nodes and 10000 intervals, etc. Further, the size of the 1000 nodes and 10000 intervals, etc. Further, the size of the
identifier space of a real RELOAD Overlay Instance is at the minimum identifier space of a real RELOAD Overlay Instance is at the minimum
2^128. 2^128.
4. Using ReDiR in a RELOAD Overlay Instance 4. Using ReDiR in a RELOAD Overlay Instance
4.1. Data Structure 4.1. Data Structure
ReDiR tree nodes are stored using the dictionary data model defined ReDiR tree nodes are stored using the dictionary data model defined
in RELOAD base [RFC6940]. The data stored is a RedirServiceProvider in the RELOAD base protocol [RFC6940]. The data stored is a
Resource Record: RedirServiceProvider Resource Record:
enum { none(0), (255) } enum { none(0), (255) }
RedirServiceProviderExtType; RedirServiceProviderExtType;
struct { struct {
RedirServiceProviderExtType type; RedirServiceProviderExtType type;
Destination destination_list<0..2^16-1>; Destination destination_list<0..2^16-1>;
opaque namespace<0..2^16-1>; opaque namespace<0..2^16-1>;
uint16 level; uint16 level;
uint16 node; uint16 node;
uint16 length; uint16 length;
select (type) { select (type) {
/* This type may be extended */ /* This type may be extended */
} extension; } extension;
} 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.
destination_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 [RFC6940]. as defined in the RELOAD base protocol [RFC6940].
namespace namespace
An opaque UTF-8 encoded 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.
skipping to change at page 10, line 4 skipping to change at page 9, line 15
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.
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, information specific to the
specific information. service or service provider.
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. This recommendation is based on RECOMMENDED that Lstart is set to 2. This recommendation is based on
the findings in [Redir], which indicate that this starting level the findings in [Redir], which indicate that this starting level
results in good performance. In subsequent registrations, Lstart results in good performance. In subsequent registrations, Lstart
MAY, as an optimization, be set to the lowest level at which a MAY, as an optimization, be set to the lowest level at which a
skipping to change at page 10, line 49 skipping to change at page 10, line 15
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 responsible for I(level,n.id). Note that node n always node responsible for I(level,n.id). Note that node n always
stores its RedirServiceProvider entry, regardless of the contents stores its RedirServiceProvider entry, regardless of the contents
of the dictionary. of the dictionary.
4. If node n's Node-ID (n.id) is the lowest or highest Node-ID 4. If node n's Node-ID (n.id) is the lowest or highest Node-ID
stored in the tree node responsible for I(Lstart,n.id), node n stored in the tree node responsible for I(Lstart,n.id), node n
MUST reduce the current level by one (i.e., set level=level-1) MUST reduce the current level by one (i.e., set level=level-1)
and continue up the ReDiR tree towards the root level (level 0), and continue up the ReDiR tree towards the root level (level 0),
repeating the steps 2 and 3 above. Node n MUST continue in this repeating steps 2 and 3 above. Node n MUST continue in this way
way until it reaches either the root of the tree or a level at until it reaches either the root of the tree or a level at which
which n.id is not the lowest or highest Node-ID in the interval n.id is not the lowest or highest Node-ID in the interval
I(level,n.id). I(level,n.id).
5. Node n MUST also perform a downward walk in the ReDiR tree, 5. Node n MUST also perform a downward walk in the ReDiR tree,
during which it goes through the tree nodes responsible for during which it goes through the tree nodes responsible for
intervals I(Lstart,n.id), I(Lstart+1,n.id), I(Lstart+2,n.id), intervals I(Lstart,n.id), I(Lstart+1,n.id), I(Lstart+2,n.id),
etc. At each step, node n MUST fetch the responsible tree node, etc. At each step, node n MUST fetch the responsible tree node
and store its RedirServiceProvider record in that tree node if and store its RedirServiceProvider record in that tree node if
n.id is the lowest or highest Node-ID in its interval. Node n 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 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). which it is the only service provider in its interval I(l,n.id).
Note that above, when we refer to 'the tree node responsible for 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.
Deciding an appropriate lifetime for the RedirServiceProvider Deciding an appropriate lifetime for the RedirServiceProvider
Resource Records is up to each service provider. However, a default Resource Records is up to each service provider. However, a default
value of 10 minutes is RECOMMENDED as this is a good tradeoff between value of 10 minutes is RECOMMENDED as this is a good trade-off
keeping the amount of ReDiR traffic in the overlay at a reasonable between keeping the amount of ReDiR traffic in the overlay at a
level and ensuring that stale information is removed quickly enough. reasonable level and ensuring that stale information is removed
Every service provider MUST repeat the entire registration process quickly enough. Every service provider MUST repeat the entire
periodically until it leaves the RELOAD Overlay Instance. The registration process periodically until it leaves the RELOAD Overlay
service provider SHOULD initiate each refresh process slightly Instance. The service provider SHOULD initiate each refresh process
earlier (e.g., when 90% of the refresh interval has passed) than the slightly earlier (e.g., when 90% of the refresh interval has passed)
expiry time of the Resource Record. than the expiry time of the Resource Record.
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 for identifier k in namespace ns is The purpose of a service lookup for identifier k in namespace ns is
to find the node that is a part of ns and whose identifier most to find the node that is a part of ns and whose identifier most
skipping to change at page 12, line 17 skipping to change at page 11, line 29
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:
Condition 1 Condition 1
If there is no successor of node n present in the just fetched If there is no successor of node n present in the just-fetched
ReDiR tree node (note: within the entire tree node and not only ReDiR tree node (note: within the entire tree node and not only
within the current interval) responsible for I(level,n.id), then within the current interval) responsible for I(level,n.id), then
the 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 the
identifier space (i.e., further up in the ReDiR tree where each identifier space (i.e., further up in the ReDiR tree where each
interval and tree node covers a larger range of the identifier interval and tree node covers a larger range of the identifier
space). Therefore, node n MUST reduce the current level by one to space). Therefore, node n MUST reduce the current level by one to
level=level-1 and carry out a new Fetch operation for the tree level=level-1 and carry out a new Fetch operation for the tree
node responsible for n.id at that level. The fetched tree node is node responsible for n.id at that level. The fetched tree node is
then analyzed and the next action determined by checking then analyzed and the next action determined by checking
Conditions 1-3. Conditions 1-3.
Condition 2 Condition 2
If n.id is neither the lowest nor the highest Node-ID within the 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 the conditions analyzed and the next action determined by checking the conditions
listed here starting at Condition 1. listed here, starting at Condition 1.
Condition 3 Condition 3
If neither of the conditions above holds, meaning that there is a 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 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 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 service lookup has finished successfully, and s must be the
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
skipping to change at page 14, line 7 skipping to change at page 13, line 13
service provider. service provider.
4.6. Removing Registrations 4.6. Removing Registrations
Before leaving the RELOAD Overlay Instance, a service provider SHOULD Before leaving the RELOAD Overlay Instance, a service provider SHOULD
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 the RELOAD base protocol [RFC6940], every Kind that
in an overlay must be associated with an access control policy. This is storable in an overlay must be associated with an access control
policy defines whether a request from a given node to operate on a policy. This policy defines whether a request from a given node to
given value should succeed or fail. Usages can define any access operate on a given value should succeed or fail. Usages can define
control rules they choose, including publicly writable values. any access 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 the RELOAD base protocol [RFC6940] is sufficient.
This document defines a new access control policy, called NODE-ID- This document defines a new access control policy, called NODE-ID-
MATCH. In this policy, a given value MUST be written and overwritten MATCH. In this policy, a given value MUST be written and overwritten
only if the the request is signed with a key associated with a only if the request is signed with a key associated with a
certificate whose Node-ID is equal to the dictionary key. In certificate whose Node-ID is equal to the dictionary key. In
addition, provided that exists=TRUE, the Node-ID MUST belong to one addition, provided that exists=True, the Node-ID MUST belong to one
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-ID
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
specifying a level in the ReDiR tree. Node number is an integer specifying a level in the ReDiR tree. Node number is an integer
identifying a ReDiR tree node at a specific level. The data identifying a ReDiR tree node at a specific level. The data
stored is a RedirServiceProvider structure that was defined in stored is a RedirServiceProvider structure, as 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
the service providers have registered. 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 4: Example of a ReDiR tree Figure 4: 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 RELOAD Overlay Instance. This tree node is the first tree node the RELOAD Overlay Instance. This tree node is the first tree node
from the left at Level 2 since key 2 is associated with the second from the left at level 2 since key 2 is associated with the second
interval of the first tree node. Peer 2 also stores its interval of the first tree node. Peer 2 also stores its
RedirServiceProvider record in that tree node. Since peer 2's Node- RedirServiceProvider record in that tree node. Since peer 2's Node-
ID is the only Node-ID stored in the tree node (i.e., peer 2's Node- ID is the only Node-ID stored in the tree node (i.e., peer 2's Node-
ID fulfills the condition in Section 4.3 that it is the numerically ID fulfills the condition in Section 4.3 that it be the numerically
lowest or highest among the keys stored in the node), peer 2 lowest or highest among the keys stored in the node), peer 2
continues up the tree. In fact, peer 2 continues up in the tree all continues up the tree. In fact, peer 2 continues up in the tree all
the way to the root inserting its own Node-ID in all levels since the the way to the root inserting its own Node-ID in all levels since the
tree is empty (which means that peer 2's Node-ID always fulfills 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 condition that it be the numerically lowest or highest Node-ID in the
interval I(level, 2) during the upward walk). As described in 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 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 node in its interval 2 does ends at level 2 since peer 2 is the only node in its interval
at that level. 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 entry in the same interval I(2,3) that already RedirServiceProvider entry in the same interval I(2,3) that already
contains the RedirServiceProvider entry of peer 2. Interval I(2,3), contains the RedirServiceProvider entry of peer 2. Interval I(2,3),
that is, the interval at Level 2 enclosing key 3, is associated with that is, the interval at level 2 enclosing key 3, is associated with
the right hand side interval of the first tree node. Since peer 3 the right-hand-side interval of the first tree node. Since peer 3
has the numerically highest Node-ID in the tree node associated with has the numerically highest Node-ID in the tree node associated with
I(2,3), peer 3 continues up the tree. Peer 3 stores its I(2,3), peer 3 continues up the tree. Peer 3 also stores its
RedirServiceProvider record also at levels 1 and 0 since its Node-ID RedirServiceProvider record at levels 1 and 0 since its Node-ID is
is numerically highest among the Node-IDs stored in the intervals to numerically highest among the Node-IDs stored in the intervals to
which its own Node-ID belongs. Peer 3 also does a downward walk which its own Node-ID belongs. Peer 3 also does a downward walk that
which starts from level 2 (i.e., the starting level). Since peer 3 starts from level 2 (i.e., the starting level). Since peer 3 is not
is not the only node in interval I(2,3), it continues down the tree the only node in interval I(2,3), it continues down the tree to level
to level 3. The downward walk ends at this level since peer 3 is the 3. The downward walk ends at this level since peer 3 is the only
only service provider in the interval I(3,3). 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, peer 7 also 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
interval. Peer 7 also has the numerically highest Node-ID in the that interval. Peer 7 also has the numerically highest Node-ID in
interval I(0,7) associated with its Node-ID at level 0. Finally, the 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
is the only node in its interval at that level. is the only node in its interval at that level.
The final peer to join the ReDiR tree is peer 4, whose Node-ID is 4. The final peer to join the ReDiR tree is peer 4, whose Node-ID is 4.
Peer 4 starts by storing its RedirServiceProvider record at level 2. Peer 4 starts by storing its RedirServiceProvider record at level 2.
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 7.2. Service Lookup
This subsection gives an example of peer 5 whose Node-ID is 5 This subsection gives an example of peer 5 whose Node-ID is 5
performing a service lookup operation in the ReDiR tree shown in performing a service lookup operation in the ReDiR tree shown in
Figure 4. This is the first service lookup peer 5 carries out and Figure 4. This is the first service lookup peer 5 carries out, and
thus the service lookup starts from the default starting level 2. As thus, the service lookup starts from the default starting level 2.
the first action, peer 5 fetches the tree node corresponding to the As the first action, peer 5 fetches the tree node corresponding to
interval I(2,5) from the starting level. This interval maps to the the interval I(2,5) from the starting level. This interval maps to
second tree node from the left at level 2 since that tree node is 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 responsible for the interval (third interval from left) to which
Node-ID 5 falls at level 2. Having fetched the tree node, peer 5 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 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 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 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 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, 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 the service lookup finishes at level 2 since Node-ID 7 is the closest
successor of peer 5. successor of peer 5.
Note that the service lookup procedure would be slightly different if 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 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 starting level, for instance, if it has already carried out service
lookups in the past and follows the heuristic in Section 4.2 to 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 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, 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 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 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 thus continues up in the tree. The next action peer 5 performs is
identical to the single action in the previous example of fetching identical to the single action in the previous example of fetching
the node associated with I(2,5) from level 2. Thus, the service the node associated with I(2,5) from level 2. Thus, the service
lookup finishes at level 2. 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
adding a new element "branching-factor" inside the new "REDIR" kind defined in the RELOAD base protocol specification [RFC6940] by 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.
The Relax NG Grammar for this element is: The RELAX NG grammar for this element is:
namespace redir = "urn:ietf:params:xml:ns:p2p:redir" namespace redir = "urn:ietf:params:xml:ns:p2p:redir"
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
This document defines a new access control policy called NODE-ID- This document defines a new access control policy called NODE-ID-
MATCH (see Section 5) whose purpose is to control which nodes in the 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. overlay are allowed read and write access to the ReDiR tree nodes.
The NODE-ID-MATCH access control policy ensures that the only node in The NODE-ID-MATCH access control policy ensures that the only node in
the overlay that can store a pointer to a specific service provider the overlay that can store a pointer to a specific service provider
in the ReDiR tree is the service provider itself. This prevents in the ReDiR tree is the service provider itself. This prevents
attacks where a malicious node is inserting pointers to other nodes attacks where a malicious node inserts pointers to other nodes in the
in the ReDiR tree. Further, the NODE-ID-MATCH access control policy ReDiR tree. Further, the NODE-ID-MATCH access control policy ensures
ensures that a node can only store in locations in the ReDiR tree that a node can only store information in locations in the ReDiR tree
where it is entitled to store information. In other words, a node where it is entitled to do so. In other words, a node can only store
can only store one RedirServiceProvider record at any given level in one RedirServiceProvider record at any given level in the ReDiR tree.
the ReDiR tree. This prevents an attack where a malicious node is This prevents an attack where a malicious node is trying to insert a
trying to insert a high number of pointers to the ReDiR tree. high number of pointers to the ReDiR tree.
When it comes to attacks such as a malicious node refusing to store a When it comes to attacks such as a malicious node refusing to store a
value or denying knowledge of value it has previously accepted, such value or denying knowledge of a value it has previously accepted,
security concerns are already discussed in the RELOAD base such security concerns are already discussed in the RELOAD base
specification [RFC6940]. specification [RFC6940].
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 adds a new access control policy to the "RELOAD Access
"RELOAD Access Control Policy" Registry: Control Policies" 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.
10.2. A New IETF XML Registry 10.2. A New IETF XML Registry
This document registers one new URI for the redir namespace in the This document registers one new URI for the 'redir' namespace in the
IETF XML registry defined in [RFC3688]. "IETF XML Registry" defined in [RFC3688].
URI: urn:ietf:params:xml:ns:p2p:redir URI: urn:ietf:params:xml:ns:p2p:redir
Registrant Contact: The IESG Registrant Contact: The IESG
XML: N/A, the requested URI is an XML namespace XML: N/A, the requested URI is an XML namespace
10.3. Data Kind-ID 10.3. Data Kind-ID
This document introduces one additional data Kind-ID to the "RELOAD This document adds one new data Kind-ID to the "RELOAD Data Kind-ID"
Data Kind-ID" Registry: registry:
+--------------+------------+----------+ +--------------+------------+-----------+
| Kind | Kind-ID | RFC | | Kind | Kind-ID | RFC |
+--------------+------------+----------+ +--------------+------------+-----------+
| REDIR | 0x104 | RFC-AAAA | | REDIR | 0x104 | [RFC7374] |
+--------------+------------+----------+ +--------------+------------+-----------+
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
specification.
10.4. RELOAD Services Registry 10.4. RELOAD Services Registry
IANA is requested to create a new registry for ReDiR namespaces. IANA has created a new registry for ReDiR namespaces:
Registry Name: RELOAD Services Registry Registry Name: RELOAD Services Registry
Reference: RFC-AAAA Reference: [RFC7374]
Registration Procedure: Specification Required Registration Procedure: Specification Required
[TO BE REMOVED: The registry should be located under
http://www.iana.org/assignments/reload and be called: RELOAD Services
Registry].
Entries in this registry are strings denoting ReDiR namespace values. Entries in this registry are strings denoting ReDiR namespace values.
The initial contents of this registry are: The initial contents of this registry are:
+----------------+----------+ +----------------+-----------+
| Namespace | RFC | | Namespace | RFC |
+----------------+----------+ +----------------+-----------+
| turn-server | RFC-AAAA | | turn-server | [RFC7374] |
+----------------+----------+ +----------------+-----------+
| voice-mail | RFC-AAAA | | voice-mail | [RFC7374] |
+----------------+----------+ +----------------+-----------+
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
RELOAD overlay. In the TURN server discovery use case, the ReDiR- RELOAD overlay. In the TURN server discovery use case, the ReDiR-
based service discovery and registration mechanism specified in this based service discovery and registration mechanism specified in this
document can be used as an alternative to the TURN server discovery document can be used as an alternative to the TURN server discovery
mechanism specified in the RELOAD base specification [RFC6940]. The mechanism specified in the RELOAD base specification [RFC6940]. The
namespace 'voice-mail' is intended for a voice mail service namespace 'voice-mail' is intended for a voice mail service
implemented on top of a RELOAD overlay. implemented on top of a RELOAD overlay.
Note to RFC Editor: please replace AAAA with the RFC number for this 11. References
specification.
11. Acknowledgments
The authors would like to thank Marc Petit-Huguenin, Joscha
Schneider, Carlos Bernardos, Spencer Dawkins, Barry Leiba, Adrian
Farrel, Alexey Melnikov, Ted Lemon, and Stephen Farrell for their
comments on the document.
12. References
12.1. Normative References 11.1. Normative References
[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,
<http://www.rfc-editor.org/info/rfc2119>.
[RFC3174] Eastlake, D. and P. Jones, "US Secure Hash Algorithm 1 [RFC3174] Eastlake, D. and P. Jones, "US Secure Hash Algorithm 1
(SHA1)", RFC 3174, September 2001. (SHA1)", RFC 3174, September 2001,
<http://www.rfc-editor.org/info/rfc3174>.
[RFC3629] Yergeau, F., "UTF-8, a transformation format of ISO [RFC3629] Yergeau, F., "UTF-8, a transformation format of ISO
10646", STD 63, RFC 3629, November 2003. 10646", STD 63, RFC 3629, November 2003,
<http://www.rfc-editor.org/info/rfc3629>.
[RFC3688] Mealling, M., "The IETF XML Registry", BCP 81, RFC 3688, [RFC3688] Mealling, M., "The IETF XML Registry", BCP 81, RFC 3688,
January 2004. January 2004, <http://www.rfc-editor.org/info/rfc3688>.
[RFC6940] Jennings, C., Lowekamp, B., Rescorla, E., Baset, S., and [RFC6940] 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", RFC 6940, January 2014. Base Protocol", RFC 6940, January 2014,
<http://www.rfc-editor.org/info/rfc6940>.
12.2. Informative References 11.2. Informative Reference
[Redir] Rhea, S., Godfrey, P., Karp, B., Kubiatowicz, J., [Redir] Rhea, S., Godfrey, B., Karp, B., Kubiatowicz, J.,
Ratnasamy, S., Shenker, S., Stoica, I., and H. Yu, "Open Ratnasamy, S., Shenker, S., Stoica, I., and H. Yu,
DHT: A Public DHT Service and Its Uses", October 2005. "OpenDHT: A Public DHT Service and Its Uses", October
2005.
Acknowledgments
The authors would like to thank Marc Petit-Huguenin, Joscha
Schneider, Carlos Bernardos, Spencer Dawkins, Barry Leiba, Adrian
Farrel, Alexey Melnikov, Ted Lemon, and Stephen Farrell for their
comments on the document.
Authors' Addresses Authors' Addresses
Jouni Maenpaa Jouni Maenpaa
Ericsson Ericsson
Hirsalantie 11 Hirsalantie 11
Jorvas 02420 Jorvas 02420
Finland Finland
Email: Jouni.Maenpaa@ericsson.com EMail: Jouni.Maenpaa@ericsson.com
Gonzalo Camarillo Gonzalo Camarillo
Ericsson Ericsson
Hirsalantie 11 Hirsalantie 11
Jorvas 02420 Jorvas 02420
Finland Finland
Email: Gonzalo.Camarillo@ericsson.com EMail: Gonzalo.Camarillo@ericsson.com
 End of changes. 91 change blocks. 
243 lines changed or deleted 239 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/