tep116.txt

tinyos-2.x.rar

============================
Packet Protocols
============================

:TEP: 116 
:Group: Core Working Group 
:Type: Documentary
:Status: Final
:TinyOS-Version: > 2.1
:Author: Philip Levis

.. Note::

   This memo documents a part of TinyOS for the TinyOS Community, and
   requests discussion and suggestions for improvements.  Distribution
   of this memo is unlimited. This memo is in full compliance with
   TEP 1.

Abstract
============================================================================

The memo documents the interfaces used by packet protocol components in  
TinyOS 2.x as well as the structure and implementation of ActiveMessageC, 
the basic data-link HIL component. It also documents the virtualized
active message interfaces AMSenderC and AMReceiverC.

1. Introduction
============================================================================

Sensor nodes are network-centric devices. Much of their software
complexity comes from network protocols and their interactions.
In TinyOS, the basic network abstraction is an *active message*,
a single-hop, unreliable packet. Active messages have a destination
address, provide synchronous acknowledgements, and can be of
variable length up to a fixed maximum size. They also have a 
type field, which is essentially a protocol identifier for
components built on top of this abstraction.

In TinyOS 1.x, the component GenericComm provides interfaces for
transmitting and receiving active messages::

  configuration GenericComm {
    provides {
      interface StdControl as Control;
      interface SendMsg[uint8_t id];
      interface ReceiveMsg[uint8_t id];
      command uint16_t activity();
    }
    uses {
      event result_t sendDone();
    }
  }

This component, while simple, has several issues. First, it has the
activity() commmand, which does not have a single caller in the entire
TinyOS tree. This command requires GenericComm to allocate a 
timer, wasting CPU cycles and RAM. 

Second, it does not allow a node to receive packets besides
those destined to it.  Several network
protocols (e.g., MintRoute [1]_, TAG [2]_) take advantage 
of snooping on these packets for a variety of improvements in efficiency or
performance. This has led to the creation of GenericCommPromiscuous,
whose Receive interface does not distinguish
between packets received that were addressed to the node and
packets received that were addressed to other nodes. Choosing
one of the two implementations is a global decision across
an application. There is a way to enable both reception
semantics at the same time for a different protocols, 
but they require a creative use of default event handlers.

Third, it assumes that components will directly access the packet
structure, the accepted approach in TinyOS 1.x. However, directly
accessing packet structures introduces unforseen dependencies:
a component that names a header field, for example, binds itself
to data link layers that have a field with that name. Similarly,
components on top of GenericComm directly access the data payload
of a packet.

TEP 111 documents the structure of a TinyOS 2.x packet buffer [3]_.
This TEP documents the interfaces used to access packet buffers,
as well as ActiveMessageC, the basic data-link packet communication
HIL.

2. Communication interfaces
============================================================================

Packet-level communication has three basic classes of interfaces.
*Packet* interfaces are for accessing message fields and payloads. 
*Send* interfaces are for transmitting packets, and are
distinguished by their addressing scheme. 
The *Receive* interface is for handling packet reception events.
Finally, depending on whether the protocol has a dispatch identifier
field, the Receive and Send interfaces may be parameterized in order
to support multiple higher-level clients.

2.1 Packet interfaces
--------------------------------------------------------------------

The basic TinyOS 2.x message buffer type is message_t, which is 
described in TEP 111. message_t right-justifies data-link
headers to the data payload so that higher-level components can 
pass buffers between different data link layers without having
to move data payloads. This means that the data payload of a 
data link frame is always at a fixed offset of a message_t.

Once protocols layer on top of each other, the data
payload for components on top of the data link layer are
no longer at a fixed offset. Where a component can put its 
header or data depends on what headers underlying components
introduce. Therefore, in order to be able to find out where
it can put its data, it must query the components below it.
The Packet interface defines this mechanism::

  interface Packet {
    command void clear(message_t* msg);
    command uint8_t payloadLength(message_t* msg);
    command void setPayLoadLength(message_t* msg, uint8_t len);
    command uint8_t maxPayloadLength();
    command void* getPayload(message_t* msg, uint8_t len);
  }

A component can obtain a pointer to its data region within a packet by
calling ``getPayload()``. A call to this command includes the length
the caller requires. The command ``maxPayloadLength`` returns the
maximum length the payload can be: if the ``len`` parameter to
``getPayload`` is greater than the value ``maxPayloadLength`` would
return, ``getPayload`` MUST return NULL.


