RFC 7374

Service Discovery Usage for REsource LOcation And Discovery (RELOAD)

📅 published October 2014, from ietf

RFC 7374 🎀 Service Discovery Usage for REsource LOcation And Discovery (RELOAD)

Part 1 of 5 🌸

  • Organization: Internet Engineering Task Force (IETF) 💜
  • Request for Comments: 7374
  • Authors: J. Maenpaa and G. Camarillo, both at Ericsson 🧚
  • Category: Standards Track ✨
  • ISSN: 2070-1721
  • Date: October 2014 📅
  • Obsoletes / Updates: this one doesn't list anything it obsoletes or updates 🫶

Abstract 🦋

okay so REsource LOcation And Discovery (RELOAD) doesn't come with a generic service discovery mechanism in its base protocol (RFC 6940) 🙈. this doc explains how the Recursive Distributed Rendezvous (ReDiR) service discovery mechanism can be used on RELOAD overlays to get a generic one. it's giving main character energy 💅✨

Status of This Memo 📜

This is an Internet Standards Track document. ✨

This document is a product of the Internet Engineering Task Force (IETF). It represents the consensus of the IETF community. It has received public review and has been approved for publication by the Internet Engineering Steering Group (IESG). Further information on Internet Standards is available in Section 2 of RFC 5741. 🎀

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 (c) 2014 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 ...........................................5
4. Using ReDiR in a RELOAD Overlay Instance ........................8
   4.1. Data Structure .............................................8
   4.2. Selecting the Starting Level ...............................9
   4.3. Service Provider Registration ..............................9
   4.4. Refreshing Registrations ..................................10
   4.5. Service Lookups ...........................................11
   4.6. Removing Registrations ....................................13
5. Access Control Rules ...........................................13
6. REDIR Kind Definition ..........................................13
7. Examples .......................................................14
   7.1. Service Registration ......................................14
   7.2. Service Lookup ............................................16
8. Overlay Configuration Document Extension .......................16
9. Security Considerations ........................................17
10. IANA Considerations ...........................................17
   10.1. Access Control Policies ..................................17
   10.2. A New IETF XML Registry ..................................17
   10.3. Data Kind-ID .............................................18
   10.4. RELOAD Services Registry .................................18
11. References ....................................................19
   11.1. Normative References .....................................19
   11.2. Informative Reference ....................................19
Acknowledgments ...................................................19
Authors' Addresses ................................................20

1. Introduction ✨

RELOAD [RFC6940] (REsource LOcation And Discovery) is a peer-to-peer signaling protocol 🦋. you can use it to keep an overlay network running, and to store data in the overlay and pull it back out again. RELOAD does come with a service discovery mechanism, but it's specific to Traversal Using Relays around Network Address Translation (TURN). it does not define a generic one as part of the base protocol 🙈. this document explains how the Recursive Distributed Rendezvous (ReDiR) service discovery mechanism from [Redir] can be applied to RELOAD overlays 💖.

In a peer-to-peer (P2P) overlay network like a RELOAD Overlay Instance, the peers share their resources so the system can provide the service it was built for 🫶. every peer both offers services to other peers and asks other peers for services 🔁. some examples of services peers in a RELOAD Overlay Instance can offer each other are a TURN relay service, a voice mail service, a gateway location service, and a transcoding service 🎀. usually only a small slice of the peers are providers for any given service. so a peer that wants a particular service has to find the peers that are providing it inside the Overlay Instance 🔍.

A naive way to do service discovery is to store the Node-IDs of every node providing a particular service under a well-known key k 🙃. the catch is that this scales linearly with the number of nodes that provide the service 📈. there are two problems here. first, the node n that's responsible for service s identified by key k may end up storing a huge pile of Node-IDs. even worse, it may also become overloaded, since every service lookup request for service s has to be answered by node n 😭. an efficient service discovery mechanism doesn't overload the nodes that store pointers to service providers 💅. on top of that, the mechanism has to make sure the load of providing a given service is spread evenly across the nodes that provide it ⚖️.

