Subject: [AVT] WGLC: draft-ietf.avt-ulp-19.txt

From: "Even, Roni" <[email-masked]>
Date: Tue, 28 Nov 2006 12:37:14 +0200

Hi,
I gave the draft for review to Steve Botzko from Polycom, he is involved with forward error correction work. The comments are from the point of view of using this work for conversional video conferencing. 
Here are his comments

Thanks
Roni Even

- For our codec profiles, the "most important" information in the packet is not at the front.   Even when motion vectors are segmented from the rest of the bitstream, you still need to get the intra block DCT coeffients, which are not placed with the motion vectors.  Also, the amount of the bitstream which is needed for the motion vector encoding varies enormously from frame to frame.  So it would be quite difficult to set the appropriate amount of uneven protection, and to change it on-the-fly to get the appropriate protection level.

- With uneven protection, this RFC is assuming error-concealment on the video layer that goes along with the FEC.  There is also an unstated assumption that this error concealment is significantly more effective if the loss of motion vectors (or other "up front" data) is reduced.  These assumptions are not validated.  There is no error-concealment in most deployed video codecs (esp. in streaming video codecs).  There is no standard for how to do error-concealment, or any agreed-upon industry metrics on how to measure the effectiveness of a concealment method.  In my own subjective testing, error concealment is of limited value, especially for content video.  Even with talking heads, error concealment results in frequent objectional video artifacts, esp. given the limited FEC protection offered by XOR.

- XOR FEC can handle isolated packet loss, but does not handle multiple packet loss per group very well.  Allowing the groups to overlap offers some improvement.  However, an XOR scheme simply is not as efficient as a systematic FEC code such as Reed-Solomon.  Note that systematic FEC codes are optimal from a theoretic coding theory perspective.  Even at modest error rates, XOR FEC produces unacceptably high overhead.  

For instance, lets assume that we are sending 100 data packets a second (not counting recovery packets), with 1% channel loss.  If we use Reed-Solomon with 2 protection packets for each 10 data packets, then we have a breakdown in protection about once in 4863 groups. At 100 packets per second, this results in a protection breakdown once every 6 minutes, with an overhead of 20%.

If we use XOR, we'd be sending 1 XOR packet every 5 data packets to get the same overhead.  Protection breakdowns then occur once every 685 groups - or about once every 33 seconds.  Reed-Solomon in this example offers an order of magnitude better performance for the same overhead.  

If we go with 4 packets for groups of 20 data packets, performance systematic codes like Reed-Solomon improves still further - breaking down once every 275721 groups, or about once every 16 hours.  Again with the same 20% overhead.  (Of course latency is increased to 200 ms).  With streaming video latencies, the gap between XOR and systematic codes increases still further.

So I see little value in an RFC that limits itself to XOR protection - the FEC effectiveness is just too weak. I also think that FEC RFCs really should include an analysis of the strength of their protection.

One minor comment on the encryption section - XORing pre-encryption creates a known mathematical relationship between the unencrypted data and the unencrypted XOR packets.  As mentioned in the text, it is certainly a bad idea to encrypt them with the same key.  I'm thinking that should be forbidden.  Its not clear that even encrypting XOR with a different key is secure enough.  Certainly best to XOR before encryption.

Steve B.

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

---

From: Colin Perkins <[email-masked]>
Date: Tue, 28 Nov 2006 12:30:23 +0000

Roni, Steve, Adam,

On 28 Nov 2006, at 10:37, Even, Roni wrote:
> I gave the draft for review to Steve Botzko from Polycom, he is  
> involved with forward error correction work. The comments are from  
> the point of view of using this work for conversional video  
> conferencing.
> Here are his comments

Thanks for sending these comments. It's clear that a further revision  
of the draft is needed before it can progress to the IESG.

