[net2-wg] Proposal for dissemination structure and interfaces

[Gilman Tolle]

Here's our proposal for dissemination interfaces and component
structure. Looking forward to your comments on the list and then to
discussion on Thursday.

Gil
-------------- next part --------------
Proposal for dissemination structure and interfaces.

We define disseminate as:

"Reliably deliver a piece of data to every node in the network."

The assumption is that dissemination has many consumers and few
producers.

A program uses the dissemination layer by declaring a dissemination
value -- a piece of data which can be modified through
dissemination. This could be a configuration constant, a small
program, or a simple state variable. The consumer interface is:

interface DisseminationValue <t> {
  command const t* get();
  event void changed();
}

The producer interface is:

interface DisseminationUpdate <t> {
  command void change(t* newVal);
}

With these interfaces, the underlying implementation caches the value.
The parameter to Disseminate.change() can be reclaimed by the caller
as soon as the commmand returns. The reason why we settled on this
signature was because we felt that making an update a single atomic
operation was the least bug prone. We started with

interface DissseminationUpdate <t> {
  command t* get();
  command void change();
}

but realized that this could easily lead components to get() the value
and modify it while forgetting to call change(). This could lead to
multiple inconsistent values with the same metadata making its way
through the network.

Declaring a dissemination value requires instantiating a generic
component:

generic configuration DisseminatorC(typedef t, uint16_t key) {
  provides interface DisseminationValue <t>;
  provides interface DisseminationUpdate <t>;
}

For now, we limit <t> to be values that can fit in a single TinyOS
packet. The implementation will check this at compile-time. The
developer selects an integer key for each value that does not conflict
with other values (like selecting AM identifiers). 

DisseminatorC instantiates a generic module, DisseminatorP, which
stores the data value. DisseminatorP sits on top of the actual
dissemination engine, using an instance parameterized interface. The
parameter defines the key of the key-value pair that comprises a
value's metadata for discovering new values.

generic module DisseminatorP(typedef t, uint16_t key) {
  provides interface DisseminationValue <t>;
  provides interface DisseminationUpdate <t>;
  uses interface Disseminate;
}
implementation {
  t valueCache;
  
  ...
}

interface Disseminate {
  command void incrementVersion();
  // the uint8_t* here is used to get the length
  event void* requestValue(uint8_t* len);
  event void valueReceived(void* val, uint8_t len);
}

The implementation of DisseminatorC looks like this:

implementation {
  component new DisseminatorP(t);
  component DisseminationEngine;

  DisseminatorP.Disseminate -> DisseminationEngine.Disseminate[key];
}

One issue that comes up when using this interfaces is the selection of
a key for each value. On one hand, using unique() is easy, but this
means that the keyspaces for two different compilations of the same
program might be different and there's no way to support a network
with more than one binary. On the other, having a component declare
its own key internally means that you can run into key collisions that
can't be resolved. In the middle, an application can select keys on
behalf of other components.

Ordinarily, dissemination keys can be generated by unique or selected
by hand. However, these defined keys can be overridden by an
application-specific header file. The unique namespace and the static
namespace are separated by their most significant bit. A component
author might write something like this:

#include <disseminate_keys.h>

configuration SomeComponentC { 
  ...
}
implementation {

#ifndef DIS_SOME_COMPONENT_KEY
  enum {
    DIS_SOME_COMPONENT_KEY = unique(DISSEMINATE_KEY) + 1 << 15;
  };
#endif

  components SomeComponentP;
  components new DisseminatorC(uint8_t, DIS_SOME_COMPONENT_KEY);

  SomeComponentP.ConfigVal -> DisseminatorC;
}

To override, you can then make a disseminate_keys.h in your app
directory:

#define DIS_SOME_COMPONENT_KEY 32

Even with careful key selection, two incompatible binaries with
keyspace collisions may end up in the same network. If this happens, a
GUID that's unique to a particular binary can be included in the
protocol. The GUID enables nodes to detect versions from other
binaries and not store them. This GUID won't be part of the external
interface, but will be used internally.

Another consistency issue comes up when allowing any node to update a
value: multiple inconsistent versions of a value can exist in the
network at the same time. E.g., if A and B both have version 5 and
both update, they'll both be advertisting version 6 yet their values
might be different. We decided that it was important that there be
globally consistent versioning. Therefore, a value's metadata is a
combination of a version number and the originator's AM address. This
means that AM address is used to break ties. In the previous exammple,
node A would eventually install node B's value (since B > A).

You can use this low-level networking primitive to build more complex
dissemination systems. For example, if you want have a dissemination
that only nodes which satisfy a predicate receive, you can do that by
making the <t> a struct that stores a predicate and data value in it,
and layering the predicate evaluation on top of the above interfaces.
This also means that you can build up a very different style of
dissemination interface, if you wanted to try to unify both
communication modes: once you have predicates you can have addressing,
and then you could just present dissemination as AMSend or Send.