// out of band discovery of groupID, perhaps by lookup in DHT
joinTree(groupID); // sends "join groupID" message

Figure 4

As stated earlier, multiple algorithms will co-exist in the overlay.

1. Peer which initiates multicast group:
   
   
2. Any joining peer:
   
   
   
   The overlay routes the join request using the overlay routing mechanism toward the peer with the nearest id to the groupID. This peer is the root. Peers on the path to the root join the tree as forwarding points.
3. Leave Tree:
   
   leaveTree(groupID) // removes this node from the tree
   
   Propagates a leave message 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 message to its parent. A child node receiving a leave message from a parent sends a join message to the groupID.
4. Message forwarding:
   
   multicastMsg(groupID, msg);
5. For the message forwarding there are two approaches:
   • SSM tree: The creator of the tree is the source. It sends data messages to the tree root which are forwarded down the tree.
   • ASM tree: A node sending a data message sends the message to its parent and its children. Each node receiving a data message from one edge forwards it to remaining tree edges it is connected to.

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 [I-D.ietf-p2psip-base] for a universal structured peer-to-peer overlay protocol. RELOAD provides the mechanism to support a number of overlay topologies. Hence the overlay multicast framework [I-D.irtf-sam-hybrid-overlay-framework] (hereafter SAM framework) can be used with P2P-SIP, and that the SAM framework is overlay agnostic.

As discussed in the SAM requirements draft, there are a variety of ALM tree formation and tree maintenance algorithms. The intent of this specification is to be algorithm agnostic, similar to how RELOAD is overlay algorithm agnostic. We assume that all control messages are propagated using overlay routed messages.

The message types needed for ALM behavior are divided into the following categories:

• Tree life-cycle (create, join, leave, re-form, heartbeat)
• Peer region and multicast properties

The message codes are defined in Section 11 of this documents. Messages are mapped to the RELOAD experimental message type.

In the following descriptions we use two datatypes: DictionaryElement and Dictionary. Definitions of these two types are as follows:

struct {
  opaque name<0..2^16-1>;
  opaque value<0..2^16-1>;
  } DictionaryElement;

struct {
  DictionaryElement elements<0..2^16-1>;
  } Dictionary;

7.2. Tree Lifecycle Messages

Peers use the overlay to transmit ALM (application layer multicast) operations defined in this section.

7.2.1. Create Tree

A new ALM tree is created in the overlay with the identity specified by group_id. The usual interpretation in a DHT based overlay of group_id is that the peer with peer id closest to and less than the group_id is the root of the tree. However, other overlay types are supported. The tree has no children at the time it is created.

The group_id is generated from a well-known session key to be used by other Peers to address the multicast tree in the overlay. The generation of the group_id from the session_key MUST be done using the overlay's id generation mechanism.

A successful Create Tree causes an ALMTree structure to be stored in the overlay at the node G responsible for node_id equal to the group_id. This node G performs the RELOAD-defined StoreReq as a side effect of performing the Create Tree. If the StoreReq fails, the Create Tree fails. Since node G is the node which receives the Create Tree, it is both the sender and receiver of the StoreReq to store the ALMTree structure.

After a successful Create Tree, peers can use the RELOAD Fetch method to retrieve the ALMTree struct at address group_id. The ALMTree kind is defined in Section 10.

      struct {  
        node_id peer_id;
        opaque session_key<0..2^32-1>;
        node_id group_id;
        Dictionary options;
      } ALMTree;

peer_id: the overlay address of the peer that creates the multicast tree.

session_key: a well-known string when hashed using the overlay's id generation algorithm produces the group_id.

group_id: the overlay address of the root of the tree

options: name-value list of properties to be associated with the tree, such as the maximum size of the tree, restrictions on peers joining the tree, latency constraints, preference for distributed or centralized tree formation and maintenance, heartbeat interval.

Tree creation is subject to access control since it involves a Store operation. The NODE-MATCH access policy defined in section 7.3.2 of RELOAD is used.

7.2.2. CreateTreeResponse

After receiving a CreateTree message from node S, the peer sends a CreateTreeReponse to node S.

        struct {  
          Dictionary options;
        } CreateTreeResponse;

options: A node may provide algorithm-dependent parameters about the created tree to the requesting node.

7.2.3. Join

