Thursday, September 20, 2018

Making Tree Topologies Dynamic

As I noted in my previous post, after years of developing higher-performance wireless networking products my focus is shifting in two ways. First, I am orienting my efforts toward working with OEMs, System Developers, System Integrators, and major agencies to integrate my software into their "things".

Second, I am refining my algorithms based on lessons from nature conferred by my friend and marine biologist (by training) Byron Henderson, which we began to explore in our book Rethinking the Internet of Things.

Trees and network switches

One of these lessons from nature involves trees. In 2002, my robotics and control system experience suggested that a tree-like branching structure would be the way to create a deterministic network architecture across a physical mesh of inter-working wireless nodes. Essentially, this is creating a switch-like topology from a physical mesh. But I also wanted networks to converge -- and more importantly, re-converge -- quickly and with more intention than conventional Spanning Tree Protocols. This required placing more independent intelligence in each node, as I’ll describe later.



With the recent emergence of new networking requirements, such as drone swarms and other mobile applications, I have been reflecting on trees in nature- again.  Tree-like branching structures have evolved multiple times and in varied lineages -- organisms as diverse as giant oaks and the marine Gorgonian soft coral colonial animals (Order Alcyonacea).


Trees are a mathematically efficient way to organize living tissue (and other things) to maximize spread and coverage from a fixed connection (such as a root).

What if the branches could move?

But a tree-like structure has limitations in adapting to rapid and unpredictable changes in environments. We’ve all seen trees and shrubs growing at odd angles to try to reach the sunlight when another tree or building shades the plant. But a tree can only adapt to environmental changes to a limited degree, as the branching structure is already set. It’s not possible for the organism to disconnect some branches and reconnect them elsewhere to optimize for the current situation.

Returning to networking, some of my recent algorithm work has aimed to enhance the efficiency and “tune-ability” of tree topologies with even more rapid re-convergence as nodes move and/or the environment changes. I’ve wanted to minimize latency and (especially) jitter to support real-time Publish/Subscribe applications in my algorithms.

So I built in the capacity to bias and tune the network topology to optimize for a flexible variety of factors, including hop count, link cost, bandwidth, and end-to-end delay. But the fundamental architectural decision that I made early-on that is enabling these refinements is distributing the networking intelligence to every node. In essence, I freed up every “branch” to make its own decision on how, where, and when to connect -- or reconnect.

This is accomplished by having each node maintain an awareness of its adjacent nodes and potential connections (usually radios and channels). The tuning and biasing takes place on top of this foundation, which nicely separates the two functions I wish to optimize: rapid convergence for immediate adaptation; and sophisticated capacity for performance optimization.

If the applications you are working on demand real-time performance in complex networking environments, I look forward to discussing how we might work together -- perhaps in the shade of a tree. 😁

Please connect via LinkedIn or my website -- and thanks for your time.