Path Discovery Mechanism/Details

This is a (more) detailed version of this brief introduction to the Path Discovery Mechanism.

PREQ clusters

After the initial cluster of PREQs were broadcasted, intermediary nodes will begin to rebroadcast them and flood the entire mesh cloud – a process called Network Wide Broadcast, or NWB – in an attempt to reach the destination. In the current implementation, the first PREQ received by an intermediary node will be immediately rebroadcast, but a delay time will be respected before additional PREQs are forwarded. During this delay time, the node may receive multiple PREQs, not only with different metrics, but also from different transmitters, but only the PREQ with the best metric will be rebroadcast after this time expires. This mechanism will avoid unnecessary consumption of airtime. After all, reactive protocols can be extremely bursty and rebroadcasting every single PREQ a node receives would make things even worse.

After the PREQ delay period is finished (by default this time is 10ms) the intermediary node may still receive additional PREQs. In this case, a new timer will be fired and again, the node will retransmit only the best PREQ received, when the timer expires.

But an intermediary node will not simply rebroadcast a single PREQ, it must actually make a new PREQ cluster based on the first PREQ received and also for every best PREQ received over the delay time period. This means that an intermediary node will rebroadcast at least a complete cluster (4 frames) and maybe more, depending on the configured delay time and on the mesh density. It is an inherent treat of a dense cloud that an intermediary node will receive many PREQs coming from different paths, with different metrics and hop counts. It is not impossible that PREQs with lower costs (better metrics) are received after PREQs with higher metrics. Thus, in a dense mesh, a short delay time will pose a higher control overhead on the cloud.

IEEE802.11s flags

For those familiar with the IEEE802.11s draft it is also worth noting that there is no DO or RF flags present in the XO path discovery frames. In fact, there is an implicit DO flag, since an intermediary node will not respond to PREQs.

Coverage and reliability

Since broadcast frames are not acknowledged they lack any retransmission mechanism, this fact alone advocates for some level of redundancy as necessary or many path discovery cycles would not succeed. On the other hand, another means for improving broadcast/multicast reliability is reducing the transmission data for multicast/broadcast frames. But lower transmission rates mean longer transmission times. There is a clear tension between coverage and reliability on one side and spectrum efficiency on the other.

A simple step-by-step

In short, a description of the path discovery mechanism implemented in the XO follows:

(0) – S wants to discover a path to D.

(1) – S will check its forwarding table for a valid path to D. A valid path will be one not expired. Route expiration time defaults to 10 seconds, currently.

(2) – If (1) fails, S will broadcast a cluster of PREQs, consisting of four frames sent back to back at the data rates of 54, 36, 11 and 1Mbps. Each of these frames will have an associated cost.

(3) – All intermediary nodes will rebroadcast the first PREQ received in a new cluster. If, for example, the intermediary node successfully decodes the 54Mbps PREQ from S, it will immediately broadcast a new cluster with values 13+13, 13+28, 13+42 and 13+64 for PREQs at 54, 36, 11 and 1Mbps, respectively.

(4) – An intermediary node will wait a configurable time – the rreq_delay – before relaying another PREQ cluster if a PREQ with a better associated cost happens to be received later. Note that it is perfectly possible for a node to listen to the 11Mbps PREQ from S (with cost 42) and only then receive another PREQ, relayed by another intermediary node, in a two hops path, with a lower cost of 26. All but the first PREQ received (3) will be stored for rreq_delay before being retransmitted. And the intermediary node will only retransmitted the best PREQ received during this period. The rreq_delay currently defaults to 10ms.

(5) – The PREQ will eventually hit the destination node D which will respond with a PREP. At this point the procedure is the same of what is described in the 802.11s proposal, besides the fact that if D needs to send traffic back to A, a new path discovery will start. Note that this is only necessary if the application that triggered the path discovery mechanism at A is bidirectional, which is the case for all TCP applications, but not necessarily the case for UDP-based applications.