tep110.txt

tinyos-2.x.rar

============================
Virtualization
============================

:TEP: 110
:Group: Core Working Group 
:Type: Documentary
:Status: Draft
:TinyOS-Version: 2.x
:Author: Philip Levis

:Draft-Created: 20-Jun-2005
:Draft-Version: $Revision: 1.5 $
:Draft-Modified: $Date: 2006/12/12 18:22:54 $
:Draft-Discuss: TinyOS Developer List <tinyos-devel at mail.millennium.berkeley.edu>

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

This memo desribes how TinyOS 2.0 virtualizes common abstractions through
a combination of static allocation and runtime arbitration. It describes
the benefits and tradeoffs of this approach and how it is used in several
major abstractions.

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

The TinyOS component model allows flexible composition, but that
flexibility is often limited by reasons which are not explicitly
stated in components. These implicit assumptions can manifest as buggy
behavior. In TinyOS 1.x, on the Telos platform, if a program
simultaneously initializes non-volatile storage and the radio, one of
them will fail: a program has to initialize them serially. They can
also manifest as compile-time errors: if two separate communication
services happen to receive packets of the same AM type, the nesC
compiler will issue a warning due to the buffer swap semantics.

On one hand, the flexbility components provide allows expert users to
build complex and intricate applications. On the other, it can make
managing complexity and intricacy very difficult when building very
simple and basic applications. To promote this latter class of
development, TinyOS 2.x has the notion of "distributions," which are
collections of system abstractions that are designed to be used
together. As long as a user implements an application in terms of the
distribution, the underlying components will operate correctly and
there will be no unforseen failures.

This memo documents an example distribution, named OSKI (Operating
System Key Interfaces). It describes the services OSKI provides and
how their implementations are structured to simplify application
writing.


2. Distributions
====================================================================

A distribution presents *services* to the programmer. A service is a
set of generic (instantiable) components that represent API
abstractions. To use an abstraction, a programmer instantiates the
generic. For example, OSKI has the ``AMSenderC`` abstraction for
sending active messages. The AMSender generic component takes a single
parameter, the AM type. For example, if a programmer wants a component
named AppM to send active messages of type 32, the configuration would
look something like this:

| configuration AppC {}
| implementation {
|   components AppM, new AMSenderC(32);
|   AppM.AMSend -> AMSenderC;
| }

Services often present abstractions at a fine grain. For example, the
active message service has AMSender, AMReceiver, and AMSnooper, each
of which is a separate abstraction.

2.1 Controlling a Service
--------------------------------------------------------------------

Every service has two abstractions: ``ServiceC``, for powering it on
and off, and ``ServiceNotifierC``, for learning when the service's
power state has changed. For example, active messages have the
``AMServiceC`` and ``AMServiceNotifierC`` abstractions. A service
abstraction provides the ``Service`` interface

| interface Service {
|   command void start();
|   command void stop();
|   command bool isRunning();
| }

while a notifier abstraction provides the ``ServiceNotify`` interface

| interface ServiceNotify {
|   event void started();
|   event void stopped();
| }

For example, if a routing layer wants to be able to turn the active
message layer on and off, then it needs to instantiate an AMServiceC.
However, many components may be using active messages and have their
own instances of AMServiceC; while routing might consider it
acceptable to turn off active messages, other components might
not. Therefore, a service abstraction does not necessarily represent
explicit control; instead, each service has a *policy* for how it
deals with control requests. When a service changes its activity
state, it MUST signal all instances of its ServiceNotifierC.

For example, the active messages service has an "OR" policy; the
service remains active if *any* of its ServiceC instances are in the
on state, and goes inactive if and only if *all* of its ServiceC
instances are in the off state. This is an example timeline for
active messages being used by two components, RouterA and RouterB:

1. System boots: active messages are off.
2. RouterA calls ``Service.start()``. The AM layer is turned on.
3. All AMServiceNotifierC abstractions signal ``ServiceNotify.started().``
4. RouterB calls ``Service.start()``.
5. RouterA calls ``Service.stop()``. RouterB is still using active messages, so the layer stays on.
6. RouterB calls ``Service.stop()``. The AM layer is turned off.
7. All AMServiceNotifierC abstractions signal ``ServiceNotify.stopped().``

By default, a service that has a control interface MUST be off. For an
application to use the service, at least one component has to call
``Service.start()``.

2.2 Service Initialization
--------------------------------------------------------------------

