[Tinyos-devel] Current status of the message buffer discussion

[Eric Decker]

In a previous life I spent 8 years (80-88) doing processor (CPU) development
and processor bring-up.  I then spent 12 years working at cisco Systems
during the early years where we extensively dealt with the
encapsulation/packet
format problem being discussed.

Here is my take on the message/packet encapsulation problem.

Packet flow: What problem are we trying to solve?  Do we need to be able to
access arbitrary layers in an arbitrary fashion?  Or is it sufficient to
deal with encapsulations as the packet is handed up the stack or conversely
down.

Classically on receive, as a packet moves up the stack, each layer  will
process whatever it needs from the header it concerns itself with.  When
done it will hand the packet to the next layer up after removing the
current header (for its layer) from the packet.

Each layer only concerns itself with its header and no access across
encapsulation boundaries is needed.  Similarily, on output only in
reverse.

Is there a need for arbritrary access to the different header
encapsulations?
I think that insisting on encapsulation boundaries is a good thing (tm), so
think we should keep things simple.  ie.  headers get processed and stripped
off on the way up and get added on the way down.  It argues for the
simplicity
of Jan's approach.


H/W and alignment considerations:  Jan's circular buffer scheme mentions the
need to potentially move the contents of a packet around to make sure that
headers fit and do not wrap.  It is clear that making a header continguous
is necessary to allow proper access when using C structures.

However, there is another consideration.  If h/w is involved then the entire
packet needs to be contiguous (to keep things simple anyway, it is possible
to cascade h/w output ie. cascaded DMA engines but it certainly complicates
things).  This argues for keeping the entire output packet contiguous.

It is desireable to provide a mechanism for a higher layer to place its data
so that more often then not the headers and footers all fit contiguously.
 In
other words avoiding the memmoves.

I actually think this is what Miklos' KISS proposal with Packet.format()
gives
us.  It could be made more automatic via something like Packet.data_offset()
which could call each layer below to see what needs to be added.  However
this
assumes we know something about what interface (MAC) encapsulation we want
to
use so requires apriori knowledge about what interface this packet wants to
get
sent out on.  Not great.  However, a reasonable compromise would combine
both
Jan's and Miklos' mechanism.  Packet.format() tells the system the
predominate
layout.  But inspection and apriori knowledge we would set this for the
specific system
being built (tuned) to minimize the packet layout problems.

What really solves this problem is scatter/gather (actually gather).
 Because
we don't have to worry about properly positioning the application layer's
data
so all the headers fit properly.  Rather we link in successive layer's
encapsulations as the packet travels down the stack.  Yes we really are
reinventing this.  Do we really want to add iovecs to the system?  I think
we can implement something like what Jan suggests fairly simply that also
allows for positioning the most used packets such that they are contiguous.


ActiveMessaging:  The AM layer is an interesting example of an encapsulation
that interfers with a lower layer.  The inner workings of the AM layer
depend
on what the MAC layer is.  For example Serial vs. C2420.  AM has a dispatch
byte (type) that determines what the encapsulation of the rest of the packet
is
but also assumes that the dest and src fields of the MAC layer are the same
as
the AM fields of the same name.   This only works if a) there is a resonable
mapping between the AM address and the underlying MAC address and b) AM
knows
ahead of time what MAC is being used so the format of the fields is known.
 But
this needs to be known apriori.

I have a system where we can switch on the fly between Serial and Radio (but
it can be any two arbritrary network interfaces).  But currently any queued
up
packets have already been written with the wrong encapsulation.  And when
switched to the different interface they are wrong.  This is because AM
knows
too much and the h/w encapsulation should be written until the packet
actually
goes out the interface.

AM really should have its own addressing which would allow mappings similar
to
IP to ethernet or serial encapsulations used on routers.  But this would
burn
scarce bytes in the payload.  The current behaviour of the AM layer confuses
the issue of how encapsulating layers should behave.  This can be handled in
the new scheme very easily.  AM can lay down an AM header and then we define
a simple MAC encapsulation for the AM type that gets written by the MAC
layer.
We define a simple AM_addr to MAC_addr transform that then results in no
loss of bytes in the payload.  The MAC encapsulation would remove the AM
layer
and replace it with the optimized header.  Conversly on the way up.  In this
way AM
wouldn't have any knowledge of what is below it.  And the smarts gets buried
in
the MAC encapsulation which is were it belongs.  This transformation would
also
not occur until it really needed to avoid miswrites.


Length:  Currently, length is maintained by AM writing to whatever it thinks
the length cell is for the MAC layer that AM is bound to.  One can not
currently
just look at the packet data and know what the size of the packet is.  One
needs
to know what the MAC encapsulation is so the appropriate cell can be looked
at
which then tells what length it is.  And this can not be determined by just
looking at the data packet as layed down in memory.

It seems to make sense that there should be a cell associated with the
packet
that tells the currently as encapsulated packets length (meta data?).  This
is
inherent in Jan's start/end cells but would be easier to access if it were
maintained independently.


Simlarily a cell that denotes the current encapsulation of the packet in
memory as it currently stands would be a reasonable thing.  ie.  Last
written
encapsulation.  This would change as the packet is handed up and down the
stack.
It also serves to tell us where in the stack it is.

Speaking of length we really need a mechanism for a higher layer
(application)
to find out what the MTU that it can send is.  If we are sitting on top of
TCP/UDP it can be one thing.  But if sitting on top of a physical interface
it should be something else.  This should be seperated from what
TOSH_MAX_DATA
is defined as.  Which is a link layer thing.

that's all I've got for now.  Hopefully that helps with the discussion.


eric


On Thu, May 7, 2009 at 5:59 PM, Vlado Handziski
<handzisk at tkn.tu-berlin.de>wrote:

> I apologize for the delay, it has been a long day. As agreed during the
> telecon, here is a short summary of the current state of the message buffers
> discussion:
>
> First of all, it is important to state that there is no disagreement about
> the need to replace the current message_t format with something that is
> more flexible and can accommodate both variably-sized headers/footers and
> can provide more freedom in the nesting/interweaving of the protocol
> components.
>
> We currently have two different proposals on the table about how to do
> this:


    .
    .
    .

>
>
> The following is my take on the pros/contras of the two proposals:
>
> It is obvious that both approaches provide a way to handle
> variable-sized headers and free composition of the protocol stack
> components without predefining of the message buffer format. The main
> differences that I see are in the associated costs: (1) the frequency
> of the needed (re)formatting commands and (2) the optimality of the
> memory allocation.
>
> As for (1) I believe that Miklos' proposal is more vulnerable mainly
> due to the time decoupling between the format calls and the send call,
> as well as due to the flat nature of the buffer and the needed
> memmoves caused by extension of the size/number of headers/footers
> (during forwarding, etc.). I think that the circular buffer in Jan's
> proposal handles some of these situations more gracefully.
>
> As for (2), if we agree that we should always be prepared to handle a
> MPDU, there is no difference in the amount of memory the two
> proposals have to allocate for the H,P,F part of the buffer,
> i.e. MSG_MAX_LENGTH in Miklos' proposal has to be >= Jan's
> MAX_MPDU_SIZE. However, because in Miklos' proposal the metadata is
> included in the "formating" stage, the MSG_MAX_LENGTH will be <= than
> the MAX_MPDU_SIZE + uniqueCount(METADATA_BYTE) in Jan's proposal.
>
> Vlado
>
> _______________________________________________
> 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/20090519/b928136c/attachment-0001.htm