The Approach

TL/DR; Hardware and software modules are made to commingle in the same graph structure, using software defined network links. Packets can be written from anywhere to anywhere in the graph; we use source routing (aka path addressing) to name and route objects, and flowcontrol to avoid buffering / overrun issues. On top of this we write a software-to-network API in the form of data endpoints that can be written to, read from, and have onData handlers etc - and a configuration system akin to a distributed model view controller mixed with graph traversal algorithms.

1. Link Layers
2. The Structural Model: Source Routing Graphs
3. Packet Structures
4. The Operational Model: Dataflow between Data Endpoints
5. MVC: Discoverability and Configuration
6. About the OSI Model and OSAP’s Position
7. Open Problems / Implementation Challenges
   1. Types and Type Conversion
   2. Network Fairness
   3. Timing !
   4. TypeScript
   5. Python
   6. Link Layers
8. Footnotes

Link Layers

How do we actually establish network links from thing-to-thing?

It was really important to me that we should be able to include almost any type of device on an OSAP graph and one of the best ways to do this is to bring the particularities of link layers outside of the system: OSAP sees virtual ports and virtual busses which are point-to-point, and one-to-many connections respectively… We abstract away the particularities of each particular bus or link, and connect each data layer to OSAP using software interfaces.

Data link layers are incorporated into OSAP using abstract software interfaces; virtual ports and virtual busses. This means that we can incorporate any existing (or not-yet existing) kind of data link into the system, so long as we can write & read data bytes to and from it.

I’ve written some helper classes that allow us to quickly instantiate a virtual port that uses an Arduino Serial data layer, or a virtual bus using Arduino’s built-in I2C Wire library, these instantiate like so:

// instantiate a new vport, using Arduino's Serial1 object to transmit & recieve 
VPort_ArduinoSerial vpSer1(&osap, "arduinoSer1", &Serial1, 115200);
// likewise, vbus, using I2C via Wire
VBus_ArduinoWire vbWire(&osap, "arduinoWire", &Wire, 0x12);

But of course there’s an API to write whatever new link layer driver (UART, SPI, I2C, WebSockets, Bluetooth, LoRA, CANBus, etc) you’d like, OSAP just needs a few callbacks:

// transmit one, delineated packet:
void SPILink_send(uint8_t* data, size_t len);

// check: are we clear to send? i.e. is tx buffer empty
boolean SPILink_clearToSend(void);

// if a new packet has arrived, place it in *data, returning size_t length 
size_t SPILink_read(uint8_t* data);

// ports also get a loop, for runtimes 
void SPILink_loop(void);

// then we instantiate via passalong callbacks;
vport_t vpSPILink(&osap, "customSPILink", SPILink_loop, SPILink_send, SPILink_read, SPILink_clearToSend);

In javascript this is very similar: we attach a series of callbacks to a base vport object.

This of course doesn’t delete the complexity of building competent link layers¹, but it does mean that we can include whichever of them that we would like. There is also enough established practice in the generation and use of link layers in OSHW that I doubt this will be a problem; for starters, just about every single dev board has a built-in USB Serial (and UART, and I2C) links available, and many are coming with even more advanced links out of the box, like WiFi and Bluetooth, even Ethernet.

This approach does mean that link layer configurations, like which COM port to open, or which I2C address to initialize with, or which IP to point a WebSocket at, are also outside of OSAP. This might seem beguiling at first: those kinds of things are the whole issue with big messy networks! I’ll come back to this point later on when I talk about the MVC / configuration layer.

The Structural Model: Source Routing Graphs

How do we name and address elements in this big ol’ graph?

The whole premise here is that we collapse software and hardware modularity into the same graph. Let’s start with the single-device instance.

I call any memory-bound computing object a context - so a microcontroller is almost always one context (until we get the multi-core micros), a browser window is one context, a python script is one (but could launch more, that are children), etc. We’re really concerned about memory bounds because within one we run virtual dataflow, and between them we run actual dataflow. It’s also impossible to have circular structures within one memory bound - of course we can *ptr-> ourselves these structures, but they don’t have any physical reality (if we stick to a memory-as-an-infinite-tape model), but networks can make genuine loops.

