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

[Vlado Handziski]

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/7a69550c/attachment.htm