futures (Re: [net2-wg] Packet interface)

[Philip Levis]

On Fri, 2005-12-02 at 09:40 -0800, Rodrigo Fonseca wrote:
> > Would we rather design and implement core network protocols on top of
> > the standard send/sendDone interface, or something more like
> > SendPoolEntry?
> 
> So let us try to extract exactly what advantages/flexibility the
> SendPoolEntry is warrantying us, versus the added complexity of
> programming against it.
> 
> Many details aside, the core issue is that the SendPoolEntry, or the
> SPSend interface in the case of SP, is:
>    - giving each client (network protocol, application, etc), one
> "queue" of many packets (futures)
>    - letting SP (let me call the link layer abstraction SP) schedule
> among these queues with an unspecified order
> 
> The heart of the idea is the "pool" concept: SP can optimize
> transmissions and have different protocols share the radio in a better
> way, for some MACs, if it can order the transmissions based on things
> like wake-up schedules and long preambles. When it can't thus
> optimize, the performance will be no worse than that of a normal
> (fair) queue, so this point is a good one.
> 
> The futures (the fact that each PoolEntry is a "queue"), also allows
> optimizations in the same fashion as before, if SP can assume the
> declared entries are for the same destination.
> 
> This is the point I think might generate confusion: if each client has
> to allocate entries for each destination, this can be a hard decision
> to make statically. On the other hand, what I see will happen is that
> clients will start changing the futures in order to multiplex
> destinations on the same pool entry. In this case, SP can't do
> optimizations, and if this is not done right, the practice may fool SP
> in its optimizations.

The way the semantics of the interface I proposed work, you can't do
this. Specifically, if an entry is running (start() has been called),
then you cannot change the destination address, the urgent bit, or the
reliable bit. If you want to send to another address, then you need to
stop the entry, reconfigure it, and start it again. 

Currently the interface does include adjustFutures(), which allows you
to change the number of futures while the entry is running. I
incorporated this because I was thinking about the case where a node
receives another packet to forward while it's forwarding. Rather that
force a rescheduling, it would be nice if the higher level code could
just say "oh, I have one more." The underlying abstraction may not be
able to send that additional packet immediately, but it simplifies the
upper level, who might have to keep track of two queues.

E.g., I have six packets to send, I set the futures to 6 and call start.
The underlying data link sends an RTS(6) and receives a CTS(6). After
sending the third packet, I receive two more, and increment my futures
by 2 to 5 (6 - 3 + 2). However, as the pool only has an RTS for three
more packets, it sends those, leaving the futures at 2, and soon
thereafter sends another RTS.

> The last point is that there will be an interaction between scheduling
> decisions that clients will be doing on each pool entry with the
> scheduling that SP will be doing among different pool entries. What
> are the semantics of the scheduling decisions that SP will make such
> that there won't be some strange feedback look among the schedulings
> at different levels?

That is a very good question. I think that there's a range of scheduling
decisions that the send pool could make, and each one has benefits as
well as drawbacks. For example, Joe's approach was to service pool
entries in a FIFO fashion and service an entry until it completes. This
means that with a CSMA-LPL MAC underneath, one protocol could send 1000
packets while others don't get to send any. There are situations where
this is what you'd want, and others when it isn't.

One of the things I personally like about pool approach is that this
scheduling *can* be hidden from the upper protocols. Of course, people
might right code that incorrectly assumes a particular scheduling
policy, but there's nothing we can do to prevent that.

> So, to summarize, I think the model of allocation of entries should be
> discussed, so as not to create destination-multiplexing behaviors in
> clients that may hinder the ability of SP to do its optimizations.
> Maybe there is a simple model in which SP has a fixed number of
> entries in its pool, and these are recycled among the clients on
> demand. Second, we need to define the scheduling semantics so as to be
> able to reason about the interactions between scheduling decisions
> intra-pool and inter-pool.
> 
> Thoughts?

I think that the fact that you have to stop() and start() an entry in
order to start multiplexing its use is a pretty good indicator that
there's a cost.

Phil