Consideration of Bandwidth in Mesh Networks

Here, you will find a brief idea, how bandwidth and delay behave in a mesh network. If you have suggestions, find errors or if you simply want to discuss that topic, please feel free to contact me.

Model

Devices

The network consist of a set of devices, called Modes (mesh nodes), equipped with two wifi cards. One of them runs in AP mode (card 0), the other in ad-hoc mode (card 1). To almost avoid mutual disturbance between those cards, card 0 uses WiFi channel 1, the second card WiFi channel 11. All devices participate in the same network over card 1 (mesh network). Card 0, may be used by foreign nodes (Strangers) to access the mesh network.

Topology

The set of Modes is equally distributed in space. Every Mode has a set of neighbors, with which it can communicate directly over channel 11. Without loss of generality, every Mode has a non-empty set of neighbors. Hence, the mesh network forms a connected graph. By use of a routing protocol all Modes may communicate with each other (only payload...no MAC frames). This routing chooses the shortest path. Further, a Mode exist with an uplink (an internet connection or whatsoever). The only communication considered here, is the exchange of messages between Strangers and the uplink. Thus, messages traverse the topology in the following (bidirected) sequence:
Stranger<-->Mode 1<-->...<-->Mode k<-->uplink

Medium Access

Stranger <--> Mode

Communication between Stranger and Mode happens without disturbing the mesh network. All Strangers, under the same mode are served exclusively. So, only one Stranger can send a message at one point in time. All Strangers are treated equally. If only one Stranger is served, it has the average bandwidh .

Mode <--> Mode

Modes use the mesh network to exchange messages with each other. For this, they communicate over the same channel 11. Thus, Modes in communication range access the medium exclusively. To avoid collisions, DCF (Distributed Coordination Function) is used. A successful message exchange between Mode 1 and Mode 2 works as follows:

1. Mode 1 sends RTS (request to send)
2. Mode 2 sends CTS (clear to send)
3. Mode 1 sends sessage
4. Mode 2 sends ACK

All nodes, which overheard RTS or CTS stay silent until transmission is finished,so every node in communication range of Mode 1 or Mode 2. One Mode may send with an average bandwidth of . Modes are treated equally.

Bandwidth

Mode Bandwidth

1-Hop Bandwidth
As descriped above a Mode can send with a bandwidth of . Because a Mode needs to share equally the channel with its neighbors and the neighbors of the receiver (DCF), the Mode will not obtain this bandwidth. Let and be the number of neighbors of the sender and the receiver. Then, bandwidth of the sender is , where are the common neighbors of sender and receiver and is the overhead produced by the DCF sequence. Thus, , where is the maximum number of neighbors a Mode has. To cut a long story short, the bandwidth for one hop is shared between Modes in communication range.

2-Hop Bandwidth
For the further considerations is used as bandwidth single Modes have. So, bandwidth loss by competing access on the channel is already considered. If messages are transmitted over 2 hops, bandwidth is reduced again to the half. Because both hops are done over the same channel, the intermediate node between sender and receiver can either receive or send. One half of the bandwidth is consumed by the first hop and the other half is consumed by the second hop, ergo

3-Hop Bandwidth
The bandwidth of a three hop communication is . As descriped above, the first two hops exclude each other. But, the third hop exclude the other hops, too. The first intermediate Mode is blocked by the RTS of the second intermediate Mode, if the second intermediate Mode forwards a message to the destination. Thus, the source can not send a message to the first intermediate Mode. So only one link is able to transmit data at one point in time. So bandwidth is distributed between three links.

4-Hop Bandwidth and more
For more than 3 hops bandwidth remains . Consider the 4 hop scenario. If the third intermediate mode forwards messages to the destination, neither the source, nor the first intermediate mode are blocked. Otherwise, a shorter routing path would exist. Thus, the source may send the next data over the first hop at the same time, the destination is receiving another message. The situation remains the same for even more hops: links with a distance of three hops may forward messages at the same time and therefore . This means bandwidth only depends on the number of nodes in communication range to nodes on the routing path (Here: hidden in ).

Stranger Bandwidth

Strangers share their bandwidth with the nodes, which are connected to the same acces point. Thus, if strangers are connected to the access point, each of them has a bandwidth of , where , is the bandwidth of the access point. So, one stranger has at least a bandwidth of .

Conclusion

The length of a routing path affects bandwidth only for less than three hops. This is because several data packets may traverse the routing path at the same time at different positions. Nevertheless, delay increases lineary with an increasing number of hops. Bandwith of a single node depends only on the number of nodes on the routing path. Consider a mesh network with a high density of strangers on one side of the network. Further, these strangers share the same route to the uplink. A single stranger in a different area of the network, may obtain a routing path, which it can use alone. So, bandwidth is shared at the uplink between the single stranger on the one side and the rest of strangers at the other side. Thus, the single stranger will obtain almost one half of the total bandwidth of the uplink (it may only lose two thirds of the bandwidth if routing distance is long enough). Depending on the application szenario it might become reasonable to distribute bandwidth equally over the entire set of strangers. This may be achieved by a routing algorithm, which counts the number of nodes using the same routing path.

"Consideration of Bandwidth in Mesh Networks" is mentioned on: Bandwidth Problems in Mesh Networks