ZeroTier now has link quality measurement. We are not using this yet but decided to put it in to prep for future QoS support and SD-WAN stuff.

6 files changed, 97 insertions, 20 deletions

diff --git a/node/Node.cpp b/node/Node.cpp
index 35940d27..a75a56b4 100644
--- a/node/Node.cpp
+++ b/node/Node.cpp
@@ -401,9 +401,10 @@ ZT_PeerList *Node::peers() const
 			memcpy(&(p->paths[p->pathCount].address),&(path->first->address()),sizeof(struct sockaddr_storage));
 			p->paths[p->pathCount].lastSend = path->first->lastOut();
 			p->paths[p->pathCount].lastReceive = path->first->lastIn();
+			p->paths[p->pathCount].trustedPathId = RR->topology->getOutboundPathTrust(path->first->address());
+			p->paths[p->pathCount].linkQuality = (int)path->first->linkQuality();
 			p->paths[p->pathCount].expired = path->second;
 			p->paths[p->pathCount].preferred = (path->first == bestp) ? 1 : 0;
-			p->paths[p->pathCount].trustedPathId = RR->topology->getOutboundPathTrust(path->first->address());
 			++p->pathCount;
 		}
 	}
diff --git a/node/Packet.hpp b/node/Packet.hpp
index 2017ce8e..d5817708 100644
--- a/node/Packet.hpp
+++ b/node/Packet.hpp
@@ -59,15 +59,17 @@
  *   + Otherwise backward compatible with protocol v4
  * 6 - 1.1.5 ... 1.1.10
  *   + Network configuration format revisions including binary values
- * 7 - 1.1.10 -- 1.2.0
+ * 7 - 1.1.10 ... 1.1.17
  *   + Introduce trusted paths for local SDN use
- * 8 - 1.2.0  -- CURRENT
+ * 8 - 1.1.17 ... 1.2.0
  *   + Multipart network configurations for large network configs
  *   + Tags and Capabilities
  *   + Inline push of CertificateOfMembership deprecated
  *   + Certificates of representation for federation and mesh
+ * 9 - 1.2.0 ... CURRENT
+ *   + In-band encoding of packet counter for link quality measurement
  */
