Subject: [AVT] Re: comments on Pre-release of draft-ietf-avt-mpeg4-simple-05.txt

From: Stephen Casner <[email-masked]>
Date: Wed, 20 Nov 2002 07:17:29 -0800 (PST)

On Tue, 19 Nov 2002, Dave Singer wrote:

> I'm concerned about the text about interleaving in this document.   I
> don't think it is workable.  I have a number of points, below, and
> then proposed text, which I believe is both simpler and more workable.
>
> First, the document seems to want to talk about the sender behavior,
> which I think is irrelevant.  We are documenting a protocol, and we
> should document the contract between the sender and receiver.  The
> computation of a 'sender delay' for pre-packetized stored content is
> meaningless, anyway.

I agree with Dave's comments here.  I am concerned about the extent to
which the interleaving text has grown, not to mention technical
considerations.

> It seems to overstate what the receiver needs to buffer.  In
> particular, the receiver only needs a buffer that will hold the range
> from (lowest AU timestamp not received) through (highest AU timestamp
> received).

Agree again.  The total interleave delay shown in the example is 8,
but the sender buffers 4 of that and the receiver only needs to buffer
4, so 4 is what should be advertised in the InterleaveDelay parameter,
not 8.

                                                        -- Steve

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

---

From: Dave Singer <[email-masked]>
Date: Tue, 19 Nov 2002 17:15:20 -0800

The definition is both remarkably complex, and quite hard to verify, 
given a stream.  I'm concerned in particular that the equations use 
the re-ordered timestamps to compute access unit durations.  If 
access units are lost, might not the values computed by, and 
applicable to, sender and receiver, be different?

It seems to overstate what the receiver needs to buffer.  In 
particular, the receiver only needs a buffer that will hold the range 
from (lowest AU timestamp not received) through (highest AU timestamp 
received).  This is the additional buffering cost of interleave; 
de-jitter or pre-decode or post-decode buffers, are, of course, 
common to all streams.  Perhaps some of the confusion comes from 
calling this "de-interleave delay".  In fact, the delay through this 
buffer might be very small.  (Consider a stream where I make one RTP 
packet one AU larger and thereby send one AU very 'early' in the 
stream.  The whole stream decode has not been 'delayed' at all 
compared to the un-re-ordered stream).  A new name may be better.

Finally, I do not think that this kind of magnitude of conceptual and 
textual change comes within the kind of editorial operations we 
should be doing in 'last call', should it?

I'd like to review the specification history here.  I proposed simple 
interleave as a way to alleviate loss in audio.  The text I wrote, 
and that ISMA uses now, assumed that the RTP time-stamps of packets, 
when considered in RTP sequence order, always increased;  one could 
never go back in time.  Unfortunately, this was only implied in the 
text and never clearly stated.  Jan's team at Philips came up with a 
scheme in which time *did* go backwards, in order to solve a certain 
set of constraints.  We decided to allow this, but receivers needed 
to know "how far backwards?".  This is the value the receiver needs 
to know, in order to size its buffer, and to detect lost AUs.  It is 
the greatest ever difference in time-stamp between the latest AU 
received and the earliest AU not received.

The current document now spends almost half the text talking about 
interleave.  It doesn't need to be this complex;  even the text I 
have below is probably excessive.  This is already substantially more 
complex than any other interleaving scheme I know of in RTP (e.g. 
MP3, QCELP).  Below I give a complete, verifiable definition, and 
also worked examples.  I'd really like to understand clearly what the 
problem is with this 'simple' definition, before we adopt anything 
more complex. 

I have been working with Jan on this, but we ran out of time, so we 
have to take the discussion public.

(The diagrams are ASCII, and require fixed-width display).

* * * * *

The de-interleave delay must be signalled as equal to or greater than 
the greatest ever difference in time-stamp between the latest AU 
received and the earliest AU not received.  Formally, with Ti being 
the time-stamp of the i'th access unit, in stream order (i.e. in RTP 
sequence number order, and then by the order within the packets):

signalled value D = max[ all i, all j>i ]( Ti - Tj )

It is not signalled if less than zero, as this documents a stream in 
which the timestamps always increase (the timestamp of any access 
unit is greater than the timestamp of any AU which precedes it in 
stream).

This definition allows the receiver to allocate the minimal extra 
buffering needed for de-interleave.  If the maximum bit-rate of the 
content is B, then a buffer of B*D is needed.  Alternatively, for 
access units of constant duration C, a buffer of D/C access units is 
needed.

