Subject: Choices for TRACK/NACK report encoding

From: Brian Whetten <[email-masked]>
Date: Mon, 28 Aug 2000 15:17:24 -0700

Hi there,
A question just came up for me on how we should best do NACK (and TRACK)
encoding for the information that is sent up.  I think there are two
primary ways that have been used so far:  List NACKs (i.e. PGM) and bitmaps
(i.e. RMTP-II & TRAM).  The other option, which hasn't been used yet but
has been discussed, is run length encoded bitmaps.  

I'd ideally like to see us use the same encoding format (as part of the
common data headers BB) for each.  I ran a quick comparison of the overhead
of encoding a window of N packets, with a uniform loss rate of P.  The
overhead for each option is:

List NACK=32*N*P
Bitmap=N
RLE Bitmap=approximately Ceiling(Log2(1/P))*N*P  (I think this is
reasonably accurate for low values of P)

Note that as P approaches 1 (worst case, which we need to plan for), we get:
List=32*N
Bitmap=N
RLE Bitmap=Actually goes down (because we encode successes rather than
losses), with a worst case always less than either of the other two (but
approaching the bitmap case).

Here are numeric results for these formulas, in bits, assuming N=1000.

p		List NACK	Bitmap		RLE Bitmap
0.001		32		1000		10
0.0031	101		1000		28.5
0.01		320		1000		70
0.031		1012		1000		158.1
0.1		3200		1000		400
0.31		10119		1000		632
0.66		21120		1000		660
0.9		28800		1000		400

As you can see, List NACKs are better than a bitmap for P<3%, and worse
otherwise.  A RLE bitmap is the most complicated to implement, but is also
the most efficient for all cases.

A related topic to this is the idea of reliable NACKs.  Taking PGM as an
example, it uses reliable NACKs, which make a lot of sense if none of these
encoding mechanisms are used, since there is no built in redundancy across
successive NACKs in that case.  I think that NORM/PGM's biggest advantage
is being able to work without needing reliability mechanisms, which gives
these protocols better scalability in the face of failures.  The reliable
NACKs actually go directly in the face of this, and increase the amount of
NACK implosion traffic that would occur when a network partition occurs.  

I believe that the need for reliable NACKs could be removed in NACK-only
protocols (as it is in TRACK oriented protocols) by reporting a full status
of all the non-stable packets.  With a RLE mechanism, this scales very
nicely, and I think the overhead of adding the RLE mechanism would be less
than the complexity of reliable NACKs.

Conclusion:  I think we should standardize on non-reliable NACKs/TRACKs
(they are basically the same thing, just generated at different times),
which use the same encoding format for their retransmission request
reports.  I think that RLE encoded bitmaps should be used for this, since
the system needs to be stable even in the face of very high loss rates and
high data rates.  

Comments?
Brian

---

From: Luigi Rizzo <[email-masked]>
Date: Tue, 29 Aug 2000 15:52:06 +0200 (CEST)

> reasonably accurate for low values of P)

mumble... wonder what did you use to compute the RLE bitmap size
for p in the range 0.1 to 0.5 below... was that an actual
encoding or just the result from the above formula (which might
not apply given your comment above)

note though that maybe it is not such a good idea to issue selective
naks for >100 losses at once (or said it differently, gropus of
1000 pkts with a loss rate of 10% or more), so maybe we could
limit our attention to a relatively small set of missing pkts
irrespective of window size.

	cheers
	luigi

---

From: "Mike Luby" <[email-masked]>
Date: Tue, 29 Aug 2000 10:27:31 -0700

Is there an option to NACK based on FEC, i.e., to just give the number of
missing packets (and which block they are from) instead of an explicit list
of missing packets?
Mike

-----Original Message-----
From: [email-masked] [mailto:[email-masked]]On Behalf Of Luigi
Rizzo
Sent: Tuesday, August 29, 2000 6:52 AM
To: Brian Whetten
Cc: [email-masked]
Subject: Re: Choices for TRACK/NACK report encoding

	cheers
	luigi

---

From: Brian Whetten <[email-masked]>
Date: Tue, 29 Aug 2000 11:10:35 -0700