ngl a simple mechanism like the one in the previous paragraph might be a perfectly good fit for a very small overlay network, maybe tens of nodes 🍓. the ReDiR-based mechanism in this document is built for overlays where the number of end users making service discovery requests can be very high (for example, tens of thousands of nodes or even more), and where a large fraction of the peers (for example, on the order of one out of ten or more) can offer the service 🌈.

ReDiR does service discovery by building a tree structure out of the service providers for a particular service 🌳. the tree gets stored into the RELOAD Overlay Instance using RELOAD Store and Fetch requests 📦. every service in the Overlay Instance gets its own tree 🧚. the nodes in a ReDiR tree hold pointers to service providers. during service discovery, a peer that wants a given service fetches ReDiR tree nodes one-by-one from the RELOAD Overlay Instance until it finds the service provider responsible for its Node-ID 🎯. it has been proved that ReDiR can find a service provider using only a constant number of Fetch operations [Redir] 🤯👑.

2. Terminology 💅

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119]. 📖

  • DHT: Distributed Hash Tables (DHTs) are a class of decentralized distributed systems that provide a lookup service similar to a regular hash table 🗝️. given a key, any peer participating in the system 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): refers to a hash function (for example, SHA-1 [RFC3174]) calculated over the value x 🔐.
  • H(x,y,z): refers to a hash function calculated over a concatenated string made of x, y, and z, where x, y, and z can be both strings and integers. the network byte order is used 🧮.
  • I(lvl,k): an interval at level lvl in the ReDiR tree that encloses key k. for example, I(5,10) refers to an interval at level 5 in the ReDiR tree whose range key 10 falls within 🎀.
  • n.id: refers to the RELOAD Node-ID of node n 🪪.
  • Namespace: an arbitrary identifier that identifies a service provided in the RELOAD Overlay Instance 🏷️. examples of potential namespaces include 'voice-mail' and 'turn-server'. the namespace is a UTF-8-encoded [RFC3629] text string 🔤.
  • numBitsInNodeId: refers to the number of bits in a RELOAD Node-ID 🔢. this value is used in the equations for calculating the ranges of intervals that ReDiR tree nodes are responsible for 📐.
  • 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. each tree node in 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 child nodes of the root node are located at level 1. the children of the tree nodes at level 1 are located at level 2, and so forth 🪜. the ReDiR tree has a branching factor b. at every level lvl in the ReDiR tree, there is room for a maximum of b^lvl tree nodes 🌸. each tree node in the ReDiR tree is uniquely identified by a pair (lvl,j), where lvl is a level in the ReDiR tree and j is the position of the tree node (from the left) at that level 📍.
  • Successor: the successor of identifier k in namespace ns is the node belonging to the namespace ns whose identifier most immediately follows the identifier k 👀.

3. Introduction to ReDiR ✨

okay so [Redir] (Recursive Distributed Rendezvous, or ReDiR for short 💖) doesn't need any new powers from the RELOAD base protocol [RFC6940]. It just talks to the RELOAD Overlay Instance by storing and fetching data using RELOAD Store and Fetch requests, which is so clean 🧚. ReDiR builds a tree of the service providers for a particular service and stores that tree in the overlay with those Store and Fetch requests. A ReDiR service lookup needs a logarithmic number of Fetch operations, but if a peer uses info from past lookups to pick the best level in the tree to start from, an average lookup can usually finish after a constant number of Fetch operations, as long as Node-IDs are spread out uniformly at random 🦋.

Every service in the overlay gets its own identifier called the namespace 🎀. All the service providers for a service store their info under that service's namespace, and peers who want the service do their lookups inside that same namespace. A ReDiR lookup for an identifier k in namespace ns gives back a RedirServiceProvider structure (see Section 4.1) for a service provider that belongs to ns and whose Node-ID is the closest successor of identifier k in the namespace. Main character energy 👑.

Each tree node in the ReDiR tree holds a dictionary of RedirServiceProvider entries for the peers providing a particular service 💅. Every tree node also belongs to a level. The root node is at level 0, its children are at level 1, the children of those are at level 2, and so on 🌸. The tree has a branching factor, which comes from a new element in the RELOAD overlay configuration document called branching-factor. That configuration document is defined in the RELOAD base protocol [RFC6940]. At every level lvl there's room for a maximum of branching-factor^lvl tree nodes. For example, if the branching-factor is 2, the second level can hold up to four tree nodes. (A level might hold fewer than the max, since empty tree nodes never get stored 🙈.) Each tree node is uniquely identified by a pair (lvl,j), where lvl is the level and j is the node's position from the left at that level. So the pair (2,3) is the third tree node from the left at level 2 🍓.

