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

[Miklos Maroti]

Ok, I have yet another message_t proposal (YAMP) that aims to achieve two goals:

1) allow variable sized headers without memory copying

2) store the send() parameters inside the message_t structure, so
networking components can do their work from working tasks without
storing these parameters separately in RAM.

I assume that the networking components are stacked, can even branch
out to support multiple networking interfaces, with the application
layer at the leaves. At layer N the message_t has the following
structure:

[header param 1] ... [header param N] [free space] [payload]

(For the sake of simplicity, let us assume that there is no footer,
but the footers can be stored at the end in reverse order with the
same method.)

When a message is sent by layer N to layer N-1, then we process the
[header param N] field, extend the [payload] field at the front as
necessary and add the relevant header information to the payload. When
receiving the message from layer N-1, then we parse the header
contained in the payload, and write the [header param N] field
accordingly. Layer N also provides a specialized interface to read and
write the content of [header param N].

For example, if IEEE 802.15.4 is at layer N, then the [header param N]
could only contain the 64-bit target and 64-bit source addresses plus
one control byte for the ACK request and other bits. These would be
accessible via standardized interfaces (e.g. AMPacket). When we send
the packet, then we decide to put 16-bit or 64-bit addresses into the
header part of the extended payload, that we construct:

[header param 1] ... [header param N-1] [free space] [header N] [old payload]

When receiving the message, we parse the header N part of the payload
and write the [header param N-1] field accordingly. The free space
moves, and in some cases copying can be completely eliminated.

At the physical layer the incoming and outgoing message has the
following structure:

[header param 1] [free space] [payload]

The [header param 1] field contains only the length of the payload.
The length of the [free space] field is only the extra space needed to
be able to set 64-bit addresses if necessary.

Of course there need to be an interface to keep track of the size of
all header parameters and the start and length of the payload, but
that can be done fairly easily. This approach has the following
benefits:

1) The metadata sections are either moved to the [header param N] or
[footer param N] sections, no need to handle them differently.

2) We can reuse the header, footer and metadata sections between
branches of the network stack

3) Some layers can completely reset/mask all parameters of the lower
layers. E.g. transport layer may decide that the link layer
acknowledgement fields should not be accessible, therefore can set up
the following layout:

[header param N] [free space] [payload]

This way you can completely reuse all metedata/header/footer fields of
the transport and link layers. This approach is flexible and scalable.

Miklos


On Tue, May 19, 2009 at 7:18 PM, Stephen Dawson-Haggerty
<stevedh at eecs.berkeley.edu> wrote:
> This is a good discussion-- a few extra points
>
>  - I use gather within blip to implement IP header processing, and
> many things about it are very convenient.  The memory overhead is only
> about 4 bytes per header for iovec-style header processing  However,
> I'm not sure I see a real advantage over these proposals in this case.
>  The reason is because unless you are dynamically allocating memory,
> the regions pointed to from the iovec must be inside the static
> message_t.  Therefore, the only new thing this would allow you to do
> is to insert headers at arbitrary places in the message, which seems
> to be of limited value to me.
>
>  - I think one real issue with proposal (2) is not knowing how much
> payload is available until you send().  In (1) presumably once the
> headers are reserved, you can call getMaxPayload() and learn how much
> room is available in the packet.
>
>  - Has there been any discussion of standardizing header processing?
> TLVs, to improve interop?
>
>
> Thanks,
> Steve
>
>
> On Mon, May 11, 2009 at 1:46 AM, Miklos Maroti <mmaroti at math.u-szeged.hu> wrote:
>> On Mon, May 11, 2009 at 6:34 AM, culler <culler at cs.berkeley.edu> wrote:
>>> Classically, on the inbound path you have a contiguous packet with the
>>> telescoping layers of encapsulation.  The trick is the outbound path, since
>>> each layer does not know what the layers around it want to wrap around it.
>>>  Classically, you build a list of these (mbufs) as you go down and perform a
>>> gather as it goes out.  Or, you need to determine from the layers below what
>>> they need.  All of addresses and header fields aree just encapsulating
>>> information.  Given that our processors are really fast compared to these
>>> paltry radios, it is not obvious that gather is a problem.  Very retro, but
>>> there is a reason that it was done in the old days.
>>
>> Gather would be very nice and flexible, but probably it would waste memory.
>>
>> David, could you please shed some light on what is the final goal?
>> What exactly do people want to archive that requires variable size
>> headers? It is not enough for me to say that 16 and 64-bit addresses,
>> because I also want to know what interfaces you want to use. Do people
>> have two interfaces in mind, one AMPacket to access 16-bit and another
>> for 64-bit, or we want to have two AMSend interfaces, one with 16-bit
>> and one for 64-bit, or we want one interfaces to be able access both
>> 16 and 64-bit addresses, or we want to always use 64bit addresses in
>> software but would like to be able to receive 16-bit addresses too and
>> cast them to 64-bit?
>>
>> My real question is: how application developers want to interact with
>> the message buffer? I would like to see use cases.
>>
>> Miklos
>>
>> _______________________________________________
>> Tinyos-devel mailing list
>> Tinyos-devel at millennium.berkeley.edu
>> https://www.millennium.berkeley.edu/cgi-bin/mailman/listinfo/tinyos-devel
>>
>