Appendix A. Examples of delay analysis with interleave

In this appendix several interleaving patterns are examined, and how 
they may be de-interleaved is shown, both when all packets arrive, 
and in the presence of loss.  It is worth re-stating the rule for a 
receiver to be able to 'emit' an access unit from the de-interleave 
buffer.  An access unit (or an erasure notification) may be emitted 
if either:
a) it has arrived and its timestamp indicates it is the next access 
unit after one that has been emitted (or is the expected first to 
arrive, at startup); or
b) its timestamp is strictly less than the timestamp of that access 
unit that has arrived with the highest timestamp, less the signalled 
de-interleave delay.

In these examples the de-interleave delay is cited in terms of an 
access unit count, for ease of reading.

A.1 Simple Group interleave

An example of regular interleave is when packets are formed into 
groups. If the 'stride' of the interleave is N, packet 0 could 
contain frame 0, frame N, frame 2N, and so on; packet 1 could contain 
frame 1, frame 1+N, 1+2N, and so on. The AU-Index field is used to 
document the sequence of the packet within the group (or the first 
frame in the packet, which is the same thing in this scheme), and all 
the AU-Index-delta fields contain N-1.

If there are M access units in a packet, then there are M*N access 
units in the group.  If the interleave is done in the regular pattern 
as given above, then the smallest de-interleave delay needed is 
((M-1)*N - 1).

This is calculated as follows.  A pair of consecutive packets contains:

Q, Q+N, Q+2N...Q+(M-1)*N
Q+1, Q+1+N, Q+1+2N,...Q+1+(M-1)*N

After receipt of the first packet, the latest AU received is 
Q+(M-1)*N, and the lowest 'hole' (AU not received) is Q+1.  The 
difference is Q+(M-1)*N - (Q+1) = (M-1)*N - 1.

This is smaller (by one access unit) than the packet size, which 
indicates (correctly) that the first access unit in each packet may 
always be emitted on arrival.

Receivers can tell when a new interleave group is starting, by noting 
that the computed time stamp of the last frame in a packet, minus the 
de-interleave delay, is later than any previously computed time 
stamp. This relies on the value of the de-interleave delay being 
correctly signalled by the transmitter;  if it is too large, then the 
receiver may buffer excessively.

An example with N=M=3 follows:

    Packet   Time stamp   Frame Numbers    AU-Index, AU-Index-delta
    0        T[0]         0, 3, 6          0, 2, 2
    1        T[1]         1, 4, 7          0, 2, 2
    2        T[2]         2, 5, 8          0, 2, 2
    3        T[9]         9,12,15          0, 2, 2

The minimum de-interleave delay here is ((3-1)*3 - 1) = 5.  In this 
case, the receiver would have to buffer 4 frames at least from 
packets 0 and 1, and can emit all frames when packet 2 arrives. 
(Frame 0 can be emitted as packet 0 arrives, since it is the earliest 
frame we hold, and likewise frame 1 from packet 1; we are therefore 
holding 3,4,6,7 until packet 2 arrives).

If there is loss, then the receiver may wait longer than is strictly 
necessary before it emits frames. For example, say packet 1 is lost 
from the above example. The pattern is as follows:

A -- arrival;
L -- loss;
E -- emission from de-interleave buffer;
w -- 'water-mark', the earliest access unit we must keep in the 
de-interleave buffer

Access unit numbers increase across the page;  each packet is a row, 
and packets are consecutive down the page.

     0   1   2   3   4   5   6   7   8   9
0   AE  w       A           A
1       L           L           L
2       E   AE  wE      A           A
3                   E   E   E   E   E   AE  w

Packet 0 allows frame 0 to be emitted as it is in the earliest slot. 
Then packet 2 arrives, allowing us to notice the loss of frame 1, and 
emit frame 2 and 3 (since the first two precede the water-mark, and 
the thirs is then the earliest in the buffer). Then it is not until 
the arrival of packet 3 (which has a time-stamp beyond the times of 
all the frames seen so far), that we can finish dealing with the 
loss, even though the first group has, in fact, ended. (This is in 
contrast to schemes which signal the group size explicitly; if the 
receiver knows that this is packet 3 of 3, then even if 2 of 3 is 
missing, it can de-interleave this group without waiting for the next 
one to start).

In the above example the AU-Index is coded with the value 0, as 
required for the modes defined in this document. To reconstruct the 
original order, the RTP time stamp and the AU-Index-delta are used. 
See also section 3.2.3.2.

