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

[Jan Hauer]

Hi Eric,

>> 1) I completely agree that wraparound is a pain and takes more CPU
>> cycles to implement that it saves
>
> After thinking about it some more I think circular/wraparound is good in
> concept but the practicalities of it make it a non-starter.

Why? The circular buffer approach that I proposed bounds the number of
memmoves to one (in the majority of cases it will be zero), allocating
a new header/footer inside the message is fast (checking the bounds of
the buffer, incrementing an index and returning a pointer) and
accessing the header/footer is no additional overhead (the client does
it via the pointer - there is never a wraparound within a
header/footer).

Jan


>
>>
>> 2) The two addressing modes are 16-bit and 64-bit, so you have 2*6 =
>> 12 bytes difference
>
> Exact sizes are specified in the encapsulation header definitions for each
> of these.  I would recomend defining two different structures rather than
> use one structure with a union.
>
>> 3) You might have other optional header components: e.g. security (7
>> bytes) or non-intra-pan frames (2 bytes)
>
> different encapsulation structures.   The system I'm putting together should
> handle this just fine.  (embedded in the encap_size data cell).
>
>> 4) Add to that your 5-byte encapsulation overhead (by the way, why do
>> you use 16-bit numbers)
>
> I count 6 bytes.  I used 16 bit numbers for certain of the fields because I
> have some need for >256 byte packets.   The minimum we can get away with is
> 4 bytes.
>
>> 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.
>
> I've actually thought about this some more.  This is build parameter that
> can be tweaked and handled by the encapsulators.  Not in general but a
> system can be built that behaves like you are describing.  Further it can be
> done in such a way that with some overhead the memmove can be bounded.
>
> The key is 1st) going to variable encapsulation (which requires the 4 bytes
> of overhead), and making the build itself determine how packets are placed
> into buffers.  I'm making my prototype behave that way.  That is the
> developer determines the placement of data into the packet buffers and how
> the encapsulators work.
>
> I think my prototype will allow you to build what you are suggesting.
>
> eric
>
>> 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
>> >
>> >
>
>
>
> --
> 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
>
>