Subject: Re-send: 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 17:25:05 +0200

Hi again!

the ML formatting messed up the tables so I send it again
---

[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

                		  1	2	5	7	10	
RTP bps	RTCP bps	
64000	      1600	       0.3	0.32	0.38	0.42	0.48
128000	3200	       0.15 0.16	0.19	0.21	0.24	
256000	6400	       0.08	0.08	0.095	0.105	0.12	
512000	12800	       0.04 0.04	0.048	0.053	0.06	

			Required Client Buffering Time vs. N [s]

                		 1	2	5	7	10
RTP bps	RTCP bps	
64000	      1600	       1.2	1.92	4.56	6.72	10.56
128000	3200	       0.6	0.96	2.28	3.36	5.28
256000	6400	       0.3	0.48	1.14	1.68	2.64
512000	12800	       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	
                		  1	2	5	7	10	
RTP bps	RTCP bps	
64000	      1600	        0.3	0.32	0.38	0.42	0.48	
128000	3200		  0.2	0.2	0.2	0.21	0.24	
256000	6400		  0.2	0.2	0.2	0.2	0.24	
512000	12800		  0.2	0.2	0.2	0.2	0.24	

				Required Client Buffering Time vs. N [s]

                		  1	2	5	7	10
RTP bps	RTCP bps	
64000	      1600	        1.2	1.92	4.56	6.72	10.56
128000	3200		  0.8	1.2	2.4	3.36	5.28
256000	6400		  0.8	1.2	2.4	3.2	5.28
512000	12800		  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

---

From: Magnus Westerlund <[email-masked]>
Date: Wed, 27 Jul 2005 14:15:28 +0200

Hi Jose,

I seem to have lost track of the actual question. Was it Marks question 
in regards to what the minimal required buffering for N possible 
retransmissions as server side?

I think you have made some errors in the calculations that are quite 
important. First of all I think that setting the RTCP_Interval and RTT 
to the same value is not really valid. The reason is that there is 
clearly bit-rate versus RTT cases that makes this fall on both sides. 
Also it is not obvious that trying to calculate this formula based on 
RTCP transmission interval is any simpler than using RTT. In fact I 
would think that RTCP_Interval is quite difficult to calculate and 
depends on a number of variables that needs to be included.

Secondly I think the average RTCP packet size you have used in 
calculations are way to small. A common RTCP average packet size is 
around 125 octets; remember the required CNAME string and the IP/UDP 
headers. Thus one can construct the following table of RTCP reporting 
intervals compared to BW.
BW	 RTCP_Reporting_Interval Deterministic
64000    0,625
128000   0,3125
256000   0,15625
5120000  0,0078125
10240000 0,00390625
5000000  0,008
10000000 0,004

This doesn't consider the normal minimal interval values. Which is a 
valid point of usage for AVPF. However it also fails to take something 
into account which concerns the retransmission use cases. That is the 
distribution of the sender and receiver classed SSRCs. If the 
retransmission is done using SSRC based multiplexing, then one has an 
RTP session with two senders and one receiver. That result in that the 
bandwidth sharing is the following: Receiver reporting is done using 1/3 
of (RR+RS) bandwidth. The sender side is then having two parts of RR+RS.

Thirdly I think the worst case wait for the next regular transmission is 
1.5*RTCP_Interval/1.21828. One can't ignore the randomization factor in 
this case as there can be requests that ends up being delayed the 
maximum time, not the average one.

In addition I think the consideration must be done for different RTTs. 
Both a very short one like 5 ms and much longer ones (1s) to ensure that 
RTT is correctly taken into consideration.

Regarding T4, the processing time on the server side. I think that 
should actually  be included in the formula as it is something that is 
implementation dependent. It is also a factor when one uses transmission 
scheduling of any type. Thus I think it should be consider to be 
maintained as a variable that has no given value.

Also I would like to introduce a T5 which is the client loss detection time:

        Sender
 >      -------------V----D--------/-----------------------V--------
 >             T1    T5      T2        T3       T4     T1   ........
 >        Receiver
 >

Where T5 is the time between T1, when it should be have been delivered 
and point D where the client has positively identified a packet as being 
lost. This would at least be the jitter-buffer depth, to allow for 
reordering. However it might be that certain algorithms do add even more 
delay here.

Thus I think that we can revisit your T calculation. Note that T here is 
server side buffering time. Which can arguable be around the same if one 
assumes that client is simply buffering T1 time later than the server:

T=T1+T2+T3+T4+T5; T1+T3 ~= RTT
T=RTT + T2 + T4 +T5; T2 = 1.5/1.21828*RTCP_Interval
T=RTT + 1.2312*RTCP_Interval + T4 + T5;

RTCP_Interval = AVG_RTCP_SIZE * 8*(Senders + Receivers) / (RR+RS); In 
the considered deployment the Sender + Receivers = 3; RR+RS is then 
equal to 5% of Session BW; AVG_RTCP_SIZE = 125
Thus
T=RTT+ 1.2312*AVG_RTCP_SIZE * 8 * 3 /(0.05*BW) + T4+T5

T(N) = N*(RTT+1.2312*AVG_RTCP_SIZE * 8 * 3 /(0.05*BW)+T4+T5)

As both T4 and T5 are difficult to give specific values for I have set 
them equal to zero which results in underestimated values.

BW       RTT     AVG_RTCP_SIZE  N=1             N=2
64000    0,05    125            1,20425         2,4085
128000   0,05    125            0,627125        1,25425
256000   0,05    125            0,3385625       0,677125
512000   0,05    125            0,19428125      0,3885625
1024000  0,05    125            0,122140625     0,24428125
5000000  0,05    125            0,0647744       0,1295488
10000000 0,05    125            0,0573872       0,1147744

BW       RTT     AVG_RTCP_SIZE  N=1             N=2
64000    0,2     125            1,35425         2,7085
128000   0,2     125            0,777125        1,55425
256000   0,2     125            0,4885625       0,977125
512000   0,2     125            0,34428125      0,6885625
1024000  0,2     125            0,272140625     0,54428125
5000000  0,2     125            0,2147744       0,4295488
10000000 0,2     125            0,2073872       0,4147744

BW       RTT     AVG_RTCP_SIZE   1              2
64000    1       125            2,15425         4,3085
128000   1       125            1,577125        3,15425
256000   1       125            1,2885625       2,577125
512000   1       125            1,14428125      2,2885625
1024000  1       125            1,072140625     2,14428125
5000000  1       125            1,0147744       2,0295488
10000000 1       125            1,0073872       2,0147744

BW       RTCP_Interval_D
64000    0,9375
128000   0,46875
256000   0,234375
512000   0,11718755
1024000  0,05859375
5000000  0,012
10000000 0,006

Which to me looks significantly different. First of all I seem to have a 
longer time for the low bit-rate cases. Probably the errors in the RTCP 
transmission schedule. Secondly I seem to have reasonable values for 
higher bit-rates due to that I avoid the simplification between RTCP 
transmission intervals and RTT.

So should we try to improve my formula and provide some guiding numbers 
for certain of the variables? I think it might be worth reconsider the 
used AVG_RTCP_SIZE to a slightly bigger number, due to that I haven't 
fully taken the NACK vector into account.

Then the T4 and T5 values should probably be considered further. The 
unfortunate thing is that T5 is really problematic and highly variable. 
In fact it needs an adoptive mechanism to talk this correctly into 
account. The jitter can be highly variable.

Cheers

Magnus

-- 

Magnus Westerlund

Multimedia Technologies, Ericsson Research EAB/TVA/A
----------------------------------------------------------------------
Ericsson AB                | Phone +46 8 4048287
Torshamsgatan 23           | Fax   +46 8 7575550
S-164 80 Stockholm, Sweden | mailto: [email-masked]