Claude Castelluccia Thierry Turletti INRIA - France November 1996 RMFP Profile for SRM Abstract This document describes an architecture to implement SRM[2] on top of the RMFP protocol[7]. 1. Introduction This draft defines a RMFP profile for the SRM protocol. In this profile, the retransmissions are sent on the data flow ,by setting the R bit to 1, and new RMFCP packets are defined for the SRM control (Nack, heartbeat, TS query and reply). 2. The Scalable Reliable Multicast Framework SRM is a reliable multicast framework, defined in [2], for application level framing and light-weight sessions. The algorithms of this framework have been designed to be efficient, robust and scalable to very large network and sessions. The framework has been prototyped in wb, a distributed whiteboard application [3], and has been extentively tested on a global scale with sessions ranging from a few to more than 1000 participants. In the rest of this section, we describe briefly SRM and its algorithms. 2.1 SRM design principles The SRM framework has been designed according to the following principles: o Lost packets are detected by the receivers o Lost packets are signaled by NACKs to avoid the well known ACK implosion problem. The NACKS are multicast in the SRM session to avoid NACK duplications and to allow others session's members to retransmit the missing packet. o Lost packets can be retransmitted both by the source and the receivers 2.2 SRM algorithms -When host A detects a loss, it schedules a repair request (NACK) for a random time in the future. The request timer is chosen from the uniform distribution on [C1.d(S,A), (C1+C2).d(S,A)] seconds, (1) where d(S,A) is host A's estimate of the one-way delay to the original source S of the missing data. When the request timer expires, host A sends a request for the missing data, and doubles the request timer to wait for the repair. -If host A receives a request for the missing data before its own request timer for that data expires, then host A does a (random) exponential backoff, and reset its request timer. Then, if the current timer had been chosen from the uniform distribution on 2^i.[C1.d(S,A), (C1+C2).d(S,A)], then the backed-off timer is randomly chosen from the uniform distribution on 2^(i+1).[C1.d(S,A), (C1+C2).d(S,A)], (2) -When host B receives a request from A that the host B is able of answering, host B sets a repair timer to a value from the uniform distribution on [D1.d(A,B), (D1+D2).d(A,B)] (3) When this repair timer expires, then host B multicasts the repair. -If host B receives a repair for the missing data before its repair timer expires, then host B cancels its repair timer. Note: C1, C2 , D1 and D2 are constants. As specified in [2], C1=C2=2 and D1=D2=log10(G), where G is the current number of members in the session. An adaptative algorithm for these parameters is presented in [2]. 3. SRM over RMFP 3.1 Introduction There are mainly 2 different solutions to implement SRM over RMFP: o The retransmittions and the original data are transmitted over the same RMFP session using the same PT. In this case, SRM only retransmits the lost packet as if it was the original one (same header and same data). The main advantage of this approach is that applications that do not "understand" SRM can still benefit from the retransmissions. o The retransmission and the original data are sent over 2 different RMFP sessions. The original data are transmitted over a RMFP session and the retransmitted data are sent over an other RMFP session. This approach is very modular: Applications that can not (because they don't have enough ressource or they don't understand SRM) or do not want to receive SRM data can only register to the original data. Also, as the first solution, applications that do not "understand" SRM can still listen the SRM session and benefit from the retransmissions. The main problem with this approach is that it can lead to situations where only reveivers that suffer from losses join the SRM session; Most of the retransmissionsa are then performed by the sources. This document describes the profile for the first approach. A profile for the second approach will be described in a companion draft. 3.2 The protocol architecture The proposed profile uses one RMFP session composed of 2 flows: o A data flow, composed of the original data and the retransmissions. o A control flow, composed of the RMFCP packets and the SRM control packets (Nacks, time-stamp queries and replies, heartbeat). The next two sections define those 2 flows. 3.3 The RMFP data flow This flow is composed of the original data and the retransmissions. The original data are sent using the packet format described in [7] with the R (Retransmission) bit set to 0. The retransmissions are sent using the packet format described in [7] with the R (Retransmission) bit set to 1. 3.4 The RMFCP flow This control flow is composed of the RMFCP packets [7] and the SRM control packets (Nacks, time-stamp queries and replies, heartbeat). We defined 4 new RMFCP packets for SRM: -The Heartbeat packets that are sent by the source to indicate the sequence number of the last transmitted packet. -The NACK packets that are sent by receivers to request the retransmission of one or several packets. -The Timer request and Timer reply sent to estimate the distance (in time) between the members of a group. The rest of this section describes the format of each of those packets and their transmission frequency (those packets and the reports (RR and SR) are concatenated). The header is the same for all those new RMFCP-SRM packets. Therefore when several of those new RMFCP packets are concatenated only one occurence of this common header is used: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |V=2|P| CC | PT=SRM=205 | length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | SSRC | +=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+ Version (V): 2 bits Identifies the version of RMFP, two (2). Padding (P): 1 bit Chunk Count (CC): 5 bits The number of chunks contained in this RMFCP_SRM packet. Packet type (PT): 8 bits Contains the constant 205 to identify this as an RMFCP_SRM packet. Packet length (length): 16 bits The length of this RMFCP packet in 32-bit words minus one, including the header. (The offset of one makes zero a valid length and avoids a possible infinite loop in scanning a compound RMFCP packet, while counting 32-bit words avoids a validity check for a multiple of 4.) 3.3.2.1 The Heartbeat Generally, a packet loss is detected by finding a gap in the sequence space. However the last data-packet may be dropped. So, each sender send a low-rate, periodic, message, (a heartbeat) announcing the highest sequence number sent. The heartbeat is also used to synchronize the cycle number (16 high bits) of the RFMP packets of the sessions using SRM. - Packet format: -------------- 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ST = 0 | unused | Sequence number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ SubType (ST) : 5 bits The type of the trunk. When ST=0, the trunk is a Heartbeat Sequence number : 16 bits The sequence number of the last packet sent. - Sending rate: ------------------- Since heartbeat transmissions are important to detect lost packets, 3 heartbeats packets are sent after each original data transmission. Those 3 heartbeats are sent respectively (T), 2*(T) and 8*(T) seconds after the emission of the last data packet. In our implementation, T is set to 1 second, but it could depend on the application (T should be small for interactive applications) and/or the number of members of the group. 3.3.2.2 The Negative Acknowledgement (NACK) -Packet format: --------------- The NACK packets is composed of two types of sub-packets that can be Concatenated together. (In this case, the SSRC_source field is shared). 1st NACK sub-packet ------------------- The header is defined as follows: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | SSRC_source | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ST=1 | Count | Sequence number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sequence number | Sequence number | .............. +=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+ SSRC_source: 32 bits The SSRC from the sender from whom we have lost a packet. Sub Payload Type (ST) : 5 bits The type of the trunk. In this case, ST=1. Count : 11 bits (Count+1) defines the number of NACKS (sequence numbers) that follows for SSRC_source. Sequence number: 16 bits The sequence number of the lost packet from SSRC_source. 2nd NACK sub-packet ------------------- The header is defined as follows: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | SSRC_source | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ST=10 | Count | Sequence number | +=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+ SSRC_source: 32 bits The SSRC from the sender from whom we have lost a packet. Sub Payload Type (ST) : 5 bits The type of the trunk. In this case, ST=10. Count : 11 bits (Count+1) defines the number of consecutive missing packets. Sequence number: 16 bits The sequence number of the first lost packet from SSRC_source. -Sending rate: -------------------- The Nacks are sent according the following SRM algorithm: -When host A detects a loss, it schedules a repair request (NACK) for a random time in the future. The request timer is chosen from the uniform distribution on [C1.d(S,A), (C1+C2).d(S,A)] seconds, (1) where d(S,A) is host A's estimate of the one-way delay to the original source S of the missing data. When the request timer expires, host A sends a request for the missing data, and doubles the request timer to wait for the repair. -If host A receives a request for the missing data before its own request timer for that data expires, then host A does a (random) exponential backoff, and reset its request timer. That is, if the current timer had been chosen from the uniform distribution on 2^i.[C1.d(S,A), (C1+C2).d(S,A)], then the backed-off timer is randomly chosen from the uniform distribution on 2^(i+1).[C1.d(S,A), (C1+C2).d(S,A)], (2) 3.3.2.3 The Time-stamp queries The time-stamp queries are used in conjonction with time-stamp replies to compute host-to-host delay, as explained in section 3.3.2.4. -Packet format: -------------- The header is defined as follows: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ST=2 | Unused | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | time-stamp | +=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+ ST : 5 bits ST=2 defines a time-stamp query time-stamp: 32 bits. The time-stamp is composed of the 32 middle bits of a 64 bits NTP time-stamp. The 16 first bits encodes the seconds and the later 16 bits encodes the fraction. -Sending rate: ----------------- A timer-stamp query is multicast to the whole group: - just after joining a SRM session - every 5 RTCP_interval (RTCP_interval is computed as specified in the RTP specification [1]). 3.3.2.4 The Time-stamp replies -Packet format: -------------- Several time-stamp replies can be concatenated into the same SRM-packet and the number of replies are count+1. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ST=3 | Count | Unused | +=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+ | SSRC_1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | last time-stamp received from SSRC_1 (LTR_1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Delay since last time-stamp request from SSRC_1 (DLTR_1)| +=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+ | SSRC_2 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | last time-stamp request received from SSRC_2 (LTR_2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Delay since last time-stamp request from SSRC_2 (DLTR_2) | +=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+ ........ ST : 5 bits ST=3 defines a time-stamp reply Count : 11 bits The number of time-stamp replies trunks that are contained in this time-stamp reply packet. SSRC_1 : 32 bits The synchronization source. LTR_n (last time-stamp received from SSRC_n) : 32 bits The time-stamp field of the last time-stamp request from SSRC_n DLTR_n (Delay since last time-stamp request from SSRC_n) : 32 bits The delay, expressed in 1/65536 seconds, since the last timer-stamp request received from SSRC_n. Let SSRC_r denotes the source on host B the member issuing this reply and source SSRC_d, a source of host A. Host A can compute its delay to host B by recording the time T when this time-stamp reply is received and using the following formula: d(A,B) = (T - LSR_d - DLSR_d)/2*S. -Sending rate: ----------------- A reply-packet of a particular receiver should only be issued if it has already received a time-stamp query and at most one every RTCP_interval. Note: It might be more efficient to unicast those replies directly to the source of the corresponding time-stamp request. In fact, the information of the time-stamp replies are only usefull to the source of the corresponding time-stamp request. 3.3.2.6 The report's (SR and/or RR) transmission period The sending rate of the reports should be kept low (e.g. 5% of the session bandwidth). An open issue is how do we prevent a poor receiver to overload the session with NACK packets? 4. Discussions SRM expects from all members of a session that it is involved in the retransmission phases. However when the machines are not very powerful, retransmissions might be a big burden for them. Those machines should be somehow exempted of retransmissions. Several solutions are possible: Solution 1 - 2 RMFP sessions. We split the RMFP session into 2 sessions: one which regroups members that are able to send NACKs and retransmit packets, and another one which regroups members that are able to send NACKs but which are not expected to participate in the retransmissions. One problem appears with this solution: how do we prevent that members with large capacity join only the 2nd SRM sessions? An automatic join could maybe used? Solution 2 - SRM modification. An other solution would be to modify the SRM algorithm by considering the machine capacities to set the retransmission timers. More preciselly, here is an example of what can be done: -When host B receives a request from A that the host B is able of answering, host B sets a repair timer to a value from the uniform distribution on [D1.d(A,B), (D1+D2).d(A,B)] with d'(A,B) = t(d(A,B),CapaB) Where CapaB is the machine capacity of host B, d(A,B) is the distance between host A and host B, and T(x,y) is function that weights d(A,B) by CapaB. T(x,y) needs to be defined, but intuitively we expect d'(A,B) to get larger as the capacity gets smaller. When this repair timer expires, then host B multicasts the repair. Solution 3 - Do nothing. The simplest solution is to let the members choose to join or not to the RMFP session, knowing that if they join the session they will be expected to participate in the retransmissions. That's the prize to pay! In some case, i.e. when the processing capacities are very low, a member may loose by joining a SRM group, because some of its computing capacity will used to process to perform the retransmissions. Is this solution acceptable? We are currently using the 3rd solution, but think that the 2nd solution is more suitable. Author's Address Questions about this memo can also be directed to: Claude Castelluccia (contact) INRIA Rhone-Alpes projet SIRAC 655, av. de l'Europe 38330 MontBonnot FRANCE email: claude.castelluccia@inrialpes.fr Thierry Turletti INRIA Sophia-Antipolis projet RODEO 2004, route des Lucioles BP93- 06902 Sophia Antipolis FRANCE email: thierry.turletti@inria.fr References [1] Henning Schulzrinne, Stephen Casner, Ron Frederick, Van Jacobson, RTP: A Transport Protocol for Real-Time Applications, RFC 1889. [2] Sally Floyd, Van Jacobson, Steven McCanne. A Reliable Multicast Framework for Light-weight Sessions and Application Level Framing. ACM SIGCOMM'95. [3] Van Jacobson. Multimedia Conferencing on the Internet. Tutorial 4, SIGCOMM'94. [4] H. Schulzrinne. RTP Profile for Audio and Video Conferences with Minimal Control. RFC 1890, January 1996. [5] M. Speer, D. Hoffman. RTP Payload Format of Sun's CellB Video Encoding. RFC 2029. [6] T. Turletti, C. Huitema. RTP Payload Format for H.261 Video Streams. RFC 2032, October 1996. [7] J.Crowcroft and al. RMFP: A Reliable Multicast Framing Protocol. Internet-Draft, Nov. 1996.