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

[Philip Levis]

There may be a bug in CTP.

Phil

Begin forwarded message:

> 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
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: https://www.millennium.berkeley.edu/pipermail/net2-wg/attachments/20090710/8fa322fb/attachment.htm