Within any given context, we instantiate software modules in these tree structures:

Within memory-bound compute contexts, we have a tree-like graph of vertices. This is what graph nerds call DAGs: Directed Acyclic (non-looping) Graphs. Given this tree, we can describe routes between elements: "go to your 0th sibling, then to its 2nd child" etc...

Each element here is a vertex in the graph, and we can describe routes between graphs using a source routing (aka path addressing)² scheme, for example a the route above starts at the 3rd child of the root node, and then traverses the route sibling(1), child(0), child(1) to arrive at its destination.

You might be guessing where this is going: some of those vertices are virtual ports and virtual busses - and so we can hook two contexts up to one another by including two new route instructions: portForward() and busForward(<rxAddr>).

Link layers (virtual ports and virtual busses) are software vertices just like anything else in the system, so once we route a packet to one of these objects, we can add a packet instruction that requests for the packet to be forwarded along that link. Now our network and software graphs are collapsed into the same routing system. Here, the route represented by the dashed line is something like "go to your 1st sibling, then its 0th child, then port forward, then go to the 2nd sibling."

Packet Structures

How do we describe (read and write) packets that traverse the graph?

Source routing under the scheme above basically deletes the need for a naming system (and along with it, any need for centralized organization), and radically simplifies the routing layer. So, we choose it for OSAP. It’s also really simple to write (and interpret) packets in source routed systems: this is awesome because it keeps OSAP codes small (and stateless in the routing layer!) and also means it can be wicked quick even in low power embedded systems. This layer is likely also simple enough to be implemented on FPGAs without much trifle, meaning we could build really quick and simple routing devices.

Since everything is a network, any data passing happens in packetized transmissions. Source routing means that we write routes right into the packet; one way to describe this is to say that packet headers are simply sequences of routing instructions³ - i.e. the image above diagrams a route which we could describe in terms of these instructions:

start(), sibling(1), child(0), portForward(), sibling(0), end()

At each step, we need to know which instruction in the packet should be executed next. So we keep a pointer in the packet structure. At the packet origin, the pointer is the 1st byte, and by the time the packet is at the destination, the pointer is at the end of the packet header.

So we have a serialization for these instructions, with instructions above and serializations below:

And then additionally serializations for the pointer and destination keys;

So serialization of our example packet is written out below. Most packet instructions have arguments, i.e. which sibling or which bus member to forward to. These are all uint16_t so we have two bytes to serialize per argument.⁴

// these instructions:
start() | sibling(1) | child(0) | portForward() | sibling(0) | end()
// become these bytes. I'm including the "|" delineation on instructions for ease-of-reading 
88, | 15, 1, 0, | 14, 0, 0, | 11, | 15, 0, 0, | 99 

Then every time an instruction is executed, we advance the pointer,

// at the origin  
88, | 15, 1, 0, | 14, 0, 0, | 11, | 15, 0, 0, | 99 
// sibling 3 -> sibling pass 1 
15, 3, 0, | 88, | 14, 0, 0, | 11, | 15, 0, 0, | 99 
// sibling 1 -> child 0 pass 
15, 3, 0, | 16, 0, 0, | 88, | 11, | 15, 0, 0, | 99 
// child 0 vport forward
15, 3, 0, | 16, 0, 0, | 11, | 88, | 15, 0, 0, | 99 
// sibling 1 -> child 0 pass 
15, 3, 0, | 16, 0, 0, | 11, | 15, 1, 0, | 88, | 99 

You’ll notice that when the pointer advances we stuff the return instruction in behind it. This is done in a manner that maintains length (speedy!) and (more importantly) means that at any point (and often at the destination) we can reverse a packet in order to send it back to the source.

// after arriving at the destination 
15, 3, 0, | 16, 0, 0, | 11, | 15, 1, 0, | 88, | 99 
// we can reverse this, to bounce back to the source 
88, | 15, 1, 0, | 11, | 16, 0, 0, | 15, 3, 0, | 99 

