[net2-wg] Fwd: CTP beacon successes window bug

[Omprakash Gnawali]

This is a bug. It is not clear the extent to which this impacts the
estimator's or router's performance.

The bug is the estimator computes the link quality estimate with pkt
window larger than BLQ_PKT_WINDOW in certain cases as described by
Juan in his email. The intention was the estimator would compute the
estimate on the window size of BLQ_PKT_WINDOW.

If we define fixing this bug as making the estimator compute estimates
over fixed window, based on my understanding of the first approach
suggested, I am not sure if the first approach fixes the bug.

- om_p

> From: Juan Batiz-Benet <jbenet at cs.stanford.edu>
> Date: July 10, 2009 15:07:40 EDT
> To: Philip Levis <pal at cs.stanford.edu>
> Cc: Mayank Jain <mayjain at stanford.edu>
> Subject: CTP beacon successes window bug
>
> Hey Phil,
> Below is the description of the bug we discussed yesterday. (It may be a bit
> too... wordy.)  About running experiments to test if the bugfix actually
> improves performance:
> I asked Tal about Mirage, and apparently there is some problem, and it may
> not get fixed soon.
> If so, should we run it on TutorNet? Should I contact Om?
> Juan
>
> ----------------------
> Bug: The Link Estimators (both regular and 4bit) are supposed to update the
> beacon inquality (prr * 255) estimate every BLQ_PKT_WINDOW (set to 3)
> beacons. As of now, CTP waits for that many successes (rather than total
> beacons, successes or failures; we know of the latter via seqnos), and then
> computes the prr over the whole set of failures + BLQ_PKT_WINDOW successes.
> Two solutions possible. The first is better, as its just a very simple
> change, and it fixed the main problem: BLQ_PKT_WINDOW successes after a
> burst of failures are "watered down" by any preceding burst of failures. The
> only benefit from the other is that (in the worst case) 3 windows of
> failures are counted individually (aggregated to the EWMA) instead of as
> one.
> - 1 (very easy): change the CTP code to compute the estimate after the
> window has expired (if the seqno gap >= BLQ_PKT_WINDOW) (once for N Failures
> + 1 success).
> this would just mean changing one line in each. diffs:
> diff -r tinyos-2.1.0/tos/lib/net/4bitle/LinkEstimatorP.nc
> tinyos-2.1.0-fix/tos/lib/net/4bitle/LinkEstimatorP.nc
> 392c392
> <     if (NeighborTable[idx].rcvcnt >= BLQ_PKT_WINDOW) {
> ---
>>     if (packetGap >= BLQ_PKT_WINDOW) {
> diff -r tinyos-2.1.0/tos/lib/net/le/LinkEstimatorP.nc
> tinyos-2.1.0-fix/tos/lib/net/le/LinkEstimatorP.nc
> 389c389
> <     if (NeighborTable[idx].rcvcnt >= BLQ_PKT_WINDOW) {
> ---
>>     if (packetGap >= BLQ_PKT_WINDOW) {
>
> - 2: change the CTP code to compute the estimate for each of the windows it
> missed. It would mean something along the lines of the following diff (need
> to test this to make sure first). It's not pretty, or decomposed, but
> minimizing code change is probably a lot better? :
> diff -r tinyos-2.1.0/tos/lib/net/4bitle/LinkEstimatorP.nc
> tinyos-2.1.0-fix/tos/lib/net/4bitle/LinkEstimatorP.nc
> 380,385c380
> <     NeighborTable[idx].lastseq = seq;
> <     NeighborTable[idx].rcvcnt++;
> <     NeighborTable[idx].inage = MAX_AGE;
> <     if (packetGap > 0) {
> <       NeighborTable[idx].failcnt += packetGap - 1;
> <     }
> ---
>>
> 388a384,385
>>       NeighborTable[idx].outage = 0;
>>       NeighborTable[idx].outquality = 0;
> 390d386
> <     }
> 392d387
> <     if (NeighborTable[idx].rcvcnt >= BLQ_PKT_WINDOW) {
> 393a389,406
>>
>>     } else {
>>       for (; packetGap > 0; packetGap = seq - NeighborTable[idx].lastseq)
>>       {
>>         if (packetGap > BLQ_PKT_WINDOW) {
>>             NeighborTable[idx].lastseq += BLQ_PKT_WINDOW;
>>             NeighborTable[idx].failcnt += BLQ_PKT_WINDOW;
>>         } else {
>>             NeighborTable[idx].lastseq += packetGap;
>>             NeighborTable[idx].failcnt += packetGap - 1;
>>             NeighborTable[idx].rcvcnt++;
>>         }
>>         NeighborTable[idx].inage = MAX_AGE;
>>
>>         if (packetGap >= BLQ_PKT_WINDOW) {
>>           updateNeighborTableEst(NeighborTable[idx].ll_addr);
>>         }
>>       }
> diff -r tinyos-2.1.0/tos/lib/net/le/LinkEstimatorP.nc
> tinyos-2.1.0-fix/tos/lib/net/le/LinkEstimatorP.nc
> 375,380c375
> <     NeighborTable[idx].lastseq = seq;
> <     NeighborTable[idx].rcvcnt++;
> <     NeighborTable[idx].inage = MAX_AGE;
> <     if (packetGap > 0) {
> <       NeighborTable[idx].failcnt += packetGap - 1;
> <     }
> ---
>>
> 387d381
> <     }
> 389d382
> <     if (NeighborTable[idx].rcvcnt >= BLQ_PKT_WINDOW) {
> 390a384,401
>>
>>     } else {
>>       for (; packetGap > 0; packetGap = seq - NeighborTable[idx].lastseq)
>>       {
>>         if (packetGap > BLQ_PKT_WINDOW) {
>>             NeighborTable[idx].lastseq += BLQ_PKT_WINDOW;
>>             NeighborTable[idx].failcnt += BLQ_PKT_WINDOW;
>>         } else {
>>             NeighborTable[idx].lastseq += packetGap;
>>             NeighborTable[idx].failcnt += packetGap - 1;
>>             NeighborTable[idx].rcvcnt++;
>>         }
>>         NeighborTable[idx].inage = MAX_AGE;
>>
>>         if (packetGap >= BLQ_PKT_WINDOW) {
>>           updateNeighborTableEst(NeighborTable[idx].ll_addr);
>>         }
>>       }
> 392a404
>>
>
> _______________________________________________
> net2-wg mailing list
> net2-wg at millennium.berkeley.edu
> https://www.millennium.berkeley.edu/cgi-bin/mailman/listinfo/net2-wg
>
>