Use ’em or Lose ’em: On Unidirectional Links in Reactive Routing Protocols

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 re­ac­tive uni­cast rout­ing pro­to­cols, Route Dis­cov­ery aims to in­clude only bidi­rec­tional links in dis­cov­ered rout­ing paths. This is typ­i­cally ac­com­plished by hav­ing routers main­tain a “black­list” of links re­cently con­firmed (through Route Re­ply pro­cess­ing) to be uni­di­rec­tional – which is then used for ex­clud­ing sub­se­quent Route Dis­cov­ery con­trol mes­sages re­ceived over these links from be­ing processed and for­warded.This pa­per first pre­sents an an­a­lyt­i­cal model, which al­lows to study the im­pact of uni­di­rec­tional links be­ing pre­sent in a net­work, on the per­for­mance of re­ac­tive rout­ing pro­to­cols. Next, this pa­per iden­ti­fies that de­spite the use of a “black­list”, the Route Dis­cov­ery process may re­sult in dis­cov­ery of false for­ward routes, i.e.,routes con­tain­ing uni­di­rec­tional links – and pro­poses a counter-mea­sure de­noted For­ward Bidi­rec­tion­al­ity Check. This pa­per fur­ther pro­poses a Loop Ex­plo­ration mech­a­nism, al­low­ing to prop­erly in­clude uni­di­rec­tional links in a dis­cov­ered rout­ing topol­ogy – with the goal of pro­vid­ing bidi­rec­tional con­nec­tiv­ity even in ab­sence of bidi­rec­tional paths in the net­work.Fi­nally, each of these pro­posed mech­a­nisms are sub­jected to ex­ten­sive net­work sim­u­la­tions in sta­tic sce­nar­ios. When the frac­tion of uni­di­rec­tional links is mod­er­ate (15–50%), sim­u­la­tions find For­ward Bidi­rec­tion­al­ity Check to sig­nif­i­cantly in­crease the prob­a­bil­ity that bidi­rec­tional rout­ing paths can be dis­cov­ered by a re­ac­tive rout­ing pro­to­col, while in­cur­ring only an in­signif­i­cant ad­di­tional over­head. Fur­ther, in net­works with a sig­nif­i­cant frac­tion of uni­di­rec­tional links ( ≥ 50%), sim­u­la­tions re­veal that Loop Ex­plo­ration pre­serves the abil­ity of a re­ac­tive rout­ing pro­to­col to es­tab­lish bidi­rec­tional com­mu­ni­ca­tion (pos­si­bly through non-bidi­rec­tional paths), but at the ex­pense of a sub­stan­tial ad­di­tional over­head.