Many will point out that we still often want unique identifiers - i.e. to find particular things in a messy network whose topology we’re not sure about. This is for sure the case, especially i.e. where we are likely to have big grids of devices on busses with dynamically allocated addresses, or lots of USB Serial devices that have a propensity for showing up with a different COMx number every time we reset them.

We also have a routing system that doesn’t yet explain anything about how we actually use it - you might be thinking ‘OK, this is neat, but where do I write these routes? do I have to know my network topology ahead of time?’ - totally great questions, and I will answer them later on, in the MVC / configuration layer section.

The Operational Model: Dataflow between Data Endpoints

How do “programs” or “systems” actually… work, to do stuff?

So far we can describe routes between vertices and ferry data between them. This (core layer) could be the basis for a number of different operational architectures - i.e. methods with which to describe programs that “run” as the gestalt of numerous nodes in a graph.

Many networked systems use what I would call “programmatic” description styles - i.e. RPC⁵ and REST APIs⁶, that make sense in the same way that a page of code does: we can imagine, step by step, how the code executes. In my opinion, these are convenient abstractions if we are computer programmers who are used to understanding line-by-line code execution, but are not great when we are thinking about networked systems where everything is happening all at once. For that, we need a dataflow-type understanding of programming.

This is from dataflow pioneer Jack Dennis' Dataflow Supercomputers (1980) - the notion is sort of self explanatory, but implimentations can get hairy.

Besides the OG Jack Dennis (above) who was mostly concerned with compute performance and scaling, dataflow appears also as a useful compute model for exposing programmatic elements of creative softwares to end users; i.e. in PureData, Rhino Grasshopper, MaxMSP, etc.

Endpoints are the software object I have written to interface between softwares and the graph. Endpoints can be written to (publishing new data) and read from; they also store the most-recently-written data, and contain a list of routes which they publish to.

In the video below, I am using one endpoint ep_button to publish the state of the board’s button. I then write a “program” using the mvc by connecting that output to the ep_led - which reads the state and sets it to a light.

// a handler, for when the LED endpoint recieves new data... 
EP_ONDATA_RESPONSES onLEDData(uint8_t* data, uint16_t len){
  if(data[0]){
    digitalWrite(OUTPUT_LED_PIN, HIGH);
  } else {
    digitalWrite(OUTPUT_LED_PIN, LOW);
  }
  return EP_ONDATA_ACCEPT;
}

// instantiating the endpoint adds it to the context's internal graph 
Endpoint ep_led(&osap, "led", onLEDData);

// we instantate a button, 
Endpoint ep_button(&osap, "button");
// and store these awkward data types 
uint8_t btn_down[1] = {1};
uint8_t btn_up[1] = {0};

// then in a recurring loop function, check states and publish them:
uint32_t lastTx = 0;
void loop() {
  osap.loop();
  if(lastTx + 50 < millis()){
    lastTx = millis();
    // write new state, 
    if(!digitalRead(BTN_INPUT_PIN)){
      ep_button.write(btn_down, 1);
    } else {
      ep_button.write(btn_up, 1);
    }
  }
}

This means that endpoints are flexible: they can be inputs or outputs, or simply stateful objects (settings, configs). Right now, they are untyped, but they will become typed later on.

MVC: Discoverability and Configuration

How do we look at systems? debug them? add / change them?

The straightforward way to configure a graph is to add routes to endpoints manually, there’s an API for this:

ep_button.addRoute((new EndpointRoute(EP_ROUTE_ACKLESS))->bfwd(1, ADDRESS_FRIEND)->sib(3));

You might be thinking: “how am I supposed to know what the right route is, to reach a given destination? isn’t this why we normally use global address spaces in networks, so that I can simply say something like ‘send this message to Bob’ rather than ‘send this message to my 3rd neighbour in the neighbourhood one block to the south’” and you’d be totally right. The reason we use destination routing so often is because we can write fixed addresses for known resources and simply write that address into a packet; the routers take care of the rest. However, destination routing also requires that we build pretty fancy protocol (TCP/IP is rarely found on a microcontroller for reasons) and then spend time handing out unique addresses, probably dynamically, etc. All of that requires lots of state in the graph, more compute power in the graph, etc etc. We want tiny simple stuff, and so we are offloading the “smarts” of picking routes from OSAP itself (well, from the core layer) into this MVC thing.