-#define ZT_PROTO_VERSION 8
+#define ZT_PROTO_VERSION 9
 
 /**
  * Minimum supported protocol version
@@ -1320,6 +1322,11 @@ public:
 	inline uint64_t packetId() const { return at<uint64_t>(ZT_PACKET_IDX_IV); }
 
 	/**
+	 * @return Value of link quality counter extracted from this packet's ID, range 0 to 7 (3 bits)
+	 */
+	inline unsigned int linkQualityCounter() const { return (unsigned int)(reinterpret_cast<const uint8_t *>(data())[7] & 7); }
+
+	/**
 	 * Set packet verb
 	 *
 	 * This also has the side-effect of clearing any verb flags, such as
diff --git a/node/Path.hpp b/node/Path.hpp
index 626f2f4f..dd6455d1 100644
--- a/node/Path.hpp
+++ b/node/Path.hpp
@@ -21,6 +21,7 @@
 
 #include <stdint.h>
 #include <string.h>
+#include <stdlib.h>
 
 #include <stdexcept>
 #include <algorithm>
@@ -30,6 +31,7 @@
 #include "SharedPtr.hpp"
 #include "AtomicCounter.hpp"
 #include "NonCopyable.hpp"
+#include "Utils.hpp"
 
 /**
  * Maximum return value of preferenceRank()
@@ -105,22 +107,34 @@ public:
 		_lastOut(0),
 		_lastIn(0),
 		_lastTrustEstablishedPacketReceived(0),
+		_incomingLinkQualityFastLog(0xffffffffffffffffULL),
+		_incomingLinkQualitySlowLogPtr(0),
+		_incomingLinkQualitySlowLogCounter(-64), // discard first fast log
+		_incomingLinkQualityPreviousPacketCounter(0),
 		_outgoingPacketCounter(0),
 		_addr(),
 		_localAddress(),
 		_ipScope(InetAddress::IP_SCOPE_NONE)
 	{
+		for(int i=0;i<(int)sizeof(_incomingLinkQualitySlowLog);++i)
+			_incomingLinkQualitySlowLog[i] = ZT_PATH_LINK_QUALITY_MAX;
 	}
 
 	Path(const InetAddress &localAddress,const InetAddress &addr) :
 		_lastOut(0),
 		_lastIn(0),
 		_lastTrustEstablishedPacketReceived(0),
+		_incomingLinkQualityFastLog(0xffffffffffffffffULL),
+		_incomingLinkQualitySlowLogPtr(0),
+		_incomingLinkQualitySlowLogCounter(-64), // discard first fast log
+		_incomingLinkQualityPreviousPacketCounter(0),
 		_outgoingPacketCounter(0),
 		_addr(addr),
 		_localAddress(localAddress),
 		_ipScope(addr.ipScope())
 	{
+		for(int i=0;i<(int)sizeof(_incomingLinkQualitySlowLog);++i)
+			_incomingLinkQualitySlowLog[i] = ZT_PATH_LINK_QUALITY_MAX;
 	}
 
 	/**
@@ -131,6 +145,39 @@ public:
 	inline void received(const uint64_t t) { _lastIn = t; }
 
 	/**
+	 * Update link quality using a counter from an incoming packet (or packet head in fragmented case)
+	 *
+	 * @param counter Packet link quality counter (range 0 to 7, must not have other bits set)
+	 */
+	inline void updateLinkQuality(const unsigned int counter)
+	{
+		const unsigned int prev = _incomingLinkQualityPreviousPacketCounter;
+		_incomingLinkQualityPreviousPacketCounter = counter;
+		const uint64_t fl = (_incomingLinkQualityFastLog = ((_incomingLinkQualityFastLog << 1) | (uint64_t)(prev == ((counter - 1) & 0x7))));
+		if (++_incomingLinkQualitySlowLogCounter >= 64) {
+			_incomingLinkQualitySlowLogCounter = 0;
+			_incomingLinkQualitySlowLog[_incomingLinkQualitySlowLogPtr++ % sizeof(_incomingLinkQualitySlowLog)] = Utils::countBits(fl);
+		}
+	}
+
+	/**
+	 * @return Link quality from 0 (min) to 255 (max)
+	 */
+	inline unsigned int linkQuality() const
+	{
+		unsigned long slsize = _incomingLinkQualitySlowLogPtr;
+		if (slsize > (unsigned long)sizeof(_incomingLinkQualitySlowLog))
+			slsize = (unsigned long)sizeof(_incomingLinkQualitySlowLog);
+		else if (!slsize)
+			return 255; // ZT_PATH_LINK_QUALITY_MAX
+		unsigned long lq = 0;
+		for(unsigned long i=0;i<slsize;++i)
+			lq += (unsigned long)_incomingLinkQualitySlowLog[i] * 4;
+		lq /= slsize;
+		return (unsigned int)((lq >= 255) ? 255 : lq);
+	}
+
+	/**
 	 * Set time last trusted packet was received (done in Peer::received())
 	 */
 	inline void trustedPacketReceived(const uint64_t t) { _lastTrustEstablishedPacketReceived = t; }
@@ -251,13 +298,18 @@ public:
 	inline unsigned int nextOutgoingCounter() { return _outgoingPacketCounter++; }
 
 private:
-	uint64_t _lastOut;
-	uint64_t _lastIn;
-	uint64_t _lastTrustEstablishedPacketReceived;
-	unsigned int _outgoingPacketCounter;
+	volatile uint64_t _lastOut;
+	volatile uint64_t _lastIn;
+	volatile uint64_t _lastTrustEstablishedPacketReceived;
+	volatile uint64_t _incomingLinkQualityFastLog;
+	volatile unsigned long _incomingLinkQualitySlowLogPtr;
+	volatile signed int _incomingLinkQualitySlowLogCounter;
+	volatile unsigned int _incomingLinkQualityPreviousPacketCounter;
+	volatile unsigned int _outgoingPacketCounter;
 	InetAddress _addr;
 	InetAddress _localAddress;
 	InetAddress::IpScope _ipScope; // memoize this since it's a computed value checked often
+	volatile uint8_t _incomingLinkQualitySlowLog[32];
 	AtomicCounter __refCount;
 };
 