The ReDiR tree gets stored in the RELOAD Overlay Instance one tree node at a time. The values of tree node (level,j) go under a key made by hashing the namespace, level, and j together, written as H(namespace,level,j). For example, the root of the tree for a voice mail service is stored at H("voice-mail",0,0) 📞. Each node (level,j) holds b intervals of the DHT's identifier space, like this:

[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 and b' is the number of an interval within the ReDiR tree node j.

Figure 1 shows a ReDiR tree with a branching factor of 2 🌈. In this picture the overlay's identifier space has size 16. Each tree node is drawn as two horizontal lines split by a vertical bar ('|') in the middle, and those two lines are the two intervals that node is responsible for. At level 0 there's only one node, (0,0), responsible for two intervals that together cover the whole identifier space of the RELOAD Overlay Instance. At level 1 there are two nodes, (1,0) and (1,1), and each one covers half the space. At level 2 there are four nodes, each owning a fourth. At level 3 there are eight nodes, each with an eighth of the space 🫶.

  Level 0  __________________|__________________
                   |                   |
  Level 1  ________|________   ________|________
              |         |         |         |
  Level 2  ___|___   ___|___   ___|___   ___|___
            |   |     |   |     |   |     |   |
  Level 3  _|_ _|_   _|_ _|_   _|_ _|_   _|_ _|_

                        Figure 1: ReDiR Tree

Figure 2 shows how the tree nodes are numbered 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 shows how the intervals get assigned to the tree nodes at levels 0 and 1 ✨. Take the single tree node (0,0) at level 0: it's split into two intervals, each covering half the overlay's identifier space, and those 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

Quick note bestie: all of these examples are simplified 🧸. In a real ReDiR tree the default branching factor is 10, so each tree node is split into 10 intervals and has 10 children. That means level 1 has 10 nodes and 100 intervals, level 2 has 100 nodes and 1000 intervals, level 3 has 1000 nodes and 10000 intervals, and so on 📈. Also, the identifier space of a real RELOAD Overlay Instance is at minimum 2^128, which is an absolutely unhinged amount of space 😭.

4. Using ReDiR in a RELOAD Overlay Instance 💜

4.1. Data Structure

ReDiR tree nodes get stored using the dictionary data model from the RELOAD base protocol [RFC6940]. The thing being stored is a RedirServiceProvider Resource Record 📦:

      enum { none(0), (255) }
        RedirServiceProviderExtType;

      struct {
        RedirServiceProviderExtType   type;
        Destination                   destination_list<0..2^16-1>;
        opaque                        namespace<0..2^16-1>;
        uint16                        level;
        uint16                        node;
        uint16                        length;

        select (type) {
            /* This type may be extended */
        } extension;

      } RedirServiceProvider;

Here's what each field in the RedirServiceProvider Resource Record does 💅:

type

The type of an extension to the RedirServiceProvider Resource Record. Unknown types are allowed 🌟.

destination_list

A list of IDs that a message gets routed through to reach the service provider. The destination list is a sequence of Destination values, and the contents of the Destination structure are defined in the RELOAD base protocol [RFC6940] 🛣️.

namespace

An opaque UTF-8-encoded string that holds 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 📏.

extension

An extension value. The RedirServiceProvider Resource Record can be extended to include, for instance, info specific to the service or service provider ✨.

4.2. Selecting the Starting Level

Before a peer registers as a service provider or does a service lookup, it needs to figure out the starting level Lstart for that registration or lookup in the ReDiR tree 🦋. It is RECOMMENDED that Lstart is set to 2. This recommendation comes from the findings in [Redir], which show that this starting level performs well 🏆. For later registrations, Lstart MAY, as an optimization, be set to the lowest level where a registration operation last completed.

For later service lookups, nodes MAY, as an optimization, record the levels where their last 16 service lookups completed, and then take Lstart to be the mode of those depths. (Mode, in statistics, is the value that shows up most often in a set of data 📊.)

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 that wants to register as a service provider starts from a starting level Lstart (see Section 4.2 for the details on picking the starting level). So node n sets the current level to level=Lstart 🎯.
  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) 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 responsible for I(level,n.id). Quick reminder: node n always stores its RedirServiceProvider entry, no matter what's already in the dictionary 💌.
  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 keep climbing up the ReDiR tree towards the root level (level 0), repeating 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 say '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