Causes the distributed algorithm for peer join of a specific ALM group to be invoked. If successful, the peer_id is notified of one or more candidate parent peers in one or more JoinAccept messages. The particular ALM join algorithm is not specified in this protocol.

RELOAD is a client server protocol. Consequently, the messages JoinAccept and JoinReject (defined below) are matching responses for Join. If JoinReject is received, then no further action on this request is carried out. If JoinAccept is received, then either a JoinConfirm or a JoinDecline message (see below) is then sent. The matching response for JoinConfirm is JoinConfirmResponse. The matching response for JoinDecline is JoinDeclineResponse.

The following list shows the matching request-responses according to the request-response mechanism defined in RELOAD.

• Join -- JoinAccept: Node C sends a Join request to node P. If node P accepts, it responds with JoinAccept.
• Join -- JoinReject: Node C sends a Join request to node P. If node P does not accept the join request, it responds with JoinReject.
• JoinConfirm -- JoinConfirmResponse: If node P sent node C a JoinAccept, then node C confirms with a JoinConfirm request. Node P then responds with a JoinConfirmResponse.
• JoinDecline -- JoinDeclineResponse: If node P sent node C a JoinAccept, then node C declines with a JoinDecline request. Node P then responds with a JoinDeclineResponse

Thus Join, JoinConfirm, and JoinDecline are treated as requests as defined in RELOAD, are mapped to the RELOAD exp_a_req message, and are therefore retransmitted until either retry limit is reached or a matching response received. JoinAccept, JoinReject, JoinConfirmResponse, and JoinDeclineResponse are treated as message responses as defined above, and are mapped to the RELOAD exp_a_ans message.

      struct {  
        node_id peer_id;
        node_id group_id;
        Dictionary options;
      } Join;

peer_id: overlay address of joining/leaving peer

group_id: the overlay address of the root of the tree

options: name-value list of options proposed by joining peer

7.2.4. Join Accept (Join Response)

Tells the requesting joining peer that the indicated peer is available to act as its parent in the ALM tree specified by group_id, with the corresponding options specified. A peer MAY receive more than one JoinAccept from different candidate parent peers in the group_id tree. The peer accepts a peer as parent using a JoinConfirm message. A JoinAccept which receives neither a JoinConfirm or JoinDecline message MUST expire.

      struct {  
        node_id parent_peer_id;
        node_id child_peer_id;
        node_id group_id;
        Dictionary options;
      } JoinAccept;

parent_peer_id: overlay address of a peer which accepts the joining peer

child_peer_id: overlay address of joining peer

group_id: the overlay address of the root of the tree

options: name-value list of options accepted by parent peer

7.2.5. Join Reject (Join Response)

A peer receiving a Join message responds with a JoinReject response to indicate the request is rejected.

7.2.6. Join Confirm

A peer receiving a JoinAccept message which it wishes to accept MUST explicitly accept it before the expiration of the JoinAccept using a JoinConfirm message. The joining peer MUST include only those options from the JoinAccept which it also accepts, completing the negotiation of options between the two peers.

      struct {  
        node_id child_peer_id;
        node_id parent_peer_id;
        node_id group_id;
        Dictionary options;
      } JoinConfirm;

child_peer_id: overlay address of joining peer which is a child of the parent peer

parent_peer_id: overlay address of the peer which is the parent of the joining peer

group_id: the overlay address of the root of the tree

options: name-value list of options accepted by both peers

7.2.7. Join Confirm Response

A peer receiving a JoinConfirm message responds with a JoinConfirmResponse

7.2.8. Join Decline

A peer receiving a JoinAccept message which does not wish to accept it MAY explicitly decline it using a JoinDecline message.

      struct {  
        node_id peer_id;
        node_id parent_peer_id;
        node_id group_id;
      } JoinDecline;

peer_id: overlay address of joining peer which declines the JoinAccept

parent_peer_id: overlay address of the peer which issued a JoinAccept to this peer

group_id: the overlay address of the root of the tree

7.2.9. Join Decline Response

A peer receiving a JoinConfirm message responds with a JoinDeclineResponse

7.2.10. Leave

A peer which is part of an ALM tree identified by group_id which intends to detach from either a child or parent peer SHOULD send a Leave message to the peer it wishes to detach from. A peer receiving a Leave message from a peer which is neither in its parent or child lists SHOULD ignore the message.

      struct {  
        node_id peer_id;
        node_id group_id;
        Dictionary options;
      } Leave;

