[Tinyos-devel] Current status of the message buffer discussion

[Jan Hauer]

On Fri, May 8, 2009 at 10:33 AM, Miklos Maroti <mmaroti at math.u-szeged.hu>
> E.g. AMSender accepts a destination address as a parameter, sets the
> address via AMPacket and the length of the message via Packet, keeps
> the message around, then sends it via SubAMSend but first queries back
> the destination, am type and length just to be able to call the
> SubAMSend which in turn overwrites these values with the same one. How
> do you implement this with Jan's proposal?

The most natural would be to not have separate commands for passing
the control information associated with a packet (addresses, flags,
etc.) and sending the packet. Instead, the send() command would
include both at the same time. In the send() command handler the
callee would typically attach and populate its own header/footer (e.g.
based on the passed control information), possibly queue the packet,
later dequeue it and possibly reformat its header/footer, and then
call send() on some other component.

While a component "owns" the packet (after it has received it via
send() and before it has passed it to some other component via some
other send(), i.e. the send() commands typically differ in the control
parameters), it can use any remaining unused memory inside the packet
to store temporary variables/addresses, component state, etc., because
at protocol layer N a packet never includes any information belonging
to the layers < N, which it could override. So even if layer N calls
send() on layer N-1 and passes/tunnels control information for layer
N-2, then layer N-1 could typically temporarily store them in front of
its own header inside the packet.

These are the disadvantages that I see with my proposal:
- the ring buffer requires two extra bytes for the "start" and "stop" index
- components MUST NOT forget to remove ("deallocate") any of their
headers/footers before passing on the sendDone() and receive() event
- on the send-path maximum 1 memmove operation is required when
forwarding a packet (otherwise no memcpy/memmove is necessary)

On Fri, May 8, 2009 at 5:31 PM, David Gay <dgay42 at gmail.com> wrote:
> Not a comment on the discussion itself, but I'd like to remind people
> that there's a
> uniqueN(METADATA_BYTE, k) "function" that will reserve k (a constant
> expression) contiguous bytes. And that k separate calls to
> unique(METADATA_BYTE) are *not* guaranteed to return contiguous
> values...

I wasn't aware of uniqueN -- this would make it easier to allocate the metadata.

On Sat, May 9, 2009 at 1:04 AM, Eric Decker <cire831 at gmail.com> wrote:
> Just a thought but has someone implemented prototype implementations of
> these approaches and looked at what it entails to actually code using these
> constructs?

Not yet -- if this discussion gets going and people are interested I'd
do it for my proposal.

Jan


On Fri, May 8, 2009 at 10:33 AM, Miklos Maroti <mmaroti at math.u-szeged.hu> wrote:
> Hi Vlado,
>
>> - The second one, proposed by Jan, uses a new "packet"
>>   abstraction that has a ring buffer in its core, with size equal to
>>   the MPDU for the given link layer (assuming LL is the last SW
>>   controlled message frame format):
>>
>>   typedef struct packet {
>>     uint8_t start;         // start of PDU, offset into ring buffer
>>     uint8_t end;           // end of PDU, offset into ring buffer
>>
>>     // the ring buffer memory, e.g. for 802.15.4 MAX_MPDU_SIZE is 127
>>     uint8_t buffer[MAX_MPDU_SIZE];
>>
>>     // for every byte a component wants to reserve in the
>>     // metadata buffer it would declare a unique(METADATA_BYTE)
>>     uint8_t metadata[uniqueCount(METADATA_BYTE)];
>>   } packet_t;
>>
>>
>>   The PDU stored in the buffer is denoted by two indices. Instead of
>>   separate "format" commands, the buffer is composed through the
>>   propagation of the send calls, each protocol level can add its own
>>   header and footer, with the convention that a header is always
>>   concatenated before the current PDU and a footer comes after the
>>   current PDU, ending in a PF_H order.
>>
>>   On the receive side, the message is stored in HPF_ order. During
>>   forwarding, in the case when the headers or the footers number/size
>>   needs to change, it might happen that one of these wraps (due to the
>>   circular nature of the buffer), so for convenient access, a memmove
>>   would be required to realign the buffer to a full header or the
>>   payload field.
>
> I want to point out that it is NOT enough to assemble/disassemble the
> message on the send/receive paths. Every component provides an
> interface that exposes the header/footer and metadata fields (e.g
> PacketAcknowledgement, AMPacket, PacketLink, PacketTimeStamp,
> PacketTimeSync). So my question is: do you want to remove the
> setAddress command of the AMPacket (or Ieee154Packet) interface? Do
> you allow to change from 16-bit addresses to 64-bit addresses via the
> Ieee154Packet interface? If yes, then you have to reformat the message
> to get a well formed message from another well formed message.
>
>> As for (1) I believe that Miklos' proposal is more vulnerable mainly
>> due to the time decoupling between the format calls and the send call,
>> as well as due to the flat nature of the buffer and the needed
>> memmoves caused by extension of the size/number of headers/footers
>> (during forwarding, etc.). I think that the circular buffer in Jan's
>> proposal handles some of these situations more gracefully.
>
> Exactly this decoupling is the strength of my proposal! I do not want
> to see send parameters in the send command because network layers
> cannot do anything with them, other than to store it in the message.
> E.g. AMSender accepts a destination address as a parameter, sets the
> address via AMPacket and the length of the message via Packet, keeps
> the message around, then sends it via SubAMSend but first queries back
> the destination, am type and length just to be able to call the
> SubAMSend which in turn overwrites these values with the same one. How
> do you implement this with Jan's proposal? What I propose is to have a
> completely well formatted message at every stage, so no send
> parameters are used, and the user has to set all parameters in the
> header and footer accordingly (which in part we already do with
> PacketLink, LowPowerListening, etc).
>
> The format(msg) command might not be the right solution for this, and
> in fact a memmove is probably going to be cheaper if at some point
> someone wants to change the size of a field in the networking stack.
> All I want is to have no send parameters, because that kills
> composability.
>
> Miklos
>
> _______________________________________________
> Tinyos-devel mailing list
> Tinyos-devel at millennium.berkeley.edu
> https://www.millennium.berkeley.edu/cgi-bin/mailman/listinfo/tinyos-devel
>