A component can set the payload length with ``setPayLoadLength.`` A
component can obtain the size of the data region of packet in use with
a call to ``payloadLength``. As Send interfaces always include a
length parameter in their send call, ``setPayLoadLength`` is not
required for sending, and so is never called in common use
cases. Instead, it is a way for queues and other packet buffering
components to store the full state of a packet without requiring
additional memory allocation.

The distinction between ``payloadLength`` and ``maxPayloadLength``
comes from whether the packet is being received or sent. In the
receive case, determining the size of the existing data payload is
needed; in the send case, a component needs to know how much data it
can put in the packet. By definition, the return value of
``payloadLength`` must be less than or equal to the return value of
``maxPayloadLength``.

The Packet interface assumes that headers have a fixed size. It is
difficult to return a pointer into the data region when its position
will only be known once the header values are bound.

The ``clear`` command clears out all headers, footers, and metadata
for lower layers. For example, calling ``clear`` on a routing
component, such as CollectionSenderC[4]_, will clear out the
collection headers and footers. Furthermore, CollectionSenderC will
recursively call ``clear`` on the layer below it, clearing out the
link layer headers and footers. Calling ``clear`` is typically
necessary when moving a packet across two link layers. Otherwise, the
destination link layer may incorrectly interpret metadata from the
source link layer, and, for example, transmit the packet on the wrong
RF channel. Because ``clear`` prepares a packet for a particular link
layer, in this example correct code would call the command on the
destination link layer, not the source link layer.

Typically, an incoming call to the Packet interface of a protocol has
an accompanying outgoing call to the Packet interface of the component
below it. The one exception to this is the data link layer. For
example, if there is a network that introduces 16-bit sequence numbers
to packets, it might look like this::

  generic module SequenceNumber {
    provides interface Packet;
    uses interface Packet as SubPacket;
  }
  implementation {
    typedef nx_struct seq_header {
      nx_uint16_t seqNo;
    } seq_header_t;

    enum {
      SEQNO_OFFSET = sizeof(seq_header_t),
    };
 
    command void Packet.clear(message_t* msg) {
      void* payload = call SubPacket.getPayload(msg, call SubPacket.maxPayloadLength());
      call SubPacket.clear();
      if (payload != NULL) {
        memset(payload, sizeof(seq_header_t), 0);
      }
    }

    command uint8_t Packet.payloadLength(message_t* msg) {
      return SubPacket.payloadLength(msg) - SEQNO_OFFSET;
    }

    command void Packet.setPayloadLength(message_t* msg, uint8_t len) {
      SubPacket.setPayloadLength(msg, len + SEQNO_OFFSET);
    }

    command uint8_t Packet.maxPayloadLength() {
      return SubPacket.maxPayloadLength(msg) - SEQNO_OFFSET;
    }

    command void* Packet.getPayload(message_t* msg, uint8_t len) {
      uint8_t* payload = call SubPacket.getPayload(msg, len + SEQNO_OFFSET);
      if (payload != NULL) {       
        payload += SEQNO_OFFSET;
      }
      return payload;
    } 
  }


The above example is incomplete: it does not include the code for
the send path that increments sequence numbers. 

In practice, calls to Packet are very efficient even if they 
pass through many components before reaching the data link
layer. nesC's inlining means that in almost all cases
there will not actually be any function calls, and since payload
position and length calculations all use constant offsets,
the compiler generally uses constant folding to generate a 
fixed offset. 

The Packet interface provides access to the one field all packet
layers have, the data payload. Communication layers can add additional
header and footer fields, and may need to provide access to these
fields. If a packet communication component provides access to header
and/or footer fields, it MUST do so through an interface. The interface 
SHOULD have a name of the form *XPacket*, where *X* is a name that
describes the communication layer. For example, active message components
provide both the Packet interface and the AMPacket interface. The latter
has this signature::

  interface AMPacket {
    command am_addr_t address();
    command am_addr_t destination(message_t* amsg);
    command am_addr_t source(message_t* amsg);
    command void setDestination(message_t* amsg, am_addr_t addr);
    command void setSource(message_t* amsg, am_addr_t addr);
    command bool isForMe(message_t* amsg);
    command am_id_t type(message_t* amsg);
    command void setType(message_t* amsg, am_id_t t);
    command am_group_t group(message_t* amsg);
    command void setGroup(message_t* amsg, am_group_t grp);
    command am_group_t localGroup();
  }


