[Tinyos-devel] message_t: starting to tease AM away from Serial and Radio

[Miklos Maroti]

Eric,

1) I completely agree that wraparound is a pain and takes more CPU
cycles to implement that it saves

2) The two addressing modes are 16-bit and 64-bit, so you have 2*6 =
12 bytes difference

3) You might have other optional header components: e.g. security (7
bytes) or non-intra-pan frames (2 bytes)

4) Add to that your 5-byte encapsulation overhead (by the way, why do
you use 16-bit numbers)

5) When faced by the choice of wasting at least 17 bytes for every
message_t or *occasionally* using a single memmove to reformat an <127
byte message, then I know that I am going to choose the latter.

Miklos

On Tue, Jul 7, 2009 at 12:52 AM, Eric Decker<cire831 at gmail.com> wrote:
> On Mon, Jul 6, 2009 at 12:53 PM, Miklos Maroti <mmaroti at math.u-szeged.hu>
> wrote:
>>
>> Eric,
>>
>> Oh, I see. I do not see this to be a viable solution, since:
>>
>> 1) no wraparound is allowed, therefore
>
> wrap around has many problems.  I've implemented wraparound previously and
> it
> turned out to be a royal pain for anything other than strictly byte data.
> If the data has any structure at all it is very expensive unless you have
> scatter/gather.
>
> If we do a byte accessor wraparound implementation, this impacts every piece
> of network
> code and is very expensive.  There has to be an assembly area where
> structured data is
> collected prior to use.  Any byte pulled from the data packet must come
> through the
> accessor because we might have wrapped.  This is expensive in code
> generated, space needed
> for the assembly area, code executed, etc.
>
> Scatter/Gather is better but has the extra cost of pointers to different
> pieces of the packet.
> Infrastructure is needed for managing these pieces etc.  A variable
> encapsulation access
> mechanism is needed for moving over and accessing different parts of the
> packet.  (Note
> this is required anyway once we go to variable encapsulation which is what
> we need).  This
> is the mechanism that Linux uses and what we used in core router code at
> cisco.  It doesn't
> necessarily lend itself to a very resource constrainted environment.  I
> don't like having to blow
> frag pointers in every single packet if I don't have to.  Too much overhead?
>
> After thinking about this for a bit, I think I've found a good compromise.
> It doesn't use wrap
> around (which is very expensive) so does waste some space.  But it does
> provide for header
> rewrite, and cascading encapsulations.  Variable encapsulation.  It doesn't
> require moving
> packet data.  Headers get rewritten as needed.  See below.
>
> I have a non-trival prototype almost completely coded.  It is AM based using
> serial and radio.
> Probably another week and I'll have it put together enough for someone to
> look at it.
>
>>
>> 2) incoming packets cannot be reformatted (e.g. switch from 16-bit to
>> 64-bit addresses) in place without memmove
>
> I disagree.  There is a solution which depends on 1) variable encapsulation
> access mechanisms and
> 2) clever determination of where received packets start.  Consider:
>
> The approach I'm taking is the following:
>
> 1) The kinds of packets handled and what transformations allowed are planned
> for
> and configured on a per platform basis.  Receive offsets are denoted in the
> platform_message.h
> file.
>
> 2) based on what overlapping/rewritable headers one wants to support it can
> be calculated
> where receives need to be laid down.  For example:
>
> A serial/radio bridge.  The serial header is smaller than the radio header.
> Radio starts receiving
> at 0 and serial receives at 5.  All headers needing rewrite fit and payload
> doesn't need to be moved.
> The header gets rewritten without any data getting moved.
>
> For the case of a large address to short address 802.15.4 transformation we
> can do the following:
>
> If I'm reading things correctly, short addresses are 16 bit while long
> addresses are 32 bits long.  Is that
> correct?
>
> Doing a header rewrite for say 16 bit vs. 32 bit addresses is similar.
> Define two different header structures,
> one for short addresses and one for long.  The difference in these two
> structures should if I'm doing
> the math correctly be 4 bytes, (2 bytes for src and 2 bytes for dest,
> difference).  We can not predict what
> kind of packet we will receive apriori so Radio receive is set up to receive
> starting at byte offset
> 4.  If we receive a long format, we can easily convert to short.  If we
> receive a short format there is
> adequate space expanding just the header that needs to be rewritten.
>
> 3) What makes all this work is having variable encapsulation mechanisms.
> The space allocated
> in the packet allocates space for different parts but isn't where the data
> necessarily goes.  A little
> odd but works.  What I mean is the payload isn't necessarily contained
> within the data area.  Rather
> data must be found by decapsulating the packet using the encapsulators.  The
> application payload
> will follow any headers present.  Depending on what headers are on the
> packet, payload data will
> start at variable places and not in the same place (ie. msg->data).  Any
> access to the actual payload
> needs to be done via an accessor.  But that is going to be true anyway
> once going to a variable encapsulator.
>
> We may want to change the definition of the message_t structure to make this
> more explicit.  A block
> of space (sum of header area, data area, and footer area) rather than
> structures.
>
>
> So I think this approach gives us the flexibility that we want while not
> consumming too many resources.
>
> If there is interest I can make my trees available for scrutuny with the
> previso that it is a work in progress
> and about 80% done.
>
> Currently, I have a custom platform that has a number of custom sensors that
> are generating data that
> gets queued.   10 sources queued.   This queue generates one load that gets
> queued with 2 other sources
> that are queued and handed to the communications switcher.
>
> The active communications port is determined at the moment that a packet is
> ready to be presented to the
> h/w.  For example, we are in the field but not within the known GPS box
> where base station transceivers are
> known to be, we are not docked.  Nothing is transmitted.  If we are within
> the base station box, then we use
> the radio, the packet encapsulation will be written to reflect going out the
> radio.  We can also be docked, in
> which case we will use the serial port.  This can't be done statically
> (which is how the original AM code was
> written) but needs to happen dynamically.
>
> The communications switcher is what provides the mechanics of sending the
> queued packets down the appropriate
> encapsulation stack and then to the appropriate h/w driver.  It requires
> variable encapsulation.  It also cleans
> up some inefficient header manipulation that the static binding had when put
> into a queueing environment.
>
>>
>> 3) therefore you might as well assume that all packets start at index 0.
>
> The key to what I've described above is to determine a non-zero index that
> supports
> the application.  That is part of what makes my scheme work.
>
> thoughts?
>
> eric
>
>>
>> What do you think?
>>
>> Miklos
>>
>> On Mon, Jul 6, 2009 at 9:59 AM, Eric Decker<cire831 at gmail.com> wrote:
>> > Here's the original again.
>> >
>> > I've got most of it put together...  But haven't checked it into my tree
>> > on
>> > the hinrg.cs.jhu.edu
>> >
>> > eric
>> >
>> > ---------- Forwarded message ----------
>> > From: Eric Decker <cire831 at gmail.com>
>> > Date: Sat, May 30, 2009 at 2:58 PM
>> > Subject: message_t: starting to tease AM away from Serial and Radio
>> > To: Jan Hauer <jan.hauer at gmail.com>, Miklos Maroti
>> > <mmaroti at math.u-szeged.hu>, Miklos Maroti <mmaroti at gmail.com>, TinyOS
>> > Development <tinyos-devel at millennium.berkeley.edu>
>> > Cc: Vlado Handziski <handzisk at tkn.tu-berlin.de>, Philip Levis
>> > <pal at cs.stanford.edu>
>> >
>> >
>> > I'm starting coding to tease the AM code away from the Serial and Radio
>> > stacks to make AM encapsulation more independent from the h/w
>> > encapsulation.
>> > The intent is to support the AM encapsulation while moving in the
>> > direction
>> > of Jan's and Miklos' suggestions.  I need something like this because
>> > I'm
>> > doing dynamic switching of queued packets.  Also I want to understand
>> > better
>> > the impact on packetAck and other pinch points with respect to what we
>> > are
>> > discussing with regards to encapsulations and the packet buffers.
>> > I'm using the following principals/goals:
>> > 1) Packet formats don't change.  The resultant code will be completely
>> > compatible with existing motes with respect to the wire/transmission.
>> > 2) Additional control cells are added to the message structure, (encap,
>> > encap_offset (where the current encapsulation starts), length, etc.)
>> > 3) One principal is given a packet one should be able to unwrap the
>> > packet
>> > just by looking at data in the current header.
>> > 4) Header information still resides in the header section of the message
>> > buffer.
>> > 5) Application data resides in the current data area.  encap_offset
>> > points
>> > at what should currently be considered data for the component that is
>> > currently working on the packet.  When the packet gets to the
>> > application
>> > layer, encap_offset will point at the data for the application.
>> > 6) All packet data is maintained contiguously, there is no wrap around.
>> >  1st
>> > structures have to be contiguous.  Splitting data fields including
>> > application data is problematic and needs to be avoided.
>> > One thing I'm added first off is a newPacket module that is used to
>> > access
>> > the packet/message control cells.  It will provide all the usual Packet
>> > interfaces, any new ones will be added to a new interface spec called
>> > oddly
>> > enough newPacket.
>> > This is a prototype to explore some of what we are talking about and to
>> > gain
>> > better understanding of how changes propagate.
>> > I could use some folks looking over my shoulder and commenting on code,
>> > better ways to do things, etc.  Especially on better ways to do things,
>> > where to put things, naming etc.
>> > Thoughts,
>> > eric
>> >
>> > --
>> > Eric B. Decker
>> > Senior (over 50 :-) Researcher
>> > Autonomous Systems Lab
>> > Jack Baskin School of Engineering
>> > UCSC
>> >
>> >
>> >
>> >
>> > --
>> > Eric B. Decker
>> > Senior (over 50 :-) Researcher
>> > Autonomous Systems Lab
>> > Jack Baskin School of Engineering
>> > UCSC
>> >
>> >
>
>
>
> --
> Eric B. Decker
> Senior (over 50 :-) Researcher
> Autonomous Systems Lab
> Jack Baskin School of Engineering
> UCSC
>
>
> _______________________________________________
> Tinyos-devel mailing list
> Tinyos-devel at millennium.berkeley.edu
> https://www.millennium.berkeley.edu/cgi-bin/mailman/listinfo/tinyos-devel
>
>