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