Intro

This is a brief summary of "Routing Without Routes: The Backpressure Collection Protocol".

Background

Traditional routing protocols, such as link state or distance vector routing protocols work by explicitly calculating a route in the network from one node to another.

While these protocols work very well (as proven by the fact that they are deeply established in today's networks), they are not the "ideal" protocols for all network topologies. Specifically, they do not necessarily provide a globally optimum distribution of congestion in many-to-one transmission topologies, often leading to possible bottlenecks.

BCP is an implementation of Backpressure Routing - a completely different routing mechanism - for wireless sensor networks. BCP implements backpressure routing on wireless sensors to try to achieve the globally optimum distribution of traffic across the sensor network.

The core concept behind Backpressure routing is simple. Consider a network where all the nodes (sources) are trying to send data to one of the nodes (a sink). This is a typical data collection application. Assuming all nodes are transmitting data at roughly equal rates and are overall transmitting data "faster" than the sink can process, it will soon reach a state where data is backlogged at each of the nodes. Also, the farther away a node is from the sink the more data is likely backlogged at that node.

Now, if a congested node tries to send more and more data along the same path, it might cause congestion bottlenecks - leading to dropped packets.

However, instead, if the node sends data to a less-congested neighbour, who in-turn passes it on to a less-congested neighbour, and so on - chances are that the load will get evenly distributed over the network, and then data will eventually reach the sink. Any node that gets too heavily backlogged will be applying a "backpressure", and will not accept more data to forward.

This is a bit of an over-simplification of Backpressure. A more rigorous mathematical treatment of this stochastic network optimization can be found under the general class of "Utility Optimal Lyapunov Networking" algorithms.

Overview of operation

The "business logic" of BCP is elegantly simple.

• Each node that has data to send calculates a weightage to each of its neighbours. It then sends to the best neighbour based on that weightage
  • The weightage is calculated as a combination of the link quality between the two nodes, and the queue size of that node. This is a critical part of BCP's operation. Details are in the paper.
  • Nodes learn their neighbours backlogs by "snooping". Nodes listen to all nearby packet transmissions that contain the backlog. Nodes also disseminate their backlog so that other nodes can pick them up.

Work in progress