A.2 More subtle group interleave

Another example of forming packets with group interleave is given 
below. In this example the packets are formed such that the loss of 
two subsequent RPT packets does not cause the loss of two subsequent 
audio frames. Note that in this example the RTP time stamps of 
packets 3 and 4 are earlier than the RTP time stamps of packets 1 and 
2, respectively.

    Packet   Time stamp   Frame Numbers    AU-Index, AU-Index-delta
    0        T[0]         0,  5            0, 5
    1        T[2]         2,  7            0, 5
    2        T[4]         4,  9            0, 5
    3        T[1]         1,  6            0, 5
    4        T[3]         3,  8            0, 5
        
    5        T[10]       10, 15            0, 5
    and so on ..

The minimum value that can be used here for the de-interleave delay 
is 8 (note that packet 2 brings access unit 9 while access unit 1 is 
still missing).  Though this format has the advantage cited above, it 
is instructive to inspect its de-interleave behavior.  The diagram is 
notated as before.  In this case we lose packet 8 of the second group.

     0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16 
17  18  19  20
0   AEw                 A  
1   w       A                   A
2       w           A                   A
3       AEw E               A
4       w       AE  E   E   E   E   AE  E
5                               w          AE                  A
6                                       w          A                   A
7                                              w             A 
A
8                                              Lw                  L
9                                              w         A                 A
10                                            E   E     E   E  E  E 
Ew  E   E   AE

It's worth noticing that even the emission of the first group (which 
has no loss) is bursty.  The second group gets held almost in its 
entirety until the first packet (packet 10) of the third group 
arrives, as a consequence of the loss.

A.3 Continuous interleave

In continuous interleave, once the scheme is 'primed', the number of 
frames in a packet exceeds the 'stride' (the distance between them). 
This shortens the buffering needed, smooths the data-flow, and gives 
slightly larger packets -- and thus lower overhead -- for the same 
interleave. For example, here is a continuous interleave also over a 
stride of 3 frames, but with 4 frames per packet, for a run of 20 
frames. This shows both how the scheme 'starts up' and how it 
finishes.

    Packet   Time-stamp    Frame Numbers      AU-Index, AU-Index-delta
    0        T[0]                      0      0
    1        T[1]                  1   4      0  2
    2        T[2]              2   5   8      0  2  2
    3        T[3]          3   6   9  12      0  2  2  2
    4        T[7]          7  10  13  16      0  2  2  2
    5        T[11]        11  14  17  20      0  2  2  2
    6        T[15]        15  18              0  2
    7        T[19]        19                  0

In this case, the receiver has to buffer only 3 frames, not 4. Say we 
are waiting for packet 4. We can emit frames 0, 1, 2, 3, 4, 5, 6; we 
are holding therefore 8, 9, 12. Packet 4 arrives, allowing us to emit 
7,8,9,10, and we are holding 12,13,16. Each arriving packet contains 
4 frames, and allows 4 frames to be emitted.

In the above example the AU-Index is coded with the value 0, as 
required for the modes defined in this document. To reconstruct the 
original order, the RTP time stamp and the AU-Index-delta are used. 
See also 3.2.3.2.  This example also has RTP time-stamps in 
increasing order.  The minimum de-interleave delay here is 5 here 
(the highest numbered access unit from one packet, less the 
lowest-numbered access unit of the next packet).

Here is the behavior under loss again:

     0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16 
17  18  19  20  21  22  23  24
0   AEw
1   w   AE          A
2           AE  w       A           A
3               L           L           L          L
4               E   E   E   E   AE  E   E  AE   w      A           A
5                                               AE E   E   AE   w 
A           A
6                                                               AE E 
E   AE  w       A           A

If there is loss, again the receiver has to wait to emit the erasure 
frames. In this case, say packet 3 is lost. We were holding frames 4, 
5, and 8. On the arrival of packet 4, the water-mark is 16-5=11.  We 
now know frame 3 was lost, we can emit frames 4,5, and we know 6 must 
be lost, and emit 7 and 8, notice the erause of 9, and emit 10. Then 
on the arrival of packet 5 with a water-mark of 20-5=15,  we can emit 
11, indicate loss of 12, and emit 13 and 14. This has completed the 
loss recovery;  the emissions on the arrival of packet 6 are the 
usual four.

-- 
David Singer
Apple Computer/QuickTime