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

[Philip Levis]

On Mon, 2005-12-05 at 03:06 -0800, Omprakash Gnawali 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.
> 
> Rodrigo's last email captures the ongoing discussion on how SP might
> take advantage of futures to optimize. I also wanted to quote Philip
> from his first email on packet interfaces:
> 
> "On one hand, simple, low-rate protocols can work fine with
> ActiveMessageC. On the other, the need for better energy efficiency
> and protocol cooperation might push things towards a more expressive
> and powerful interface.".
> 
> Is this interface defition driven by the optimizations that we can do
> ? From a protocol/application developer perspective, in addition to
> the network/link optimizations, does it make it easier or harder to
> implement things ? Certainly, this interface is more complex than
> send/sendDone. Philip, you and Jonathan probably discussed things this
> abstraction might buy us in terms of programming ease for common
> patterns while you chalked out the interface ? I would like to hear
> them. I can see that the system decrementing futures so that an
> application can keep track of outstanding number of packets without
> having to declare a global variable and manipulate that as one such
> convenience.

Sure.

The reason why we settled on a data structure with get/set rather than a
simple function call is that we assumed use of a given entry would not
change that much. For example, a routing protocol is probably never
going to use the urgent bit for its data transmissions, but will use the
reliable bit. Similarly, in current traffic patterns, nodes often send a
lot of packets to one or two destinations, and if two it's the broadcast
address. So it seemed similar to be able to configure the ADT and then
just tell it to start() and stop(). 

Now, an any-to-any protocol like BVR does make this a bit more
complicated. The protocol has a table of possible destinations, and
unlike most collection routing, which only uses one entry of the table,
BVR may use any entry in the table. My assumption here was that
something like BVR would establish a priority queue of destinations and
then put the top N values into N pool entries (where N could very well
be 1). E.g., if you have six packets for destination A, then you might
put that at the top of the queue, but since a packet for destination B
has been outstanding for a while maybe it is second priority.

Alternatively, the priority could just be a FIFO order. So if B is at
the head of the FIFO queue, then you configure the pool entry for B,
counting how many packets are in currently in the FIFO queue (so it's
not pure FIFO).

The ability to decouple starting communication and the communication
itself (e.g., more than send/sendDone) means that suppression protocols
can become much easier. You also see this in the 2.x Send interfaces,
where there is a new command, cancel(). From a send pool standpoint, you
can call stop(). We thought this was important for a lot of protocols,
like Trickle, FSFQ, that data link protocol from MIT with multiple
destination addresses whose name I can't remember (HotNets?), reacting
to congestion, etc.


Phil