I just used the formula, which is only a quick and dirty approximation.  I
need to go back and freshen up on encoding/compression algorithms (Mike,
I'm sure this is trivial for you...do you have a more accurate formula?).  

I think the issue of the # of packets you NACK is orthogonal to how you
respond to the NACKs.  It strikes me that we should always (within the
bounds of efficiency) be striving to get as much information as possible to
the sender, and then it is a different issue as to how those NACKs are
dealt with.  The rate of retransmissions needs to be explicitly considered
by the congestion control BB.  

Also, in very high bandwidth-delay product networks, I think you may want
to be NACKing 100 or more packets at a time in some cases...but again, this
should be dealt with by congestion control.

Brian

---

From: Brian Whetten <[email-masked]>
Date: Tue, 29 Aug 2000 11:14:45 -0700

Hi there,
We certainly need to be able to send this information up.  If the sender
knows the FEC window boundaries, then I believe the FEC information can be
extracted from the bitmap (another reason to use a compressed bitmap).  So
unless the FEC coding windows were as a common case quite large, I'm not
sure that the added complexity of offering an explicit count per window
option would be worth it, at least for NACK/TRACK protocols.

Brain

---

From: "Todd L. Montgomery" <[email-masked]>
Date: Tue, 29 Aug 2000 14:59:56 -0400 (EDT)

I hope there is. PGMs FEC adds a nice feature that allows a block
to report it's loss count and pack that into a 32-bit number
no matter how big the block. That is a LOT smaller with List NAKs
than a bitmap can be.

To do this, the block size (in packets) must be a power of 2, but that is
not very restrictive.

-- 
Todd L. Montgomery
Talarian Corporation
304-291-5972
[email-masked]

---

From: "Mike Luby" <[email-masked]>
Date: Tue, 29 Aug 2000 12:36:29 -0700

As design goals, it would seem to be desirable:

(1) That explicit packets can be NACKed per block.
(2) That a count of packets can be NACKed per block.
(3) That the mechanisms that achieve (1) and (2) are compatible with each
other.
(4) That the mechanisms would work relatively efficiently independent of the
loss per block or the size of the block.
    (a) Would be desirable to work with small as well as large blocks (in
terms of number of packets per block).
    (b) Would be desirable that the block size in packets doesn't have to
fit any special requirements, e.g., be a power of 2.
    (c) Would be desirable that the scheme would scale with the number of
losses per block, in particular when the report is a count then one should
report any number between 0 and the size of the block in packets.

Do these goals make sense, and how would people prioritize these goals, and
are there other goals that are even more important that are missing?  Once
the goals and their relative priority are clear, then the design may just
fall out as a natural consequence.
Mike

-----Original Message-----
From: Todd L. Montgomery [mailto:[email-masked]]
Sent: Tuesday, August 29, 2000 12:00 PM
To: Mike Luby
Cc: Luigi Rizzo; Brian Whetten; [email-masked]
Subject: RE: Choices for TRACK/NACK report encoding

--
Todd L. Montgomery
Talarian Corporation
304-291-5972
[email-masked]

---

From: Brian Whetten <[email-masked]>
Date: Tue, 29 Aug 2000 14:46:10 -0700

I would add:
(5) Being able to efficiently encode as many losses across as many blocks
as possible.  i.e. being able to report a history of outstanding lost
packets, rather than just the most recent ones.
(6) Simplicity
(7) Being stable in the face of very high loss rates, either of data
packets and/or NACK packets.

I would prioritize 1,2,6,7 as having the highest importance.  

Brian

---

From: "Mike Luby" <[email-masked]>
Date: Tue, 29 Aug 2000 16:00:14 -0700

The additional design goals make sense.  I would prioritize almost the same:

(1,2),6,(4,7),5,3.

(Parenthesis enclose goals of similar priority).  Given this, the question
then is: does a NACK scheme that meets these goals in this priority order
jump out?  (My only goal was to drive the design process starting from the
goals, not from the mechanisms.  This may be where I stop contributing.)

Mike

-----Original Message-----
From: Brian Whetten [mailto:[email-masked]]
Sent: Tuesday, August 29, 2000 2:46 PM
To: Mike Luby; Todd L. Montgomery
Cc: Luigi Rizzo; [email-masked]
Subject: RE: Choices for TRACK/NACK report encoding

I would add:

Brian

---

From: Brian Whetten <[email-masked]>
Date: Tue, 29 Aug 2000 17:21:36 -0700

This was a good contribution.  Thanks, Mike.  As always, I was assuming
everyone already agreed on the design principles and was just throwing out
potential solutions.  :)