peer_id: overlay address of leaving peer

group_id: the overlay address of the root of the tree

options: name-value list of options

7.2.11. Leave Response

A peer receiving a Leave message responds with a LeaveResponse

7.2.12. Re-Form or Optimize Tree

This triggers a reorganization of either the entire tree or only a sub-tree. It MAY include hints to specific peers of recommended parent or child peers to reconnect to. A peer receiving this message MAY ignore it, MAY propagate it to other peers in its subtree, and MAY invoke local algorithms for selecting preferred parent and/or child peers.

      struct {  
        node_id group_id;
        node_id peer_id;
        Dictionary options;
      } Reform;

group_id: the overlay address of the root of the tree

peer_id: if omitted, then the tree is reorganized starting from the root, otherwise it is reorganized only at the sub-tree identified by peer_id.

options: name-value list of options

7.2.13. Reform Response

A peer receiving a Reform message responds with a ReformResponse

      struct {  
        Dictionary options;
      } ReformResponse;

options: algorithm dependent information about the results of the reform operation

7.2.14. Heartbeat

A child node signals to its adjacent parent nodes in the tree that it is alive. If a parent node does not receive a Heartbeat message within N heartbeat time intervals, it MUST treat this as an explicit Leave message from the unresponsive peer. N is configurable.

      struct {  
        node_id peer_id_1;
        node_id peer_id_2;
        node_id group_id;
        Dictionary   options;
      } Heartbeat;

peer_id_1: source of heartbeat

peer_id_2: destination of heartbeat

group_id: overlay address of the root of the tree

options: an algorithm may use the heartbeat message to provide state information to adjacent nodes in the tree

7.2.15. Heartbeat Response

A parent node responds to a Heartbeat message from a child node in a tree that it has received the Heartbeat message.

7.2.16. NodeQuery

The NodeQuery message is used to obtain information about the state and performance of the tree on a per node basis. A set of nodes could be queried to construct a centralized view of the multicast trees, similar to a web crawler.

        struct {  
          node_id peer_id_1;
          node_id peer_id_2;
        } NodeQuery;

peer_id_1: source of query

peer_id_2: destination of query

7.2.17. NodeQuery Response

The response to a NodeQuery message contains a NodeStatistics instance for this node.

public struct {
   uint32        node_lifetime;
   uint32        total_number_trees;
   uint16        number_algorithms_supported;
   uint8         algorithms_supported[32];
   TreeData      max_tree_data;
   uint16        active_number_trees;
   TreeData      tree_data<0..2^8-1>;
   ImplementationInfo  imp_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
• active_number_trees: current number of trees that the node is part of
• tree_data: details of each active tree, the number of such is specified by the number_active_trees.
• impl_info: information about the implementation of this usage

public struct {
  uint32       tree_id;
  uint8        algorithm;
  NodeId       tree_root;
  uint8        number_parents;
  NodeId       parent<0..2^8-1>;
  Uint16       number_children_nodes;
  NodeId       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 NodeId of each parent node
• number_children_nodes: 0..2^16-1 indicates number of children
• children: the RELOAD NodeId of each child node
• path_length_to_root: number of overlay hops to the root of the tree
• path_delay_to_root: RTT in millisec. to root node
• path_delay_to_child: last measured RTT in msec to child node with largest RTT.

public struct {
  uint32       join_confim_timeout;
  uint32       heartbeat_interval;
  uint32       heartbeat_reponse_timeout;
  uint16       info_length;
  uint8        info<0..2^16-1>;
} ImplementationInfo;

• join_confirm_timeout: The default time for join confirm/decline, 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.
• heartbeat interval: The heartbeat interval is 2000 msec.
• heartbeat timeout interval: The 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.
• info_length: length of the info field
• info: implementation specific information, such as name of implementation, build version, and implementation specific features

7.2.18. Push

A peer sends arbitrary multicast data to other peers in the tree. 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

length: length of the data field in bytes

data: the data

7.2.19. PushResponse

After receiving a Push message from node S, the peer sends a PushReponse 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 which were forwarded the push message, and the number of adjacent nodes from which a PushResponse was received.

8. Scribe Algorithm

8.1. Overview

The following table shows a mapping between RELOAD ALM messages (as defined in Section 5 of this draft) and Scribe messages as defined in [CASTRO2002].

