Subject: Re: Choices for TRACK/NACK report encoding

From: Dah Ming Chiu - Sun Microsystems <[email-masked]>
Date: Thu, 7 Sep 2000 15:01:14 -0400 (EDT)

I had a brief discussion with Brian Whetten regarding his concerns
on loss packet report encoding.

He seems to be concerned with a scenario where there are a large number,
K, packets in flight (meaning potentially a receiver may report a
loss of any one of them), where K can be as large as many thousands.
A receiver lost the first of the K packets; and due to the fat-long
pipe to its repair head (or sender), it soon is receiving the Kth packet
before the first lost packet is repaired.  In this "worse case" example,
the receiver also lost the (K-1)th packet. So this receiver needs an
efficient way to report the status of K packets (received or not received)
to its repair head or the sender.

Based on this, he did a quick analysis of three schemes:
a) listing out the sequence number of each lost packet
b) use a bitmask of size K to indicate which ones are lost
c) use Run Length Encoding to indicate which ones are lost
and concluded that RLE is the best.

In the particular example above, a total of 2 of K packets lost, the rough
encoding overhead is respectively:
a) 2*W
b) W+K
c) W+2*logK
where W is the size of a sequence number (32).

If in additional to the above 2 lost packet, there are an additional (n-2)
lost packets - making it a total of n lost packets, then:
a) n*W
b) W+K
c) W+n*logK

What is wrong with this analysis, I think some other people have also
pointed out, is that it does not take into account the option of sending
multiple ACKs (here an ACK is a general term for a common receipt/lost
reporting message).  Of course, there is some overhead in sending each
ACK.  But in the case of (b), sending multiple ACKs would be more efficient
than sending a huge bitmask of size K.

It is complicated to do an exact analysis of the different encodings taking
into account of the option of sending multiple ACKs.  On the other hand,
I don't think the result differ that much for us to be concerned about it.

I think we should just adopt something simple.  Having a sequence number
plus an optional bit mask - where the sequence number indicates receipt
up to, and the mask indicates lost packets - is simple and flexible.

As to whether it makes sense to run a reliability service with K packets
in flight for such large K makes sense or not, that is another debate.

Does this make sense?

Dah Ming

---

From: Jon Crowcroft <[email-masked]>
Date: Fri, 08 Sep 2000 08:15:24 +0100

analysis
looks ok to me - there was an analysis done for SACK in TCP that is
worth re-reading (look on end2end-interest archive)

its not clear why multicast is so different (theres probably enough
reasons for occasional  feedback messages and a hierarchy for very
large groups that within each group the loss feedback packet encdoding
can be similar to SACK or possibly RTCP...

one thing is do we believe in long loss bursts or scattered
bursts...?

In message <[email-masked]>, Dah Ming Chiu - Sun Micros

 >>in flight for such large K makes sense or not, that is another debate.

 cheers

   jon

---

From: Luigi Rizzo <[email-masked]>
Date: Fri, 8 Sep 2000 10:34:37 +0200 (CEST)

> worth re-reading (look on end2end-interest archive)

i do not remember the details but the result ("we only need 3
sack blocks") look more driven by available option space than
other considerations. I believe one reason multicast is somewhat different
is that delayed feedback gives you the chance to report slightly higher
amt of losses in a single msg as opposed to what you do in TCP
where you {S|N}AK immediately.

> one thing is do we believe in long loss bursts or scattered

the experience with mbone sessions is often 30s bursts of silence,
but that can be fixed hopefully...
Seriously speaking, as long as multicast sessions are not as bursty
as TCP, i think that more than long loss bursts (which are usually
due to routing problems) we can see the typical losses due to rate
mismatches, or patterns like this

	....x....x....x....x....x....
	...x..x..x..x..x..x..x..x..x.
	.xxx.xxx.xxx.xxx.xxx.xxx.xxx.

	cheers
	luigi

---

From: Jon Crowcroft <[email-masked]>
Date: Fri, 08 Sep 2000 09:37:54 +0100

luigi

and of course wee might want  to consider router or repair server
assist in aggregating the loss patterns...

 cheers

   jon

---

From: Brian Adamson <[email-masked]>
Date: Fri, 8 Sep 2000 10:52:05 -0400

>	.xxx.xxx.xxx.xxx.xxx.xxx.xxx.

One of the nice applications of reliable multicast is over satellite 
services ... at reasonable data rates (several megabits per second), 
outages which are relatively momentary (a few seconds) can span 
several FEC coding blocks worth of information and do occur 
occasionally ... Also depending upon different application policies 
of when/how receivers join & leave groups or discontinuities during 
handoff in mobile-wireless systems, there will be times when 
receivers need to NACK for large portions of data ... Those are some 
of the reasons I would propose a hierarchical scheme for NACK 
encoding given that use of FEC blocks (if applicable) provide a 
natural boundary ... I suppose this isn't much different from the end 
result of a run-length encoding scheme, but alignment of hierarchical 
NACKs to coding blocks was easy to implement.

>	luigi

Brian
__________________________________
Brian Adamson
<http://manimac.itd.nrl.navy.mil>
<mailto:[email-masked]>

---

From: Jon Crowcroft <[email-masked]>
Date: Fri, 08 Sep 2000 16:10:49 +0100

so we have a large range+accuracy problem in returning 
data to the sender(s) about missing sequence numbers
and so if the ack return path is noisy, then lets subject
the problem to the same attack s we did to data in the forward
path

layered FEC encoded SACK messages...

 cheers

   jon

---

From: Brian Whetten <[email-masked]>
Date: Fri, 08 Sep 2000 10:39:30 -0700

Hello,

My original concern were that I would like us to come up with ONE form for
NACK encoding, that is the same for both TRACK and NACK, and is as simple
as possible.  Also, I would like the mechanism to have enough redundancy
built in that reliable NACKs are not needed.

Jon, RM is different than unicast primarily because optimizing the return
control traffic is one of our primary challenges (i.e. minimizing ACK/NACK
implosion).

Dah Ming, good point.  Actually, the biggest problem with bitmaps, that I
forgot about, is how you do the aggregation of FEC counts as you move up a
hierarchy.  You can solve this, but only with added complexity.  If you are
using one big RLE bitmap, you have to unpack it to make it intelligible by
the intermediary nodes, which is probably too much overhead. 

Jon, I think FEC encoded NACK bitmaps is overly complex and unecessary, but
I'm not sure I actually understand what your proposal is.

Brian, my initial reaction to your proposal was that it was too complex,
but now I'm not so sure.  One issue though, is that you need to pass up the
most recent congestion information you have in each NACK.  If you are not
NACKing the most recent packets, then this has to definitely be explicitly
reported, rather than implicitly derived at the sender.  This might cause
problems for PGMCC, for example.

I think that the need to do FEC count aggregation is a good argument
against using a single long RLE bitmap.  

So I think we are left with three primary design choices:
1) How to encode each block of packets?  i.e. Count, Bitmap, None  (for
list NACKs, each block is of size 1)
2) How to encode the series of blocks?  Do we assume that they are all
sequential, or do you encode each block with its starting sequence number?
(note that this assumes the length of each block is the same)
3) How much history to put in each NACK?  Do we just list the most
immediate packets, or do we have some partial redundancy, or do we always
encode the entire outstanding window?  The more information we encode, the
simpler the NACK generation algorithms become, but the harder the encoding
algorithms in order to be able to deal with large windows.

