Hood

From NESTFE Wiki

Contents 1 Overview 2 API 2.1 Reflections 2.2 Membership 2.3 Scribbles 2.4 Interfaces 2.5 Wirings 3 Setting Up 4 New Changes/Features since last implementation 5 Questionable Features that require review 6 Implementation

Overview

Hood is a programming abstraction in which a module may request a "reflection" of its neighbors' Registry values, ie. a locally cached copy. For example, if all node's have a value called "location" in the registry, a node may ask for reflections of those locations. The Hood abstraction takes care of the caching and communication of the values, and the module can simply do a "get" on them when it wants to look at neighbors' locations.

A complete sample application can be found in contrib/hood/apps/TestHood. The Hood libraries can be found in tos/lib/Hood. A complete paper on the Hood abstraction can be found here. Some documentation of the API is below.

API

Reflections

Hood relies on the Registry, and the APIs are very similar. The registry allows one to declare a Registry Attribute as follows:

   interface Attribute<uint16_t> as Light @registry("Light");

which means there is now a uint16_t value called "Light" which this module can use, and share with all other modules that use it. Similarly, Hood allows you to declare a reflection of neighbors' Light attribute as follows:

   interface Reflection<uint16_t> as LightRefl @reflection("Light","LightHood");

which means that the module now has access to cached values of the Light attribute for all the neighbors in the LightHood (a node can define multiple neighborhoods, eg LightHood, RoutingHood, etc. Each Hood will generall have different reflections and different membership criteria).

Membership

The membership of the LightHood must be defined by the user through a LightHoodManager module that implements the "HoodManager" interface, as follows:

   interface HoodManager @hood("LightHood", 8, "Light","Location"); 

Where 8 is the maximum number of neighbors to be in the LightHood and Light and Location indicate "required fields for the LightHood. When the Hood has collected all required fields for a candidate neighbor, it signals a "newCandidate" event through this interface and LightHoodManager must either accept or reject that candidate.

Scribbles

A "scribble" is like a reflection in that there is a value for each neighbor in the Hood. However, scribbles are only local annotations of reflections; they do not originate at the neighbor. Think of a "mirror" as the set of all "reflections" of a neighbor. A "scribble" is a local annotation written on the mirror, but not on the actual neighbor. One can define a scribble as:

   interface Reflection<uint16_t> as Timestamp @scribble("LightHood","Timestamp");

which might hold, for example, the timestamp of the last message from that neighbor.

Interfaces

The Reflection interface is used for both reflections and scribbles, and has the following functions:

 interface Reflection<t>
 {
   command bool valid(uint16_t nodeID);
   command t get(uint16_t nodeID);
   command result_t scribble(uint16_t nodeID, t val);
   command result_t update(uint16_t nodeID);
   event void updated(uint16_t nodeID,t val);
 }

The Hood manager must handle one event and can call 3 functions:

 interface HoodManager  
 {
   command result_t removeNeighbor(uint16_t nodeID);
   command result_t acceptCandidate(uint16_t nodeID);
   command result_t replaceNeighborWithCandidate(uint16_t neighborID, uint16_t candidateID);
   event void newCandidate(uint16_t nodeID);
 }

Wirings

Any component that uses a reflection or scribble interface must wire it to the corresponding neighborhood, as follows:

 components  
   TestHoodM,
   LightHoodC,
   ...
 
 TestHoodM.LightRefl -> LightHoodC.LightRefl;
 TestHoodM.LocationRefl -> LightHoodC.LocationRefl;

At least one component must include the Hood Manager in it's component list to make sure it gets compiled into the application. Usually, this will be some top level app which also initializes the hood and the registry:

 components  
   TestHoodM,
   LightHoodC,
   LightHoodManagerC,
   RegistryC,
   ...

 Main.StdControl -> TestHoodM;
 Main.StdControl -> LightHoodC;
 Main.StdControl -> LightHoodManagerC;
 ....

Setting Up

In order to use the API described above, the user must:

1. use the new makesystem by setting the Makerules environment variable to point to the tinyos-1.x/tools/make/Makerules file
2. add the following include directories to their makefile

CFLAGS += -I$(TOSDIR)/../tos/lib/Registry
CFLAGS += -I$(TOSDIR)/../tos/lib/Hood
CFLAGS += -I$(TOSDIR)/../beta/Drip
CFLAGS += -I$(TOSDIR)/../beta/Drain