okay so everything in the ReDiR tree is soft state ⏳, which means nothing is forever. Every service provider has to keep re-registering to refresh its RedirServiceProvider Resource Record 🔄. If a record expires, the peer storing that tree node MUST drop it from the dictionary 💀. Each service provider gets to pick its own lifetime for these records, but a default of 10 minutes is RECOMMENDED because it hits the sweet spot between not flooding the overlay with ReDiR traffic and clearing out stale info fast enough 🎀. Every service provider MUST repeat the entire registration process periodically until it leaves the RELOAD Overlay Instance 🫶. And the service provider SHOULD start each refresh a bit early, like when 90% of the refresh interval has passed, instead of waiting for the expiry time of the Resource Record ⏰.

No new mechanisms are needed to track how much lifetime is left on a RedirServiceProvider record 🙌. The storage_time and lifetime fields of RELOAD's StoredData structure already do this job, used in the usual way ✨.

4.5. Service Lookups

so the whole point of a service lookup 🔍 is for identifier k in namespace ns to find the node that lives in ns and has the identifier that most immediately follows k, aka the closest successor of k 🦋.

A service lookup works a lot like the service registration from Section 4.3 🔁. It starts at a given starting level, level=Lstart, in the ReDiR tree (see Section 4.2 for how to pick it 🧭). At each step, a node n that wants to find 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 📨. Once it has that tree node, node n MUST figure out its next move like this:

Condition 1

If there is no successor of node n in the tree node that was just fetched (and yes, I mean the entire tree node, not just the current interval) responsible for I(level,n.id), then the successor has to be sitting in a bigger chunk of the identifier space, further up the ReDiR tree where each interval and tree node covers more ground 🌳. So node n MUST reduce the current level by one, to level=level-1, and run a new Fetch operation for the tree node responsible for n.id at that level 🪜. Then it analyzes the fetched tree node and works out the next action by checking Conditions 1-3 again 🔄.

Condition 2

