Network programming language tutorial

Spanning trees

In this example we take a look at the construction of a spanning tree. We'll start out using the built-in communication primitives and gradually replace them by low level constructs as we go. Our end goal is to be able to route through our spanning tree using only a low level primitive send function Send(target: int, message: MContext).

The figure above describes the tree construction process. A gateway node (node 3) kickstarts the process by broadcasting a tree contruction message into the environment (figure B). All nodes which receive this packet (figure C) select the sender as their parent and transmit a tree construction message of their own (figure D, E). This process repeats itself until the entire network is covered by a single spanning tree (Figure F).

The tree construction program is implemented with a single OSAS service. An event generator will initiate the tree construction (such that subscribing to a node constructs the tree) and an event handler will process the tree construction message. The program fragment below defines the tree construction service.

service TreeNode()
  define
    parent := 0
    myphase := 0

  forward SetParent(node, phase)

  on event construct_tree when True do
    parent := NodeID();
    SendMessage([Network|1], SetParent, NodeID(), myphase);
    myphase := (myphase + 1) % 255;

  action SetParent(node, phase) do
    # new phase check, with wrap around (0 <= phase < 255)
    if (myphase < phase && phase < myphase + 128)
       || (phase < myphase - 128)
    then
      parent := node;
      myphase := phase;
      SendMessage([Network|1], SetParent, NodeID(), phase)
    fi

subscription TreeConstruction
to TreeNode()
with (period=10s, deadline=1m, send="Normal", exec="Normal")

for [Network|*]
  install TreeNode

for [Network|*|NodeType()=="Gateway"]
  install TreeConstruction on [Network|*|NodeType()=="Gateway"]
.

The above program only constructs a spanning tree, it does not yet provide any mechanism for utilizing the tree. Two new elements are required:

  • a function for transmission of a message payload (the routing API)
  • a handler for routing this payload to the sink (and processing the payload at the sink node).

In order to communicate between nodes, we can employ the low-level communication primitive Send(target: int, message: mcontext). The send primitive unicasts a packet to a neighbour node (target 255 is a special case which broadcasts to all neighbours). When using the send primitive, no OSAS headers are added. We add these manually to the message (66 = protocol id, 0 = QoS, 0 = Deadline, 0 = Hopcount).

The concatenation operator ++ copies the left operand into the right operand. The NotifySink function below takes a message context (i.e. a packet with some metadata) and prefixes it with (66, 0, 0, 0, ToSink). Packets grow to the left, so prefixing additional headers is cheap. Appending data to the back of a message involves the more costly operation of copying all data to the front to make room at the back.

Finally a new action ToSink is introduced. Whenever a packet is received by a non root node it is forwarded to the parent node. The root node will execute whatever payload was embedded into the ToSink handler.

service TreeNode()
  define
    parent := 0
    myphase := 0

  forward SetParent(node, phase)
  forward ToSink()

  function NotifySink(message) do
    Send(parent, Message(66,0,0,0, ToSink) ++ message)

  on event construct_tree when True do
    parent := NodeID();
    SendMessage([Network|1], SetParent, NodeID(), myphase);
    myphase := (myphase + 1) % 255;

  action SetParent(node, phase) do
    # new phase check, with wrap around (0 <= phase < 255)
    if (myphase < phase && phase < myphase + 128)
       || (phase < myphase - 128)
    then
      parent := node;
      myphase := phase;
      SendMessage([Network|1], SetParent, NodeID(), phase)
    fi

  action ToSink() do
    if parent != NodeID() # not the root node
      Send(parent, self.message)
    else                  # root node
      InvokeHandler(self.message, self.handler_start+1, self.handler_end)
    fi

subscription TreeConstruction
to TreeNode()
with (period=10s, deadline=1m, send="Normal", exec="Normal")

for [Network|*]
  install TreeNode

for [Network|*|NodeType()=="Gateway"]
  install TreeConstruction on [Network|*|NodeType()=="Gateway"]
.

To report any value to the sink one can now invoke the NotifySink function with a message context as parameter. For example:

NotifySink(Message(print, NodeID(), Temp()))

The implementation refers to self.message, self.handler_start and self.handler_end. Any fields starting with self. reference the current context (i.e. a subscription context in event generators and a message context in event handlers). The following table describes the available fields:

context field description
mcontext message content of the packet (an array)
message_length length of the packet array
signal_strength RSSI value of received message
handler_start index in the packet of the ID of currently executing handler
handler_end packet index of the first value which is not an argument to the currently executing handler
scontext subvars an array containing all subscription variables
varcount number of subscription variables
period period of currently firing subscription
subscriber node id of subscriber
QoS Quality of Service parameters, unused

So for any executing handler we have the following properties

  • self.message[self.handler_start] is the ID of the handler
  • self.message[self.handler_start+1] is the first argument
  • self.message[self.handler_start+1:self.handler_end] are all parameters to this handler (excl. the upper bound).

If a handler declares arguments such as node and phase in SetParent then these are bound from left to right. E.g. within SetParent, node is an alias for self.message[self.handler_start+1] and phase is an alias for self.message[self.handler_start+2]. Note that handlers can have unbound parameters (i.e. ones which do not have a name). Also note that the bytecode generated to refer to an alias is more efficient than the bytecode to index the message.

ToSink uses these to make a call to InvokeHandler(message: mcontext, start: int, end: int) which processes the part message[start:end] as a handler.

To following figure describes how the messages passed to ToSink are processed

Initially the first message is taken from the Message Queue. The dispatcher routine skips over the headers and processes the payload handler (ToSink). At some point ToSink makes a call to InvokeHandler which hands the message back to the dispatcher (with new slice indexes). Again the dispatcher performs a lookup of the handler (here, print) and executes that handler. Finally the print handler will print the NodeID and Temperature value within the message.
tutorial-example3