Performance Analysis of Three Competing Mesh Architectures

 

This analysis has been partially funded by a United States Air Force (USAF) contract. The contract relates to specialized deployments of Structured MeshTM in battlefield situations.

  
Introduction
 

Figure 1: Three Mesh Architectures: Ad hoc Mesh, 1-Radio Meshed Backhaul, 3-Radio Structured Mesh 

MeshDynamics has been talking about multiple radio mesh since 2002, but there has been confusion about what “multiple-radio” means, and how the MeshDynamics approach is different from others.
 
A companion document clarifies differences between Structured Mesh and two other mesh approaches: the 1-Radio Ad Hoc and the 1 Radio Meshed Backhaul. The document focuses is on the backhaul path back to the Ethernet link through the mesh. That’s where the differences lie. That is what makes Structured Mesh the most efficient means of providing coverage in dense urban environments on a metro-wide scale.
 
In another document, 3-radio Performance claims are experimentally verified at a US Air Force Lab..  
 
This document, analyses the relative performance of 3 competing mesh architectures. It shows why the 3 radio system provides far better bandwidth distribution than other competing architectures. It also explains why with merely 5 simultaneous clients per mesh node, both the 1-Radio Ad hoc and the 1+1 Ad hoc mesh architectures cannot provide usable bandwidth beyond 2 hops - and the implications of these limitations.
  

The 1-Radio Effect

Modern mesh network requirements have evolved. Today, Internet connectivity is needed rather than local peer-to-peer connectivity. Data sources are primarily resident on the Internet, not on a peer. Also, to cover large areas cost effectively, nodes may be further away - requiring more hops to the Ethernet feed.
 
Therein lies inherent limitations of conventional mesh networks. In a conventional mesh network there is one radio for all nodes to talk to each other – but they must all be “talking” on the same channel. Also for data to be relayed, (hopping)  it must be repeated - a node listens and retransmits.
 

Figure 2: Bandwidth degrades with each Hop in 1-Radio Multihop Backhauls

One serious disadvantage of having only one radio in the mesh is that it can’t send and receive at the same time. It also can’t send when another node within range is talking, but let’s leave this latter effect out since it just complicates the analysis further.
 
Simply put, if a node cannot send and receive at the same time, it loses ˝ of it’s bandwidth as it attempts to relay packets up and down the backhaul path. A loss of ˝ with each hop implies that after 4 hops, you would be left with (˝*˝*˝*˝) = 1/16 of the bandwidth available at the Ethernet link. This is a 1/(2^N) relationship where this equation defines the fraction of the bandwidth that is available after N hops.
 

The 1/N vs. the 1/2^N Controversy

 
Figure 3: Competing mesh products suffer from Bandwidth loss with each hop

There has been much argument on this. Competing mesh providers concede that their products do suffer from bandwidth degradation with each hop. However, some claim that if the hops is large, there can be simultaneous conversations along a path through the mesh and that degradation is closer to 1/N.
 
The controversy boils down to defining typical mesh topologies. The amount of degradation depends on the mesh topology being examined.
 
If a path through a 1-Radio mesh backhaul is linear – a “string of pearls” – and spaced so only neighboring nodes in the string can hear each other, then if the string is long, bandwidth loss could approach 1/N. 
 

But with service coverage as shown (left) for the “string of pearls” topology, the potential for carrying on simultaneous conversations in different parts of the chain mandates that the chain be long.

Therein lies the contradiction. A look at the NMS screen shots for mesh vendors shows mesh nodes typically have 3-4 neighbors around them in the mesh, and sometimes as many as 6. This is hardly a string of pearls topology -  interference from neighboring nodes makes losses far closer to 1/2ⁿ.
 
Note: Independent studies agree with this analysis. A study sponsored by the USAF and conducted by a independent research institution indicates degradation of 1/(1.68)ⁿ for typical mesh topologies.

The 1/N argument also overlooks the fact that communications through a modern mesh are focused on a path to the Internet - involving multiple hops though a grid like topology. With even moderate client traffic at each hop, the degradation in single radio mesh backhaul - from bandwidth sharing - causes so much deterioration that the system cannot support enough hops to validate the much defended 1/N number.
 
For the sake of this performance analysis, we shall use the 1/N number to avoid needless discussion. The numbers still strongly favor the 3-Radio Structured Mesh^TM architecture over other competing approaches.
 

Involuntary Bandwidth Sharing
 

Figure 4: Effects of Compounded Contention in 1-Radio Ad Hoc Mesh

Wireless is a shared medium.  People communicating on the same channel and within hearing range of each other will be contending for available bandwidth - which is being shared based on collision avoidance rules for wireless (e.g. CSMA/CA). Bandwidth reduction - caused from bandwidth sharing - limits backhaul traffic at each hop and is also compounded at each hop.
 
If there are C simultaneous clients per mesh node, packets coming from the client at the mesh node farthest from the backhaul have a 1/C bandwidth share as they attempt to reach the closest mesh node
  
Then, aggregated traffic from this node gets a 1/C share again as it attempts to reach the next mesh node along the way towards the Internet backhaul. At that point, the bandwidth share for the original packet is 1/C² . This compounding process continues (1/C^2.. 1/C^{3 ..} 1/C⁴) until the Ethernet links is reached.

Thus, in the case of single 1-Radio mesh with just 3 clients ( the mesh node is effectively another "client") the bandwidth degradation follows the 1/3 .. 1/9 .. 1/27 effect. (see above).

In other words, clients get a piece, of a piece, etc of the total available bandwidth.

When analyzing the "1+1" mesh  the effect is more complicated. The “1+1” mesh has a separate service radio in addition to the backhaul radio that participates in the ad hoc mesh. Clients attaching to the service radio contend with each to share service radio bandwidth. Data enters the service radio and is transferred over the backhaul mesh through a bridge.

When client packets transfer to the backhaul radio, they are subject to contention (involuntary bandwidth sharing) with neighboring mesh radios. Remember: all backhaul mesh nodes are on the same channel.
 

Figure 5: Urban Grid mesh topology and involuntary sharing with 1+1 Mesh

 
How many neighboring 1+1 mesh nodes are in contention, depends on the mesh topology. In the Urban Grid (above) communications must traverse the “Urban Canyons” - tall buildings between blocks. If the nodes are placed at road intersections then nodes typically are in range at least 3 nodes At peak times- when all mesh nodes are trying to move packets at the same time - each 1+1 mesh backhaul radio will receive 1/4 of available bandwidth - there are a total of 4 nodes involuntarily sharing the radio medium.
 
Involuntary bandwidth sharing for the 1+1 mesh in an Urban Grid is 1/4 .. 1/16 .. 1/64 etc.
 

Bandwidth Comparison of  3 Competing Mesh Network Architectures

We examined bandwidth performance for 3 competing mesh architectures:
 
1.  1-radio ad hoc mesh with a single 802.11b radio
2.  1-Radio Mesh Backhaul: 2 radios, Backhaul 802.11a in an ad hoc mesh, Service 802.11b/g.
3.  3-radio Structured Mesh with 802.11b/g service radio and two 802.11a backhaul radios.

 
Figure 6: Bandwidth Available at each hop for 3 competing mesh architectures

A bandwidth analysis of mesh architectures compares the fraction of root node bandwidth available to a client (N) hops away where there are on average (C) clients per node demanding access simultaneously.

Assumptions underlying this analysis are:

For this analysis we ignore the effect of bandwidth sharing with some neighboring mesh nodes for the simple 1-radio architecture (2-dimensional view) since it just makes already bad numbers look worse.

In the case of the 1+1 mesh, we assume 4 neighboring nodes as typical for an urban grid. Thus, in an urban grid topology with high client density, the 1+1 mesh will propagate about 1/4 of the bandwidth available at each hop. The bandwidth degradation would then follow 1/4 .. 1/16 .. 1/64 etc.

We use the 1/N per hop bandwidth degradation for the 1 radio effect  as opposed to the more realistic 1/2^N number. With even 1/N degradation, the results overwhelmingly favor the 3-Radio Structured Mesh.
 

Performance Comparison

  

 
Figure 7: Comparison Table for 3 competing mesh Architectures

 
The comparison table above reveals the limitations of an ad hoc mesh backhaul for wide area coverage.

Maximum bandwidth (BW) that can be supported for the root backhaul is specified for each scenario, thus the results are normalized according to the maximum backhaul capability. Shown in the upper half of the table are the bandwidths available to clients after N hops given C simultaneous clients per node. For the (1+1) scenarios with separate backhaul radios, it is assumed that there are 4 contending neighbors per node in the mesh backhaul. (Diagrams on in competitor's literature, show as many as 6-7 neighbors).

Even with these concessions, the (1+1) mesh solution with 802.11a (54 Mb) backhaul provides 42 Kbps of service to a client 4 hops away from the root. This is not even equivalent to dialup levels. It is barely usable for VoIP - where 64Kbps is desirable. 1-radio backhaul configuration cannot scale beyond 2-3 hops.

The lower half of the table shows the ratio between bandwidth available with the 3-radio Structured Mesh when compared with that from other systems for an equivalent number of hops and clients per hop.
 
Note that for any sizeable degree of client loading, conventional mesh is not usable beyond 2 or 3 hops, and must be "re-powered" often by connecting to a high-speed backhaul link - which increases both capital and running costs of the deployment. On a metro wide scale, this is significant. WISPs and municipalities deploying 1-Radio Mesh network variants are learning this lesson - the hard way.
 
Based on bandwidth analysis alone, a multi-radio, multi-channel backhaul is essential for a mesh solution to be useful over wide areas and support a realistic number of simultaneous users. MeshDynamics has the multi-radio, multi-channel backhaul technology required.
 
Few large deployments have been done with ad hoc mesh and most that exist are only used for police and fire departments – normally a low traffic situation. Ad hoc mesh backhauls can work acceptably with light traffic, but bandwidth falls off a cliff when the numbers of simultaneous users and resultant traffic increase.

As shown above, with merely 5 simultaneous clients per mesh node, both the 1-Radio Ad hoc and the 1+1 Ad hoc mesh cannot provide usable bandwidth beyond 2 hops in cases of even moderate loading. WISPs and municipalities who have deployed 1-Radio Mesh network variants will learn this - the hard way.
 
Based on bandwidth analysis alone, a multi-radio, multi-channel backhaul is essential for a mesh solution to be useful over wide areas and support a realistic number of simultaneous users. MeshDynamics has the multi-radio, multi-channel backhaul technology required.
 

Competing mesh technologies lack the ability to distribute bandwidth over wide areas requiring multiple hops of the mesh backhaul. As a result, they need to be "re-charged" every few hops - through an Ethernet link. Costs of additional Ethernet links must be added to compare the overall deployment cost, especially for large Hotspots and city-wide HotZones requiring many nodes (see grids below).

In dense areas with many simultaneous accessing users per node, conventional mesh cannot deliver better than "dialup" bandwidth beyond 3 hops. A city wide wireless network therefore requires additional Ethernet links if each mesh is limited to 2-3 hops. 

Every Point to Point Ethernet link to the mesh adds increased capital equipment expenses. Also, each Ethernet feed service adds to the running cost of the network. For wide area, city wide WiFi deployments,  Structured Mesh is by far the most cost effective means of providing VOIP and data coverage.

More Mesh Network Information:

• Various Approaches of Mesh Networking
• Hybrid Mesh Networks
• Wireless ISP Mesh Networks
• Technical Overview of Mesh Networks
• Advantages of Structured Mesh Network Modules
• Mesh Network Management Platform
• Benefits of a Mesh Control Layer
• Performance Analysis of Mesh Networks
• Test Results of Mesh Networks Real World Testing
• Deploying Wi-Fi Cellular Networks for Voice over IP Services