> - For our codec profiles, the "most important" information in the  
> packet is not at the front.   Even when motion vectors are  
> segmented from the rest of the bitstream, you still need to get the  
> intra block DCT coeffients, which are not placed with the motion  
> vectors.  Also, the amount of the bitstream which is needed for the  
> motion vector encoding varies enormously from frame to frame.  So  
> it would be quite difficult to set the appropriate amount of uneven  
> protection, and to change it on-the-fly to get the appropriate  
> protection level.
>
> - With uneven protection, this RFC is assuming error-concealment on  
> the video layer that goes along with the FEC.  There is also an  
> unstated assumption that this error concealment is significantly  
> more effective if the loss of motion vectors (or other "up front"  
> data) is reduced.  These assumptions are not validated.  There is  
> no error-concealment in most deployed video codecs (esp. in  
> streaming video codecs).  There is no standard for how to do error- 
> concealment, or any agreed-upon industry metrics on how to measure  
> the effectiveness of a concealment method.  In my own subjective  
> testing, error concealment is of limited value, especially for  
> content video.  Even with talking heads, error concealment results  
> in frequent objectional video artifacts, esp. given the limited FEC  
> protection offered by XOR.
>
> - XOR FEC can handle isolated packet loss, but does not handle  
> multiple packet loss per group very well.  Allowing the groups to  
> overlap offers some improvement.  However, an XOR scheme simply is  
> not as efficient as a systematic FEC code such as Reed-Solomon.   
> Note that systematic FEC codes are optimal from a theoretic coding  
> theory perspective.  Even at modest error rates, XOR FEC produces  
> unacceptably high overhead.
>
> For instance, lets assume that we are sending 100 data packets a  
> second (not counting recovery packets), with 1% channel loss.  If  
> we use Reed-Solomon with 2 protection packets for each 10 data  
> packets, then we have a breakdown in protection about once in 4863  
> groups. At 100 packets per second, this results in a protection  
> breakdown once every 6 minutes, with an overhead of 20%.
>
> If we use XOR, we'd be sending 1 XOR packet every 5 data packets to  
> get the same overhead.  Protection breakdowns then occur once every  
> 685 groups - or about once every 33 seconds.  Reed-Solomon in this  
> example offers an order of magnitude better performance for the  
> same overhead.
>
> If we go with 4 packets for groups of 20 data packets, performance  
> systematic codes like Reed-Solomon improves still further -  
> breaking down once every 275721 groups, or about once every 16  
> hours.  Again with the same 20% overhead.  (Of course latency is  
> increased to 200 ms).  With streaming video latencies, the gap  
> between XOR and systematic codes increases still further.
>
> So I see little value in an RFC that limits itself to XOR  
> protection - the FEC effectiveness is just too weak. I also think  
> that FEC RFCs really should include an analysis of the strength of  
> their protection.

Given these comments, I think it would be useful if the draft were  
revised to more clearly state its applicability, and to include more  
discussion and analysis of the strengths and weaknesses of the  
protection mechanism chosen. I think there is value in the simple  
parity-FEC codes defined by the draft, compared to the more complex  
Reed-Solomon codes, but the trade-off between complexity and  
performance needs to be made explicit.

> One minor comment on the encryption section - XORing pre-encryption  
> creates a known mathematical relationship between the unencrypted  
> data and the unencrypted XOR packets.  As mentioned in the text, it  
> is certainly a bad idea to encrypt them with the same key.  I'm  
> thinking that should be forbidden.  Its not clear that even  
> encrypting XOR with a different key is secure enough.  Certainly  
> best to XOR before encryption.

I'd also like to either see a revision that makes this restriction,  
or some explanation why the current approach is sufficient.

Colin

---

From: "Marshall Eubanks" <[email-masked]>
Date: Tue, 28 Nov 2006 09:31:55 -0500

Hello;

> of the draft is needed before it can progress to the IESG.
<snip>
> > best to XOR before encryption.