Todd had a good point about being able to encode the number of lost packets
in a block very efficiently.  I've added another column for this, which
I'll title block count.  I model its overhead as:

Block Count=32*n/b*(1-(1-p)^b), where n=number of packets in the encoded
window, b is the size of the FEC block, and p is the probability for loss.

I ran three cases, for b=8, 32, and 128.  I actually think that smaller
block sizes will most often be used for NACK/TRACK based protocols, since
otherwise you would likely use the ALC scheme instead.  Again, for RLE it
is probably off by up to a factor of 2 for the middle cases due to my rough
model used.

For b=8, the block count is only marginally better than a straight list
NACK until the loss rate gets above 10%, and is still worse than bitmap at
that point.  For b=32, the block count  method is approximatley equal to
the list for low loss rates, and equal to bitmap for high loss rates, which
is a desireable combination.   For b=128, Block Count is the most
efficient.  For B=8 or B=32, RLE still appears to be the most efficient.

Going by your prioritization list:

- I believe that all of these EXCEPT for List NACKs can easily meet #1 and
#2, and therefore also #3.  List NACKs has to be combined with one of the
others to meet these requirements.  Again, this assumes that the sender can
derive block counts from a complete bitmap list.
- In terms of #6 (simplicity), I believe that RLE is the most complex of
the four, and that any single one is less complex than having to specify
and implement any two of the others.  I think that List NACKs bring higher
reliance on reliable NACK mechanisms, which (in terms relative to the
complexity of these mechanisms) are very complex.
- In terms of #4 and #7 (efficiency in all/worst cases), I think that RLE
best meets these requirements, because it works efficiently with b=1 (no
FEC, which is a common case we need to be concerned with), b=8, and b=128.
The only scenario where it is not the best (again, given my rough model for
RLE) is when both p and b are large (p>=10% and b>=64).
- For #5, Bitmap and RLE satisfy this, the others don't.

So, I think that RLE is the best of the mechanisms proposed, given this
analysis and set of requirements.  The complexity of having to do two
encoding schemes and/or reliable NACKs, combined with its efficiency, is
what recommends it to me.

Comments?  Any mistakes I've made?
Brian 

Tables:

b	p	List	Bitmap	RLE	Block Count
8	0.001	32	1000	10	32
8	0.003	101	1000	28	100
8	0.010	320	1000	70	309
8	0.032	1012	1000	158	907
8	0.100	3200	1000	400	2278
8	0.316	10119	1000	632	3809
8	0.500	16000	1000	500	3984
8	0.660	21120	1000	660	3999
8	0.900	28800	1000	400	4000

 b	p	List	Bitmap	RLE	Block Count
32	0.001	32	1000	10	32
32	0.003	101	1000	28	96
32	0.010	320	1000	70	275
32	0.032	1012	1000	158	642
32	0.100	3200	1000	400	966
32	0.316	10119	1000	632	1000
32	0.500	16000	1000	500	1000
32	0.660	21120	1000	660	1000
32	0.900	28800	1000	400	1000

b	p	List	Bitmap	RLE	Block Count
128	0.001	32	1000	10	30
128	0.003	101	1000	28	83
128	0.010	320	1000	70	181
128	0.032	1012	1000	158	246
128	0.100	3200	1000	400	250
128	0.316	10119	1000	632	250
128	0.500	16000	1000	500	250
128	0.660	21120	1000	660	250
128	0.900	28800	1000	400	250

---

From: Luigi Rizzo <[email-masked]>
Date: Wed, 30 Aug 2000 16:13:00 +0200 (CEST)

> Hi there,
...
> Brain

interesting typo... does not look so nice for my name!

	lugii

---

From: Brian Adamson <[email-masked]>
Date: Wed, 30 Aug 2000 17:30:16 -0400

