RFC 7019
Application-Layer Multicast Extensions to REsource LOcation And Discovery (RELOAD)
RFC 7019: Application-Layer Multicast Extensions to REsource LOcation And Discovery (RELOAD) 💖
Okay bestie, let's set the scene 🎀 This is an Experimental RFC from the IRTF (Internet Research Task Force) stream, published in September 2013. It's RFC number 7019 with ISSN 2070-1721. The authors are J. Buford (Avaya Labs Research) and M. Kolberg, who is listed as editor (Ed.) from the University of Stirling ✨ The title block doesn't list any RFCs as obsoleted or updated, so nothing to flag there 🙈
Abstract ✨
Okay so this doc defines a RELOAD Usage for Application-Layer Multicast (ALM) 🦋 It also maps ALM onto the RELOAD experimental message type so the two can work together. The whole point is that the ALM Usage can handle a bunch of different ALM control algorithms without caring which overlay it's running on, which is so iconic 👑 Two example algorithms are included, one based on Scribe and one based on P2PCast.
This document is a product of the Scalable Adaptive Multicast Research Group (SAM RG) 🌸
Status of This Memo 📝
Real talk, this is not an Internet Standards Track spec. It's published so people can examine it, try implementing it, and evaluate it 🔍
It defines an Experimental Protocol for the Internet community and comes out of the Internet Research Task Force (IRTF). The IRTF shares results of Internet-related research and development, and those results might not be suitable for deployment 💀 This RFC reflects the consensus of the SAM RG inside the IRTF. Documents the IRSG approves for publication are not candidates for any level of Internet Standard, so see Section 2 of RFC 5741 for the details 🫶
You can check the current status, any errata, and send feedback at http://www.rfc-editor.org/info/rfc7019 💅
Copyright Notice 💜
Copyright (c) 2013 IETF Trust and the people listed as 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) as they stood on the publication date. Please read these carefully, because they spell out your rights and restrictions for this doc 🎀
Table of Contents 🌈
1. Introduction ....................................................4
1.1. Requirements Language ......................................5
2. Definitions .....................................................5
2.1. Overlay Network ............................................5
2.2. Overlay Multicast ..........................................5
2.3. Source-Specific Multicast (SSM) ............................6
2.4. Any-Source Multicast (ASM) .................................6
2.5. Peer .......................................................6
3. Assumptions .....................................................6
3.1. Overlay ....................................................6
3.2. Overlay Multicast ..........................................7
3.3. RELOAD .....................................................7
3.4. NAT ........................................................7
3.5. Tree Topology ..............................................7
4. Architecture Extensions to RELOAD ...............................7
5. RELOAD ALM Usage ................................................9
6. ALM Tree Control Signaling ......................................9
7. ALM Messages Mapped to RELOAD ..................................11
7.1. Introduction ..............................................11
7.2. Tree Lifecycle Messages ...................................12
7.2.1. CreateALMTree ......................................12
7.2.2. CreateALMTreeResponse ..............................13
7.2.3. Join ...............................................13
7.2.4. JoinAccept (Join Response) .........................14
7.2.5. JoinReject (Join Response) .........................15
7.2.6. JoinConfirm ........................................15
7.2.7. JoinConfirmResponse ................................16
7.2.8. JoinDecline ........................................16
7.2.9. JoinDeclineResponse ................................16
7.2.10. Leave .............................................17
7.2.11. LeaveResponse .....................................17
7.2.12. Reform or Optimize Tree ...........................17
7.2.13. ReformResponse ....................................18
7.2.14. Heartbeat .........................................18
7.2.15. Heartbeat Response ................................18
7.2.16. NodeQuery .........................................19
7.2.17. NodeQueryResponse .................................19
7.2.18. Push ..............................................21
7.2.19. PushResponse ......................................22
8. Scribe Algorithm ...............................................22
8.1. Overview ..................................................22
8.2. Create ....................................................23
8.3. Join ......................................................24
8.4. Leave .....................................................24
8.5. JoinConfirm ...............................................24
8.6. JoinDecline ...............................................24
8.7. Multicast .................................................24
9. P2PCast Algorithm ..............................................25
9.1. Overview ..................................................25
9.2. Message Mapping ...........................................25
9.3. Create ....................................................26
9.4. Join ......................................................26
9.5. Leave .....................................................28
9.6. JoinConfirm ...............................................28
9.7. Multicast .................................................28
10. Message Format ................................................28
10.1. ALMHeader Definition .....................................30
10.2. ALMMessageContents Definition ............................31
10.3. Response Codes ...........................................31
11. Examples ......................................................32
11.1. Create Tree ..............................................32
11.2. Join Tree ................................................33
11.3. Leave Tree ...............................................35
11.4. Push Data ................................................35
12. Kind Definitions ..............................................36
12.1. ALMTree Kind Definition ..................................36
13. RELOAD Configuration File Extensions ..........................37
14. IANA Considerations ...........................................37
14.1. ALM Algorithm Types ......................................37
14.2. Message Code Registration ................................38
14.3. Error Code Registration ..................................38
15. Security Considerations .......................................39
16. Acknowledgements ..............................................40
17. References ....................................................40
17.1. Normative Reference ......................................40
17.2. Informative References ...................................401. Introduction ✨
Scalable adaptive multicast is about two big ideas: scaling and adaptability 🦋 Scalability covers the following:
- large group size
- large numbers of small groups
- rate of group membership change
- admission control for QoS
- use with network-layer QoS mechanisms
- varying degrees of reliability
- trees connecting nodes over the global Internet
Adaptability includes these:
- use of different control mechanisms for different multicast trees depending on initial application parameters or application classes
- changing multicast tree structure depending on changes in application requirements, network conditions, and membership
Application-Layer Multicast (ALM) has already been shown to work well where native multicast isn't available, and lots of ALM designs exist 🌸 This ALM Usage focuses on three things:
- ALM implemented in RELOAD-based overlays
- support for a variety of ALM control algorithms
- providing a basis for defining a separate hybrid ALM RELOAD Usage
RELOAD [RELOAD] has an application extension mechanism where a new type of application defines a Usage 💅 A RELOAD Usage defines a set of data types and rules for using them. On top of that, this document adds some new message types and a new ALM algorithm plugin architectural component 🧚
This document reflects the consensus of the SAM RG. It was discussed a lot inside the research group, and also with other Application-Layer Multicast experts, so it's been well stress-tested 🫶
1.1. Requirements Language
Here's the key-word part, and it's important 🔥 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].
2. Definitions 📚
Okay so we're borrowing the vocabulary from Section 3 of [RELOAD], especially the difference between "node", "peer", and "client" 💖
2.1. Overlay Network
Overlay network: An application-layer virtual or logical network with addressable endpoints. It gives you connectivity, routing, and messaging between those endpoints 🦋 People use overlay networks as a base for deploying new network services, or to get a routing topology the underlying physical network can't give you. A lot of peer-to-peer systems are overlay networks running on top of the Internet. In Figure 1, "P" marks overlay peers, and the peers sit in a logical address space. The links in the figure are predecessor/successor links. Depending on the overlay routing model, there may be additional or different links too ✨
P P P P P
..+....+....+...+.....+...
. +P
P+ .
. +P
..+....+....+...+.....+...
P P P P PFigure 1: Overlay Network Example 🌈
2.2. Overlay Multicast
Overlay Multicast (OM): Hosts in a multicast session form an overlay network and use unicast connections between pairs of hosts to get the data around [BUFORD2009] [KOLBERG2010] [BUFORD2008] 🎀 The hosts handle group management, routing, and tree construction all by themselves, with zero help from Internet routers. This is also commonly called Application-Layer Multicast (ALM) or End-System Multicast (ESM) 💜 Systems that use proxies connected in an overlay multicast backbone are called "proxied overlay multicast" or POM.
2.3. Source-Specific Multicast (SSM)
SSM tree: The creator of the tree is the source. The source sends data messages to the tree root, and those messages get forwarded down the tree 🦋
2.4. Any-Source Multicast (ASM) 🎀
okay so ASM trees work like this 🌸 when a node sends a data message, it sends it to its parent AND all its children. and when a node gets a data message from one edge, it forwards it out every other tree edge it's connected to. literally passing the tea down the whole tree 🍵💅
2.5. Peer 🦋
a peer is an autonomous end system that's connected to the physical network and actually shows up for overlay construction, routing, and maintenance. peers chip in their own resources too ✨. some peers can also take on extra jobs like connection relays, super nodes, NAT traversal assistance, and data storage. main character energy fr 👑
3. Assumptions 🧚
3.1. Overlay 💜
peers connect in a big overlay 🌈. it can be used for all kinds of peer-to-peer apps, not just multicast sessions. peers can also take on extra roles in the overlay beyond just being in it and in multicast trees. we assume a single-structured overlay routing algorithm is used. and honestly, any of a bunch of multi-hop, one-hop, or variable-hop overlay algorithms could work 🫶
castro et al. [CASTRO2003] compared multi-hop overlays and found that tree-based construction in one overlay beat using separate overlays for each multicast session 😭. so we use a single overlay instead of separate overlays per multicast session. iykyk 🙈
an overlay multicast algorithm can lean on the overlay's own mechanism for keeping overlay state when churn happens 🔥. for example, a peer may store a bunch of DHT (Distributed Hash Table) entries. when that peer gracefully leaves the overlay, it hands those entries off to the nearest peer 🍓. and when a new peer joins that's closer to some of those entries than the peer currently holding them, those entries get migrated ✨. overlay churn affects multicast trees too, and the remedies include automatic migration of the tree state and automatic rejoin operations for dislocated child nodes 🦋
3.2. Overlay Multicast 🌸
the overlay supports concurrent multiple multicast trees 💖. how many trees can run at once depends on peer and network resources. it's not some built-in property of the overlay itself 💅
3.3. RELOAD 🎀
we use RELOAD [RELOAD] as the peer-to-peer (P2P) overlay for data storage, and as the mechanism peers use to interconnect and route messages 🧚. RELOAD is a generic P2P overlay. app support is defined by profiles called Usages, which is super iconic 👑
3.4. NAT 🌈
some nodes in the overlay may be in a private address space and sitting behind firewalls 🙈. we use the RELOAD mechanisms for NAT traversal. and we allow clients to be leaf nodes in an ALM tree 🫶
3.5. Tree Topology 🍓
all tree control messages get routed in the overlay ✨. two types of data or media topologies are envisioned: 1) tree edges are paths in the overlay, and 2) tree edges are direct connections between a parent and child peer in the tree, formed using the RELOAD AppAttach method 💜
4. Architecture Extensions to RELOAD 🔥
there are two changes, shown in Figure 2 🎀. new ALM messages get mapped to RELOAD Message Transport using the RELOAD experimental message type. a plugin for ALM algorithms handles the ALM state and control. and the ALM algorithm is under control of the application via the Group API [COMMON-API] 💅
+---------+
|Group API|
+---------+
|
------------------- Application ------------------------
+-------+ |
| ALM | |
| Usage | |
+-------+ |
-------------- Messaging Service Boundary --------------
|
+--------+ +-----------+---------+ +---------+
| Storage|<---> | RELOAD | ALM |<-->| ALM Alg |
+--------+ | Message | Messages| +---------+
^ | Transport | |
| +-----------+---------+
v | |
+-------------+ |
| Topology | |
| Plugin | |
+-------------+ |
^ |
v v
+-------------------+
| Forwarding & |
| Link Management |
+-------------------+
---------- Overlay Link Service Boundary --------------
Figure 2: RELOAD Architecture Extensionsthe ALM components work with RELOAD like this 🧚:
- ALM uses the RELOAD data storage functionality to store an ALMTree instance when a new ALM tree is created in the overlay, and to retrieve ALMTree instance(s) for existing ALM trees 💖.
- ALM applications and management tools may use the RELOAD data storage functionality to store diagnostic information about how trees are operating 📊. that includes average number of trees, delay from source to leaf nodes, bandwidth use, and packet loss rate 🌈. diagnostic info may also include statistics specific to the tree root or to any node in the tree ✨.
5. RELOAD ALM Usage 💅
RELOAD apps are restricted in the data types that can be stored in the DHT. the profile of accepted data types for an app is called a Usage 🎀. RELOAD is designed so new apps can easily define new Usages, which is so smart 🧠. new RELOAD Usages are needed for multicast apps, because the data types in base RELOAD and the existing Usages just aren't enough 😭.
we define an ALM Usage in RELOAD 🦋. this ALM Usage is sufficient for apps that need ALM functionality in the overlay. Figure 2 shows the internal structure of the ALM Usage 🌸. it contains the Group API ([COMMON-API]), an ALM algorithm plugin (e.g., Scribe), and the ALM messages that then get sent out to the RELOAD network 🫶.
a RELOAD Usage is required [RELOAD] to define the following:
- Kind-ID and code points
- data structures for each Kind
- access control rules for each Kind
- the Resource Name used to hash to the Resource ID that determines where the Kind is stored
- address restoration after recovery from a network partition (to form a single coherent network)
- the types of connections that can be initiated using AppConnect
an ALM group_id is a RELOAD node_id 🔑. the owner of an ALM group creates a RELOAD node_id as specified in [RELOAD]. that means a group_id gets used as a RELOAD Destination for overlay routing purposes 💜.
6. ALM Tree Control Signaling 🌈
peers use the overlay to support ALM operations such as:
- CreateALMTree
- Join
- Leave
- Reform or optimize tree
there are a variety of algorithms for peers to form multicast trees in the overlay 🍓. the approach here lets multiple algorithms be supported in the overlay, since different algorithms may be more suitable for certain app requirements, and it also supports experimentation 🧪. so overlay messaging for the set of overlay multicast operations MUST carry algorithm identification information 🚨✨.
for example, for small groups the join point might be directly assigned by the rendezvous point 🎀. but for large trees, the Join request might get propagated down the tree, with candidate parents forwarding their position directly to the new node 🌸.
here's a simplistic notation for forming a multicast tree in the overlay 💅. its main advantage is using the overlay for routing both control and data messages 🫶. the group creator doesn't have to be the root of the tree, or even in the tree 👑. it doesn't consider per-node load, admission control, or alternative paths 🙈. after the tree is created, the group_id is expected to be advertised or distributed out of band, perhaps by publishing in the DHT 📣. similarly, joining peers will discover the group_id out of band, perhaps by a lookup in the tree 🔍.
as stated earlier, multiple algorithms will coexist in the overlay 🦋.
- Peer that initiates multicast group:
group_id = create(); // Allocate a unique group_id.
// The root is the nearest
// peer in the overlay.- Any joining peer:
joinTree(group_id); // sends "join group_id" messagethe overlay routes the Join request using the overlay routing mechanism toward the peer with the nearest ID to the group_id 🎯. that peer is the root. peers on the path to the root join the tree as forwarding points 🌳.
- Leave Tree:
leaveTree(group_id); // removes this node from the treethis propagates a Leave request to each child node and to the parent node 👋. if the parent node is a forwarding node and this is its last child, then it propagates a Leave request to its own parent 🍂. a child node that receives a Leave request from a parent sends a Join request to the group_id 🔁.
- Message forwarding:
multicastMsg(group_id, msg);for message forwarding, both Any-Source Multicast (ASM) and Source-Specific Multicast (SSM) approaches may be used 📨✨.
7. ALM Messages Mapped to RELOAD 🧚
7.1. Introduction 💖
in this document, we define messages for overlay multicast tree creation, using an existing protocol (RELOAD) in the P2P-SIP WG [RELOAD] for a universal structured peer-to-peer overlay protocol 🌸. RELOAD provides the mechanism to support a number of overlay topologies. so the overlay multicast framework defined here can be used with P2P-SIP, and it makes the Scalable Adaptive Multicast (SAM) framework overlay agnostic 🦋.
as discussed in the SAM requirements document [SAM-GENERIC], there are a variety of ALM tree formation and tree maintenance algorithms 🌈. the goal of this spec is to be algorithm agnostic, kind of like how RELOAD is overlay algorithm agnostic 🫶. we assume all control messages get propagated using overlay routed messages 🛣️.
the message types needed for ALM behavior are divided into these categories:
- Tree lifecycle (Create, Join, Leave, Reform, Heartbeat)
- Peer region and multicast properties
the message codes are defined in Section 14.2 of this document 🔢. messages are mapped to the RELOAD experimental message type 🎀.
in the following sections, the protocol messages as mapped to RELOAD are discussed 💅. detailed example message flows are provided in Section 11 📖.
in the following descriptions, we use the datatype Dictionary, which is a set of opaque values indexed by an opaque key, with one value for each key 🗝️. a single dictionary entry is represented by a DictionaryEntry, as defined in Section 7.2.3 of the RELOAD document [RELOAD] ✨. the Dictionary datatype is defined as follows:
struct {
DictionaryEntry elements<0..2^16-1>;
} Dictionary;7.2. Tree Lifecycle Messages 🌟
peers use the overlay to transmit the ALM operations defined in this section 💜.
7.2.1. CreateALMTree 🌸
okay so CreateALMTree is how a brand new ALM tree gets born in the overlay, and it's identified by group_id. bestie, the classic move in a DHT-based overlay is that the peer whose peer_id is closest to group_id (but still less than it) becomes the root of the tree 👑. Other overlay types work too, just not the DHT way. And at birth the tree has zero children, so it's giving brand-new-and-empty 🥺
The group_id gets cooked up from a well-known session key, so other peers can find the multicast tree in the overlay. The cooking step MUST be done with the overlay's ID-generation mechanism, no shortcuts 💅
struct {
node_id peer_id;
opaque session_key<0..2^32-1>;
node_id group_id;
Dictionary options;
} ALMTree;peer_id: overlay address of the peer that creates the multicast tree.session_key: a well-known string that, once hashed with the overlay's ID-generation algorithm, produces thegroup_id.group_id: overlay address of the root of the tree.options: a name-value list of properties for the tree, like its max size, who's allowed to join, latency constraints, whether it's built and maintained in a distributed or centralized way, and the Heartbeat interval 🎀
Creating a tree counts as a Store operation, so it gets access control 🔒 The NODE-MATCH access policy from Section 7.3.2 of [RELOAD] is the one that applies.
When CreateALMTree works, an ALMTree structure gets stored in the overlay at node G, the one responsible for group_id. Node G runs the RELOAD-defined StoreReq operation as a side effect of CreateALMTree. And if that StoreReq fails, CreateALMTree fails right along with it 😭
After a successful CreateALMTree, any peer can use the RELOAD Fetch method to grab the ALMTree struct sitting at address group_id. The ALMTree Kind is defined in Section 12.1 ✨
7.2.2. CreateALMTreeResponse 💌
Once a peer gets a CreateALMTree message from node S, it sends back a CreateALMTreeResponse to node S.
struct {
Dictionary options;
} CreateALMTreeResponse;options: a node can hand the requesting node algorithm-dependent parameters about the tree it just made 🧚
7.2.3. Join 🦋
Join is what kicks off the distributed algorithm for a peer to join a specific ALM group. Here's what a Join request looks like 👀 If it works, the joining peer gets told about one or more candidate parent peers, through one or more JoinAccept messages. The actual ALM join algorithm isn't specified in this protocol, so that part's a mystery for now 🔮
struct {
node_id peer_id;
node_id group_id;
Dictionary options;
} Join;peer_id: overlay address of the joining or leaving peergroup_id: overlay address of the root of the treeoptions: a name-value list of options the joining peer is proposing 🍓
RELOAD is a request-response protocol, so JoinAccept and JoinReject are the matching responses to Join. If a JoinReject shows up, that's the end of it for this request, no further action. If a JoinAccept shows up, the joining peer sends either a JoinConfirm or a JoinDecline (more on those below). JoinConfirm gets JoinConfirmResponse back, and JoinDecline gets JoinDeclineResponse back.
Here's how the request-response pairs line up under the RELOAD mechanism:
JoinandJoinAccept: Node C sends a Join request to node P. If node P is down with it, it replies with JoinAccept.JoinandJoinReject: Node C sends a Join request to node P. If node P isn't feeling it, it replies with JoinReject.JoinConfirmandJoinConfirmResponse: If node P sent node C a JoinAccept, and node C says yes with a JoinConfirm request, then node P replies with a JoinConfirmResponse.JoinDeclineandJoinDeclineResponse: If node P sent node C a JoinAccept, and node C passes with a JoinDecline request, then node P replies with a JoinDeclineResponse.
So Join, JoinConfirm, and JoinDecline count as requests under RELOAD. They get mapped onto the RELOAD exp_a_req message and get retransmitted until either a retry limit hits or a matching response comes back 🔁 JoinAccept, JoinReject, JoinConfirmResponse, and JoinDeclineResponse count as responses and get mapped onto the RELOAD exp_a_ans message 💜
The Join behavior goes like this:
if(checkAccept(msg)) {
recvJoins.add(msg.source, msg.group_id)
SEND(JoinAccept(node_id, msg.source, msg.group_id))
}7.2.4. JoinAccept (Join Response) 💌
JoinAccept tells the joining peer that the indicated peer is up for being its parent in the ALM tree named by group_id, with the matching options. A peer MAY get more than one JoinAccept, from different candidate parents in the group_id tree, and that's totally fine ✨ To actually pick a parent, the peer sends a JoinConfirm. A JoinAccept that gets neither a JoinConfirm nor a JoinDecline MUST expire, no ghosting allowed 👻 RELOAD implementations can read a local configuration file for their settings. It's assumed that this file holds the timeout value to use.
struct {
node_id parent_peer_id;
node_id child_peer_id;
node_id group_id;
Dictionary options;
} JoinAccept;parent_peer_id: overlay address of the peer that accepts the joining peerchild_peer_id: overlay address of the joining peergroup_id: overlay address of the root of the treeoptions: a name-value list of options the parent peer accepted 🫶
7.2.5. JoinReject (Join Response) 🙅♀️
When a peer gets a Join request, it answers with a JoinReject to say the request got rejected. Rude but clear 💀
7.2.6. JoinConfirm 💖
If a peer gets a JoinAccept it actually wants, it MUST explicitly accept it with a JoinConfirm message, and it has to do that before the JoinAccept's timer runs out ⏰ The joining peer MUST include only the options from the JoinAccept that it also accepts. That's how the two peers finish negotiating options, bestie, it's a team effort 🤝
struct {
node_id child_peer_id;
node_id parent_peer_id;
node_id group_id;
Dictionary options;
} JoinConfirm;child_peer_id: overlay address of the joining peer, which is about to be a child of the parent peerparent_peer_id: overlay address of the peer that's about to be the parent of the joining peergroup_id: overlay address of the root of the treeoptions: a name-value list of options both peers accepted 🌈
The JoinConfirm behavior is described below:
if(recvJoins.contains(msg.source,msg.group_id)){
if !(groups.contains(msg.group_id)) {
groups.add(msg.group_id)
SEND(msg,msg.group_id)
}
groups[msg.group_id].children.add(msg.source)
recvJoins.del(msg.source, msg.group_id)
}7.2.7. JoinConfirmResponse 🧁
A peer that gets a JoinConfirm message answers it with a JoinConfirmResponse message. Simple and iconic 💅
7.2.8. JoinDecline 🙅♀️
If a peer gets a JoinAccept it doesn't want, it MAY explicitly decline it with a JoinDecline message. Totally optional, but a polite no is always iconic 🌸
struct {
node_id peer_id;
node_id parent_peer_id;
node_id group_id;
} JoinDecline;peer_id: overlay address of the joining peer that's declining the JoinAcceptparent_peer_id: overlay address of the peer that sent this peer the JoinAcceptgroup_id: overlay address of the root of the tree
The JoinDecline behavior goes like this:
if(recvJoins.contains(msg.source,msg.group_id))
recvJoins.del(msg.source, msg.group_id)7.2.9. JoinDeclineResponse 🧚
A peer that gets a JoinConfirm message answers it with a JoinDeclineResponse message. Yes, it really says JoinConfirm here, so that's the wording we've got 🙈
7.2.10. Leave 👋
A peer that's part of an ALM tree named by group_id and wants to detach from a child or parent peer SHOULD send a Leave request to the peer it's detaching from. And if a peer gets a Leave request from someone who isn't on its parent or child lists, it SHOULD ignore that message 🙃
struct {
node_id peer_id;
node_id group_id;
Dictionary options;
} Leave;peer_id: overlay address of the leaving peergroup_id: overlay address of the root of the treeoptions: a name-value list of options
The Leave request behavior can be described as:
groups[msg.group_id].children.remove(msg.source)
if (groups[msg.group].children = 0)
SEND(msg,groups[msg.group_id].parent)7.2.11. LeaveResponse 🌷
A peer that gets a Leave request answers with a LeaveResponse message. Bye bye, bestie 👋
7.2.12. Reform or Optimize Tree 🔧
This one triggers a reorganization of either the whole tree or just a subtree. It MAY include hints naming specific peers to reconnect to as recommended parents or children. A peer that receives this message MAY ignore it, MAY pass it along to other peers in its subtree, and MAY run local algorithms to pick its preferred parent and/or child peers. Freedom-of-choice energy 🦋
struct {
node_id group_id;
node_id peer_id;
Dictionary options;
} Reform;group_id: overlay address of the root of the treepeer_id: if this is left out, the tree gets reorganized starting from the root. Otherwise it only gets reorganized at the subtree identified bypeer_id. 🌳options: a name-value list of options
7.2.13. ReformResponse 🍓
A peer that gets a Reform message answers with a ReformResponse.
struct {
Dictionary options;
} ReformResponse;options: algorithm-dependent info about how the Reform operation turned out ✨
7.2.14. Heartbeat 💓
A child node tells its adjacent parent nodes in the tree that it's still alive 🫀 If a parent node doesn't get a Heartbeat within N Heartbeat time intervals, it MUST treat that as an explicit Leave request from the unresponsive peer. Ghosted, officially. N is configurable, and RELOAD implementations can read a local configuration file for it. It's assumed that this file has the value for N to use 🎀
struct {
node_id peer_id_src;
node_id peer_id_dst;
node_id group_id;
Dictionary options;
} Heartbeat;peer_id_src: source of the Heartbeatpeer_id_dst: destination of the Heartbeatgroup_id: overlay address of the root of the treeoptions: an algorithm can use the Heartbeat message to share state information with adjacent nodes in the tree 🧠
7.2.15. Heartbeat Response 💜
A parent node answers a Heartbeat from a child node with a HeartbeatResponse, which says "got it, you're good" 🫶
7.2.16. NodeQuery 🔍
NodeQuery is how you find out about the state and performance of the tree on a per-node basis. A bunch of nodes could get queried to build a centralized view of the multicast trees, kind of like a web crawler crawling around 🕷️ It's giving detective energy 🕵️♀️
struct {
node_id peer_id_src;
node_id peer_id_dst;
} NodeQuery;peer_id_src: source of the querypeer_id_dst: destination of the query
7.2.17. NodeQueryResponse ✨
okay so the response to a NodeQuery message carries a NodeStatistics instance for this node 💅 it's basically the node's whole report card 🎀
public struct {
uint32 node_lifetime;
uint32 total_number_trees;
uint16 number_algorithms_supported;
uint8 algorithms_supported[32];
TreeData max_tree_data;
uint16 number_active_trees;
TreeData tree_data<0..2^8-1>;
ImplementationInfo impl_info;
} NodeStatistics;node_lifetime: time the node has been alive in seconds since last restart ⏰total_number_trees: total number of trees this node has been part of during the node lifetime 🌳number_algorithms_supported: value between 0..2^16-1 corresponding to the number of algorithms supported 🔢algorithms_supported: list of algorithms, each byte encoded using the corresponding algorithm code 🧩max_tree_data: data about tree with largest number of nodes that this node was part of. NodeQuery can be used to crawl all the nodes in an ALM tree to fill this field. This is intended to support monitoring, algorithm design, and general experimentation with ALM in RELOAD. 🕵️♀️ this one is the main character of the stats, bestienumber_active_trees: current number of trees that the node is part of 🌸tree_data: details of each active tree; the number of such is specified bynumber_active_trees📋impl_info: information about the implementation of this Usage 🧠
public struct {
uint32 tree_id;
uint8 algorithm;
node_id tree_root;
uint8 number_parents;
node_id parent<0..2^8-1>;
uint16 number_child_nodes;
node_id children<0..2^16-1>;
uint32 path_length_to_root;
uint32 path_delay_to_root;
uint32 path_delay_to_child;
} TreeData;tree_id: the ID of the tree 🆔algorithm: code identifying the multicast algorithm used by this tree 🦋tree_root: node_id of tree root, or 0 if unknown 👑number_parents: 0 .. 2^8-1 indicates number of parent nodes for this node 👪parent: the RELOAD node_id of each parent node 💜number_child_nodes: 0..2^16-1 indicates number of children 🧸children: the RELOAD node_id of each child node 🧚path_length_to_root: number of overlay hops to the root of the tree 🛤️path_delay_to_root: RTT in milliseconds to root node ⚡path_delay_to_child: last measured RTT in milliseconds to child node with largest RTT 🍓
public struct {
uint32 join_confirm_timeout;
uint32 heartbeat_interval;
uint32 heartbeat_response_timeout;
uint16 info_length;
uint8 info<0..2^16-1>;
} ImplementationInfo;join_confirm_timeout: The default time for JoinConfirm/JoinDecline, intended to provide sufficient time for a Join request to receive all responses and confirm the best choice. Default value is 5000 msec. An implementation can change this value. ⏳ basically the "wait, let me think" window before a Join gets locked inheartbeat_interval: The default Heartbeat interval is 2000 msec. Different interoperating implementations could use different intervals. 💓heartbeat_response_timeout: The default Heartbeat timeout is 5000 msec and is the max time between Heartbeat reports from an adjacent node in the tree at which point the Heartbeat is missed. 🚨 ghosting threshold, iykykinfo_length: length of the info field 📏info: implementation-specific information, such as name of implementation, build version, and implementation-specific features 🎀 the vibe check of the whole node
7.2.18. Push 🦋
okay this is the glow-up moment ✨ a peer sends arbitrary multicast data to other peers in the tree, and nodes in the tree forward this message to adjacent nodes in the tree in an algorithm-dependent way 📣
struct {
node_id group_id;
uint8 priority;
uint32 length;
uint8 data<0..2^32-1>;
} Push;group_id: overlay address of root of the ALM tree 🌈priority: the relative priority of the message; highest priority is 255. A node may ignore this field. 🙈 so yeah, nodes can totally skip this one if they wantlength: length of the data field in bytes 📐data: the data 💌
In pseudocode, the behavior of Push can be described as:
foreach(groups[msg.group_id].children as node_id)
SEND(msg,node_id)
if memberOf(msg.group_id)
invokeMessageHandler(msg.group_id, msg)7.2.19. PushResponse 💬
after receiving a Push message from node S, the receiving peer sends a PushResponse to node S 🫶
struct {
Dictionary options;
} PushResponse;options: A node may provide feedback to the sender about previous Push messages in some window, for example, the last N Push messages. The feedback could include, for each Push message received, the number of adjacent nodes that were forwarded the Push message and the number of adjacent nodes from which a PushResponse was received. 📊 receipts, but make it multicast
8. Scribe Algorithm 🍓
8.1. Overview
Figure 3 shows a mapping between RELOAD ALM messages (as defined in Section 5 of this document) and Scribe messages as defined in [CASTRO2002]. bestie this table is the cheat sheet 📖
+---------+-------------------+-----------------+
| Section |RELOAD ALM Message | Scribe Message |
+---------+-------------------+-----------------+
| 7.2.1 | CreateALMTree | Create |
+---------+-------------------+-----------------+
| 7.2.3 | Join | Join |
+---------+-------------------+-----------------+
| 7.2.4 | JoinAccept | |
+---------+-------------------+-----------------+
| 7.2.6 | JoinConfirm | |
+---------+-------------------+-----------------+
| 7.2.8 | JoinDecline | |
+---------+-------------------+-----------------+
| 7.2.10 | Leave | Leave |
+---------+-------------------+-----------------+
| 7.2.12 | Reform | |
+---------+-------------------+-----------------+
| 7.2.14 | Heartbeat | |
+---------+-------------------+-----------------+
| 7.2.16 | NodeQuery | |
+---------+-------------------+-----------------+
| 7.2.18 | Push | Multicast |
+---------+-------------------+-----------------+
| | Note 1 | deliver |
+---------+-------------------+-----------------+
| | Note 1 | forward |
+---------+-------------------+-----------------+
| | Note 1 | route |
+---------+-------------------+-----------------+
| | Note 1 | send |
+---------+-------------------+-----------------+Figure 3: Mapping to Scribe Messages
Note 1: These Scribe messages are handled by RELOAD messages.
The following sections describe the Scribe algorithm in more detail. 🔍
8.2. Create
This message will create a group with group_id. This message MUST be delivered to the node whose node_id is closest to the group_id. This node becomes the rendezvous point and root for the new multicast tree. Groups MAY have multiple sources of multicast messages. 🌟 the group's birthday party, and the closest node hosts
8.3. Join
To join a multicast tree, a node SHOULD send a Join request with the group_id as the key. This message gets routed by the overlay to the rendezvous point of the tree. If an intermediate node is already a forwarder for this tree, it SHOULD add the joining node as a child. Otherwise, the node SHOULD create a child table for the group and add the joining node. It SHOULD then send the Join request towards the rendezvous point terminating the Join request from the child. 🙋♀️
To adapt the Scribe algorithm to the ALM Usage proposed here, after a Join request is accepted, a JoinAccept message MUST be returned to the joining node. 💖
8.4. Leave
When leaving a multicast group, a node SHOULD change its local state to indicate that it left the group. If the node has no children in its table, it MUST send a Leave request to its parent, from where it SHOULD travel up the multicast tree and stop at a node that still has children remaining after removing the leaving node. 👋 bye bye, but make it tidy
8.5. JoinConfirm
This message is not part of the Scribe protocol but is required by the basic protocol proposed in this document. Thus, the Usage MUST send this message to confirm a joining node accepting its parent node. ✅
8.6. JoinDecline
Like JoinConfirm, this message is not part of the Scribe protocol. Thus, the Usage MUST send this message if a peer receiving a JoinAccept message wishes to decline it. 🙅♀️
8.7. Multicast
A message to be multicast to a group MUST be sent to the rendezvous node from where it is forwarded down the tree. If a node is a member of the tree rather than just a forwarder, it SHOULD pass the multicast data up to the application. 📣🎀
9. P2PCast Algorithm 🧚
9.1. Overview
P2PCast [P2PCAST] creates a forest of related trees to increase load balancing. P2PCast is independent of the underlying P2P substrate. Its goals and approach are similar to SplitStream [SPLITSTREAM] (which assumes Pastry as the P2P overlay). In P2PCast, the content provider splits the stream of data into f stripes. Each tree in the forest of multicast trees is an (almost) full tree of arity f. These trees are conceptually separate: every node of the system appears once in each tree, with the content provider being the source in all of them. To ensure that each peer contributes as much bandwidth as it receives, every node is a leaf in all the trees except for one, in which the node will serve as an internal node (proper tree of this node). To reduce the complexity of the discussion that follows, the remainder of this section will assume that f = 2. However, the algorithm scales for any number f. 🌈 a whole forest of trees, and everybody gets a branch
P2PCast distinguishes the following types of nodes:
- Incomplete Node: A node with less than f children in its proper stripe 🥺
- Only-Child Node: A node whose parent (in any multicast tree) is an incomplete node 👶
- Complete Node: A node with exactly f children in its proper stripe 💪
- Special Node: A single node that is a leaf in all multicast trees of the forest ⭐
9.2. Message Mapping
Okay bestie, so here's the map 🗺️✨ Figure 4 shows how the RELOAD ALM messages from Section 5 of this document line up with the P2PCast messages in [P2PCAST]. Lowkey the most useful table in the whole doc 💅
+---------+-------------------+-----------------+
| Section |RELOAD ALM Message | P2PCast Message |
+---------+-------------------+-----------------+
| 7.2.1 | CreateALMTree | Create |
+---------+-------------------+-----------------+
| 7.2.3 | Join | Join |
+---------+-------------------+-----------------+
| 7.2.4 | JoinAccept | |
+---------+-------------------+-----------------+
| 7.2.6 | JoinConfirm | |
+---------+-------------------+-----------------+
| 7.2.8 | JoinDecline | |
+---------+-------------------+-----------------+
| 7.2.10 | Leave | Leave |
+---------+-------------------+-----------------+
| 7.2.12 | Reform | Takeon |
| | | Substitute |
| | | Search |
| | | Replace |
| | | Direct |
| | | Update |
+---------+-------------------+-----------------+
| 7.2.14 | Heartbeat | |
+---------+-------------------+-----------------+
| 7.2.16 | NodeQuery | |
+---------+-------------------+-----------------+
| 7.2.18 | Push | Multicast |
+---------+-------------------+-----------------+
Figure 4: Mapping to P2PCast MessagesNext up, the P2PCast messages get the full breakdown in more detail 🦋
9.3. Create
This message creates a group with group_id 🌸 It MUST be delivered to the node whose node_id is closest to the group_id. That node becomes the rendezvous point and root for the new multicast tree 👑 The rendezvous point will maintain f subtrees.
9.4. Join
Main character moment alert 🎀 To join a multicast tree, a joining node N MUST send a Join request to a random node A already part of the tree. Depending on what kind of node A is, the joining algorithm goes like this:
- Incomplete Node: Node A will arbitrarily select for which tree it wants to serve as an internal node and adopt N in that tree. In the other tree, node N will adopt node A as a child (taking node A's place in the tree), thus becoming an internal node in the stripe that node A didn't choose.
- Only-Child Node: As this node has a parent that is an incomplete node, the joining node will be redirected to the parent node and will handle the request as detailed above.
- Complete Node: The contacted node A must be a leaf in the other tree. If node A is a leaf node in Stripe 1, node N will become an internal node in Stripe 1, taking the place of node A and adopting it at the same time. To find a place for itself in the other stripe, node N starts a random walk down the subtree rooted at the sibling of node A (if node A is the root and thus does not have siblings, node N is sent directly to a leaf in that tree), which ends as soon as node N finds an incomplete node or a leaf. In this case, node N is adopted by the incomplete node.
- Special Node: as this node is a leaf in all subtrees, the joining node MAY adopt the node in one tree and become a child in the other.
P2PCast uses its own defined messages for communication between nodes during reorganization 🔄 To use P2PCast in this context, those messages get wrapped up in the message type Reform. So the P2PCast message goes inside the options parameter of Reform 🎁 These are the reorganization messages P2PCast defines:
- Takeon: To take another peer as a child
- Substitute: To take the place of a child of some peer
- Search: To obtain the child of a node in a particular stripe
- Replace: Different from Substitute in that the calling node that makes a node its child sheds off a random child
- Direct: To direct a node to its would-be parent
- Update: A node sends its updated state to its children
To adapt the P2PCast algorithm to the ALM Usage proposed here, after a Join request is accepted, a JoinAccept message MUST be returned to the joining node (one for every subtree) 💖
9.5. Leave
Leaving is still a vibe 🦋 When a node leaves a multicast group, it changes its local state to show that it left. Unless the leaving node is the root of the tree, it has to be complete or incomplete in its proper tree. In the other trees, the node is a leaf and can just disappear by notifying its parent 👋 In the proper tree, if the node is incomplete, it gets replaced by its child. But if the node is complete, a gap opens up and gets filled by a random child. If that child is incomplete, it can simply fill the gap. If it's complete though, it needs to shed a random child. That child gets directed to its sibling, which sheds a random child of its own. This process ripples down the tree until the next-to-last level is reached. The shed node is then taken as a child by the parent of the deleted node in the other stripe 🌈
Again, for the reorganization of the tree, the Reform message type is used, same as in the previous section ✨
9.6. JoinConfirm
Okay this one's a little different 👀 This message is not part of the P2PCast protocol, but it is required by the basic protocol defined in this document. So the Usage MUST send this message to confirm that a joining node is accepting its parent node 🫶 Just like with Join and JoinAccept, this MUST be carried out for every subtree.
9.7. Multicast
Multicast is where the data actually flies 🚀 A message to be multicast to a group MUST be sent to the rendezvous node, where it gets forwarded down the tree by being split into k stripes. Each stripe is then sent via a subtree 🌊 If a receiving node is a member of the tree rather than just a forwarder, it MAY pass the multicast data up to the application 💜
10. Message Format
Every message gets mapped to the RELOAD experimental message type 🎀 The mapping is shown in Figure 5. The message codes are listed in Section 14.2. The format of the body of a message is provided in [RELOAD].
+-------------------------+------------------+
| Message |RELOAD Code Point |
+-------------------------+------------------+
| CreateALMTree | exp_a_req |
+-------------------------+------------------+
| CreateALMTreeResponse | exp_a_ans |
+-------------------------+------------------+
| Join | exp_a_req |
+-------------------------+------------------+
| JoinAccept | exp_a_ans |
+-------------------------+------------------+
| JoinReject | exp_a_ans |
+-------------------------+------------------+
| JoinConfirm | exp_a_req |
+-------------------------+------------------+
| JoinConfirmResponse | exp_a_ans |
+-------------------------+------------------+
| JoinDecline | exp_a_req |
+-------------------------+------------------+
| JoinDeclineResponse | exp_a_ans |
+-------------------------+------------------+
| Leave | exp_a_req |
+-------------------------+------------------+
| LeaveResponse | exp_a_ans |
+-------------------------+------------------+
| Reform | exp_a_req |
+-------------------------+------------------+
| ReformResponse | exp_a_ans |
+-------------------------+------------------+
| Heartbeat | exp_a_req |
+-------------------------+------------------+
| HeartbeatResponse | exp_a_ans |
+-------------------------+------------------+
| NodeQuery | exp_a_req |
+-------------------------+------------------+
| NodeQueryResponse | exp_a_ans |
+-------------------------+------------------+
| Push | exp_a_req |
+-------------------------+------------------+
| PushResponse | exp_a_ans |
+-------------------------+------------------+
Figure 5: RELOAD Message Code MappingFor Data Kind-IDs, the RELOAD specification [RELOAD] states: "Code points in the range 0xF0000001 to 0xFFFFFFFE are reserved for private use". ALM Usage Kind-IDs are defined in that private use range 🔒
All ALM Usage messages map to the RELOAD Message Extension mechanism 🧚
Code points for the Kinds defined in this document MUST NOT conflict with any defined code points for RELOAD 🚫 RELOAD defines exp_a_req and exp_a_ans for experimental purposes, and this specification uses only these message types for all ALM messages. RELOAD defines the MessageContents data structure, and the ALM mapping uses its fields as follows:
- message_code: exp_a_req for requests and exp_a_ans for responses
- message_body: contains one instance of ALMHeader followed by one instance of ALMMessageContents
- extensions: unused
10.1. ALMHeader Definition
struct {
uint32 sam_token;
uint16 alm_algorithm_id;
uint8 version;
} ALMHeader;Here's how the fields in ALMHeader work 💅
- sam_token: The first four bytes identify this message as an ALM message. This field MUST contain the value
0xD3414D42(the string"SAMB"with the high bit of the first byte set) 🎯 - alm_algorithm_id: The ALM Algorithm ID of the ALM algorithm being used. Each multicast tree uses only one algorithm. Trees with different ALM algorithms can coexist and can share the same nodes 🌸 ALM Algorithm ID codes are defined in Section 14.1.
- version: The version of the ALM protocol being used. This is a fixed-point integer between 0.1 and 25.4. This document describes version 1.0 with a value of
0xA✨
10.2. ALMMessageContents Definition
struct {
uint16 alm_message_code;
opaque alm_message_body;
} ALMMessageContents;And the fields in ALMMessageContents, bestie 💖
- alm_message_code: This indicates the message being sent. The message codes are listed in Section 14.2.
- alm_message_body: The message body itself, represented as a variable-length string of bytes. The bytes themselves depend on the code value. See Sections 8 and 9, which describe the various ALM methods for the definitions of the payload contents 🦋
10.3. Response Codes ✨
okay so the response codes are defined in Section 6.3.3.1 of [RELOAD] 🎀 this spec maps onto RELOAD ErrorResponse like this:
ErrorResponse.error_code = Error_Exp_A;Error_info carries an ALMErrorResponse instance 💖
public struct {
uint16 alm_error_code;
opaque alm_error_info<0..2^16-1>;
} ALMErrorResponse;alm_error_code is where the drama is 💅 these are the error code values that are defined. The numeric values live in Section 14.3 🔢
Error_Unknown_Algorithm: the multicast algorithm is not known or not supported 🙈Error_Child_Limit_Reached: the maximum number of child nodes has been reached for this node 🌸Error_Node_Bandwidth_Reached: the overall data bandwidth limit through this node has been reached 📉Error_Node_Conn_Limit_Reached: the total number of connections to this node has been reached 🦋Error_Link_Cap_Limit_Reached: the capacity of a link has been reached 🧚Error_Node_Mem_Limit_Reached: an internal memory capacity of the node has been reached 💜Error_Node_CPU_Cap_Limit_Reached: an internal processing capacity of the node has been reached 😭Error_Path_Limit_Reached: the maximum path length in hop count over the multicast tree has been reached 🛤️Error_Path_Delay_Limit_Reached: the maximum path length in message delay over the multicast tree has been reached ⏳Error_Tree_Fanout_Limit_Reached: the maximum fanout of a multicast tree has been reached 🌳Error_Tree_Depth_Limit_Reached: the maximum height of a multicast tree has been reached 📏Error_Other: a human-readable description is placed in thealm_error_infofield 📝
11. Examples 🎬
all the peers in these examples are assumed to have finished bootstrapping, so everyone's already in the group chat 🫶 "Pn" means peer N, and "group_id" is the peer responsible for storing the ALMTree instance with that group_id 👑
11.1. Create Tree 🌸
a node with "NODE-MATCH" rights sends a CreateALMTree request to the group_id node. that node also has NODE-MATCH rights for its own address 💅 the group_id node decides whether to create the new tree and, if it does, does a local StoreReq. once CreateALMTree succeeds, the ALMTree instance can be retrieved using Fetch ✨ the message flow for creating a tree is shown in Figure 6 🦋
P1 P2 P3 P4 group_id
| | | | |
| | | | |
| | | | |
| CreateALMTree | | |
|------------------------------->|
| | | | |
| | | | | StoreReq
| | | | |--+
| | | | | |
| | | | | |
| | | | |<-+
| | | | | StoreResponse
| | | | |--+
| | | | | |
| | | | | |
| | | | |<-+
| | | | |
| | | | |
| | CreateALMTreeResponse |
|<-------------------------------|
| | | | |
| | | | |
| Fetch | | |
|------------------------------->|
| | | | |
| | | | |
| | FetchResponse |
|<-------------------------------|
| | | | |Figure 6: Message Flow Example for CreateALMTree 🎀
11.2. Join Tree 🌈
P1 joins the node group_id as a child node 💖 then P2 joins the tree as a child of P1, and P4 joins the tree as a child of P1 too 🧚 the message flow is in Figure 7 ✨
P1 P2 P3 P4 group_id
| | | | |
| | | | |
| Join |
|------------------------------->|
| | | | |
| JoinAccept |
|<-------------------------------|
| | | | |
| | | | |
| |Join |
| |----------------------->|
| | | | |
| Join|
|<-------------------------------|
| | | | |
|JoinAccept | | |
|------>| | | |
| | | | |
|JoinConfirm | | |
|<------| | | |
| | | | |
| | | |Join |
| | | |------>|
| | | | Join |
|<-------------------------------|
| | | | |
| Join | | | |
|------>| | | |
| | | | |
| JoinAccept | | |
|----------------------->| |
| | | | |
| | JoinAccept | |
| |--------------->| |
| | | | |
| | | | |
| | JoinConfirm | |
|<-----------------------| |
| | | | |
| | JoinDecline | |
| |<---------------| |
| | | | |
| | | | |Figure 7: Message Flow Example for Tree Join 🦋
11.3. Leave Tree 🍓
P1 P2 P3 P4 group_id
| | | | |
| | | | |
| | | Leave | |
|<-----------------------| |
| | | | |
| LeaveResponse | | |
|----------------------->| |
| | | | |
| | | | |Figure 8: Message Flow Example for Leave Tree 👋
11.4. Push Data 📣
the multicast data gets pushed recursively, P1 => group_id => P1 => P2, P4, following the tree topology we built in the Join example above 🌳 an example message flow is in Figure 9 💅
P1 P2 P3 P4 group_id
| | | | |
| Push | | | |
|------------------------------->|
| | | | |
| | | PushResponse|
|<-------------------------------|
| | | | |
| | | | Push|
|<-------------------------------|
| | | | |
| PushResponse | | |
|------------------------------->|
| | | | |
|Push | | | |
|------>| | | |
| | | | |
|PushResponse | | |
|<------| | | |
| | | | |
| Push | | | |
|----------------------->| |
| | | | |
| | PushResponse | |
|<-----------------------| |
| | | | |
| | | | |
| | | | |Figure 9: Message Flow Example for Pushing Data 🚀
12. Kind Definitions 🧸
12.1. ALMTree Kind Definition 🍭
this section defines the ALMTree Kind per Section 7.4.5 of [RELOAD] 🎀 an instance of the ALMTree Kind gets stored in the overlay for each ALM tree instance, at the address group_id 💜
Kind-ID: 0xF0000001. (this is a private-use code point per Section 14.6 of [RELOAD] 🔒) the Resource Name for the ALMTree Kind-ID is the session_key that identifies the ALM tree 🪪
Data Model: the data model is the ALMTree structure 🏗️
Access Control: NODE-MATCH. the node performing the store operation is required to have NODE-MATCH access 🚪
Meaning: the meaning of the fields is given in Section 7.2.1 📖
struct {
node_id peer_id;
opaque session_key<0..2^32-1>;
node_id group_id;
Dictionary options;
} ALMTree;13. RELOAD Configuration File Extensions 🌷
there are no ALM parameters defined for the RELOAD configuration file, so this one's a chill little section 😌
14. IANA Considerations 🧾
this section lists the new code points that this document registers 🍓
14.1. ALM Algorithm Types 🌟
IANA has created the "SAM ALM Algorithm IDs" registry 📋 the entries in this registry are 16-bit integers that name Application-Layer Multicast algorithms, as described in Section 10.1 of this document 🦋 code points in the range 0x0003 to 0x7FFF SHALL be registered via RFC 5226 [RFC5226] Expert Review 🔎 code points in the range 0x8000 to 0xFFFF are reserved for private use 🔐 the initial contents of this registry are in Figure 10 💅
+----------------+-------------------+-----------+
| Algorithm Name | ALM Algorithm ID | RFC |
+----------------+-------------------+-----------+
| INVALID-ALG | 0x0000 | RFC 7019 |
| SCRIBE-SAM | 0x0001 | RFC 7019 |
| P2PCAST-SAM | 0x0002 | RFC 7019 |
| Reserved | 0x8000-0xFFFF | RFC 7019 |
+----------------+-------------------+-----------+Figure 10: "SAM ALM Algorithm IDs" Registry Allocations 🌈
these values were made available for experimentation 🧪 they are not meant for vendor-specific use of any sort, and they MUST NOT be used for operational deployments ⚠️
14.2. Message Code Registration ✨
Okay bestie, so IANA made a registry called "SAM ALM Message Codes" 💅 Its entries are 16-bit integers that name the message codes from Section 10.2 of this document. Code points in the range 0x0014 to 0x7FFF SHALL be registered via RFC 5226 [RFC5226] Expert Review. Code points in the range 0x8000 to 0xFFFF are reserved for private use. Here's what's in it at the start 🎀
+-------------------------+----------------------+-----------+
| Message Code Name | Message Code Value | RFC |
+-------------------------+----------------------+-----------+
| InvalidMessageCode | 0x0000 | RFC 7019 |
| CreateALMTree | 0x0001 | RFC 7019 |
| CreateALMTreeResponse | 0x0002 | RFC 7019 |
| Join | 0x0003 | RFC 7019 |
| JoinAccept | 0x0004 | RFC 7019 |
| JoinReject | 0x0005 | RFC 7019 |
| JoinConfirm | 0x0006 | RFC 7019 |
| JoinConfirmResponse | 0x0007 | RFC 7019 |
| JoinDecline | 0x0008 | RFC 7019 |
| JoinDeclineResponse | 0x0009 | RFC 7019 |
| Leave | 0x000A | RFC 7019 |
| LeaveResponse | 0x000B | RFC 7019 |
| Reform | 0x000C | RFC 7019 |
| ReformResponse | 0x000D | RFC 7019 |
| Heartbeat | 0x000E | RFC 7019 |
| HeartbeatResponse | 0x000F | RFC 7019 |
| NodeQuery | 0x0010 | RFC 7019 |
| NodeQueryResponse | 0x0011 | RFC 7019 |
| Push | 0x0012 | RFC 7019 |
| PushResponse | 0x0013 | RFC 7019 |
| Reserved | 0x8000-0xFFFF | RFC 7019 |
+-------------------------+----------------------+-----------+Figure 11: "SAM ALM Message Codes" Registry Allocations
These values are here for experimenting 🧪 They are not meant for vendor-specific use of any sort, and they MUST NOT be used for operational deployments. Please don't ship these in the real world, babe 🙈
14.3. Error Code Registration 🚨
IANA also made a "SAM ALM Error Codes" registry 🫶 Its entries are 16-bit integers for the error codes from Section 10.3 of this document. Code points in the range 0x000D to 0x7FFF SHALL be registered via RFC 5226 [RFC5226] Expert Review. Code points in the range 0x8000 to 0xFFFF are reserved for private use. The starter lineup looks like this:
+----------------------------------+---------------+-----------+
| Error Code Name | Code Value | RFC |
+----------------------------------+---------------+-----------+
| InvalidErrorCode | 0x0000 | RFC 7019 |
| Error_Unknown_Algorithm | 0x0001 | RFC 7019 |
| Error_Child_Limit_Reached | 0x0002 | RFC 7019 |
| Error_Node_Bandwidth_Reached | 0x0003 | RFC 7019 |
| Error_Node_Conn_Limit_Reached | 0x0004 | RFC 7019 |
| Error_Link_Cap_Limit_Reached | 0x0005 | RFC 7019 |
| Error_Node_Mem_Limit_Reached | 0x0006 | RFC 7019 |
| Error_Node_CPU_Cap_Limit_Reached | 0x0007 | RFC 7019 |
| Error_Path_Limit_Reached | 0x0008 | RFC 7019 |
| Error_Path_Delay_Limit_Reached | 0x0009 | RFC 7019 |
| Error_Tree_Fanout_Limit_Reached | 0x000A | RFC 7019 |
| Error_Tree_Depth_Limit_Reached | 0x000B | RFC 7019 |
| Error_Other | 0x000C | RFC 7019 |
| Reserved | 0x8000-0xFFFF | RFC 7019 |
+----------------------------------+---------------+-----------+Figure 12: "SAM ALM Error Codes" Registry Allocations
Same deal as the message codes: these values are for experimentation only 🧪 They are not meant for vendor-specific use of any sort, and they MUST NOT be used for operational deployments. Experiment, don't deploy 💜
15. Security Considerations 🔐
Okay, this part is seriously important, so pay attention 👑 Overlays are vulnerable to DoS and collusion attacks. This document is NOT solving overlay security issues, so please don't think it does 😭 We assume that the node authentication model as defined in [RELOAD] will be used.
Security issues specific to ALM usage include the following:
- The right to create group_id at some node_id
- The right to store Tree info at some location in the DHT
- A limit on number of messages per second and bandwidth use
- The right to join an ALM tree
16. Acknowledgements 🫶
Huge shoutout to Marc Petit-Huguenin, Michael Welzl, Joerg Ott, and Lars Eggert, who gave important comments on earlier versions of this document 🌸 You're all iconic 💖
17. References 📚
17.1. Normative Reference
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.17.2. Informative References
[BUFORD2008] Buford, J. and H. Yu, "P2P: Overlay Multicast",
Encyclopedia of Wireless and Mobile Communications,
2008, <http://www.tandfonline.com/doi/abs/10.1081/
E-EWMC-120043583>.
[BUFORD2009] Buford, J., Yu, H., and E. Lua, "P2P Networking and
Applications (Chapter 9)", Morgan Kaufman, 2009,
<http://www.sciencedirect.com/science/book/
9780123742148>.
[CASTRO2002] Castro, M., Druschel, P., Kermarrec, A., and A.
Rowstron, "SCRIBE: A large-scale and decentralized
application-level multicast infrastructure", IEEE
Journal on Selected Areas in Communications, Vol. 20,
No. 8, October 2002, <http://ieeexplore.ieee.org/xpl/
login.jsp?tp=&arnumber=1038579>.
[CASTRO2003] Castro, M., Jones, M., Kermarrec, A., Rowstron, A.,
Theimer, M., Wang, H., and A. Wolman, "An Evaluation of
Scalable Application-level Multicast Built Using Peer-
to-peer Overlays", Proceedings of IEEE INFOCOM 2003,
April 2003, <http://ieeexplore.ieee.org/xpl/
login.jsp?tp=&arnumber=1208986>.
[COMMON-API] Waehlisch, M., Schmidt, T., and S. Venaas, "A Common
API for Transparent Hybrid Multicast", Work in
Progress, April 2013.
[KOLBERG2010] Kolberg, M., "Employing Multicast in P2P Overlay
Networks", Handbook of Peer-to-Peer Networking, 2010,
<http://link.springer.com/content/pdf/
10.1007%2F978-0-387-09751-0_30.pdf>.
[P2PCAST] Nicolosi, A. and S. Annapureddy, "P2PCast: A Peer-to-
Peer Multicast Scheme for Streaming Data", Stanford
Secure Computer Systems Group Report, May 2003,
<http://www.scs.stanford.edu/~reddy/research/p2pcast/
report.pdf>.
[RELOAD] Jennings, C., Lowekamp, B., Ed., Rescorla, E., Baset,
S., and H. Schulzrinne, "REsource LOcation And
Discovery (RELOAD) Base Protocol", Work in Progress,
February 2013.
[RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing
an IANA Considerations Section in RFCs", BCP 26, RFC
5226, May 2008.
[SAM-GENERIC] Muramoto, E., Imai, Y., and N. Kawaguchi, "Requirements
for Scalable Adaptive Multicast Framework in Non-GIG
Networks", Work in Progress, November 2006.
[SPLITSTREAM] Castro, M., Druschel, P., Nandi, A., Kermarrec, A.,
Rowstron, A., and A. Singh, "SplitStream: High-
Bandwidth Multicast in a Cooperative Environment", SOSP
'03, Lake Bolton, New York, October 2003,
<http://dl.acm.org/citation.cfm?id=945474>.Authors' Addresses 🦋
John Buford
Avaya Labs Research
211 Mt. Airy Rd.
Basking Ridge, New Jersey 07920
USA
Phone: +1 908 848 5675
EMail: buford@avaya.com
Mario Kolberg (editor)
University of Stirling
Dept. of Computing Science and Mathematics
Stirling FK9 4LA
UK
Phone: +44 1786 46 7440
EMail: mkolberg@ieee.org
URI: http://www.cs.stir.ac.uk/~mko📦 where this page comes from
- ietf: rfc7019 2013-09
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms