Scale the hurdles associated with mesh networks

Point-to-point mesh networks are usually small in size. Metcalfe's law states that the usefulness of a network grows at a square of the network's size. Yet mesh networking is targeted at small applications such as first responders and small-scale home automation.

People often assume that mesh is used only in small networks because of market forces. The real "dirty secret" of mesh networks is that they're fundamentally limited to small sizes.

Many routing protocols are based on flat routing, a new type of mesh network that overcomes this scaling problem. The common ones are ad-hoc on-demand distance vectoring, destination-sequenced distance vectoring and dynamic source routing.

The primary problem with flat routing is that the control bandwidth needed to maintain the network grows faster than the size of the network. This problem is a direct result of how datapaths are created and maintained.

In a flat routing network, every node in the network must play a part in establishing a connection between two nodes in the network.

In a small network, this flood is manageable. However, in a larger or more mobile network, this flood will rapidly overwhelm the available bandwidth.

A hierarchical approach to routing is taken by such protocols as zone-routing protocol (ZRP), landmark ad hoc routing (LANMAR) and hierarchical state routing (HSR). These protocols scale by breaking the network into smaller groups and then organizing these groups with a flat-routing protocol. ZRP and LANMAR use only two layers, while HSR uses as many hierarchy layers as needed.

This approach allows some scaling past conventional flat routing. However, it introduces some compromises. First, optimal routes between nodes that are not in the same subgroup are almost impossible. Second, the name of the node specifies its location in the hierarchy. If a node changes its location by moving from one group to another, it becomes instantly unreachable.

This problem is compounded if a node further up the hierarchy changes its location in the network. This can cause parts of the network to become unreachable until the hierarchy is reestablished. If these subgroups are not optimally chosen, low-power nodes may end up handling large amounts of traffic. Or worse, the network may revert to behaving like a simple flat-routing protocol. Implementation of this type of network is quite difficult and needs to be customized to suit the types of nodes and deployed configuration.

Routing algorithms
Ad hoc mesh networks have always been a suitable solution to network architecture problems because of their ability to self-organize and self-heal. This translates into reduced network administration time and improved network use. The promise of mesh networks has remained unfulfilled because of their failure to scale past a few hundred nodes. Some imaginative structures have raised this limit by several times, but at the cost of compromising the benefits of a true ad hoc mesh.

Simple network architectures, such as the tree structure used on the Internet, have the advantage of structural simplicity that can scale through the use of increasingly powerful hardware. The biggest single strength of the tree architecture is the inevitability of hierarchy. A trunk inherently goes to branches. The logic of a tree network is easy to understand and implement.

In contrast, the logic of a mesh network is neither obvious nor easy to understand, given its multiple paths and connections, fluid structure and dynamic activity. Failure to meaningfully scale mesh networks has been caused by an inability to see an inherent structure with a simple tree network.

This new routing algorithm offers a way to reveal a hierarchical structure in mesh networks, enabling significant scaling while retaining all the advantages of a mesh network. The algorithm can scale past tens of thousands of nodes, and supports mobile and low-capacity nodes. Every node in the network uses the same algorithm, with the only variation being the amount of memory and the type of interconnects available to a node. There are no special nodes, tweaks or complicated configuration required.

The routing algorithm comprises two sections. The first is a distance vector protocol similar to DSDV, except that it doesn't need periodic large updates. Because total control bandwidth is limited to 5-10 percent, route updates are prioritized by importance. Node Y will order a route update for node X by how close Y is to X, or how close Y is to a stream of data traveling to X.

To form the hierarchy, each node needs to determine its parent (the node that is above it in the hierarchy). The parent is chosen as the node most often selected as a "next best step" to other nodes. This simple process reveals the hierarchy of the network.

A tree-like structure is more effective because it has more connections or branches, reflecting the many connections made by nodes in a mesh network. This hierarchy will smoothly change and adjust to reflect the network topology because it is generated directly by the network topology. This differs from conventional hierarchical networks where the hierarchy is imposed on the network.

The revealed hierarchy will naturally form at the center of the network and near more powerful nodes with more bandwidth. It does this because the center of the network and high-bandwidth nodes provide the most direct route to the other nodes.

In this new approach, the name of the node is independent of its location in the network. Each node uses a mechanism called a high-speed propagation path (HSPP) to push a route to itself up the hierarchy.

If node X is trying to establish a connection to node Y, but doesn't have a "next best step" to node Y, it can send a request toward the top of the hierarchy, asking for a route to node Y. This request is called an HSPP. Because node Y has already pushed a route to itself up the hierarchy, node X is guaranteed to find a route to node Y if it looks up the hierarchy. This allows a first connection to be established between any two nodes in the network without the need for a global flood, as is the problem with a conventional flat-routing protocol.

Simulation results
Simulations run using this approach have produced promising results. Up-time exceeded 99.9 percent in a network with 844 nodes, each with a 50m wireless radius, all moving at 1m/s, randomly spread across a circle with a diameter of 665m. Control bandwidth was limited to about 250bps for each connection.

The following behaviors were noted during simulation testing:
1. Large networks—Networks can easily scale up to the maximum size supported by the simulation. Current computing resources limit this to around 1,000 nodes.
2. Integration of very large wired and wireless networks—Wired and wireless networks can operate together seamlessly. Using variable connection weights allows the network to prefer wired over wireless connections.
3. Complete self-healing and self-configuring—When nodes or connections are removed or changed, the network automatically restores broken connections and begins to re-converge.
4. Support of devices—Low-capacity nodes could exist in the same network as more powerful nodes. Low-capacity nodes could connect to other low-capacity nodes on opposite sides of the network, even though the low-capacity nodes had only a fraction of the memory required to know of the entire network.
5. Never a single point of failure—When the network is divided, the parts operate independently. If the parts reconnect, the network reestablishes itself so that nodes in separate parts can communicate.
6. Nearly instantaneous connection across large networks—Two new nodes attached to either side of a large network can almost instantly establish a connection to each other without a global flood.
7. Generation of an optimal path—Once a connection had been made, the network immediately converges to the optimal path. When the network topology changes, the connection is re-optimized.
8. High communication up-time—The network maintains a route between communicating nodes in unstable, low-bandwidth networks. Data communication between highly mobile nodes is continuous and consistent.
9. Low control bandwidth—Only an absolute minimum of control bandwidth is required. This permits scaling from battery-powered devices with 10kbit/s connections to wired devices with gigabit per second of bandwidth.

David Davies, Chief Operating Officer
Chris Davies, Chief Technical Officer
OrderOne Networks