Path Discovery Mechanism/Details

JUST A DRAFT

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 rebroadcasted, 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 rebroadcasted 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.

Since broadcasted 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 rate addressed to multicast/broadcast addresses. 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.

After the PREQ delay period is finished (by default this time is 10ms, but it is adjustable as we will see in the next chapter) 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.

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. 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 and route expiration time defaults to 10 seconds, currently. (2) – If (1) fails, A 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 (default values can be seen in table ***). (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. Figure *** illustrates this scenario.

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.