The Neighborlist Functionality: Design Document

Introduction

This document discusses the design of the Neighborlist feature -- essentially, what it does and how it does what it does.

Purpose of the Neighborlist Functionality

This functionality is necessary/important in order to:

allow applications/other modules to query the current list of valid neighbors
characterize links and expose these statistics to other modules
provide a convenient API to allow applications to query these statistics
optionally, allow applications to filter out "bad" links based on configurable thresholds.

We'll discuss each of these aspects in the following sections:

Link Characterization: Design Considerations

In designing this aspect, we were faced with the following considerations/issues/choices.

active (beaconing) vs. passive (observing packets already in the air) approaches to characterizing loss rate with neighbors

The active approach takes care of periods of low network activity. Hence, the active ingredient has to be part of the design
Passive mode is useful because it comes free anyway. In this approach, each packet is given a per-node sequence number that is incremented for each packet sent from that node.. Sequence number gaps can then be used to calculate loss rate.

In order to observe all packets (even those not destined to an observing node), we need to add a module in between two layers of the UC Berkeley stack -- and this is not "neat".
If we instead decided to have per-neighbor sequence numbers on each node, it would probably complicate things more than we want for the current implementation.

Chosen approach: active approach (beaconing) only. Each node broacasts special beacon packets which contain sequence numbers. Neighbors can then calculate loss rate using sequence number gaps.

1 way vs. 2 way loss statistics maintenance

2 way is important because we want to have metrics that would accurately reflect link asymmetries, etc.

Data structure used to calculate loss rate -- bitmap + end sequence number (CHOSEN) vs. sequence array :

bitmap + end sequence number is preferable keeping in mind memory constraints

Strategy used for continuous maintenance of loss rates

EWMA (CHOSEN) vs. simple windowed:

EWMA in order to filter out transcients in link quality due to, say, an animal walking through the pasture.

API to access the per-neighbor statistics: Design Considerations

Ability to configure parameters involved in loss rate calculation

desirable if some application wants to have capture loss jitter.

this can be done in the init() function for the NeighborBeacon module

Single, unified API to access neighbor statistics from any application:

It would be good to provide a single place where this API can be invoked (more in the next section)

The API provided :

command int getNeighbors (uint16_t *nList); // returns # neighbors
command int getNumNeighbors ();
command uint16_t getNextNeighbor (); // enables an interator on the neighbors in the NeighborStore

command getMetric16ForAll (NeighborValue16 *neighbors, uint8_t count, uint8_t type);
command getNeighborMetric16 (uint16_t neighborId, uint8_t type, uint16_t *pVal);
// similarly for 32 bit metrics

command uint8_t getNeighborBlob (uint16_t neighbor, uint8_t type, uint8_t *buffer, uint8_t *pLength);

// set commands are similar
command result_t setNeighborBlob (uint16_t neighbor, uint8_t type, uint8_t *buffer, uint8_t length);
// and so on...

command result_t removeNeighbor (uint16_t neighbor);

struct NeighborValue16
{
uint8_t neighborId;
uint16_t metric;
};

struct NeighborValue32
{
uint8_t neighborId;
uint32_t metric;
};

Module Structure

Core Modules

NeighborBeacon module :

Sends out beacons at a specified interval.

The format of these beacon packets is as below:

+-------------+--------------+-------------+------------+-----------+---------+-----------+---------+------
| TOS_Msg ... | sequence no. | incarnation | numRecords | neighbor1 | value 1 | neighbor2 | value 2 | . . .
+-------------+--------------+-------------+------------+-----------+---------+-----------+---------+------
    7 bytes       2 bytes       1 byte          1 byte      2 bytes   2 bytes    2 bytes    2 bytes

numNeighbors | (neighbor | value)+

This allows us to pack neighbor records in an unexpanded TOS_Msg packet.
For now, the packet format is kept really simple and functional... but later, if and when we have a need or have a bigger packet size, it can be expanded to include more metrics.
If all neighbor records do not fit in on beacon packet, they are rotated and included subsequent beacon packets.

Receives all beacons and incorporates received loss values into the NeighborStore (see below)
Calculates loss rates based on gaps in beacon sequence numbers...
Handles ageing of neighbors that haven't responded for a little while

Uses a standard AM "port" (type 63, according to msg_types.h) as any other application
Stores intermediate values used in loss calculation (bitmap, end sequence number, incarnation) in a struct that is stored as a "blob" in the NeighborStore.

NeighborStore module:

Stores various parameters corresponding to a neighbor
Supports three types of data:

16 bit metrics: stored as an array of a predefined size (which can be 0 if there are no 16 bit metrics)
32 bit metrics: stored as an array of a predefined size (which can be 0 if there are no 32 bit metrics)

blobs: stored as T-L-V tuples in a buffer of predefined size; the NeighborStore does not care how long a blob of a particular type is, as long as there is space to hold it. (the size of this buffer can be 0, thereby disabling blobs in favor of conserving memory)

+--------+----------+----------------+-----------+--------+----------+----------------+------------+
| type 1 | length 1 | values 1 . . . |   . . .   | type n | length n | values n . . . | end marker |
+--------+----------+----------------+-----------+--------+----------+----------------+------------+
  1 byte   1 byte     length 1 bytes               1 byte   1 byte     length n bytes    1 byte

Supports the aforementioned API

Application Design

In our implementation, the customer for the neighborlist functionality is TinyDiffusion, which assumes that all links that are seen are bidirectional and "good". Now, one design approach that would keep the TinyDiffusion code simple by providing it an abstraction of bidirectional and "good" links. To achieve this, the layered structure, as described below, involving the NeighborFilter module is provided.

TinyDiffusion uses NeighborFilter as its communication layer
The NeighborFilter module itself uses GenericComm as its communication layer
The NeighborFilter module passes up packes only from "good" neighbors and sends out packets only to "good" neighbors (this might not be strictly necessary, but if nothing comes out of sending a packet to a "bad" neighbor, why waste the energy in doing so?)
The NeighborFilter module can be configured with two thresholds lowWater and highWater to implement
hysterisis on the calculated "bidirectional loss rate" for that neighbor.

hysterisis is important to prevent high frequence flapping of link status beween "good" and "bad".

bidirectional_loss_rate = in_loss_rate + (1 - in_loss_rate) * out_loss_rate
implementation of hysterisis needs state regarding whether we are going "up" (BAD_LINK) or going "down" (GOOD_LINK) ...

This "good" or "bad" information can be stored in the NeighborStore module

Other modules that may benefit from the notion of "good" or "bad" can use it
But would perhaps not allow simulataneous existence of multiple per-application NeighborFilter modules

OR, It can be maintained internal to NeighborFilter module in a table.

Allows multiple NeighborFilter modules to operate simultaneously
But consumes more memory

For now, the former approach is implemented, but going to the latter (which seems to have its advantages) is a very small change, which should probably be done.

Future Work

Adding support for promiscuous mode listening to allow computation of loss rates more frequently: but this will need us to go and insert some code in between two layers of the Berkeley Communication Stack, which will need some thinking.