Babel: Add support for the RTT extension

This adds support to the Babel protocol for the RTT extension specified
in draft-ietf-babel-rtt-extension. While this extension is not yet at the
RFC stage, it is one of the more useful extensions to Babel[0], so it
seems worth having in Bird as well.

The extension adds timestamps to Hello and IHU TLVs and uses these to
compute an RTT to each neighbour. An extra per-neighbour cost is then
computed from the RTT based on a minimum and maximum interval and cost
value specified in the configuration. The primary use case for this is
improving routing in a geographically distributed tunnel-based overlay
network.

The implementation follows the babeld implementation when picking
constants and default configuration values. It also uses the same RTT
smoothing algorithm as babeld, and follows it in adding a new 'tunnel'
interface type which enables RTT by default.

[0] https://alioth-lists.debian.net/pipermail/babel-users/2022-April/003932.html

1 files changed, 24 insertions, 0 deletions

diff --git a/proto/babel/babel.h b/proto/babel/babel.h
index dcd303e1..edde4cab 100644
--- a/proto/babel/babel.h
+++ b/proto/babel/babel.h
@@ -53,10 +53,16 @@
 #define BABEL_GARBAGE_INTERVAL		(300 S_)
 #define BABEL_RXCOST_WIRED		96
 #define BABEL_RXCOST_WIRELESS		256
+#define BABEL_RXCOST_RTT		96
 #define BABEL_INITIAL_HOP_COUNT		255
 #define BABEL_MAX_SEND_INTERVAL		5	/* Unused ? */
 #define BABEL_INITIAL_NEIGHBOR_TIMEOUT	(60 S_)
 
+#define BABEL_RTT_MAX_VALUE		(600 S_)
+#define BABEL_RTT_MIN			(10 MS_)
+#define BABEL_RTT_MAX			(120 MS_)
+#define BABEL_RTT_DECAY			42
+
 /* Max interval that will not overflow when carried as 16-bit centiseconds */
 #define BABEL_TIME_UNITS		10000	/* On-wire times are counted in centiseconds */
 #define BABEL_MIN_INTERVAL		(0x0001 * BABEL_TIME_UNITS)
@@ -96,6 +102,8 @@ enum babel_tlv_type {
 enum babel_subtlv_type {
   BABEL_SUBTLV_PAD1		= 0,
   BABEL_SUBTLV_PADN		= 1,
+  BABEL_SUBTLV_DIVERSITY	= 2, /* we don't support this */
+  BABEL_SUBTLV_TIMESTAMP	= 3,
 
   /* Mandatory subtlvs */
   BABEL_SUBTLV_SOURCE_PREFIX    = 128,
@@ -106,6 +114,7 @@ enum babel_iface_type {
   BABEL_IFACE_TYPE_UNDEF	= 0,
   BABEL_IFACE_TYPE_WIRED	= 1,
   BABEL_IFACE_TYPE_WIRELESS	= 2,
+  BABEL_IFACE_TYPE_TUNNEL	= 3,
   BABEL_IFACE_TYPE_MAX
 };
 
@@ -141,6 +150,12 @@ struct babel_iface_config {
   uint ihu_interval;			/* IHU interval, in us */
   uint update_interval;			/* Update interval, in us */
 
+  btime rtt_min;			/* rtt above which to start penalising metric */
+  btime rtt_max;			/* max rtt metric penalty applied above this */
+  u16 rtt_cost;			/* metric penalty to apply at rtt_max */
+  u16 rtt_decay;			/* decay of neighbour RTT (units of 1/256) */
+  u8  rtt_send;			/* whether to send timestamps on this interface */
+
   u16 rx_buffer;			/* RX buffer size, 0 for MTU */
   u16 tx_length;			/* TX packet length limit (including headers), 0 for MTU */
   int tx_tos;
@@ -229,6 +244,10 @@ struct babel_neighbor {
   u16 next_hello_seqno;
   uint last_hello_int;
 
+  u32 last_tstamp;
+  btime last_tstamp_rcvd;
+  btime srtt;
+
   u32 auth_pc_unicast;
   u32 auth_pc_multicast;
   u8 auth_passed;
@@ -326,6 +345,8 @@ struct babel_msg_hello {
   u16 seqno;
   uint interval;
   ip_addr sender;
+  u32 tstamp;
+  btime pkt_received;
 };
 
 struct babel_msg_ihu {
@@ -335,6 +356,9 @@ struct babel_msg_ihu {
   uint interval;
   ip_addr addr;
   ip_addr sender;
+  u32 tstamp;
+  u32 tstamp_rcvd;
+  btime pkt_received;
 };
 
 struct babel_msg_update {