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

[Eric Decker]

I keep thinking that it is a byte bounded circular buffer.  But I think I
misunderstood.
It is on a per field basis.  If something doesn't fit, the entire header
that doesn't fit gets
moved.  Yes?

How does this work for cascading encapsulations?  Do we need to worry about
that?

eric


On Thu, Jul 9, 2009 at 12:55 AM, Jan Hauer <jan.hauer at gmail.com> wrote:

> 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
> >
> >
>



-- 
Eric B. Decker
Senior (over 50 :-) Researcher
Autonomous Systems Lab
Jack Baskin School of Engineering
UCSC
-------------- next part --------------
An HTML attachment was scrubbed...
URL: https://www.millennium.berkeley.edu/pipermail/tinyos-devel/attachments/20090709/e8265177/attachment-0001.htm