Dear Babel users and hackers, I'm pleased to announce the availability of my RTT-aware branch of babeld, which I've developed as part of an internship mentored by Juliusz and Matthieu. The code is available in the 'babeld-rtt' branch of the main repository:
git clone -b babeld-rtt git://git.wifi.pps.univ-paris-diderot.fr/babeld.git The motivation behind this feature is the following: when running babeld on an overlay network, using tunnels or VPNs, there is currently no way to distinguish between "good" links and "bad" links. Unless configured manually, all links are seen as wired and have a fixed metric (96 by default). For instance, babeld may use multiple long-range links to reach geographically close nodes, if the hop count is lower. A natural metric in such an environment is the RTT: while relatively cheap to measure, it allows to easily spot "long" virtual links over the Internet, which are likely to be less reliable and more expensive. My implementation computes the RTT between neighbours by piggybacking timestamps on Hello and IHU messages. This achieves a very low overhead on control traffic: about 5 additional bytes per message (Hello or IHU), which is negligible in most cases. Also, the time at which messages are sent on the wire is not modified. More specifically, we are able to compute the RTT even if a neighbour doesn't reply immediately, with an algorithm due to Dave Mills — which was used in the HELLO protocol as well as being a basis for NTP. The RTT samples are smoothed out using a moving exponential average, and then used to compute a metric, which is added to the regular metric associated to a neighbour. From a theoretical point of view, there is a known issue with dynamic metrics, such as the RTT: stability. Since a dynamic metric depends on the real-time condition of the network, it can leads to persistent routing oscillations. For instance, if a link is highly loaded, the RTT will increase, which will eventually lead installed routes to move away from the link. But the RTT will then decrease, and the best routes will use the link again, and so on. However, our early tests show that the smoothing (both on RTT samples and then on the metric itself, introduced in the 1.4.x branch) is enough to prevent such oscillations from being a real issue. I'm currently investigating more thorough tests and theory, along with more sophisticated techniques to further avoid stability issues. How to use in practice ====================== The additional metric is computed from the RTT using three parameters: 'rtt-min', 'rtt-max' and 'max-rtt-penalty'. The metric is piecewise affine between 'rtt-min' and 'rtt-max'. Below 'rtt-min', the value is 0; above 'rtt-max', the value is 'max-rtt-penalty'. An example configuration might look like the following: default rtt-min 10 # in milliseconds default rtt-max 120 # in milliseconds default max-rtt-penalty 150 # Maximum additional metric which would, for each interface, increase the metric — up to 150 — depending on the RTT to a neighbour. For a RTT lower than 10 ms, nothing is done; for a RTT higher than 120 ms, the metric associated to the neighbour is increased by 150. A maximum penalty of 150 is reasonable in a wired environment, as it will favour lower-RTT paths in the general case; in extreme cases, it will even allow itself an additional hop in order to avoid a high-RTT link. Please experiment and report any issue, or interesting real-world behaviour, that you might encounter. Baptiste
pgppGyl8EH6Ys.pgp
Description: PGP signature
_______________________________________________ Babel-users mailing list [email protected] http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/babel-users