(BTW, I would assume that this last line should actually read, "after
encryption".)

XORing after encryption is merely protecting encrypted packets, and
thus raises no
instrinsic issues.

XORing before encryption is the issue here, and there are 4
possibilities, as discussed in the draft (I have added numbers for
disucssion).

1       o The FEC stream may be encrypted, while the media stream is not.
The draft implies that this SHOULD NOT be done.

2       o The media stream may be encrypted, while the FEC stream is not.
The draft implies that this SHOULD NOT be done.

3      o The media stream and FEC stream are both encrypted, but using
        different keys.
The draft implies that this or case 4 SHOULD be done.

4      o The media stream and FEC stream are both encrypted, but using
        the same key.
The draft implies that this or case 3 SHOULD be done.

As far as I can tell, cases 3 and 4 are not distinguished further.

I would urge changing case 2 to MUST NOT. If the main stream is sent
in the clear and the FEC is protected (case 1) then you are wasting
CPU cycles, but doing no real harm, so SHOULD NOT is ok there.

If you do the reverse, case 2, then you are opening yourself to
known-plaintext attacks. In many case, much or all of some packets of
an RTP stream may be predictable or guessable (headers of MPEG frames,
configuration information, etc.). Suppose that you are XORing two
packets a and b and sending f(a), f(b) and a * b (where f() is a
cryptographic function and * means XOR). If I can predict or guess a,
then I can determine b. There may be enough structure in the packets
to make this possible even if I know nothing of f(), but if I can
calculate f(a), which may well be possible, then I can just look for
f(a) being sent and then determine b from the unencrypted FEC. If I
only know part of a, I may still be able to brute force this. Even if
I am XORing multiple packets together, I am still leaking information
about each packet into the XOR and sending it into the clear. This is
bad, bad, bad.

(The same sort of attacks would be possible in case 2 for any FEC
function, such as Reed-Solomon, as long as the attacker knows or can
guess what it is.)

So, I think case 2 needs to be MUST NOT. By the same reasoning, case 3
MUST NOT use a weaker encryption for the FEC than for the main rtp
stream.

Steve worries that case 3 is better than case 4. I would argue that it
doesn't matter much. As before, we should assume that it is possible
to guess some of the packets being sent (i.e., known plaintext attacks
must be assumed). In particular, if
I know some packet of an RTP stream, it may be possible to guess
subsequent ones.
So, while case 4 means that the attacker knows something of the
structure of the stream being sent, this sort of knowledge has to be
assumed anyway. So I would regard case 3 as an illusionary
complication, and cases 3 and 4 as being equally good.

Regards
Marshall

---

From: Andrea Lorenzo VITALI <[email-masked]>
Date: Tue, 28 Nov 2006 16:23:04 +0100

XOR codes not only are simple but also they can be used efficiently to
recover from losses.

Examples mentioned refer to (N,K) codes, where K is the number of data
packets, and N-K is the number of added recovery packets.

Reed-Solomon codes are based on Galois fields GF(2^n). They have the
nice property that they can recover up to N-K losses. In other words:
you recovery capability is exactly as much as the added redundancy.

XOR codes are based on Galois fields GF(2). They can also be used to
recover from losses. However they can recover slightly less than N-K
losses. In other words: there is an overhead. Depending on the loss
pattern you may need to receive more than the absolute minimum (K
packets out of N) in order to recover losses.

The examples mentioned below are summarized here:
  1. Reed-Solomon (12,10), 100% probability to recover
  2. XOR          ( 6, 5), 100% probability to recover
  3. Reed-Solomon (24,20), 100% probability to recover

I would like to add a couple of examples:
  4. XOR          (12,10),  51% probability to recover
  5. XOR          (24,20),  65% probability to recover

This is the concept behind digital fountains, as you may already know.
One of the simplest schemes is as follows: you transmit K data packets,
then you generate N-K redundancy packets by (pseudo)random selection and
XOR of data packets.

At the receiver side, depending on the loss pattern, the code will allow
recovery with a given probability. The probability grows to nearly 100%
when N grows.

The advantage of Reed-Solomon codes (and XOR (N+1,N) codes) is that the
probability is exactly 100%. And this is useful when N is small. The
advantage disappear when N is large enough.

The disadvantage of Reed-Solomon codes is that they are very very
complex to implement, while XOR is very simple.

A final remark: one may decide to limit the number of packet-XOR
operations at the decoder and trade-off computational power for recovery
performance.

  Andrea

>> second (not counting recovery packets), with 1% channel loss.  If we
>> use Reed-Solomon with 2 protection packets for each 10 data packets,
>> then we have a breakdown in protection about once in 4863 groups. At
>> 100 packets per second, this results in a protection breakdown once
>> every 6 minutes, with an overhead of 20%.
>>
>> example offers an order of magnitude better performance for the same
>> overhead.
>>
>> systematic codes like Reed-Solomon improves still further - breaking
>> down once every 275721 groups, or about once every 16 hours.  Again
>> with the same 20% overhead.  (Of course latency is increased to 200
>> ms).  With streaming video latencies, the gap between XOR and
>> systematic codes increases still further.
>>
>> So I see little value in an RFC that limits itself to XOR protection -
>> the FEC effectiveness is just too weak. I also think that FEC RFCs
>> really should include an analysis of the strength of their protection.
> 
> Reed-Solomon codes, but the trade-off between complexity and performance
> needs to be made explicit.

-- 
 ______________________________________________________________

  Andrea VITALI                            [email-masked]

  tel (+39) 039 603 7244             mobile (+39) 347 93 08 433
  fax (+39) 039 603 6129

  STMicroelectronics
  Centro Direzionale COLLEONI - Palazzo "DIALETTICA"
  20041 Agrate Brianza (MI) ITALY
 ______________________________________________________________

---

From: Adam Li <[email-masked]>
Date: Tue, 28 Nov 2006 07:53:16 -0800

Hi Roni, Steve,

Thanks for the comments.

(1) About the effectiveness of ULP
This issue was the first thing that we presented when we proposed ULP
extension to RFC 2733 (which evolved to the current draft). In our
presentation in IETF-50, the rate-distortion performance of ULP is
throughly tested with H.263 at various loss rates. The gain is from
around 1/4 dB at 1% loss to around 1 dB at 5% loss. Please check the
detailed graphs in that presentation. Hope that answered your concern there.

(2) About the effectiveness of XOR
As also pointed out by Andrea Lorenzo in an earlier reply, the XOR can
be quite effective recover from loss, and more importantly is extremely
simple to implement. The fact that we now have RFC 2733 implemented in
many endpoints is a good validation that XOR can be used effectively.
The current draft being an update to RFC 2733, I don't feel we need to
re-justify that fact again, right?

Regards,

Adam

---

From: Colin Perkins <[email-masked]>
Date: Tue, 28 Nov 2006 16:08:18 +0000

> re-justify that fact again, right?

No - given the advances since RFC 2733 was published, I think it  
worthwhile to include further justification and explanation of where  
this fits in with other FEC schemes.

Colin

---

From: Steve Underwood <[email-masked]>
Date: Wed, 29 Nov 2006 00:27:45 +0800

>re-justify that fact again, right?
Could you point to some end points actually using RFC2733? I've been 
trying to find some real world implementations of RFC2733, and I've come 
up blank. I noticed someone recently asked on this list if anyone had 
implemented RFC2733, and there seemed to be no reply.

I am currently interested in implementing RFC2733 for T.38 over RTP. 
However, the results so far make it look like a waste of time. The only 
way to get a meaningful boost in packet loss tolerance over simple 
redundancy causes too much latency. If I didn't care much about latency 
I wouldn't be using RTP in the first place. For the more commonly used 
UDPTL transport for T.38 I have implemented both the redundancy scheme 
which is akin to RFC2198 and the FEC scheme akin to simple XOR'ing with 
RFC2733. In the real world it seems everyone uses only the redundancy 
option, and important packets are sent multiple times.

Regards,
Steve

---

From: Andrea Lorenzo VITALI <[email-masked]>
Date: Thu, 30 Nov 2006 10:04:59 +0100

> this fits in with other FEC schemes.

I didn't read all RFCs and all IETF drafts related to FEC, however I
used RFC2733 so I can mention two points which may have already discussed:

- as specified in RFC2733 the header contains a bitmap which specify
which packets have been XORed; it would be nice to save these bits and
implement something more flexible so that the decoder can guess what the
encoder has done (e.g. using the packet's sequence number and a
pseudo-random number generator) - Digital Fountains could be easily
implemented this way.

- allow more than XOR ops, e.g. GF(2^n) operations; so that XOR codes
will be just a special case and Reed-Solomon codes could be done.

  Andrea

  STMicroelectronics

---

From: Stephan Wenger <[email-masked]>
Date: Thu, 30 Nov 2006 14:27:34 +0200

Steve,

On Nov 28, 2006, at 6:27 PM, Steve Underwood wrote:
[...]

> Could you point to some end points actually using RFC2733? I've  
> been trying to find some real world implementations of RFC2733, and  
> I've come up blank. I noticed someone recently asked on this list  
> if anyone had implemented RFC2733, and there seemed to be no reply.

We (that's Nokia) have proposed the use of RFC2733 or ULP in  
conjunction with video in 3GPP SA4, and we provided simulation  
results, so I guess we have an implementation :-)  But as you I'm  
unaware of product implementations.

regards,
Stephan
[...]

---

From: Stephan Wenger <[email-masked]>
Date: Thu, 30 Nov 2006 14:38:37 +0200

Hi Colin, all,

On Nov 28, 2006, at 6:08 PM, Colin Perkins wrote:

> worthwhile to include further justification and explanation of  
> where this fits in with other FEC schemes.

Some fairly advanced media formats offer tricks that in our view  
allow to employ simple XOR FEC (only) without significant delay  
increase.  We (Nokia) have proposed such tricks in 3GPP SA4. There,  
we protect two important media packets (whatever that means for the  
specific media codec) with one FEC packet.   I don't want to re- 
create ongoing discussions in SA4 here, where the usefulness of our  
trick is challenged, but I can provide pointers to documents for  
those interested.  (Please contact me in private.  We also have  
academic work in preparation, which should be available in the  
foreseeable future).

IMHO, there is little point in evaluating Reed-Solomon or any other  
"higher" FEC code for an RTP payload format.  If your delay tolerance  
is such high that you can afford multiple repair packets per FEC  
block, go use fecframe WG's technology, or use feedback based repair  
(whatever fits your application better).  When using only a single  
repair packet per FEC block, there is no difference between XOR FEC  
and the other FEC schemes.

With respect to the uneven protection feature, and in response to  
Stephen: yes, there are media formats that could employ uneven  
protection.  Examples include G.723.1 with Annex C enabled, H.263  
with Annex V enabled, H.264 in extended profile or in baseline when  
RFC3984 aggregation packets are used, and these packets are populated  
in a smart way.  Yes, no one is using any of these in the way they  
could be used, but are we all sure that's not a chicken-and-egg problem?

In consequence, let me speak in favor of moving the ULP draft finally  
forward.  Yes, there is value in adding some discussion why Reed- 
Solomon (or any higher FEC code) does not make much sense, perhaps  
along the lines of point 1 above.  But then, PLEASE, let's call it a  
day.  18 revisions are enough.

Regards,
Stephan