wiki:Proto/cModules/c0DesignSandbox/a0LinkQualityEstimate
close Warning: Can't synchronize with repository "(default)" ("(default)" is not readable or not a Git repository.). Look in the Trac log for more information.

Current Approach (as of 8/1/2014)

  • Routers periodically (T-period) broadcast probe messages to reach neighbors (incl. hosts). This is sent out on all interfaces of the router.
  • Neighbors in reception acknowledge by reverting the packet, also as a broadcast. The payload is modified to reflect the probe originator as the destination of the ACK.
  • Originating router uses the ACKs as neighbor discovery, and to keep a fixed-size history of ACK properties (turnaround time, loss ratio, etc) for each neighbor, and hence the link.
  • Short term link quality is estimated by considering a small window of past 'R_s' rounds of probes.
  • Long term link quality is estimated by considering a large(r) window of past 'R_l' rounds of probes.
  • R_s=3, R_l=10, with T=2s
  • Link quality is intended to be modeled as ETT (Expected Transmission Time)for the wireless links, but is grossly approximated in the current code as 1/2 of average rtt of successfully returned probes within estimation window.
  • Estimated link quality, over short and long terms, are used in a relative sense to decide if the short term quality is worse, better, or about the same as long term quality. If worse (by > 10%), then the packet is buffered temporarily (called a 'store').
  • Path quality is estimated as summation of individual link qualities, and look-ahead routing is performed by buffering packets in cases where quality of path to destination in short term is worse than the longer term path quality.

Discussion

  • Link quality is being estimated as 'average_rtt/2' for both wired and wireless links. This is causing two issues:
    • For very low latency wired links, with delays less than 1 ms, the rtts show significant deviation (> 10%) due to scheduling variability in the software stack. This causes unnecessary stores, even when there's no congestion or losses.
    • For wireless links, the rtt metric does not consider losses.
  • ETT is considered a reasonable metric for link quality in wireless mesh networks, and is computed as ((S/B) * ETX) ; where S is packet size, B is link data rate, and ETX is Expected Transmission Count.
    • ETX is calculated as 1/(df*dr), where df and dr are delivery ratios in the forward and reverse directions.
    • The delivery ratios can be estimated using the periodic probe messages, with the neighbor reporting it's observations in the probe ACK.
    • Data packet transfers can also be used to asses the link probabilities. However, this may also include losses due to congestion. While this may be desirable, the approach may interfere with separate mechanisms to deal with congestion explicitly.
    • bandwidth can be estimated using the packet-pair (or packet train) approach which involves sending 2 (or more) unicast packets in quick succession and measuring reception rate at the peer.
  • For wireless links, the transmission time dominates the packet delivery latency for common radio-radio distances. But for wireline links, the propagation delay can easily dominate. Losses in wireline are also very rare under normal (not congested) conditions. Therefore, if we plan on combining link quality metrics across wired and wireless for path quality, ETT may not be the right metric. Then, what else? Rtt/2? But we start to include processing delays here, which may dominate both propagation and transmission delays.
Last modified 7 years ago Last modified on Nov 30, 2014, 5:35:34 AM
Note: See TracWiki for help on using the wiki.