[net2-wg] call notes 23/3/06

[Philip Levis]

On Thu, 2006-03-23 at 10:13 -0800, Joe Polastre wrote:
> >       Basic question: what does 'urgent' mean? Existing protocols from SP
> >       paper never use urgent. Vaguely defined, hard to know whether or not to
> >       use it.
> 
> Urgent is VERY clearly defined (and I use it!).  Urgent is a
> single-bit priority.  That is all urgent is, and it is defined as such
> in both my thesis and the SP sensys paper.

Where is it used? I thought Gil's conclusion surveying the code (which I
looked at again yesterday) was that the urgent bit was never set. I have
the SPM.nc with this CVS entry:

/SPM.nc/1.101/Tue Jul 19 19:15:47 2005//

Correct me if I'm wrong, but in the SenSys implementation, the name of
the urgent field is "latency":

typedef struct sp_message_t {
  // fields to set
  uint16_t addr;
  uint8_t service;
  uint8_t quantity;
  bool busy;
  TOS_MsgPtr msg;
  bool latency;
  bool reliability;
  ...
};

When I grepped through the SenSys CVS for latency, it was only ever set
to FALSE. This doesn't mean that urgent isn't useful, just that in the
protocols written for the paper it wasn't used. 

I looked through the Boomerang code, and wasn't able to find any place
where SP_FLAG_URGENT is used. MultiHopLQI uses SP_FLAG_RELIABLE, but not
URGENT.

> What is the difference between this and calling cancel() if the
> message becomes too stale?

The functional difference is that the data link layer can provide a form
of admission control. If a protocol asks, "send this within 30ms" and
the TDMA schedule means that the next chance to transmit is in 100ms,
the data link layer can respond with "no." It adds the possibility of a
hard-real-time component to the interface. 

More importantly, though, it pushes the state keeping and logic down
into the data link layer (L2+). L2+ might be making scheduling decisions
based on outstanding pool entries. If upper layers are canceling these
entries based on timeouts, it can disrupt the underlying schedule and
force L2+ to recompute. Furthermore, it means that each L3 protocol is
going to have to maintain its own timer/timeout and cancel, rather than
pushing it into L2+, which can do so in a much more coherent manner. 


> Back when we had the first SP proposals, there was this notion that we
> should have deadlines.  Eventually we removed it because nothing in
> the system can actually guarantee that a deadline is met.  That's how
> priority emerged as a much more useful concept, with cancel() as a
> mechanism to remove the message if it couldn't be sent after a long
> period of time.

On one hand, I agree that urgent seems like a much simpler approach; the
problem is that, in practice, it's not used. The issue is that, as
written, SP (on an LPL link) has a policy of an implicit timeout before
a long preamble. There is no way to know what this timeout is. For a
protocol like Trickle, this puts a developer in a tricky spot. To ensure
correct execution of the algorithm, you need to transmit a packet in the
interval [tau/2, tau]. While you can deal with some jitter (t is
randomly selected), you can only deal with so much. What I'd really like
to do is at time tau/2 tell L2+ "send this before tau." 

With the urgent bit, I have to do something like tell SP at time tau/2
to send without urgency, then as some point close to tau approaches,
cancel the send, resubmit the send with urgency set. 

I understand that I implemented Trickle for the SenSys submission. But
that was much more a proof of concept than a deep evaluation and
demonstration. E.g., we never evaluated the efficiency or performance of
Trickle under SP.

> Using explicit times are very difficult because they require knowledge
> of the underlying link in detail so that you don't make mistakes at
> runtime.  What happens if you continually select a time offset that is
> not even possible with the underlying link?  I can see all kinda of
> chaos from this parameter.

The offset is not a "send at this time," rather a "send by this time or
give up." If L2+ knows when the request is submitted that it cannot send
by that time, it can return fail. If it thought it could send by that
time but was incorrect, it can signal a stopped().

> My proposal is the following: If you want to ADD to SP, you have to
> implement that functionality within one of the two SP frameworks and
> illustrate its utility before the addition is considered.

I'm thinking of doing a clean rewrite. I'm not sure if that will result
in something that's just of academic interest or something whose
efficiency and expressiveness is on par with the Berkeley and Moteiv
implementations, but I'll never know until I try. It seems like this is
just such an important problem in sensornets that I should get my hands
a bit dirty to understand it better from a practical (read:
implementation) standpoint. 

That being said, I agree that the utility of the timeout should be
heavily considered and evaluated before being included in a TEP
interface. That's why I tried to present it as just a summary of a
conversation and some thoughts that I'd been having. It's far from a
definite proposal, even. We had 10 minutes to go, and I thought people
might be interested in talking a bit about some of these tradeoffs.

But I can also flip around and say that I don't think the utility of
urgent has at all been illustrated (as far as I can tell), so we should
cut it. :)

Phil