[Tinyos-devel] retransmissions in networking protocols

[Andreas Koepke]

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 (NET_C_FE_DUPLICATE_CACHE_AT_SEND);
>           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
>