The command address() returns the local AM address of the
node. AMPacket provides accessors for its four fields, destination, 
source, type and group. It also provides commands to set these 
fields, for the same
reason that Packet allows a caller to set the payload length.  Packet
interfaces SHOULD provide accessors and mutators for all of their
fields to enable queues and other buffering to store values in a
packet buffer. Typically, a component stores these values in the
packet buffer itself (where the field is), but when necessary it may
use the metadata region of message_t or other locations.

The group field refers to the AM group, a logical network identifier.
Link layers will typically only signal reception for packets whose AM
group matches the node's, which ``localGroup`` returns.

2.2 Sending interfaces
--------------------------------------------------------------------

There are multiple sending interfaces, corresponding to different
addressing modes. For example, address-free protocols, such as
collection routing, provide the basic ``Send`` interface. Active
message communication has a destination of an AM address, so
it provides the ``AMSend`` interface.  This, for example, is the 
basic, address-free Send interface::

  interface Send {
    command error_t send(message_t* msg, uint8_t len);
    command error_t cancel(message_t* msg);
    event void sendDone(message_t* msg, error_t error);  

    command uint8_t maxPayloadLength();
    command void* getPayload(message_t* msg, uint8_t len);
  }

while this is the AMSend interface::

  interface AMSend {
    command error_t send(am_addr_t addr, message_t* msg, uint8_t len);
    command error_t cancel(message_t* msg);
    event void sendDone(message_t* msg, error_t error);

    command uint8_t maxPayloadLength();
    command void* getPayload(message_t* msg, uint8_t len); 
  }

Sending interfaces MUST include these four commands and one event.
The duplication of some of the commands in Packet is solely for ease
of use: ``maxPayloadLength`` and ``getPayload`` MUST behave
identically as ``Packet.maxPayloadLength`` and ``Packet.getPayload.``
Their inclusion is so that components do not have to wire to
both Packet and the sending interface for basic use cases.

When called with a length that is too long for the underlying
maximum transfer unit (MTU), the send command MUST return ESIZE.

The ``Send`` and ``AMSend`` interfaces have an explicit queue of
depth one. A call to ``send`` on either of these interfaces MUST 
return EBUSY if a prior call to ``send`` returned SUCCESS but no
``sendDone`` event has been signaled yet. More explicitly::

  if (call Send.send(...) == SUCCESS &&
      call Send.send(...) == SUCCESS) {
     // This block is unreachable.
  }

Systems that need send queues have two options. They can
use a QueueC (found in tos/system) to store pending packet pointers
and serialize them onto sending interface, or they can introduce
a new sending interface that supports multiple pending transmissions.

The cancel command allows a sender to cancel the current transmission.
A call to cancel when there is no pending sendDone event MUST return
FAIL.  If there is a pending sendDone event and the cancel returns
SUCCESS, then the packet layer MUST NOT transmit the packet and MUST
signal sendDone with ECANCEL as its error code. If there is a pending
sendDone event and cancel returns FAIL, then sendDone MUST occur as if
the cancel was not called.

2.3 Receive interface
--------------------------------------------------------------------

Receive is the interface for receiving packets. It has this signature::

  interface Receive {
    event message_t* receive(message_t* msg, void* payload, uint8_t len);
  }

The ``receive()`` event's ``payload`` parameter MUST be identical to
what a call to the corresponding ``Packet.getPayload()`` would return,
and the ``len`` parameter MUST be identical to the length that a call
to ``Packet.getPayload`` would return. These parameters are for
convenience, as they are commonly used by receive handlers, and their
presence removes the need for a call to ``getPayload()``. Unlike Send,
Receive does not have a convenience ``getPayload`` call, because doing
so prevents fan-in. As Receive has only a single event, users of
Receive can be wired multiple times.

Receive has a *buffer-swap* policy. The handler of the event MUST
return a pointer to a valid message buffer for the signaler to
use. This approach enforces an equilibrium between upper and lower
packet layers. If an upper layer cannot handle packets as quickly as