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

[Eric Decker]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: https://www.millennium.berkeley.edu/pipermail/tinyos-devel/attachments/20090706/71b30d09/attachment.htm