In short, the MVC is the layer that makes this kind of graph reconstruction and reconfiguration possible:

I should probably come up with a name for this system… in the source, you’ll see that it’s called netRunner.js - in any case this is just about what it does; runs around the graph, poking things to see whether they exist or not. It then returns its caller with a data object (in JS) that is structured in the same manner as the graph, i.e. nodes have .parent links, .child[<indice>] links etc; everything also has a String .name and virtual ports have .reciprocal partners.

This layer is all very much ‘in-the-works’ but it does run the UI that you’ve probably seen in the demos. Is anyone still reading down here? I need more diagrams.

About the OSI Model and OSAP’s Position

Is this a networking layer? Which one?

The OSI model is a useful abstraction until it collapses, which seems to happen a lot in embedded systems; i.e. CANBus actually specifies aspects of all 7 layers, as do some parts of the USB protocol. Some of this is semantic, so I might be getting myself in trouble with that statement.

The OSI model also more or less supposes that we are building flexible, changing applications on top of static, often-homogenous networks. Networks are, after all, normally infrastructural - not things we build quickly. But this seems to be changing as we build more and more IoT systems and things with smarts “at the edges” - suddenly it becomes important to change networks and the applications that run on top of them rapidly.

With firmware modules, it is actually more difficult to change the “application code” (the firmware) than it is to change the networks they are connected to (wiring). I hadn’t been thinking of this at the start, but OSAP is some kind of upside-down OSI stack: it asks module developers to build “static” applications (endpoints doing particular things) and then introduces a method to rapidly reconfigure networks.

So, no, OSAP is not “really” a networking layer, it’s an application (Layer 7) that does networking things. It’s a little confused, and doesn’t fit neatly in the old boxes.

Open Problems / Implementation Challenges

There’s handfuls of neat problems in here. I am working on them ~ sort of in this order, and fitfully. Get in touch if you want to join in.

Types and Type Conversion

Endpoints are not typed at the moment, we .write(<buffer>, len) and recieve similar. Instead we would want to do something like:

Endpoint<uint32_t> my_typed_endpoint(&osap, <name>, <onData>);

This is probably less challenging in i.e. JS than in embedded code, but also probably more important to implement in embedded. We have the challenge there also of recognizing which type is which, and then combining types without replicating too much code (and sucking RAM), i.e.

typedef struct motion_t {
  float pos[AXIS_COUNT];
  float rate;
  uint8_t tk;
} motion_t;

Endpoint<motion_t> my_struct_endpoint(&osap, <name>, <onData>);

Then we would also want to have in-line operations, like pulling just the x axis out of that motion target, etc… and in-line conversions, so that we can still make i.e. modules written with really rigorous types compatible with systems (like JS) that natively produce all float64_ts etc.

Network Fairness

Network nerds are often concerned with “fairness” - and for good reason. This refers to the ability of a networking system to intelligently dole out resource (bandwidth) to different users in a manner that doesn’t favour any participant in particular.

Operation of the internal dataflow pipelines in OSAP contexts needs to do this also, and they’re often running on flow control limits (there’s not a lot of buffering space), so getting a little rigorous with fairness would be cool, along with really analyzing how the main loops run, and looking for performance improvements.

Timing !

I started this adventure for machine controllers, but OSAP is still asynchronous; I manually provision network resource to make sure my control loops will run in time, and I built the ucbus link layer to have a deterministic bus for these reasons. So, timing remains an open problem.

TypeScript

A rewrite of osapjs -> osapts seems like it would be worthwhile.

Python

Likewise, there’s heaps of scientific computing libraries in Python that require an osappy package.

Link Layers

CANBus, LoRA, BLE, SPI, etc… there’s lots of awesome link layers to include.

Footnotes