Subject: Simple estimate for Nr. of retransmissions (WAS:RE: [AVT] IESG comments on draft-ietf-avr-rtp-retransmission-11.txt- Issue 4: more parameters needed for RTX?)

From: "Jose Rey" <[email-masked]>
Date: Fri, 22 Jul 2005 16:58:49 +0200

[warning: long email!]

Hi all,

Following Marks' suggestions (quoted email below) I will try to draft an
algorithm for finding out a simple estimate of the default number of
retransmissions (per packet) that a streaming client and server using
RTX should attempt in order to minimise the packet loss, while
considering the available RTCP bandwidth and the client buffering time
(both values usually known to the client).   The algorithm also requires
knowledge of the RTT, which shall be known at the client at least (?).
The absolute minimum number of retransmission attempts should of course
be one, but the algorithm tries to extract the highest number possible.

This email shall be thought as a first version; there many assumptions I
made and some of them might be wrong.  As a result of these
simplifications, the estimate seems overly conservative but that might
even be good.  I would like to get feedback if people think this is
reasonable, in the first place.  I have not experimented with this since
I don't have the resources to do so.  Also, it would useful to know if
this would help someone creating SDP sessions using RTX to get an idea
of the factors to take into account.

Here it goes:

Scenario
=========
* streaming scenario; two RTP entities:server and client
* retransmission draft used
* RTCP bandwidth for SRs and RRs = 5% (default), 2,5% for server and
client.
* RTP bandwidths of 64, 128, 256 and 512 kbps 
* RTT = 200ms
* RTCP RR compound packet size of  44 bytes containing: 1 RR, 1 SDES
item with CNAME, no encryption header, no profile specific extensions.
This ignores the other RR that could be present because of SSRC
multiplexing since it is not useful for the calculation
* AVPF Generic NACKs used for requesting retransmissions: this add 16
bytes of overhead to the RR for reporting a 16bit mask and 4 bytes more
every multiple of 16: 20 for 32, 24 for 48, etc.
* We assume 1 packet loss every RTCP
* We assume that the additional retransmissions queued on sender don't
add any delay to the first-time transmissions. 

Observations:

1.- The RTCP_interval at which the client sends retransmission requests
shall be greater than the RTT.  This is logical otherwise the
retransmissions don't have enough time to be received. 
 + this means for higher RTP bandwidths the default (5% RTP bw for RTCP)
may yield two small RTCP_intervals which have to be adapted using
bandwidth modifiers, so that the resulting RTCP intervals are >= RTT
 + For this it is required that the creator of the SDP session has an
estimate of the RTT.
2.- We assume a worst-case scenario at which a new Generic NACK report
block is added every to every new RTCP compound RR.  This may be too
conservative for some scenarios where the packet rate is low but it is
realistic for others like video at 30fps (which may yield in more than
30 packets per second).  
3.- We assume that each packet exhausts its corresponding number of
available retransmissions, N.  This means that if a packet is requested
for retransmission a maximum of two times, the corresponding generic
NACK report block requesting that particular packet is sent in two
consecutive RTCP compounds; likewise, if it is requested for
retransmission 10 times, then the RTCP compound contains that generic
NACK 10 times.  This assumption fixes the RTCP packet size (leaving out
the averaging with SR packets) to the same value after N*RTCP_interval
seconds, namely to 44 bytes + 12 bytes (fixed Generic NACK headers) +
4*N = 56 bytes + 4*N

Solution
========

In the diagram below, the worst case situation for singleton losses is
represented (first packet SN=0 is lost).  There, the client buffering
time required to allocate at least one retransmission  is T= T1+T2+
(T3+T4+T1+T2).  The first term accounts for the downlink one-way-delay
and the lost packet detection time (due to reordering buffer).  The
second (in brackets) additionally includes the feedback transmission on
the uplink channel and the processing and queueing delay.  In detail:

