X-Git-Url: https://tinc-vpn.org/git/browse?p=tinc;a=blobdiff_plain;f=src%2Fnet_packet.c;h=2f15bb4ef245acdde94c5cd0c89812b02b3f4e6d;hp=f51aec37ebb02be5ad9077f2289ed1942cc58b90;hb=24d28adf64934c8d726959e25dce8c10dbd10d1f;hpb=df6f67895723dd0c4226fa0f94257245a81a273f

diff --git a/src/net_packet.c b/src/net_packet.c
index f51aec37..2f15bb4e 100644
--- a/src/net_packet.c
+++ b/src/net_packet.c
@@ -66,17 +66,17 @@ int udp_discovery_timeout = 30;
 #define MAX_SEQNO 1073741824
 
 static void try_fix_mtu(node_t *n) {
-	if(n->mtuprobes > 30)
+	if(n->mtuprobes < 0)
 		return;
 
-	if(n->mtuprobes == 30 || n->minmtu >= n->maxmtu) {
+	if(n->mtuprobes == 90 || n->minmtu >= n->maxmtu) {
 		if(n->minmtu > n->maxmtu)
 			n->minmtu = n->maxmtu;
 		else
 			n->maxmtu = n->minmtu;
 		n->mtu = n->minmtu;
 		logger(DEBUG_TRAFFIC, LOG_INFO, "Fixing MTU of %s (%s) to %d after %d probes", n->name, n->hostname, n->mtu, n->mtuprobes);
-		n->mtuprobes = 31;
+		n->mtuprobes = -1;
 	}
 }
 
@@ -144,7 +144,7 @@ static void udp_probe_h(node_t *n, vpn_packet_t *packet, length_t len) {
 		if(probelen >= n->maxmtu + 8) {
 			logger(DEBUG_TRAFFIC, LOG_INFO, "Increase in PMTU to %s (%s) detected, restarting PMTU discovery", n->name, n->hostname);
 			n->maxmtu = MTU;
-			n->mtuprobes = 10;
+			n->mtuprobes = 30;
 			return;
 		}
 
@@ -157,10 +157,9 @@ static void udp_probe_h(node_t *n, vpn_packet_t *packet, length_t len) {
 			try_fix_mtu(n);
 		}
 
-		/* Calculate RTT and bandwidth.
+		/* Calculate RTT.
 		   The RTT is the time between the MTU probe burst was sent and the first
-		   reply is received. The bandwidth is measured using the time between the
-		   arrival of the first and third probe reply (or type 2 probe requests).
+		   reply is received.
 		 */
 
 		struct timeval now, diff;
@@ -180,12 +179,7 @@ static void udp_probe_h(node_t *n, vpn_packet_t *packet, length_t len) {
 		if(n->probe_counter == 1) {
 			n->rtt = diff.tv_sec + diff.tv_usec * 1e-6;
 			n->probe_time = probe_timestamp;
-		} else if(n->probe_counter == 3) {
-			/* TODO: this will never fire after initial MTU discovery. */
-			struct timeval probe_timestamp_diff;
-			timersub(&probe_timestamp, &n->probe_time, &probe_timestamp_diff);
-			n->bandwidth = 2.0 * probelen / (probe_timestamp_diff.tv_sec + probe_timestamp_diff.tv_usec * 1e-6);
-			logger(DEBUG_TRAFFIC, LOG_DEBUG, "%s (%s) RTT %.2f ms, burst bandwidth %.3f Mbit/s, rx packet loss %.2f %%", n->name, n->hostname, n->rtt * 1e3, n->bandwidth * 8e-6, n->packetloss * 1e2);
+			logger(DEBUG_TRAFFIC, LOG_DEBUG, "%s (%s) RTT %.2f ms, rx packet loss %.2f %%", n->name, n->hostname, n->rtt * 1e3, n->packetloss * 1e2);
 		}
 	}
 }
@@ -903,16 +897,16 @@ static void try_mtu(node_t *n) {
 		return;
 	}
 
-	/* mtuprobes == 0..29: initial discovery, send bursts with 1 second interval, mtuprobes++
-	   mtuprobes ==    30: fix MTU, and go to 31
-	   mtuprobes ==    31: send one >maxmtu probe every pingtimeout */
+	/* mtuprobes == 0..89: initial discovery, send bursts with 1 second interval, mtuprobes++
+	   mtuprobes ==    90: fix MTU, and go to -1
+	   mtuprobes ==    -1: send one >maxmtu probe every pingtimeout */
 
 	struct timeval now;
 	gettimeofday(&now, NULL);
 	struct timeval elapsed;
 	timersub(&now, &n->probe_sent_time, &elapsed);
-	if(n->mtuprobes < 31) {
-		if(n->mtuprobes != 0 && elapsed.tv_sec < 1)
+	if(n->mtuprobes >= 0) {
+		if(n->mtuprobes != 0 && elapsed.tv_sec == 0 && elapsed.tv_usec < 333333)
 			return;
 	} else {
 		if(elapsed.tv_sec < pingtimeout)
@@ -922,22 +916,36 @@ static void try_mtu(node_t *n) {
 	try_fix_mtu(n);
 
 	int timeout;
-	if(n->mtuprobes == 31) {
+	if(n->mtuprobes < 0) {
 		/* After the initial discovery, we only send one >maxmtu probe
 		   to detect PMTU increases. */
 		if(n->maxmtu + 8 < MTU)
 			send_udp_probe_packet(n, n->maxmtu + 8);
 	} else {
-		/* Probes are sent in batches of three, with random sizes between the
-		   lower and upper boundaries for the MTU thus far discovered. */
-		for (int i = 0; i < 3; i++) {
-			int len = n->maxmtu;
-			if(n->minmtu < n->maxmtu)
-				len = n->minmtu + 1 + rand() % (n->maxmtu - n->minmtu);
-
-			send_udp_probe_packet(n, MAX(len, 64));
-		}
-
+		/* Decreasing the number of probes per cycle might make the algorithm react faster to lost packets,
+		   but it will typically increase convergence time in the no-loss case. */
+		const length_t probes_per_cycle = 8;
+
+		/* This magic value was determined using math simulations.
+		   It will result in a 1339-byte first probe, followed (if there was a reply) by a 1417-byte probe.
+		   Since 1417 is just below the range of tinc MTUs over typical networks,
+		   this fine-tuning allows tinc to cover a lot of ground very quickly. */
+		const float multiplier = 0.982;
+
+		const float cycle_position = probes_per_cycle - (n->mtuprobes % probes_per_cycle) - 1;
+		const length_t minmtu = MAX(n->minmtu, 64);
+		const float interval = n->maxmtu - minmtu;
+
+		/* The core of the discovery algorithm is this exponential.
+		   It produces very large probes early in the cycle, and then it very quickly decreases the probe size.
+		   This reflects the fact that in the most difficult cases, we don't get any feedback for probes that
+		   are too large, and therefore we need to concentrate on small offsets so that we can quickly converge
+		   on the precise MTU as we are approaching it.
+		   The last probe of the cycle is always 1 byte in size - this is to make sure we'll get at least one
+		   reply per cycle so that we can make progress. */
+		const length_t offset = powf(interval, multiplier * cycle_position / (probes_per_cycle - 1));
+
+		send_udp_probe_packet(n, minmtu + offset);
 		if(n->mtuprobes >= 0)
 			n->mtuprobes++;
 	}