Subject: Re: Choices for TRACK/NACK report encoding

From: "Sukanta Ganguly" <[email-masked]>
Date: Mon, 28 Aug 2000 17:06:16 -0600

Brian,
  Reliable NACK should not be the fact based on which the design should be done. Scalability is the obvious probelm with it. So most of your assumptions are correct. I don't quite understand how you came up with the overheads. I also could not quite understand where did you get the 32 in the calculation. 
  However, what do you mean by full status of the non-stable packets? Where is this full status generated? Are we assumming that the RLE data reaches the target without any loss?

SG

>>> Brian Whetten <[email-masked]> 08/28/00 04:17PM >>>
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: Brian Whetten <[email-masked]>
Date: Tue, 29 Aug 2000 10:58:00 -0700

I'm glad you agree.  32 comes from the size of a sequence number.  No, I'm not
assuming that any sets of packets reach the sender without loss...that is part
of the point of this.  Most of the TRACK/NACK RMT protocols out there have the
notion of a non-stable receiver window, which is the set of packets from the
lost packet with lowest sequence packet that is still considered recoverable,
up through the loss detected with the highest sequence number (or
alternatively, up through the highest sequence number the receiver is aware
of).  

The core idea is that if you only NACK individual packets, then there is no
built in redundancy from NACK to NACK, and you have to build in a reliability
mechanism for the NACKs.  If you send up a compressed bitmap for the packets in
the non-stable window, then you don't need to do this.  This status is
generated at the receivers, and passed up.  (See TRAM or RMTP-II for details)

Brian

At 05:06 PM 8/28/2000 -0600, Sukanta Ganguly wrote: 
>
> Brian,
>   Reliable NACK should not be the fact based on which the design should be
> done. Scalability is the obvious probelm with it. So most of your assumptions
> are correct. I don't quite understand how you came up with the overheads. I
> also could not quite understand where did you get the 32 in the calculation. 
>   However, what do you mean by full status of the non-stable packets? Where
> is this full status generated? Are we assumming that the RLE data reaches the
> target without any loss?
>  
> SG
>