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

[Omprakash Gnawali]

I committed a fix that updates the estimate when packet gap exceeds
BLQ_PKT_WINDOW. It ran it for 1 hr on 56 nodes and it seems to work.
Not enough data to quantify the improvement but this is a bug that
needed to be fixed.

- om_p

On Thu, Jul 16, 2009 at 7:17 PM, Omprakash Gnawali<gnawali at usc.edu> wrote:
> 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
>>
>>
>