T1= physical delay DL + transmission delay DL (=avg-packet-size/downlink
bitrate) + interarrival delay jitter
T2= packet-loss-detection-time + time-to-next-client-rtcp-report
T3= physical delay UL + transmission delay UL + interarrival delay
jitter
T4= feedback processing time + queuing time

      Sender
     +-+---------------------------------^-----\-----------------
      \ \                               /       \
       \ \                             |         |
 SN=0   \ \ SN=1                  SN=n /         \  RTX(SN=0)
         \ \                          /           \
          X \                        /             \
             `.                     /               \
               \                   /                 \
                \                 |                   |
                 \                /                   \    ......
                  \              /                     \
     -------------V-------------/-----------------------V--------
            T1           T2        T3       T4     T1   ........
       Receiver

If there should more than one retransmission required, say N, just
multiply the second term by N.  This means that the client buffering
time required assure N retransmissions is T1+T2 + N*(T3+T4+T1+T2) .

Now we have to find out or simplify each term Ti.  We start with T1+T2.
We know that T1+T3 is ~=RTT, so T1 ~= T3 ~= RTT/2. On the other hand,
the worst case T2~=interarrival delay jitter + RTCP_interval ~=
RTCP_interval (?).  So T1+T2 < 2*RTCP_interval. T4 is probably very
small so we ignore it (?).  
If these approximations are acceptable (T3+T4+T1+T2)~= RTT+
RTCP_interval_client <= 2*RTCP_interval_client  (as per observation 1
above).  Summarising, the *very conservative* client buffering time
required to guarantee N retransmissions is N* 2* RTCP_interval_client. 

T = 2*RTCP_interval_client + 2*N*RTCP_interval_client = 2* (N+1)*
RTCP_interval_client

Numbers:
========

Some numerical examples for RTT~=200ms

Table 1
				RTCP_interval_client vs. N	Required
Client Buffering Time vs. N [s]				
                		  1	2	5	7	10
1	2	5	7	10
RTP bps	RTCP bps	
64000	      1600	       0.3	0.32	0.38	0.42	0.48
1.2	1.92	4.56	6.72	10.56
128000	3200	       0.15 0.16	0.19	0.21	0.24	0.6
0.96	2.28	3.36	5.28
256000	6400	       0.08	0.08	0.095	0.105	0.12	0.3
0.48	1.14	1.68	2.64
512000	12800	       0.04 0.04	0.048	0.053	0.06	0.15
0.24	0.57	0.84	1.32

Table 2 presents basically the same result as in Table 1 *only* that
those RTCP_intervals < RTT have been replaced with RTT!!

				RTCP_interval_client vs. N	Required
Client Buffering Time vs. N [s]	
                		  1	2	5	7	10
1	2	5	7	10
RTP bps	RTCP bps	
64000	      1600	        0.3	0.32	0.38	0.42	0.48
1.2	1.92	4.56	6.72	10.56
128000	3200		  0.2	0.2	0.2	0.21	0.24	0.8
1.2	2.4	3.36	5.28
256000	6400		  0.2	0.2	0.2	0.2	0.24	0.8
1.2	2.4	3.2	5.28
512000	12800		  0.2	0.2	0.2	0.2	0.24	0.8
1.2	2.4	3.2	5.28

Summary
=======

The conservative estimate for the number of possible retransmissions as
a function of the client buffering time and the RTCP_client_interval,
under the assumptions given would be then:

	N= [Client-buffering-time / 2* RTCP_interval_client] -1 

>From the Tables it can be seen that the estimate does not result in
excessive buffer requirements.  

Comments?

---------------------------------------------
Jose Rey     mailto:[email-masked]
P R D C G - Panasonic R&D Center Germany GmbH
Phone/Fax: +49(0)6103766-134/166
--------------------------------------------- 

--quote

> >>This still sounds like a big dose of handwaving to me. Can 
> you not at 
> >>least include some min/max here so you are sure that 
> packets don't get 
> >>lost? A recommended default that would at least *work* and 
> not cause 
> >>lost packets? Sure, leave room for optimization based on bandwidth 
> >>modifiers, specific configuration, etc. but I'm afraid that 
> without a 
> >>starting point or specific algorithm you could end up with widely 
> >>variant choices here from future implementations (unless, 
> as I said, 
> >>people just go figure out what vendor x does and copy it, in which 
> >>case it should have just been in the spec).
> >>
> > 
> > 
> > Of course, the minimum is one. For enabling at least one 
> rtx per packet, the server is only required to save it for 
> some period of time.  This time has several components:
> > 
> > 1- the time that the client takes to notice the loss.  For 
> single tone losses this is when the next packet comes (taking 
> out reordering buffer now), that is the intearrivel jitter plus
> > 2- the time it has to wait until the next RTCP send time, 
> which is ~1/2*RTCP interval if we assume uniform 
> distribution,which is common plus
> > 3- the time it takes for the server to process rtx request 
> (ignore it?)
> > 4- 1 RTT to account for the initial (failed) tx and the 
> time it takes for the rtx packet to the client
> > 
> > For more than 1, just multiply.  
> > 
> > This is a rough & quick analysis using common sense but I 
> haven't experimented with this. For bursty losses this is 
> more complex, of course (term 2 is complex).  Reordering is a 
> fixed delay, more or less.
> > 
> > The maximum can be calculated in the same way by using up 
> the available buffer.  
> > 
> > For the time being, one could make a table with link 
> bandwidths, typical RTTs and what the buffer amount should be 
> as f(RTT) for different RTCP bws, at least for the default 
> 5%.  As well as for the maximum rtxs that the buffer allows.
> > 
> > Does this make sense?
> 
> Yes, it is at least something for an implementation to go by. 
> Since you mention 
> that you haven't experimented with this, I assume there is not much 
> implementation of such a method? I was hoping that there were some 
> implementations to try and document here rather than 
> designing on the fly based 
> on my comments. If this is brand new, perhaps you could pass 
> the table and 
> algorithm by the WG in a separate thread to see if there is 
> consensus for it.
> 
> Thanks,
> 
> - Mark

_______________________________________________
Audio/Video Transport Working Group
[email-masked]
https://www1.ietf.org/mailman/listinfo/avt