Brian

---

From: Brian Adamson <[email-masked]>
Date: Fri, 8 Sep 2000 14:19:02 -0400

>I'm not sure I actually understand what your proposal is.

I haven't grok'd that yet either.

>problems for PGMCC, for example.

The congestion control feedback could use different sequence 
information than the data content identification ... For example, if 
a different sequence number (i.e. different than the data content 
identification sequencing) is used to mark packets for loss detection 
that could be used in congestion control feedback ... In our MDP 
congestion control implementation, we don't insert congestion control 
probing information (which is marked with its own sequence number) 
separately from transmitted data ... For something like PGMCC which 
is doing a TCP-like ACK of the data packets, the "packet loss" 
sequence marker on the data packets could perhaps be used? ... I 
think data content identification needs to be separate for selective 
repair anyway? ...

The "hierarchy" of coding block and segments gives you a degree of 
NACK compression  analogous to RLE and then aggregation doesn't 
require the RLE decompression/re-encoding step you mention above

>(note that this assumes the length of each block is the same)

Yes ... my assumption was that the bitmask marked a sequential series 
of coding blocks ... in our case, the blocks are uniform in size so 
the "offset" or data content sequence identifier of the first segment 
of the block serves as the block identifier ... I think non-uniform 
blocks could be accommodated, but the block identifier might need to 
be interpreted differently ... but that might only be the concern of 
the end systems ... intermediate systems (like generic assist 
routers) might still be able to perform aggregation/pruning, etc 
without needing to know that information ... this would be different 
for more tree-based protocols which might wish to perform repair 
subcasting, etc.

>algorithms in order to be able to deal with large windows.

The policy I have used in the past is to put as much history in the 
NACK (only back to the point to where repair is needed) which will 
fit into a single NACK message using the multicast session MTU as the 
maximum payload size ... For normal circumstances, NACKs tend to be 
small ... this limit is only hit when conditions are bad ... In our 
protocol, the sender actually sort of nacks NACKs when those repair 
requests ask for repairs earlier in history than the server is 
willing to repair (for whatever reason, buffer limitations, expired 
data, etc) ... In this NACK to the NACK (which we actually call a 
SQUELCH command in protocol specification), the sender advertises his 
current "window" of data he
is willing to repair ...  This "SQUELCH" is multicast so that all 
receivers (some of which may be in the same state as the original 
NACKer) can "re-sync" to the sender and not generate anymore useless 
NACKs ... again this is the _exceptional_ occurrence when conditions 
are very bad, and server buffer limits (or other limits) are 
otherwise exceeded.

Brian

---

From: Jon Crowcroft <[email-masked]>
Date: Sun, 10 Sep 2000 14:58:22 +0100

In message <[email-masked]>, Brian Whetten t

 >>I'm not sure I actually understand what your proposal is.

the info in the return path does not have to be 100% accurate -we can
err in either direction - not giveing enough detail _can_ result in
excessive retransmits (not necessariyl a big problem for
aggregating/filtering routers or servers),  or excessive
stall/congestion back off.....giving too much detail clogs the return
path.....layered fec coding the receive sequence number lists allows the
aggregtion ponts to choose how to err...

 cheers

   jon