[net2-wg] Re: Collection queue policy

[Rodrigo Fonseca]

I tend to think that the second approach is better. The first seems at
first to give too little bandwidth for send. Further, simplifying the
users of collection C is preferrable, IMHO.

Rodrigo


On 4/26/06, Philip Levis <pal at cs.stanford.edu> wrote:
> On Apr 26, 2006, at 7:55 AM, Rodrigo Fonseca wrote:
>
> > Hi,
> >
> > checked in a fairly complete skeleton of TreeRoutingEngineImplP.nc,
> > missing is the function that chooses the current parent given the
> > state of the neighbors and the simpler sendBeaconTask.
> >
> > It interfaces with Phil's ForwardingEngine, and with the
> > LinkEstimator.
> > Specifically, from the link estimator it uses the Packet and
> > LinkSrcPacket interfaces.
> > It maintains its own network level table with the route info about the
> > neighbors: their parent, hopcount, cost (metric), and this table is
> > synchronized with the LinkEstimator neighbor table. For this, it only
> > needs an event evicted, that informs when a neighbor should be removed
> > from the table.
>
> Great. Once everyone has progressed far enough to be convinced that
> the current component signatures work and don't require revision,
> then I think we can start testing our individual parts, then stick
> them together.
>
> One interesting thing that came up in Kyle and my discussions was the
> relationship between sending clients and the forwarding queue with
> regards to scheduling. CollectionC creates both ForwardingEngineP's
> forwarding pool as well as its send queue. The send queue has to have
> one slot for every packet in the forwarding pool: the question is how
> many slots to allocate for send clients.
>
> The two options we considered were "1 slot for all sending clients"
> and "1 slot for each sending client." There are some implementation
> implications for these decisions. The former is a little simpler in
> the ForwardingEngineP, as all of the sending clients establish a
> queue above the engine and share the one send queue slot. The latter
> is a little more within ForwardingEngineP, but it doesn't require an
> additional queue above, so the composition is simpler.
>
> The more important difference, however, is how the decision affects
> bandwidth allocation. If all send clients share a single slot, then
> if there are C clients and F entries in the forwarding pool, each
> client's minimum share of the bandwidth is 1 / (C(F+1)). The 1/(F+1)
> is because there's a single slot in the send queue for all clients
> (which is therefore length F+1), and the 1/C is because there are C
> clients. Note that this is single-hop, not multi-hop, bandwidth.
>
> If each send client has its own slot, then a client minimum share is
> 1 / (C + F), as the queue is of size C+F. This also saves a single
> slot worth of RAM, as we're not putting a queue on top of another queue.
>
> Kyle is currently running with the latter approach.
>
> I've added two helper components to the collection directory, Queue
> and Pool. My guess is that these should move into system/ at some
> point. When I get a chance, I can trim a byte from the QueueC
> implementation (no need to keep head, tail, and size, head + size is
> sufficient). I didn't use the Moteiv pool because it's not race-free
> on all platforms; if reading/writing a pointer is a non-atomic
> operation, you can corrupt the pool. This isn't an issue on MSP430-
> based platforms, but is on atm128-based ones.
>
> Phil
>