My colleagues Jiazi, Juan, and I, just finished the final editorial bits of process on a new paper “Use ’em or Lose ’em: On Unidirectional Links in Reactive Routing Protocols”, published in Elsevier Ad Hoc Networks – and with the paper (still being copyedited by the publishing house) being available here: https://doi.org/10.1016/j.adhoc.2018.02.004.
The problem that this paper addresses was sourced in our work on LOADng, the IoT routing protocol used – for example – for providing (data) connectivity over PLC (or, as the French say, CPL) in the Smart Grid. In such networks, a significant fraction of links were found to be uni-directional, and the mechanisms traditionally proposed (blacklisting of neighbouring nodes with which unidirectionality was detected) insufficient:
- Simply excluding uni-directional links (the purpose of the “blacklist” mechanism) would lead to the network being disconnected
- The “blacklist” mechanism itself, we found, did not actually guard against uni-directional links.
With this in mind, we set out to both analytically understand the impact that the presence of uni-directional links has on the performance of a reactive routing protocol – and to develop mechanisms for allowing reactive routing protocols to incorporate and use uni-directional links in their routing topologies.
Of course, all good science starts with a problem, followed by intense, and erratic full-contact white-boarding of various ideas, until some deeper understanding, and a solution, emerges…
We owe a hat-tip to Mario Gerla and Axel Colin de Verdiere, whose work on asymmetric links in ODMRP, ended up being the key inspiration for how we solved one part of this problem.
Go read the paper – the abstract of which is:
In reactive unicast routing protocols, Route Discovery aims to include only bidirectional links in discovered routing paths. This is typically accomplished by having routers maintain a “blacklist” of links recently confirmed (through Route Reply processing) to be unidirectional – which is then used for excluding subsequent Route Discovery control messages received over these links from being processed and forwarded.This paper first presents an analytical model, which allows to study the impact of unidirectional links being present in a network, on the performance of reactive routing protocols. Next, this paper identifies that despite the use of a “blacklist”, the Route Discovery process may result in discovery of false forward routes, i.e.,routes containing unidirectional links – and proposes a counter-measure denoted Forward Bidirectionality Check. This paper further proposes a Loop Exploration mechanism, allowing to properly include unidirectional links in a discovered routing topology – with the goal of providing bidirectional connectivity even in absence of bidirectional paths in the network.Finally, each of these proposed mechanisms are subjected to extensive network simulations in static scenarios. When the fraction of unidirectional links is moderate (15–50%), simulations find Forward Bidirectionality Check to significantly increase the probability that bidirectional routing paths can be discovered by a reactive routing protocol, while incurring only an insignificant additional overhead. Further, in networks with a significant fraction of unidirectional links ( ≥ 50%), simulations reveal that Loop Exploration preserves the ability of a reactive routing protocol to establish bidirectional communication (possibly through non-bidirectional paths), but at the expense of a substantial additional overhead.