diff --git a/node/Peer.cpp b/node/Peer.cpp
index c4c8774e..1dde8b65 100644
--- a/node/Peer.cpp
+++ b/node/Peer.cpp
@@ -142,6 +142,9 @@ void Peer::received(
 	}
 
 	if (hops == 0) {
+		if (_vProto >= 9)
+			path->updateLinkQuality((unsigned int)(packetId & 7));
+
 		bool pathIsConfirmed = false;
 		{
 			Mutex::Lock _l(_paths_m);
diff --git a/node/Switch.cpp b/node/Switch.cpp
index bf309e36..0392aec1 100644
--- a/node/Switch.cpp
+++ b/node/Switch.cpp
@@ -185,17 +185,6 @@ void Switch::onRemotePacket(const InetAddress &localAddr,const InetAddress &from
 			} else if (len >= ZT_PROTO_MIN_PACKET_LENGTH) { // min length check is important!
 				// Handle packet head -------------------------------------------------
 
-				// See packet format in Packet.hpp to understand this
-				const uint64_t packetId = (
-					(((uint64_t)reinterpret_cast<const uint8_t *>(data)[0]) << 56) |
-					(((uint64_t)reinterpret_cast<const uint8_t *>(data)[1]) << 48) |
-					(((uint64_t)reinterpret_cast<const uint8_t *>(data)[2]) << 40) |
-					(((uint64_t)reinterpret_cast<const uint8_t *>(data)[3]) << 32) |
-					(((uint64_t)reinterpret_cast<const uint8_t *>(data)[4]) << 24) |
-					(((uint64_t)reinterpret_cast<const uint8_t *>(data)[5]) << 16) |
-					(((uint64_t)reinterpret_cast<const uint8_t *>(data)[6]) << 8) |
-					((uint64_t)reinterpret_cast<const uint8_t *>(data)[7])
-				);
 				const Address destination(reinterpret_cast<const uint8_t *>(data) + 8,ZT_ADDRESS_LENGTH);
 				const Address source(reinterpret_cast<const uint8_t *>(data) + 13,ZT_ADDRESS_LENGTH);
 
@@ -297,6 +286,17 @@ void Switch::onRemotePacket(const InetAddress &localAddr,const InetAddress &from
 				} else if ((reinterpret_cast<const uint8_t *>(data)[ZT_PACKET_IDX_FLAGS] & ZT_PROTO_FLAG_FRAGMENTED) != 0) {
 					// Packet is the head of a fragmented packet series
 
+					const uint64_t packetId = (
+						(((uint64_t)reinterpret_cast<const uint8_t *>(data)[0]) << 56) |
+						(((uint64_t)reinterpret_cast<const uint8_t *>(data)[1]) << 48) |
+						(((uint64_t)reinterpret_cast<const uint8_t *>(data)[2]) << 40) |
+						(((uint64_t)reinterpret_cast<const uint8_t *>(data)[3]) << 32) |
+						(((uint64_t)reinterpret_cast<const uint8_t *>(data)[4]) << 24) |
+						(((uint64_t)reinterpret_cast<const uint8_t *>(data)[5]) << 16) |
+						(((uint64_t)reinterpret_cast<const uint8_t *>(data)[6]) << 8) |
+						((uint64_t)reinterpret_cast<const uint8_t *>(data)[7])
+					);
+
 					Mutex::Lock _l(_rxQueue_m);
 					RXQueueEntry *const rq = _findRXQueueEntry(now,packetId);
 
@@ -344,7 +344,7 @@ void Switch::onRemotePacket(const InetAddress &localAddr,const InetAddress &from
 								rq = tmp;
 						}
 						rq->timestamp = now;
-						rq->packetId = packetId;
+						rq->packetId = packet.packetId();
 						rq->frag0 = packet;
 						rq->totalFragments = 1;
 						rq->haveFragments = 1;
diff --git a/node/Utils.hpp b/node/Utils.hpp
index 7b1994be..ceb29d7e 100644
--- a/node/Utils.hpp
+++ b/node/Utils.hpp
@@ -253,6 +253,20 @@ public:
 	}
 
 	/**
+	 * Count the number of bits set in an integer
+	 *
+	 * @param v 64-bit integer
+	 * @return Number of bits set in this integer (0-64)
+	 */
+	static inline uint64_t countBits(uint64_t v)
+	{
+		v = v - ((v >> 1) & (uint64_t)~(uint64_t)0/3);
+		v = (v & (uint64_t)~(uint64_t)0/15*3) + ((v >> 2) & (uint64_t)~(uint64_t)0/15*3);
+		v = (v + (v >> 4)) & (uint64_t)~(uint64_t)0/255*15;
+		return (uint64_t)(v * ((uint64_t)~(uint64_t)0/255)) >> 56;
+	}
+
+	/**
 	 * Check if a memory buffer is all-zero
 	 *
 	 * @param p Memory to scan