[net2-wg] Collection queue policy

[Philip Levis]

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