If n.id is neither the lowest nor the highest Node-ID within the interval I(level,n.id) (and this time it's the interval, not the whole tree node 👀), n MUST next check the tree node responsible for n.id one level down the tree. So node n MUST increase the level by one, to level=level+1, and run a new Fetch operation at that level 📈. Then it analyzes the fetched tree node and goes through the conditions again, starting at Condition 1 💅.

Condition 3

If neither of the conditions above holds, that means there is a successor s of n.id in the tree node that was just fetched, and n.id is the highest or lowest Node-ID in its interval 🎉. The service lookup is finished successfully, and s has to be the closest successor of n.id in the ReDiR tree 🏆.

Quick clarification bc this gets confusing 🙈: when we say 'the tree node responsible for interval I(l,k)', we mean the whole tree node (every interval inside it) that is responsible for I(l,k). When we just say I(l,k), we're talking about one specific interval inside a tree node 🧩.

Also, sometimes no successor can be found in the ReDiR tree at all 😭. One example is when every service provider stored in the tree has a Node-ID smaller than identifier k. In that case the upward walk of the service lookup reaches the root of the tree without ever hitting a successor 🌲. The recommended move then is to pick one of the RedirServiceProvider entries stored in the dictionary of the root node at random 🎲.

Because RedirServiceProvider records expire and registrations keep getting refreshed, there are rare moments where a service lookup can fail even though a valid successor is actually in the tree 🥲. Picture this: a ReDiR tree node gets fetched right after the RedirServiceProvider entry of the only successor of k in that node has expired, and right before a Store request meant to refresh that entry reaches the peer storing the node 💔. That successor is temporarily missing, so the lookup fails and has to be run again 🔁. It's super unlikely, but it's real, so keep it in mind 👀.

To handle situations like that, a ReDiR implementation MAY use the optimization described next ✨. It MAY keep a local temporary cache on a RELOAD node, and that cache only lives for the duration of one service lookup operation 🗂️. The cache stores all the RedirServiceProvider entries fetched during the upward and downward walks of the lookup 🧺. If a service lookup fails because the downward walk hits a level with no successor, the cache gets searched for successors of the search key 🔎. If any successors are in the cache, the closest one is picked as the service provider 🏅.

4.6. Removing Registrations

before leaving the RELOAD Overlay Instance, a service provider SHOULD clean up after itself 🧹. That means removing the RedirServiceProvider records it has stored by storing exists=False values in their place, as described in [RFC6940] 👋.

5. Access Control Rules

okay so in the RELOAD base protocol [RFC6940] every Kind that can be stored in an overlay must be associated with an access control policy 🔐. That policy decides whether a request from a given node to operate on a given value succeeds or fails ✅. Usages are free to set whatever access control rules they like, including values that anyone can write to 🌍.

ReDiR needs a policy where multiple nodes in the overlay get read and write access to the ReDiR tree nodes stored there 🤝. None of the access control policies in the RELOAD base protocol [RFC6940] cut it for that, so we need something new 💅.

This document defines a brand new access control policy called NODE-ID-MATCH 🎀. With this policy, a given value MUST be written and overwritten only if the request is signed with a key tied to a certificate whose Node-ID equals the dictionary key 🔑. On top of that, as long as exists=True, the Node-ID MUST belong to one of the intervals associated with the tree node (how many intervals each tree node has is set by the branching-factor parameter) 📏. And, also as long as exists=True, H(namespace,level,node) MUST be equal to the Resource-ID for the resource, where namespace, level, and node come from the RedirServiceProvider structure being stored 🧮. The NODE-ID-MATCH policy may only be used with dictionary types 📚.

6. REDIR Kind Definition

this section defines the REDIR Kind 💜.

Name

REDIR 🏷️

Kind-ID

the Resource Name for the REDIR Kind-ID gets made by smooshing together three pieces of info: namespace, level, and node number 🧩. Namespace is an opaque UTF-8-encoded string that identifies a service, like 'turn-server' 🎮. Level is an integer that specifies a level in the ReDiR tree 🪜. Node number is an integer that identifies a ReDiR tree node at a specific level 🔢. The data stored is a RedirServiceProvider structure, as 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 we defined in Section 5 🔐✨.

7. Examples

7.1. Service Registration ✨

okay bestie, let's watch peers 2, 3, 4, and 7 set up shop in a ReDiR tree 🌳💖 The Node-IDs are 2, 3, 4, and 7, and numBitsInNodeId=4 for this whole example. The tree starts out totally empty, and Figure 4 is the snapshot of what it looks like once everyone has registered 📸

     Level 0  ____2_3___4_____7_|__________________
                      |                   |
     Level 1  ____2_3_|_4_____7   ________|________
                 |         |         |         |
     Level 2  ___|2_3   4__|__7   ___|___   ___|___
               |   |     |   |     |   |     |   |
     Level 3  _|_ _|3   _|_ _|_   _|_ _|_   _|_ _|_

                     Figure 4: Example of a ReDiR Tree

First up, peer 2 joins the namespace 🎀 Since it's the very first registration peer 2 does, it sets its starting level Lstart to 2, like we covered in Section 4.2. Every other peer in this example starts at level 2 too. Peer 2 grabs the contents of the tree node tied to interval I(2,2) from the RELOAD Overlay Instance. That's the first tree node from the left at level 2, because key 2 lives in the second interval of that node. Then peer 2 drops its RedirServiceProvider record into that node 📝 Now here's the thing: peer 2's Node-ID is the only one in that node, so it meets the condition in Section 4.3 (it's the numerically lowest or highest key stored in the node), and it keeps climbing 🧗‍♀️ Honestly, it goes all the way up to the root, adding its Node-ID at every level, because the tree is empty and peer 2 is automatically the lowest and highest Node-ID in I(level, 2) on the way up. Then, as Section 4.3 describes, peer 2 does a downward walk too. That walk stops at level 2 because peer 2 is the only node in its interval there 🙌

Next, peer 3 joins with Node-ID 3 🦋 Peer 3 starts at level 2 and stores its RedirServiceProvider entry in the same interval I(2,3) that peer 2 already filled. I(2,3) is the level 2 interval enclosing key 3, and it's the right-hand-side interval of the first tree node. Since peer 3 has the numerically highest Node-ID in the tree node for I(2,3), it keeps going up the tree. It stores its record at levels 1 and 0 too, because its Node-ID is the highest among the Node-IDs in the intervals it belongs to 🌈 For the downward walk, peer 3 starts from level 2 (the starting level). It isn't alone in I(2,3), so it keeps going down to level 3. That walk ends there, because peer 3 is the only service provider in I(3,3) 💅

Third up is peer 7, Node-ID 7 🍓 Like the first two, peer 7 starts at level 2 because this is its first registration. It stores its record at level 2. At level 1, peer 7 is the numerically highest and lowest Node-ID in I(1,7), since it's the only node in that interval. (Peers 2 and 3 share the same tree node but sit in a different interval, so this is totally separate 🙈) So peer 7 stores its Node-ID in the tree node for that interval. At level 0, peer 7 also has the numerically highest Node-ID in I(0,7), the interval tied to its Node-ID. Then peer 7 does a downward walk that ends at level 2, since it's the only node in its interval at that level 🎯

The last peer to join the ReDiR tree is peer 4, Node-ID 4 🫶 It starts by storing its RedirServiceProvider record at level 2. Since it has the numerically lowest Node-ID in the tree node for I(2,4), it keeps climbing to level 1. At level 1, peer 4 stores its record in the tree node for I(1,4), because it has the numerically lowest Node-ID in that interval. Then peer 4 continues to the root level, where it stores its record and wraps up the upward walk, since the root has been reached 🏁 Peer 4 also does a downward walk starting at level 2. That walk stops at level 2, because peer 4 is the only peer in I(2,4). Iconic, honestly ✨

7.2. Service Lookup ✨

This subsection shows peer 5 (Node-ID 5) doing a service lookup in the ReDiR tree from Figure 4 🔍 It's peer 5's first lookup, so the search starts at the default starting level, which is 2. First step: peer 5 fetches the tree node for interval I(2,5) from that starting level. That interval maps to the second tree node from the left at level 2, since that node covers the interval (the third interval from the left) where Node-ID 5 falls at level 2. Once it has the tree node, peer 5 checks what's inside 👀

Check number one: there's a successor in that node, peer 7. So Condition 1 of Section 4.5 is false, and there's no need for an upward walk. Check number two: Node-ID 5 is the highest Node-ID in its interval, which makes Condition 2 of Section 4.5 false too, so no downward walk is needed either. The lookup wraps up at level 2, since Node-ID 7 is the closest successor of peer 5 💖

Now, the lookup would go a bit differently if peer 5 started at level 3 instead. Peer 5 might pick that starting level if it has already done service lookups before and used the heuristic in Section 4.2 to choose it 🧠 In that case, peer 5's first step is to fetch the tree node at level 3 responsible for I(3,5), which means the third tree node from the left. That node is empty, so peer 5 drops the current level down by one to 2, which means it's going up the tree 🪜 The next action is exactly the same one from the previous example, fetching the node for I(2,5) at level 2. So the lookup finishes at level 2 too 🌸

8. Overlay Configuration Document Extension 🎀

This document extends the RELOAD overlay configuration document defined in the RELOAD base protocol specification [RFC6940] 📄 It adds one new element, "branching-factor", which goes inside the new "REDIR" kind element:

  • redir:branching-factor: The branching factor of the ReDiR tree. The default value is 10 🔢

The RELAX NG grammar for this element looks like this:

namespace redir = "urn:ietf:params:xml:ns:p2p:redir"

parameter &= element redir:branching-factor { xsd:unsignedInt }?

Last bit: the 'redir' namespace gets added into the <mandatory-extension> element in the overlay configuration file 💜

9. Security Considerations 🔐

Okay, this part is seriously important, bestie 😤 This document defines a brand-new access control policy called NODE-ID-MATCH (see Section 5). Its whole job is to control which nodes in the overlay can read and write ReDiR tree nodes 🛡️ NODE-ID-MATCH makes sure that the only node in the overlay able to store a pointer to a specific service provider in the ReDiR tree is that service provider itself. That shuts down attacks where a malicious node tries to shove pointers to other nodes into the tree 🚫 It also makes sure a node can only write to places in the ReDiR tree it's actually allowed to write to. In other words, a node can store only one RedirServiceProvider record at any given level in the tree. That stops a sneaky attack where a malicious node tries to flood the tree with a huge pile of pointers 💀

As for attacks where a malicious node refuses to store a value, or denies knowing a value it already accepted, those concerns are already covered in the RELOAD base specification [RFC6940] 📚 Go check them out, they're important 🙏

10. IANA Considerations 🧚

10.1. Access Control Policies 💅

This document adds a new access control policy to the "RELOAD Access Control Policies" registry:

  • NODE-ID-MATCH

We described this access control policy back in Section 5 💜

10.2. A New IETF XML Registry 🌈

This document registers one new URI for the 'redir' namespace in the "IETF XML Registry" defined in [RFC3688] 🗂️

URI: urn:ietf:params:xml:ns:p2p:redir

Registrant Contact: The IESG

XML: N/A, the requested URI is an XML namespace

10.3. Data Kind-ID 🔑

This document adds one new data Kind-ID to the "RELOAD Data Kind-ID" registry:

          +--------------+------------+-----------+
          | Kind         |    Kind-ID |    RFC    |
          +--------------+------------+-----------+
          | REDIR        |      0x104 | [RFC7374] |
          +--------------+------------+-----------+

We defined this Kind-ID back in Section 6 ✨

10.4. RELOAD Services Registry 🎀

IANA set up a brand-new registry for ReDiR namespaces, and here are the deets:

  • Registry Name: RELOAD Services Registry
  • Reference: [RFC7374]
  • Registration Procedure: Specification Required

The entries in this registry are strings naming ReDiR namespace values. The initial contents are:

          +----------------+-----------+
          | Namespace      |     RFC   |
          +----------------+-----------+
          | turn-server    | [RFC7374] |
          +----------------+-----------+
          | voice-mail     | [RFC7374] |
          +----------------+-----------+

The 'turn-server' namespace is for nodes that want to register as providers of a TURN relay service in the RELOAD overlay, and also for nodes that want to find TURN relay service providers in the overlay 🔥 For TURN server discovery, the ReDiR-based service discovery and registration mechanism in this document can be used as an alternative to the TURN server discovery mechanism in the RELOAD base specification [RFC6940]. The 'voice-mail' namespace is meant for a voice mail service built on top of a RELOAD overlay 📞💌

11. References 📚

11.1. Normative References 💖

11.2. Informative Reference 🦋

  • [Redir] Rhea, S., Godfrey, B., Karp, B., Kubiatowicz, J., Ratnasamy, S., Shenker, S., Stoica, I., and H. Yu, "OpenDHT: A Public DHT Service and Its Uses", October 2005.

Acknowledgments 🫶

okay bestie, the authors wanna give a huge shoutout to Marc Petit-Huguenin, Joscha Schneider, Carlos Bernardos, Spencer Dawkins, Barry Leiba, Adrian Farrel, Alexey Melnikov, Ted Lemon, and Stephen Farrell for reviewing the document and leaving comments. literally the MVPs 👑✨

Authors' Addresses 🎀

Here are the authors and how to reach them. Both are from Ericsson in Finland, so if you wanna slide into their emails, here they are 💌

Jouni Maenpaa
Ericsson
Hirsalantie 11
Jorvas  02420
Finland

EMail: Jouni.Maenpaa@ericsson.com


Gonzalo Camarillo
Ericsson
Hirsalantie 11
Jorvas  02420
Finland

EMail: Gonzalo.Camarillo@ericsson.com
📦 where this page comes from