         +------------------+-------------------+-----------------+
         | Section in Draft |RELOAD ALM Message | Scribe Message  |
         +------------------+-------------------+-----------------+
         | 7.2.1            | CreateALMTree     | Create          |
         +------------------+-------------------+-----------------+
         | 7.2.2            | Join              | Join            |
         +------------------+-------------------+-----------------+
         | 7.2.3            | JoinAccept        |                 |
         +------------------+-------------------+-----------------+
         | 7.2.4            | JoinConfirm       |                 |
         +------------------+-------------------+-----------------+
         | 7.2.5            | JoinDecline       |                 |
         +------------------+-------------------+-----------------+
         | 7.2.6            | Leave             | Leave           |
         +------------------+-------------------+-----------------+
         | 7.2.7            | Reform            |                 |
         +------------------+-------------------+-----------------+
         | 7.2.8            | Heartbeat         |                 |
         +------------------+-------------------+-----------------+
         | 7.2.9            | NodeQuery         |                 |
         +------------------+-------------------+-----------------+
         | 7.2.10           | Push              | Multicast       |
         +------------------+-------------------+-----------------+
         |                  | Note 1            | deliver         |
         +------------------+-------------------+-----------------+
         |                  | Note 1            | forward         |
         +------------------+-------------------+-----------------+
         |                  | Note 1            | route           |
         +------------------+-------------------+-----------------+
         |                  | Note 1            | send            |
         +------------------+-------------------+-----------------+
            

CREATE : groups.add(msg.group_id)

JOIN : if(checkAccept(msg)) {
		  recvJoins.add(msg.source, msg.group_id)
		  SEND(JOINAccept(node_id, msg.source, msg.group_id))
	}

LEAVE : groups[msg.group_id].children.remove(msg.source)
           if (groups[msg.group].children = 0)
              SEND(msg,groups[msg.group_id].parent)

JOINConfirm: 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)
	      }

JOINDecline: if(recvJoins.contains(msg.source,msg.group_id))
			 recvJoins.del(msg.source, msg.group_id)

MULTICAST : foreach(groups[msg.group_id].children as node_id)
                   SEND(msg,node_id)
            if memberOf(msg.group_id)
                   invokeMessageHandler(msg.group_id, msg)

JOINDecline: if(recvJoins.contains(msg.source,msg.group_id))
			 recvJoins.del(msg.source, msg.group_id)

      struct {  
        node_id peer_id;
        opaque session_key<0..2^32-1>;
        node_id group_id;
        Dictionary options;
      } ALMTree;

      +-------------------------+------------------+------------------+
      | Message                 |RELOAD Code Point | ALM Message Code |
      +-------------------------+------------------+------------------+
      | CreateALMTRee           | exp_a_req        | 00               |
      +-------------------------+------------------+------------------+
      | CreateALMTreeResponse   | exp_a_ans        | 01               |
      +-------------------------+------------------+------------------+
      | Join                    | exp_a_req        | 02               |
      +-------------------------+------------------+------------------+
      | JoinAccept              | exp_a_ans        | 03               |
      +-------------------------+------------------+------------------+
      | JoinReject              | exp_a_ans        | 04               |
      +-------------------------+------------------+------------------+
      | JoinConfirm             | exp_a_req        | 05               |
      +-------------------------+------------------+------------------+
      | JoinConfirmResponse     | exp_a_ans        | 06               |
      +-------------------------+------------------+------------------+
      | JoinDecline             | exp_a_req        | 07               |
      +-------------------------+------------------+------------------+
      | JoinDeclineResponse     | exp_a_ans        | 08               |
      +-------------------------+------------------+------------------+
      | Leave                   | exp_a_req        | 09               |
      +-------------------------+------------------+------------------+
      | LeaveResponse           | exp_a_ans        | x0A              |
      +-------------------------+------------------+------------------+
      | Reform                  | exp_a_req        | x0B              |
      +-------------------------+------------------+------------------+
      | ReformResponse          | exp_a_ans        | x0C              |
      +-------------------------+------------------+------------------+
      | Heartbeat               | exp_a_req        | x0D              |
      +-------------------------+------------------+------------------+
      | HeartbeatResponse       | exp_a_ans        | x0E              |
      +-------------------------+------------------+------------------+
      | NodeQuery               | exp_a_req        | x0F              |
      +-------------------------+------------------+------------------+
      | NodeQueryResponse       | exp_a_ans        | x10              |
      +-------------------------+------------------+------------------+
      | Push                    | exp_a_req        | x11              |
      +-------------------------+------------------+------------------+
      | PushResponse            | exp_a_ans        | x12              |
      +-------------------------+------------------+------------------+

 struct {
    uint32           sam_token;
    uint32           algorithm;
    uint8             version;
}  ALMHeader;