Because distributions are collections of services that are designed to
work together, they can avoid many of the common issues that arise
when composing TinyOS programs. For example, user code does not have
to initialize a service; this is done automatically by the
distribution.  If a user component instantiates a service abstraction,
the distribution MUST make sure that the service is properly
initialized. Section 4 goes into an example implementation of how a
distribution can achieve this.


3. OSKI Services
====================================================================

This section briefly describes the services that OSKI, an example
distribution provides. It is intended to give a feel for how a
distribution presents its abstractions. 

3.1 Timers
--------------------------------------------------------------------

OSKI provides timers at one fidelity: milliseconds. Timers do not have
a Service abstraction, as their use implicitly defines whether the
service is active or not (the timer service is off if there are no
pending timers).  The ``OSKITimerMsC`` component provides the
abstraction: it provides a single interface, ``Timer<TMilli>``.

This is an example code snippet for instantiating a timer in a
configuration:

| configuration ExampleC {
|   uses interface Timer<TMilli>;
| }
|
| configuration TimerExample {}
| implementation {
|   components ExampleC, new OSKITimerMsC() as T;
|   ExampleC.Timer -> T;
| }


3.2 Active Messages
--------------------------------------------------------------------

OSKI provides four functional active messaging abstractions:
``AMSender``, ``AMReceiver``, ``AMSnooper``, and
``AMSnoopingReceiver``. Each one takes an ``am_id_t`` as a parameter,
indicating the AM type. Following the general TinyOS 2.x approach to
networking, all active message abstractions provide the ``Packet`` and
``AMPacket`` interfaces.

AMSender
  This abstraction is for sending active messages. In addition to Packet
  and AMPacket, it provides the AMSend interface.
AMReceiver
  This abstraction is for receiving active messages addressed to the
  node or to the broadcast address. In addition to Packet and AMPacket,
  it provides the Receive interface.
AMSnooper
  This abstraction is for receiving active messages addressed to other
  nodes ("snooping" on traffic). In addition to Packet and AMPacket,
  it provides the Receive interface.
AMSnoopingReceiver
  A union of the functionality of AMReceiver and AMSnooper, this
  abstraction allows a component to receive *all* active messages
  that it hears. The AMPacket interface allows a component to determine
  whether such a message is destined for it. In addition to
  Packet and AMPacket, this component provides the Receive interface.

This snippet of code is an example of a configuration that composes a
routing layer with needed active message abstractions. This
implementation snoops on data packets sent by other nodes to improve
its topology formation:

| configuration RouterC {
|   uses interface AMSend as DataSend;
|   uses interface AMSend as ControlSend;
|   uses interface Receive as DataReceive;
|   uses interface Receive as BeaconReceive;
| }
|
| configuration RoutingExample {
|   components RouterC;
|   components new AMSender(5) as CSender;
|   components new AMSender(6) as DSender;
|   components new AMReceiver(5) as CReceiver;
|   components new AMSnoopingReceiver(6) as DReceiver;
|
|   RouterC.DataSend -> DSender;
|   RouterC.ControlSend -> CSender;
|   RouterC.DataReceive -> DReceiver;
|   RouterC.ControlReceive -> CReceiver;
| }

The active messages layer has control abstractions, named ``AMServiceC``
and ``AMServiceNotifierC``. Active messages follow an OR policy.


3.3 Broadcasts
--------------------------------------------------------------------

In addition to active messages, OSKI provides a broadcasting service.
Unlike active messages, which are addressed in terms of AM addresses,
broadcasts are address-free. Broadcast communication has two
abstractions: ``BroadcastSenderC`` and ``BroadcastReceiverC``, both of
which take a parameter, a broadcast message type. This parameter is
similar to the AM type in active messages. Both abstractions provide
the Packet interface. The broadcast service has control abstractions,
named ``BroadcastServiceC`` and ``BroadcastServiceNotifierC``, which
follow an OR policy.

3.4 Tree Collection/Convergecast
--------------------------------------------------------------------

**NOTE: These services are not supported as of the 2.x prerelease. 
They will be supported by the first full release.**

OSKI's third communication service is tree-based collection routing.
This service has four abstractions:

CollectionSenderC
  This abstraction is for sending packets up the collection tree,
  to the collection root. It provides the Send and Packet interfaces. 

CollectionReceiverC
  This abstraction is for a collection end-point (a tree root). It
  provides the Receive, Packet, and CollectionPacket interfaces.

CollectionInterceptorC