[Tinyos-devel] problem of using FTSP and CTP

[Philip Levis]

On Mar 23, 2009, at 2:04 AM, Miklos Maroti wrote:

> Phil,
>
> On Mon, Mar 23, 2009 at 6:26 AM, Philip Levis <pal at cs.stanford.edu>  
> wrote:
>>
>> On Mar 22, 2009, at 9:05 PM, Janos Sallai wrote:
>>
>>> On Sun, Mar 22, 2009 at 7:42 PM, Philip Levis  
>>> <pal at cs.stanford.edu> wrote:
>>>>
>>>> It was a bug in FTSP to wire directly to ActiveMessageC; Brano  
>>>> fixed
>>>> it, correct?
>>>
>>> No, you can't do that, because AMSender does not provide the
>>> TimeSyncAMSend interface.
>>
>> So shouldn't there be a TimeSyncAMSenderC?
>
> Here is the problem with the TimeSyncAMSenderC implementation: you
> have to use the same AMQueueImplP.nc module to share the same message
> buffer to store the pending messages, otherwise the no EBUSY semantics
> will not work. However, for certain AM types you need to call the
> AMSend interface of ActiveMessageC or the TimeSyncAMSend interface of
> TimeSyncActiveMessageC. First you do not know which one to call and on
> top of that you need the extra event time parameter for the time sync
> message. Where do you store that event time? The
> TimeSyncActiveMessageC is platform dependent, so it is harder to break
> it apart.
>
> There are other problems. There can be several reasons why a MAC layer
> may return EBUSY when it cannot temporary send a message, one of them
> is that it is currently sending another message, but there are others:
> for example while changing to another channel, or the PLL gets
> unsynchronized (yes, it does happens) but is expected to work shortly.
> There are also other factors, if for example you allow 6LOWPAN
> components or any other alternative stack. You CANNOT funnel
> everything everything through the AMSenderC component.

This is all true. Let me explain the issue that we ran into 1.x which  
we don't want to revisit.

The problem is when a component calls Send and gets a transient  
failure (not SUCCESS) return code. The component wants to try calling  
Send again, but doesn't know when to. Furthermore, the component may  
not know when another component may call or signal it again. Without a  
future call or signal, the component won't execute and can't retry.

Let's simplify the issue and say that the reason the stack returned a  
failure code was because it was already busy sending a packet.

One approach is for the component to use a Timer. On a transient  
failure code, it starts a Timer and then retries. But the component  
has no idea *what* is causing the failure, so doesn't know how to set  
the timer. Should it be fast? Slow? What's the underlying packet  
timing? Furthermore, this means every sender needs a Timer, costing  
RAM and cycles in the timer implementation.

The second approach, which 1.x used, was to have a global sendDone  
event, which the messaging system signaled after each transmission.  
Components could wire to this event; if their call to Send returned a  
failure code, they could guess it was due to a busy stack, wait for  
the global sendDone, and try again. Due to some edge conditions I  
can't quite recall, this global sendDone had to be signaled after the  
sender's SendMsg.sendDone.

Note that neither of these two cases solve the problem when a sender  
always called send in its sendDone event. In both cases, the sending  
component had the first shot at the idle radio, and so would always go  
first and prevent other components from sending. This would lead to  
starvation and problematic packet timing; strange conflicts between  
protocol implementations caused unexpected and at times inexplicable  
runtime failures. Note also that the global sendDone event introduced  
a random yet deterministic priority between senders, based on the  
order of the fan-out.

There are two invariants that we want to take from this:

1) Any transient failure code from Send should have a corresponding  
event that denotes the condition has cleared. For example:
	EOFF: SplitControl.startDone
         EBUSY: Send.sendDone

2) An implementation that allows multiple sending components must  
preclude starvation by providing some kind of fairness between the  
senders.

If we need to rework the queue implementations to deal with new send  
interfaces, 6lowpan, etc., that's fine; replacing some of these  
internal implementations in order to deal with changing needs is much  
better than violating one of the above invariants.

Phil