struct {
   uint16       alm_message_code;
   opaque       alm_message_body;
} ALMMessageContents;

public struct {
   uint16   alm_error_code;
   opaque   alm_error_info<0..2^16-1>;
} ALMErrorResponse;

     P1      P2      P3       P4      GroupID
     |       |       |        |       |
     |       |       |        |       |
     |       |       |        |       |
     | CreateTree    |        |       |
     |------------------------------->|
     |       |       |        |       |
     |       |       |        |       | StoreReq
     |       |       |        |       |--+
     |       |       |        |       |  |
     |       |       |        |       |  |
     |       |       |        |       |<-+
     |       |       |        |       | StoreResponse
     |       |       |        |       |--+
     |       |       |        |       |  |
     |       |       |        |       |  |
     |       |       |        |       |<-+
     |       |       |        |       |
     |       |       |        |       |
     |       |    CreateTreeResponse  |
     |<-------------------------------|
     |       |       |        |       |
     |       |       |        |       |
     | Fetch         |        |       |
     |------------------------------->|
     |       |       |        |       |
     |       |       |        |       |
     |       |         FetchResponse  |
     |<-------------------------------|
     |       |       |        |       |

     P1      P2      P3       P4      GroupID
     |       |       |        |       |
     |       |       |        |       |
     | Join                           |
     |------------------------------->|
     |       |       |        |       |
     | JoinAccept                     |
     |<-------------------------------|
     |       |       |        |       |
     |       |       |        |       |
     |       |Join                    |
     |       |----------------------->|
     |       |       |        |       |
     |                            Join|
     |<-------------------------------|
     |       |       |        |       |
     |JoinAccept     |        |       |
     |------>|       |        |       |
     |       |       |        |       |
     |JoinConfirm    |        |       |
     |<------|       |        |       |
     |       |       |        |       |
     |       |       |        |Join   |
     |       |       |        |------>|
     |       |       |        |  Join |
     |<-------------------------------|
     |       |       |        |       |
     | Join  |       |        |       |
     |------>|       |        |       |
     |       |       |        |       |
     | JoinAccept    |        |       |
     |----------------------->|       |
     |       |       |        |       |
     |       | JoinAccept     |       |
     |       |--------------->|       |
     |       |       |        |       |
     |       |       |        |       |
     |       |   Join Confirm |       |
     |<-----------------------|       |
     |       |       |        |       |
     |       |   Join Decline |       |
     |       |<---------------|       |
     |       |       |        |       |
     |       |       |        |       |

     P1      P2      P3       P4      GroupID
     |       |       |        |       |
     |       |       |        |       |
     |       |       |  Leave |       |
     |<-----------------------|       |
     |       |       |        |       |
     | LeaveResponse |        |       |
     |----------------------->|       |
     |       |       |        |       |
     |       |       |        |       |

     P1      P2      P3       P4      GroupID
     |       |       |        |       |
     | Push  |       |        |       |
     |------------------------------->|
     |       |       |        |       |
     |       |       |    PushResponse|
     |<-------------------------------|
     |       |       |        |       |
     |       |       |        |   Push|
     |<-------------------------------|
     |       |       |        |       |
     | PushResponse  |        |       |
     |------------------------------->|
     |       |       |        |       |
     |Push   |       |        |       |
     |------>|       |        |       |
     |       |       |        |       |
     |PushResponse   |        |       |
     |<------|       |        |       |
     |       |       |        |       |
     | Push  |       |        |       |
     |----------------------->|       |
     |       |       |        |       |
     |       |   PushResponse |       |
     |<-----------------------|       |
     |       |       |        |       |
     |       |       |        |       |
     |       |       |        |       |