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

[Vlado Handziski]

Dear all,

I forgot to include pointers to the original proposal documents:

Miklos' proposal:
http://mail.millennium.berkeley.edu/pipermail/tinyos-devel/2009-March/003724.html
Jan's proposal:
http://mail.millennium.berkeley.edu/pipermail/tinyos-2.0wg/2009-May/003585.html

So please check the above messages and their attachments for details.

Vlado


On Fri, May 8, 2009 at 02:59, Vlado Handziski <handzisk at tkn.tu-berlin.de>wrote:

> I apologize for the delay, it has been a long day. As agreed during the
> telecon, here is a short summary of the current state of the message buffers
> discussion:
>
> First of all, it is important to state that there is no disagreement about
> the need to replace the current message_t format with something that is
> more flexible and can accommodate both variably-sized headers/footers and
> can provide more freedom in the nesting/interweaving of the protocol
> components.
>
> We currently have two different proposals on the table about how to do
> this:
>
> - The first one, proposed by Miklos, is based on a flat, opaque
>   message buffer:
>
>   typedef struct message_t
>   {
>     uint8_t buffer[MSG_MAX_LENGTH];
>   } message_t;
>
>   where the H-Headers, P-Payload, F-Footers, _-Free space and the
>   M-Metadata are stored in the order HPF_M, with all "fields" apart
>   from the M growing upwards/right, and the M growing downwards/left,
>   as the protocol component are nested.
>
>   The formatting of the buffer is performed explicitly by issuing a
>   "format" command with the intended layout as parameters, e.g.:
>
>   call Packet.format(msg, LAYOUT_6LOWPAN | LAYOUT_TIMESYNC, payloadLength)
>
>   the "format" commands can be stacked so that the call propagates
>   along the send "path" all the way to the lowest protocol
>   component, thus solidifying the internal structure of the buffer.
>
>   The actual sending of the message buffer is achieved using a
>   separate "send" call, that contains no formatting information.
>
>
> - 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.
>
>   The metadata is maintained in a separate memory space from the
>   message buffer and has a fixed size equal to the sum of the
>   metadata space requested by all of the component on the
>   send/receive path.
>
>
> The following is my take on the pros/contras of the two proposals:
>
> It is obvious that both approaches provide a way to handle
> variable-sized headers and free composition of the protocol stack
> components without predefining of the message buffer format. The main
> differences that I see are in the associated costs: (1) the frequency
> of the needed (re)formatting commands and (2) the optimality of the
> memory allocation.
>
> 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.
>
> As for (2), if we agree that we should always be prepared to handle a
> MPDU, there is no difference in the amount of memory the two
> proposals have to allocate for the H,P,F part of the buffer,
> i.e. MSG_MAX_LENGTH in Miklos' proposal has to be >= Jan's
> MAX_MPDU_SIZE. However, because in Miklos' proposal the metadata is
> included in the "formating" stage, the MSG_MAX_LENGTH will be <= than
> the MAX_MPDU_SIZE + uniqueCount(METADATA_BYTE) in Jan's proposal.
>
> Vlado
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: https://www.millennium.berkeley.edu/pipermail/tinyos-devel/attachments/20090508/7c809889/attachment-0001.htm