[Tinyos Core WG] Fwd: [Tinyos-devel] message_t

[Philip Levis]

Begin forwarded message:

> From: Jan Hauer <hauer at tkn.tu-berlin.de>
> Date: March 14, 2009 8:05:06 AM PDT
> To: Miklos Maroti <mmaroti at math.u-szeged.hu>
> Cc: tinyos-devel at millennium.berkeley.edu
> Subject: Re: [Tinyos-devel] message_t
>
>> So this is the hard choice: with my proposal you need to reformat the
>> message when the layout is changed, with your proposal you need to  
>> out
>> mix in network layer configuration options in the metadata, thus
>> wasting RAM in every message.
>
> With my proposal you wouldn't need to (temporarily) store
> control/address information in a separate metadata buffer, the
> metadata part is optional: if none of the components in the
> send/receive path are using metadata (e.g. no timestamps, no RSSI,
> etc.) then the matadata buffer size would be 0 byte. The message
> buffer would still only be MAX_PACKET_SIZE byte, e.g. 127 for
> 802.15.4. The send() interface either includes the address/control
> parameters or they are set via a different protocol-specific interface
> and then send() only takes the packet_t as parameter. I.e. either
>
>  call Send.send(packet, address, ackrequest, ...);
>
> or
>
>  call Protocol.setControl(packet, addresses, ackrequest, ...);
>  call Send.send(packet);
>
> In a protocol implementation any control/address information would
> typically be written immediately into the message buffer
> (packet_t->data[]) and could later also be overwritten without
> changing the layout of the remaining parts of the message, e.g. the
> following would only result in re-formatting the header, but not the
> rest of the message buffer in the packet:
>
>  call Protocol_X.setShortHeader(packet, shortAdress, ackrequest, ...);
>  // ... we changed our mind ...
>  call Protocol_X.setExtendedHeader(packet, extendedAdress,  
> ackrequest, ...);
>
> This works because packet_t is based on a circular buffer, i.e. data
> can be attached to/removed from front (header) or back (footer)
> without having to shift the remaining parts in the message buffer.
> Unfortunately this is not for free: (1) per packet_t we'd need two
> uint8_t indices pointing to start/end of the current PDU (we might
> actually need another uint8_t); and (2) an intermediate layer on the
> send() path (but only there) that wants to add/remove a header/footer
> MUST use special accessor functions which are more expensive than
> accessing the memory directly (the accessor funtions would hide the
> wrap arounds in the array beneath the ring buffer). For example, to
> set the header the protocol could implement a command like this:
>
> command error_t Protocol_X.setShortHeader(packet_t *packet,
>                        uint16_t shortAddress, uint8_t control){
>  call Control.add(packet, ackrequest);
>  call ShortAddress.add(packet, shortAddress);
> }
>
> Here the Control and ShortAddress interfaces could be provided by a
> (generic) library component that provides the typed interface
> Header<val_t> with two commands add(packet_t, val_t) and
> remove(packet_t), i.e. in the example the signature of Protocol_X
> would include:
>
>    uses Header<uint8_t> as Control;
>    uses Header<uint16_t> as ShortAddress;
>
> This is meant as one example of how the accessors could look like
> (they probably should use network types as parameters). So... I agree
> with you that both proposals have their individual drawbacks -- it
> seems like there is no solution that has all the nice properties of
> message_t (buffer swapping, zero-copy-semantics, direct buffer access)
> and at the same time supports variable-sized headers/footers.
>
> Jan
>
>
>
> On Fri, Mar 13, 2009 at 6:18 PM, Miklos Maroti <mmaroti at math.u-szeged.hu 
> > wrote:
>> Hi Jan,
>>
>>> 1) I'm not sure if I understood the format() part correctly.  
>>> Couldn't
>>> the following happen: The app calls format(). The call propagates
>>> downwards through all protocol layers. When it reaches the routing
>>> protocol, the next hop must be chosen which, say, has a short  
>>> address
>>> (16-bit): by calling format() on the MAC the routing layer would
>>> somehow tell the MAC to use/reserve 16-bit for the destination  
>>> address
>>> in the MAC header. Some time later the application decides to put  
>>> some
>>> data in the payload section and then call send(). Because send() is
>>> split-phase it might take some more time until the send() call  
>>> reaches
>>> the routing layer (packet can be queued in a send-queue on upper
>>> layers, etc.). By the time send() reaches the routing protocol the
>>> original next hop has disappeared (was dropped from the forwarding
>>> table). The next hop now has an extended address (64-bit), which
>>> wouldn't fit in the MAC header anymore -- so the packet couldn't be
>>> sent?
>>
>> Your analysis is correct, the message needs to be reformatted if you
>> wait a lot of time between format() and send() and the routing layer
>> decides to use a different layout.
>>
>>> 2) When a sendDone() returns FAIL and the application tries to  
>>> resend
>>> the same packet, then it might have to clear() the packet content  
>>> and
>>> write the same payload again, because this time format() might  
>>> result
>>> in a different layout?
>>
>> That is also correct if you add layers dynamically without the
>> knowledge of the user.
>>
>>> 3) To forward a message it has to be copied as soon as the size of  
>>> any
>>> headers/footers changes and to be compatible with AM you'd also have
>>> to copy, right?
>>
>> True.
>>
>> Now, let me tell you what the alternative is: Do not move the
>> parameters from Send.send() to Packet.format() so you can change the
>> layout at Send.send() time. This means that you have to include ALL
>> parameters in the Send.send() command and you cannot mix in optional
>> header components. For example, the PacketAcknowledgement interface
>> cannot set the ACK bit in the 802.15.4 header because it does not  
>> know
>> where the header is going to be when Send.send is called, so it must
>> store that information in a metadata field and copy it to the header
>> when that is constructed. The same goes for the security interface,
>> you cannot store that 14 bytes in the header, so you must store it in
>> the metadata and copy it when needed. This leaves you two options:
>>
>> 1) You pass ALL parameters in the Send.send() command including data
>> stored/accessed with the PacketAcknowledgement, PacketLink,
>> PacketSecurity, PacketTimeSync interfaces. This would require a
>> routing layer to receive and move these bits of information around
>> with the message_t separately. But where would it store this info?
>> Somewhere it the metadata, so practically the routing layer has to do
>> the next option implicitly:
>>
>> 2) Store all this mix in information in the metadata section, so you
>> can mix them in the header when the header is constructed at
>> Send.send() time. But then you are wasting a lot of RAM as every
>> possible extension must reserve enough space in the metadata section
>> to work properly.
>>
>> So this is the hard choice: with my proposal you need to reformat the
>> message when the layout is changed, with your proposal you need to  
>> out
>> mix in network layer configuration options in the metadata, thus
>> wasting RAM in every message.
>>
>> Miklos
>>
> _______________________________________________
> Tinyos-devel mailing list
> Tinyos-devel at millennium.berkeley.edu
> https://www.millennium.berkeley.edu/cgi-bin/mailman/listinfo/tinyos-devel