1. include the XXHoodC.nc module somewhere in their application, where XX is the name of the hood
2. include their own XXManagerC.nc module somewhere in their application, where XXManager is the name of the manager module

1. invoke the hood.extra file their make process by either declaring "hood" on the command line when making the application as follows

make telosb hood

or adding registry to the GOALS variable in their makefile

GOALS+=hood

For problems, the Pytos Installation Instructions setup instructions may contain more details.

New Changes/Features since last implementation

• each Hood is defined with a group of "required" attrs, and when one is pushed they are all pushed. This eliminates the need for "bootstrap"
• the limitation that all "required" attrs must fit into one message has been removed
• NeighborManager does not have to manage "updatedNaN" events or candidate nodes. This is done by the hood; the manager only accepts or rejects "complete" candidates.
• changes to multiple attrs result in only one message being sent, if possible (ie. there is marshalling)
• multiple subsequent changes to the same attribute result in transmission of only the last value (current threshold set to 100msec)
• a pull of multiple attrs from the same node results in only one query message instead of one query per attr
• the response to pulls from multiple nodes is sent in only message if they are requesting the same attr, instead of a response to each node. This is most useful during "bootstrapping".
• bootstrapping no longer exists. The manager just "pulls" a required attr on "TOS_BCAST_ADDR" and all neighbors send all attrs that are "required"
• only the RegistryC.nc, Registry.h, LightHoodC.nc, etc, and Hood.h files are generated
• no "global" values, ie it runs in the simulator
• node 0 is not an error condition, ie it runs in the simulator
• "valid" flags on every reflection
• no need to make fake attribute to make a scribble
• No more constructor of hoods, attrs, reflections, etc. All are defined implicitly by their use so there is no more composability problem.
• all attrs, scribbles, etc are automatically numbered, so there is no more naming conflict problem

Questionable Features that require review

• maximum of 8 "required" attributes per hood, as defined in the struct @hood in Hood.h (required attributes are those that the HoodManager needs to make a membership decision)
• if HoodA requires Light and Location and HoodB requires Temp and Location, and HoodA does a "pull" on Location, Light, Location and Temp will all be sent. It's easy to do it either way, but I thought this would be more efficient if there was a HoodB out there that could piggyback on HoodA's pull.
• if a pull is done on multiple attrs, but some of them cannot be gotten (they are invalid), there is no error message sent to the module requesting the pull. I chose to do it this way because it is easier, and because, if the module wanted reliability, it would need to implement it's own logic to deal with network unreliability anyway.
• if an attribute is pushed, but other attrs that are "required" with it cannot be pushed (they are invalid), it is pushed anyway even though it is not useful for membership without the other required attrs. this is done just in case another hood could use the value.
• right now, scribbles and reflections are identical accept that scribbles are not pushed or pulled. However, the requesting module does not get an error; the push or pull simply fails when the comm layer notices that there is no attr in the registry with that value. Could be changes by adding a Scribble.nc and ScribbleM.nc, but this is low priority. I'm leaving the "update" function in there, however, because a modules that "provides" a scribble may be able to update it.
• for attributes, "update" means "generate a new value" while for reflections "update" means "pull". We are semantically overloading the word "update", which could be either easier or confusing to the user.

Implementation

ReflectionM.nc is simply an array, which caches the values of the neighbors and provides the Reflection.nc interface. The HoodM.nc is simply an array that holds the nodeIDs of the neighbors, and provides the Hood.nc interface. ReflBackend.nc is the backend interface used between the Hood and the Reflection.

HoodM.nc connects to HoodTransportM.nc to send/receive all communication to neighboring nodes (through the HoodTransport interface). HoodTransportM queues requests to send/receive attributes for about 100msec, to make sure duplicates do not occur. It also makes heavy use of MarshallerM, which simply takes a set of attrIDs and marshalls them, or takes a buffer of marshalled attrs and unmarshalls them. The Marshaller is written to be very generic because it is also reused for RegisterQuery, RamQuery, HoodQuery, etc, and can be kind of confusing. There is heavy documentation inside that module, for in general you don't need to know anything about it.

ReflectionM is a generic component that is instantiated for every reflection of every Hood. Similarly, HoodM is a generic component that is instantiated for every Hood on the node. These are all tied together with, eg. LightHoodC, which is automatically generated based on the @tags in the interface definitions. Hood.h is also automatically generated to create some necessary constants.