[Tinyos-devel] retransmissions in networking protocols

Philip Levis pal at cs.stanford.edu
Thu Oct 4 12:06:29 PDT 2007

As a note -- the images in the mail caused the list to hold them, so  
not everyone saw my reply. Waiting for them to  be approved.


On Oct 4, 2007, at 12:04 PM, Andreas Koepke wrote:

> I found this master thesis, he has a good comparison of existing work.
> ftp://ftp.tik.ee.ethz.ch/pub/students/2006-2007-Wi/MA-2007-02.pdf
> He claims that often only single packets are lost, somewhat in line  
> with
> the measurements of 802.11 in an industrial environment that I  
> examined
> some time ago.
> I guess that the major difference is what you measure. If your link is
> usually bad, it will stay bad for quite a while. If your link is  
> usually
> good, an immediate retransmit is a good idea. This is how I would
> summarize the BER measurements that I have seen so far (Gilbert,
> Mandelbrot and so forth.) I think your observation is pretty  
> independent
> from the link layer -- it fits the history of BER measurements. We
> should check UWB though, it has much wider frequency spread than any
> system so far, more comparable with 802.11b at 1 or 2 MBps. That may
> explain the difference.
> A link with 60% PRR is not a good one, is it? So I guess it is more
> susceptible to consecutive packet losses than the links we usually try
> to use for routing (those with an PRR > 90%).
> In my MAC protocols I assume that ACKs are lost due to high  
> traffic. So
> I use the backoff to reduce the traffic on the links. I have two
> backoffs: one for "busy channel" where the backoff window stays the  
> same
> and one for "too many busy channels or lost ACKs" where I increment  
> the
> backoff window. But the network level protocols do not have this  
> kind of
> knowledge, so their backoff attempts are based on CC2420 timings --
> quite inappropriate for a duty cycle of 0.5s to 2s ;-)
> I have to do the performance eval anyway. I will look into the  
> number of
> retransmission attempts and see how it works out.
> Does anyone mind if I suppress the duplicates also in multihoplqi?
> (Tests with eyesIFX, later porting to CC2420, the standard assumption
> for network protocols).
> Thanks for the long answer, Andreas
> Philip Levis wrote:
>> On Oct 4, 2007, at 8:47 AM, Andreas Koepke wrote:
>>> Thanks, done. I understand that the decision was postponed. Just   
>>> for the
>>> records: the tda5250 MAC protocols had atomic ACKs and retries   
>>> since the
>>> first working CSMA, if I remember correctly. So it is not only the
>>> CC2420 that can do it. I added this because of the   
>>> PacketAcknowledgment
>>> interface: If I have to support it, I can also handle the  
>>> retries. In
>>> addition, I guessed that there is a reason why many wireless  
>>> standards
>>> like 802.11 and 802.15.4 define retries as part of the MAC.
>> Kannan, a student here at Stanford, has measured the CC2420 pretty
>> exhaustively. His results suggest that MAC-layer immediate
>> retransmissions are not a good strategy when the network is lightly
>> loaded (i.e., when losses are due to low SNR and not collisions).   
>> This
>> is because losses are tightly correlated: if you have a PRR of,  say,
>> 50%, then the probability that a packet will arrive successfully   
>> if the
>> one before it failed is often significantly less than 50%.
>> The figure below is an example conditional packet delivery function
>> (CPDF) of an intermediate link. The Y axis is the probability of a
>> packet arriving successfully. The X-axis is the number of   
>> *consecutive*
>> packet deliveries (positive) or failures (negative). So  the value  
>> at +5
>> is "the probability a packet will arrive successfully  if the 5 prior
>> packets arrived successfully." This data comes from  sending packets
>> every 10ms (the max MAC backoff for the CC2420 in T2):
>> --------------------------------------------------------------------- 
>> ---
>> You can see that, although the PRR of the link is around 60%,  
>> after  two
>> consecutive failures it has dropped to 50% and after 10 or so it  is
>> down at 30%. As far as intermediate links go, this one's curve is
>> pretty kind to automatic MAC ARQ. Take a look at this one (sorry it's
>> so big):
>> --------------------------------------------------------------------- 
>> ---
>> Our experience when designing and evaluating CTP is that rapid route
>> adaptation is critical to achieving high reliability and performance.
>> Automatic MAC ARQ makes this much harder, and furthermore causes
>> problems when trying to apply any kind of fair queueing on the  
>> node.  In
>> my mind, automatic MAC ARQ has only one benefit: in packet radios,
>> where you have to load the complete packet into a buffer, ARQ can   
>> save
>> you the cost of loading the same packet multiple times.
>> MAC-layer retransmissions are a bit easier to detect as duplicates as
>> they have shorter delays between them. If the retransmissions are at
>> layer 3, then other layer 3 protocols might get to send packets in
>> between, which would give other transmitters for the first layer 3
>> protocol a longer chance to transmit. Om -- this might be a good
>> experiment for us to run sometime, to examine how the activity of   
>> other
>> layer 3 protocols affects CTP's duplicate suppression.
>> All of these claims come with a caveat, of course: this is the   
>> behavior
>> we've observed on a *single* link layer, and other link  layers may
>> behave very differently. We've looked at data sets from  other link
>> layers (Roofnet 802.11b and Reis et al.'s data from  SIGCOMM 2006)  
>> and
>> see similar link burstiness in some but not all of  them. In  
>> particular,
>> 802.11b at 11Mbps, whether indoor or outdoor,  seems to have similar
>> behavior to what we have observed in 802.15.4,  but 1Mbps outdoor  
>> seems
>> to have pretty much independent packet losses.
>>> At MAC level the random retransmission delay can be computed without
>>> much problems, they can also be adapted more easily to the duty  
>>> cycle
>>> than in the network protocol. Of course the network protocol can
>>> retransmit more or less immediately and trust the fairness   
>>> mechanisms of
>>> the MAC to introduce a sensible amount of delay. I don't care, as  
>>> long
>>> as the performance does not suffer too much when the ACK status  
>>> in the
>>> packet is a "false negative".
>> CTP's reaction to false negatives tends to be pretty good but not
>> perfect. The time when it breaks down is when, because it didn't
>> receive an ACK, it changes its parent (who then doesn't see it as a
>> duplicate). Also, as the load increases, the chances a packet has   
>> been
>> flushed from the duplicate cache before the duplicate arrives   
>> goes up.
>> Kannan has been running some low rate (total network load of   
>> 9pps) CTP
>> experiments in the Mirage testbed at Intel Berkeley, and  has seen  
>> that
>> about 1% of the packets arriving at the root are  duplicates.
>> MultihopLQI also suppresses duplicate packets. LqiRoutingEngineP.nc:
>>       // supress duplicate packets
>>       for (i = 0; i < MHOP_HISTORY_SIZE; i++) {
>>         if ((gRecentPacketSender[i] == call AMPacket.source(msg)) &&
>>             (gRecentPacketSeqNo[i] == hdr->seqno)) {
>>           call CollectionDebug.logEvent  
>>           dbg("LQI", "%s no route as this is a duplicate!\n",
>> __FUNCTION__);
>>           return FAIL;
>>         }
>>       }
>> One last note (if you made it this far!): I found a memory leak  
>> in  CTP
>> two days ago that was a major cause of packet losses in our low
>> transmission rate experiments (0.3% of sent packets). It was actually
>> triggered by the duplicate suppression code. :) I checked a fix  
>> into  CVS.
>> Phil

More information about the Tinyos-devel mailing list