I agree with these goals for NACKs as well ... The NACK Content 
discussion in the current NORM building block draft (but I probably 
should have put more on "goals" in the draft than just the 
"solutions" presented) tries to meet these sorts of goals:

1) Explicit packets per block
2) Count of packets NACKed per block
3) Simplicity
4) Independent of block size (within constraints of messaging size 
... if a coding blocks are so large that a bit mask (even compressed) 
representing it can't be fit into a single NACK message some 
additional fields to support
fragmentation might be needed ... but does not necessarily break the 
protocol given other aspects of the sender<->receiver NACK/repair 
process)

I think the other important goals (stability in high loss, _working_ 
at all) are also dependent upon the entire NACK process ... i.e. how 
the NACK messages are used and of course not just the format of the 
messages themselves.

I think it's worthwhile to consider creating a a general NACK format 
... particularly to get to a goal of generic router assist in NACK 
aggregation. I think a general format can be created which satisfies 
the stated goals and provides the functionality needed for different 
protocols using NACKs ... The goals outlined make sense for what I 
hope NORM turns out to be

These are also in line with the goals we had for the MDP protocol 
(some of the current NORM ideas are of course pulled from my 
experience here) ... In MDP, a NACK message can contain a 
concatenation of repair requests for coding blocks missed in entirety 
(if any, which can happen for various reasons) as well as an explicit 
indication of missing packets within specific partially received 
coding blocks _and_ a count of the number of erasures for each of 
those coding blocks.

So an individual Repair Request has the following fields:

ObjectId	  - Identifier of transport object or stream
                     requiring repair

RepairRequestType - SEGMENT, BLOCK, OBJECT, or INFO

NumErasures       - count of missing packets (segments) for
                     SEGMENT repair request

Offset	          - starting point of bit mask which follows
                     (coding block identifier)

MaskLen		  - length of bit mask which follows

Mask		  - Bit mask which marks specific blocks or
                     segments needing repair depending upon
                     the RepairRequestType

Multiple of these "Repair Requests" are concatenated as needed to 
form a NACK message.  We limit the growth of the size of an 
individual NACK message to the current multicast session MTU.  At 
most, a single NACK message is sent per repair cycle by a given 
receiver with respect to a given sender.  There is no need for 
reliability of NACKs given that subsequent transmissions (or lack 
thereof) by the sender provide an implicit indication of whether the 
receiver needs to NACK again or not.

As Brian Whetten points out, run-length encoding of the bit masks 
would improve the efficiency of NACK packing in _some_ cases.  We 
have found the above scheme to work well in a variety of situations, 
but haven't studied NACK size explicitly. (BTW, this could be easily 
studied with some ns simulations)

The above hierarchical NACK lets us NACK for either an entire object 
(or stream), or some set missing blocks, and/or missing segments 
efficiently.  The receivers' NACKs aren't allowed to grow beyond one 
session MTU in size

The NACK process is self-limited in that all receivers always NACK 
for the _oldest_ missing data ... the sender follows the rule that it 
will repair oldest data first (This allows the packing of NACK 
content be limited to what will fit in one packet)... Thus, receivers 
constrain themselves from NACKing again until they see the sender's 
sequence of transmission exceed the point at which they have missing 
data (This is how the receiver is implicitly aware that the sender 
has failed to fulfill his repair needs whether from lost repair 
transmissions or that the receiver's NACK was lost)... The receiver 
is also constrained by GRTT timing rules to allow the sender 
sufficient time to receive NACKs, aggregate them, and begin 
transmitting repairs, etc

The above fields may need some additional generalization ... For 
example, in MDP the "NumErasures" field is an 8-bit value assuming 
Reed Solomon FEC with 8-bit words ... The erasure count simplifies 
sender-side processing ...

The explicit content is important so that there doesn't need to be 
synchronization among clients and the sender with respect to multiple 
repair cycles ... An erasure count alone isn't sufficient to tell the 
sender to which repair round (1st, 2nd, 3rd, etc) the NACK is 
applicable ... We found it simplest to have the receivers provide an 
indication of explicit repair needs even though FEC is usually used 
for repair ... And the bit masks are easy for the server to process 
for repair aggregation and receivers (and hopefully eventually 
routers) to process for NACK suppression purposes ...

> >fall out as a natural consequence.

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