draft-ietf-p2psip-service-discovery-07.txt   draft-ietf-p2psip-service-discovery-08.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: August 20, 2013 February 16, 2013 Expires: August 27, 2013 February 23, 2013
Service Discovery Usage for REsource LOcation And Discovery (RELOAD) Service Discovery Usage for REsource LOcation And Discovery (RELOAD)
draft-ietf-p2psip-service-discovery-07.txt draft-ietf-p2psip-service-discovery-08.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 August 20, 2013. This Internet-Draft will expire on August 27, 2013.
Copyright Notice Copyright Notice
Copyright (c) 2013 IETF Trust and the persons identified as the Copyright (c) 2013 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
skipping to change at page 2, line 10 skipping to change at page 2, line 10
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4
3. Introduction to ReDiR . . . . . . . . . . . . . . . . . . . . 4 3. Introduction to ReDiR . . . . . . . . . . . . . . . . . . . . 4
4. Using ReDiR in a RELOAD Overlay Instance . . . . . . . . . . . 6 4. Using ReDiR in a RELOAD Overlay Instance . . . . . . . . . . . 7
4.1. Data Structure . . . . . . . . . . . . . . . . . . . . . . 6 4.1. Data Structure . . . . . . . . . . . . . . . . . . . . . . 7
4.2. Selecting the Starting Level . . . . . . . . . . . . . . . 7 4.2. Selecting the Starting Level . . . . . . . . . . . . . . . 8
4.3. Service Provider Registration . . . . . . . . . . . . . . 8 4.3. Service Provider Registration . . . . . . . . . . . . . . 9
4.4. Refreshing Registrations . . . . . . . . . . . . . . . . . 8 4.4. Refreshing Registrations . . . . . . . . . . . . . . . . . 9
4.5. Service Lookups . . . . . . . . . . . . . . . . . . . . . 9 4.5. Service Lookups . . . . . . . . . . . . . . . . . . . . . 10
4.6. Removing Registrations . . . . . . . . . . . . . . . . . . 10 4.6. Removing Registrations . . . . . . . . . . . . . . . . . . 11
5. Access Control Rules . . . . . . . . . . . . . . . . . . . . . 10 5. Access Control Rules . . . . . . . . . . . . . . . . . . . . . 12
6. REDIR Kind Definition . . . . . . . . . . . . . . . . . . . . 11 6. REDIR Kind Definition . . . . . . . . . . . . . . . . . . . . 12
7. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 7. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
7.1. Service Registration . . . . . . . . . . . . . . . . . . . 11 7.1. Service Registration . . . . . . . . . . . . . . . . . . . 13
7.2. Service Lookup . . . . . . . . . . . . . . . . . . . . . . 13 7.2. Service Lookup . . . . . . . . . . . . . . . . . . . . . . 15
8. Overlay Configuration Document Extension . . . . . . . . . . . 14 8. Overlay Configuration Document Extension . . . . . . . . . . . 15
9. Security Considerations . . . . . . . . . . . . . . . . . . . 14 9. Security Considerations . . . . . . . . . . . . . . . . . . . 16
10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 14 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 16
10.1. Access Control Policies . . . . . . . . . . . . . . . . . 14 10.1. Access Control Policies . . . . . . . . . . . . . . . . . 16
10.2. Data Kind-ID . . . . . . . . . . . . . . . . . . . . . . . 14 10.2. Data Kind-ID . . . . . . . . . . . . . . . . . . . . . . . 16
10.3. ReDiR Namespaces . . . . . . . . . . . . . . . . . . . . . 15 10.3. ReDiR Namespaces . . . . . . . . . . . . . . . . . . . . . 16
11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 15 11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 17
12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 15 12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 17
12.1. Normative References . . . . . . . . . . . . . . . . . . . 15 12.1. Normative References . . . . . . . . . . . . . . . . . . . 17
12.2. Informative References . . . . . . . . . . . . . . . . . . 15 12.2. Informative References . . . . . . . . . . . . . . . . . . 17
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 16 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 17
1. Introduction 1. Introduction
REsource LOcation And Discovery (RELOAD) [I-D.ietf-p2psip-base] is a REsource LOcation And Discovery (RELOAD) [I-D.ietf-p2psip-base] is a
peer-to-peer signaling protocol that can be used to maintain an peer-to-peer signaling protocol that can be used to maintain an
overlay network, and to store data in and retrieve data from the overlay network, and to store data in and retrieve data from the
overlay. Although RELOAD defines a Traversal Using Relays around overlay. Although RELOAD defines a Traversal Using Relays around
Network Address Translation (TURN) specific service discovery Network Address Translation (TURN) specific service discovery
mechanism, it does not define a generic service discovery mechanism mechanism, it does not define a generic service discovery mechanism
as a part of the base protocol. This document defines how the as a part of the base protocol. This document defines how the
skipping to change at page 3, line 44 skipping to change at page 3, line 44
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 nodes that provide a particular service and embedding it into the the service providers that provide a particular service. The tree
RELOAD Overlay Instance using RELOAD Store and Fetch requests. Each structure is stored into the RELOAD Overlay Instance using RELOAD
service provided in the Overlay Instance has its own tree. The nodes Store and Fetch requests. Each service provided in the Overlay
in a ReDiR tree contain pointers to service providers. During Instance has its own tree. The nodes in a ReDiR tree contain
service discovery, a peer wishing to use a given service fetches pointers to service providers. During service discovery, a peer
ReDiR tree nodes one-by-one from the RELOAD Overlay Instance until it wishing to use a given service fetches ReDiR tree nodes one-by-one
finds a service provider responsible for its Node-ID. It has been from the RELOAD Overlay Instance until it finds a service provider
proved that ReDiR can find a service provider using only a constant responsible for its Node-ID. It has been proved that ReDiR can find
number of Fetch operations [Redir]. a service provider using only a constant number of Fetch operations
[Redir].
2. Terminology 2. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [RFC2119]. document are to be interpreted as described in RFC 2119 [RFC2119].
This document uses the terminology and definitions from the Concepts This document uses the terminology and definitions from the Concepts
and Terminology for Peer to Peer SIP [I-D.ietf-p2psip-concepts] and Terminology for Peer to Peer SIP [I-D.ietf-p2psip-concepts]
draft. draft.
skipping to change at page 4, line 46 skipping to change at page 4, line 48
service. The nodes embed the ReDiR tree into the RELOAD Overlay service. The nodes embed the ReDiR tree into the RELOAD Overlay
Instance using RELOAD Store and Fetch requests. Instance using RELOAD Store and Fetch requests.
Successor: The successor of identifier k in namespace ns is the node Successor: The successor of identifier k in namespace ns is the node
belonging to ns whose identifier most immediately follows k. belonging to ns whose identifier most immediately follows k.
3. Introduction to ReDiR 3. Introduction to ReDiR
Recursive Distributed Rendezvous (ReDiR) [Redir] does not require new Recursive Distributed Rendezvous (ReDiR) [Redir] does not require new
functionality from the RELOAD base protocol. This is possible since functionality from the RELOAD base protocol. This is possible since
ReDiR interacts with the RELOAD overlay through a put/get API using ReDiR interacts with the RELOAD Overlay Instance by simply storing
RELOAD Store and Fetch requests. ReDiR builds a tree structure of and fetching data, that is, using RELOAD Store and Fetch requests.
the nodes that provide a particular service and embeds it into the ReDiR creates a tree structure of the service providers of a
RELOAD Overlay Instance using the Store and Fetch requests. ReDiR particular service and stores it into the RELOAD Overlay Instance
performs lookup in a logarithmic number of Fetch operations with high using the Store and Fetch requests. ReDiR service lookups require a
probability. Further, if the height of the ReDiR tree is estimated logarithmic number of Fetch operations. Further, if information from
based on lookups carried out previously, the average lookup can be past service lookups is used to determine the optimal level in the
reduced to a constant number of Fetch operations assuming that Node- ReDiR tree from which to start new service lookups, an average
IDs are distributed uniformly at random. service lookup can typically finish after a constant number of Fetch
operations assuming that Node-IDs are distributed uniformly at
random.
In ReDiR, each service provided in the overlay is identified by an In ReDiR, each service provided in the overlay is identified by an
identifier, called the namespace. All service providers of a given identifier, called the namespace. All service providers of a given
service join the namespace of that service. Peers wishing to use a service store their information under the namespace of that service.
service perform lookups within the namespace of the service. The Peers wishing to use a service perform lookups within the namespace
result of a ReDiR lookup for an identifier k in namespace ns is a of the service. The result of a ReDiR lookup for an identifier k in
RedirServiceProvider structure (see Section 4.1) of a service namespace ns is a RedirServiceProvider structure (see Section 4.1) of
provider that belongs to ns and whose Node-ID is the closest a service provider that belongs to ns and whose Node-ID is the
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 level
2, and so forth. The ReDiR tree has a branching factor, whose value 2, and so forth. The ReDiR tree has a branching factor, whose value
is determined by a new element in the RELOAD overlay configuration is determined by a new element in the RELOAD overlay configuration
document, called branching-factor. At every level l in the ReDiR document, called branching-factor. At every level lvl in the ReDiR
tree, there is room for a maximum of branching-factor^l tree nodes. tree, there is room for a maximum of branching-factor^lvl tree nodes.
As an example, in a tree whose branching-factor is 2, the second As an example, in a tree whose branching-factor is 2, the second
level can contain up to 4 tree nodes (note that a given level may level can contain up to 4 tree nodes (note that a given level may
contain less than the maximum number of tree nodes since empty tree contain less than the maximum number of tree nodes since empty tree
nodes are not stored). Each tree node in the ReDiR tree is uniquely nodes are not stored). Each tree node in the ReDiR tree is uniquely
identified by a pair (l,j), where l is a level in the ReDiR tree and identified by a pair (lvl,j), where lvl is a level in the ReDiR tree
j is the position of the tree node (from the left) at that level. As and j is the position of the tree node (from the left) at that level.
an example, the pair (2,3) identifies the 3rd tree node from the left As an example, the pair (2,3) identifies the 3rd tree node from the
at level 2. 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) at key by tree node, by storing the values of tree node (level,j) under a
H(namespace,level,j). As an example, the root of the tree for a key created by taking a hash over the concatenation of the namespace,
voice mail service is stored at H("voice-mail",0,0). Each node level, and j, that is, as H(namespace,level,j). As an example, the
(level,j) in the ReDiR tree contains b intervals of the DHT's root of the tree for a voice mail service is stored at H("voice-
identifier space as follows: mail",0,0). Each node (level,j) in the ReDiR tree contains b
intervals of the DHT's identifier space as follows:
[2^numBitsInNodeID*b^(-level)*(j+(b'/b)), [2^numBitsInNodeID*b^(-level)*(j+(b'/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. where b is the branching-factor.
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 is
2. Each tree node is shown as two horizontal lines separated by a 2. In the figure, the size of the identifier space of the overlay is
vertical bar in the middle. The lines represent the two intervals 16. Each tree node in the ReDiR tree is shown as two horizontal
each node is responsible for. At level 0, there is only one node, lines separated by a vertical bar ('|') in the middle. The
(0,0) responsible for two intervals that together cover the entire horizontal lines represent the two intervals each node is responsible
identifier space of the RELOAD Overlay Instance. At level 1, there for. At level 0, there is only one node, (0,0) responsible for two
are two nodes, (1,0) and (1,1), each of which is responsible for half intervals that together cover the entire identifier space of the
of the identifier space of the RELOAD Overlay Instance. At level 2, RELOAD Overlay Instance. At level 1, there are two nodes, (1,0) and
there are four nodes. Each of them owns one fourth of the identifier (1,1), each of which is responsible for half of the identifier space
space. At level 3, there are eight nodes each of which is of the RELOAD Overlay Instance. At level 2, there are four nodes.
responsible for one eight of the identifier space. 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
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
levels 0-2.
Level 0 ________________(0,0)________________
| |
Level 1 ______(1,0)______ ______(1,1)______
| | | |
Level 2 _(2,0)_ _(2,1)_ _(2,2)_ _(2,3)_
| | | | | | | |
Level 3 _|_ _|_ _|_ _|_ _|_ _|_ _|_ _|_
Figure 2: ReDiR tree nodes
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
(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
[0,7] and [8,15].
Level 0 ______[0,7]_______|_______[8,15]_____
| |
Level 1 _[0,3]__|__[4,7]_ _[8,11]_|_[12,15]
| | | |
Level 2 ___|___ ___|___ ___|___ ___|___
| | | | | | | |
Level 3 _|_ _|_ _|_ _|_ _|_ _|_ _|_ _|_
Figure 3: Intervals in ReDiR tree
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 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
intervals. Level 2 contains 100 nodes and 1000 intervals, level 3
1000 nodes and 10000 intervals, etc. Further, the size of the
identifier space of a real RELOAD Overlay Instance is at the minimum
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 [I-D.ietf-p2psip-base]. The data stored is a in RELOAD base [I-D.ietf-p2psip-base]. The data stored is a
RedirServiceProvider Resource Record: RedirServiceProvider Resource Record:
enum { none(0), (255) } enum { none(0), (255) }
RedirServiceProviderExtType; RedirServiceProviderExtType;
skipping to change at page 8, line 13 skipping to change at page 9, line 13
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:
1. A node n with Node-ID n.id wishing to register as a service 1. A node n with Node-ID n.id wishing to register as a service
provider starts from a starting level Lstart (see Section 4.2 for provider starts from a starting level Lstart (see Section 4.2 for
the details on selecting the starting level). Therefore, node n the details on selecting the starting level). Therefore, node n
sets level=Lstart. sets the current level to level=Lstart.
2. Node n MUST send a RELOAD Fetch request to fetch the contents of 2. Node n MUST send a RELOAD Fetch request to fetch the contents of
the tree node responsible for I(level,n.id). An interval I(l,k) the tree node responsible for I(level,n.id). An interval I(l,k)
is the interval at level l in the ReDiR tree that includes key k. is the interval at level l in the ReDiR tree that includes key k.
The fetch MUST be a wildcard fetch. The fetch MUST be a wildcard fetch.
3. Node n MUST send a RELOAD Store request to add its 3. Node n MUST send a RELOAD Store request to add its
RedirServiceProvider entry to the dictionary stored in the tree RedirServiceProvider entry to the dictionary stored in the tree
node responsible for I(level,n.id) node responsible for I(level,n.id). Note that node n always
stores its RedirServiceProvider entry, regardless of the contents
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 the steps 2 and 3 above. Node n MUST continue in this
way until it reaches either the root of the tree or a level at way until it reaches either the root of the tree or a level at
which n.id is not the lowest or highest Node-ID in the interval which 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
skipping to change at page 9, line 17 skipping to change at page 10, line 19
'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
immediately follows (i.e., is the closest successor of) the immediately follows (i.e., is the closest successor of) the
identifier k. identifier k.
A service lookup is similar to the service registration operation A service lookup operation resembles the service registration
described in Section 4.3. Service lookups start from a given operation described in Section 4.3. Service lookups start from a
starting level level=Lstart in the ReDiR tree (see Section 4.2 for given starting level level=Lstart in the ReDiR tree (see Section 4.2
the details on selecting the starting level). At each step, a node n for the details on selecting the starting level). At each step, a
wishing to discover a service provider MUST fetch the tree node node n wishing to discover a service provider MUST fetch the tree
responsible for the interval I(level,n.id) that encloses the search node responsible for the interval I(level,n.id) that encloses the
key n.id at the current level using a RELOAD Fetch request. Having search key n.id at the current level using a RELOAD Fetch request.
fetched the tree node, node n MUST determine the next action to carry Having fetched the tree node, node n MUST determine the next action
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 and not only within
the current interval) responsible for I(level,n.id), then the the current interval) responsible for I(level,n.id), then the
successor of node n must be present in a larger segment of 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 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 to 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 node responsible for n.id at that level. The fetched tree node
skipping to change at page 10, line 17 skipping to change at page 11, line 20
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
being refreshed periodically, there can be certain rare situations in
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
tree node is fetched just after a RedirServiceProvider entry of the
only successor of k present in the tree node has expired and just
before a Store request that has been sent to refresh the entry
reaches the peer storing the tree node. In this rather unlikely
scenario, the successor that should have been present in the tree
node is temporarily missing. Thus, the service lookup will fail and
needs to be carried out again.
To recover from the kinds of situations described above, a ReDiR
implementation MAY choose to use the optimization described next.
The ReDiR implementation MAY implement a local temporary cache that
is maintained for the duration of a service lookup operation in a
RELOAD node. The temporary cache is used to store all
RedirServiceProvider entries that have been fetched during the upward
and downward walks of a service lookup operation. Should it happen
that a service lookup operation fails due to the downward walk
reaching a level that does not contain a successor, the cache is
searched for successors of the search key. If there are successors
present in the cache, the closest one of them is selected as the
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 exists=False values in their place, as described in
[I-D.ietf-p2psip-base]. [I-D.ietf-p2psip-base].
5. Access Control Rules 5. Access Control Rules
As specified in RELOAD base [I-D.ietf-p2psip-base], every kind which As specified in RELOAD base [I-D.ietf-p2psip-base], every kind which
skipping to change at page 11, line 34 skipping to change at page 13, line 17
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 2 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 2 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 2: 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 RedirServiceProvider record in that tree node. Since peer 2's
skipping to change at page 13, line 22 skipping to change at page 15, line 9
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 2. 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. As
the first action, peer 5 fetches the tree node corresponding to the the first action, peer 5 fetches the tree node corresponding to the
interval I(2,5) from the starting level. This interval maps to the interval I(2,5) from the starting level. This interval maps to the
second tree node from the left at level 2 since that tree node is 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
skipping to change at page 15, line 37 skipping to change at page 17, line 23
The authors would like to thank Marc Petit-Huguenin and Joscha The authors would like to thank Marc Petit-Huguenin and Joscha
Schneider for their comments on the draft. Schneider for their comments on the draft.
12. References 12. References
12.1. Normative References 12.1. Normative References
[I-D.ietf-p2psip-base] [I-D.ietf-p2psip-base]
Jennings, C., Lowekamp, B., Rescorla, E., Baset, S., and Jennings, C., Lowekamp, B., Rescorla, E., Baset, S., and
H. Schulzrinne, "REsource LOcation And Discovery (RELOAD) H. Schulzrinne, "REsource LOcation And Discovery (RELOAD)
Base Protocol", draft-ietf-p2psip-base-24 (work in Base Protocol", draft-ietf-p2psip-base-25 (work in
progress), January 2013. progress), February 2013.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997. Requirement Levels", BCP 14, RFC 2119, March 1997.
12.2. Informative References 12.2. Informative References
[I-D.ietf-p2psip-concepts] [I-D.ietf-p2psip-concepts]
Bryan, D., Willis, D., Shim, E., Matthews, P., and S. Bryan, D., Willis, D., Shim, E., Matthews, P., and S.
Dawkins, "Concepts and Terminology for Peer to Peer SIP", Dawkins, "Concepts and Terminology for Peer to Peer SIP",
draft-ietf-p2psip-concepts-04 (work in progress), draft-ietf-p2psip-concepts-04 (work in progress),
 End of changes. 21 change blocks. 
88 lines changed or deleted 160 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/