New multicast algorithm work in progress...

5 files changed, 87 insertions, 306 deletions

diff --git a/node/Constants.hpp b/node/Constants.hpp
index 926bac6f..a46937ed 100644
--- a/node/Constants.hpp
+++ b/node/Constants.hpp
@@ -231,26 +231,6 @@ error_no_ZT_ARCH_defined;
 #define ZT_RELAY_MAX_HOPS 3
 
 /**
- * Breadth of tree for rumor mill multicast propagation
- */
-#define ZT_MULTICAST_DEFAULT_PROPAGATION_BREADTH 3
-
-/**
- * Depth of tree for rumor mill multicast propagation
- */
-#define ZT_MULTICAST_DEFAULT_PROPAGATION_DEPTH 6
-
-/**
- * Length of ring buffer history of recent multicast packets
- */
-#define ZT_MULTICAST_DEDUP_HISTORY_LENGTH 1024
-
-/**
- * Expiration time in ms for multicast deduplication history items
- */
-#define ZT_MULTICAST_DEDUP_HISTORY_EXPIRE 2000
-
-/**
  * Period between announcements of all multicast 'likes' in ms
  *
  * Announcement occurs when a multicast group is locally joined, but all
@@ -265,6 +245,11 @@ error_no_ZT_ARCH_defined;
 #define ZT_MULTICAST_LIKE_EXPIRE ((ZT_MULTICAST_LIKE_ANNOUNCE_ALL_PERIOD * 2) + 1000)
 
 /**
+ * Expiration for remembered MULTICAST_GOTs, in ms
+ */
+#define ZT_MULTICAST_MAGNET_STATE_EXPIRE 30000
+
+/**
  * Time between polls of local taps for multicast membership changes
  */
 #define ZT_MULTICAST_LOCAL_POLL_PERIOD 10000
diff --git a/node/Multicaster.hpp b/node/Multicaster.hpp
index c7e34d2f..40b7b468 100644
--- a/node/Multicaster.hpp
+++ b/node/Multicaster.hpp
@@ -31,349 +31,146 @@
 #include <stdint.h>
 #include <string.h>
 
-#include <utility>
-#include <algorithm>
 #include <stdexcept>
 #include <map>
-#include <set>
 #include <vector>
-#include <string>
+#include <set>
+#include <algorithm>
 
 #include "Constants.hpp"
-#include "Buffer.hpp"
-#include "Packet.hpp"
+#include "Mutex.hpp"
 #include "MulticastGroup.hpp"
 #include "Utils.hpp"
-#include "MAC.hpp"
 #include "Address.hpp"
-#include "SharedPtr.hpp"
-#include "BloomFilter.hpp"
-#include "Identity.hpp"
-#include "CMWC4096.hpp"
-#include "C25519.hpp"
 
 namespace ZeroTier {
 
 /**
- * Multicast propagation engine
- *
- * This is written as a generic class so that it can be mocked and tested
- * in simulation. It also always takes 'now' as an argument, permitting
- * running in simulated time.
- *
- * This does not handle network permission or rate limiting, only the
- * propagation algorithm.
+ * Multicast propagation algorithm
  */
 class Multicaster
 {
 public:
-	/**
-	 * Simple bit field bloom filter included with multicast frame packets
-	 */
-	typedef BloomFilter<ZT_PROTO_VERB_MULTICAST_FRAME_BLOOM_FILTER_SIZE_BITS> MulticastBloomFilter;
-
-	Multicaster()
-		throw()
-	{
-		memset(_multicastHistory,0,sizeof(_multicastHistory));
-		_multicastHistoryPtr = 0;
-	}
-
-	/**
-	 * Generate a signature of a multicast packet using an identity
-	 *
-	 * @param id Identity to sign with (must have secret key portion)
-	 * @param nwid Network ID
-	 * @param from MAC address of sender
-	 * @param to Multicast group
-	 * @param etherType 16-bit ethernet type
-	 * @param data Ethernet frame data
-	 * @param len Length of frame
-	 * @return Signature of packet data and attributes
-	 * @throws std::runtime_error Cannot sign, e.g. identity has no private key
-	 */
-	static inline C25519::Signature signMulticastPacket(const Identity &id,uint64_t nwid,const MAC &from,const MulticastGroup &to,unsigned int etherType,const void *data,unsigned int len)
-		throw(std::runtime_error)
-	{
-		char tmp[65536];
-		void *tmp2 = (void *)tmp;
-		*((uint64_t *)tmp2) = Utils::hton((uint64_t)nwid);
-		memcpy(tmp + 8,from.data,6);
-		memcpy(tmp + 14,to.mac().data,6);
-		*((uint32_t *)(tmp + 20)) = Utils::hton((uint32_t)to.adi());
-		*((uint16_t *)(tmp + 24)) = Utils::hton((uint16_t)etherType);
-		memcpy(tmp + 26,data,std::min((unsigned int)(sizeof(tmp) - 26),len)); // min() is a sanity check here, no packet is that big
-		return id.sign(tmp,len + 26);
-	}
-
-	/**
-	 * Verify a signature from a multicast packet
-	 *
-	 * @param id Identity of original signer
-	 * @param nwid Network ID
-	 * @param from MAC address of sender
-	 * @param to Multicast group
-	 * @param etherType 16-bit ethernet type
-	 * @param data Ethernet frame data
-	 * @param len Length of frame
-	 * @param signature Signature
-	 * @param siglen Length of signature in bytes
-	 * @return True if signature verification was successful
-	 */
-	static bool verifyMulticastPacket(const Identity &id,uint64_t nwid,const MAC &from,const MulticastGroup &to,unsigned int etherType,const void *data,unsigned int len,const void *signature,unsigned int siglen)
-	{
-		char tmp[65536];
-		void *tmp2 = (void *)tmp;
-		*((uint64_t *)tmp2) = Utils::hton(nwid);
-		memcpy(tmp + 8,from.data,6);
-		memcpy(tmp + 14,to.mac().data,6);
-		*((uint32_t *)(tmp + 20)) = Utils::hton(to.adi());
-		*((uint16_t *)(tmp + 24)) = Utils::hton((uint16_t)etherType);
-		memcpy(tmp + 26,data,std::min((unsigned int)(sizeof(tmp) - 26),len)); // min() is a sanity check here, no packet is that big
-		return id.verify(tmp,len + 26,signature,siglen);
-	}
+	Multicaster() {}
 
 	/**
-	 * Compute the CRC64 code for multicast deduplication
+	 * Add or renew a peer's subscription to a multicast group
 	 *
-	 * @param nwid Network ID
-	 * @param from Sender MAC
-	 * @param to Destination multicast group
-	 * @param etherType Ethernet frame type
-	 * @param payload Multicast frame data
-	 * @param len Length of frame
+	 * @param a Address that LIKEd
+	 * @param mg Multicast group
+	 * @param now Current time
 	 */
-	static inline uint64_t computeMulticastDedupCrc(
-		uint64_t nwid,
-		const MAC &from,
-		const MulticastGroup &to,
-		unsigned int etherType,
-		const void *payload,
-		unsigned int len)
-		throw()
+	inline void likesGroup(const Address &a,const MulticastGroup &mg,uint64_t now)
 	{
-		// This CRC is only used locally, so byte order issues and
-		// such don't matter. It can also be changed without protocol
-		// impact.
-		uint64_t crc = Utils::crc64(0,from.data,6);
-		crc = Utils::crc64(crc,to.mac().data,6);
-		crc ^= (uint64_t)to.adi();
-		crc ^= (uint64_t)etherType;
-		crc = Utils::crc64(crc,payload,len);
-		crc ^= nwid; // also include network ID in CRC
-		return crc;
+		Mutex::Lock _l(_lock);
+		std::map< Address,_PeerInfo >::iterator pi(_peers.find(a));
+		if (pi == _peers.end()) {
+			pi = _peers.insert(std::pair< Address,_PeerInfo >(a,_PeerInfo())).first;
+			_proximity.push_front(a);
+			pi->second.proximitySlot = _proximity.begin();
+		}
+		pi->second.groups[mg] = now;
 	}
 
 	/**
-	 * Check multicast history to see if this is a duplicate
+	 * Bring a peer closer in terms of propagation priority
 	 *
-	 * @param crc Multicast CRC
+	 * @param a Address to bring closer (e.g. due to unicast message)
 	 * @param now Current time
-	 * @return True if this appears to be a duplicate to within history expiration time
 	 */
-	inline bool checkDuplicate(uint64_t crc,uint64_t now) const
-		throw()
+	inline void bringCloser(const Address &a)
 	{
-		for(unsigned int i=0;i<ZT_MULTICAST_DEDUP_HISTORY_LENGTH;++i) {
-			if ((_multicastHistory[i][0] == crc)&&((now - _multicastHistory[i][1]) <= ZT_MULTICAST_DEDUP_HISTORY_EXPIRE))
-				return true;
+		Mutex::Lock _l(_lock);
+		std::map< Address,_PeerInfo >::iterator pi(_peers.find(a));
+		if (pi != _peers.end()) {
+			if (pi->second.proximitySlot != _proximity.begin())
+				_proximity.splice(_proximity.begin(),_proximity,pi->second.proximitySlot);
 		}
-		return false;
 	}
 
 	/**
-	 * Add a multicast CRC to the multicast deduplication history
+	 * Indicate that a peer reported that it GOT a multicast
+	 *
+	 * This only happens on magnet nodes for a propagation.
 	 *
-	 * @param crc Multicast CRC
+	 * @param mcGuid Multicast GUID
+	 * @param peer Peer that GOT multicast
 	 * @param now Current time
 	 */
-	inline void addToDedupHistory(uint64_t crc,uint64_t now)
-		throw()
+	inlien void got(const Address &peer,uint64_t mcGuid,uint64_t now)
 	{
-		unsigned int mhi = ++_multicastHistoryPtr % ZT_MULTICAST_DEDUP_HISTORY_LENGTH;
-		_multicastHistory[mhi][0] = crc;
-		_multicastHistory[mhi][1] = now;
+		Mutex::Lock _l(_lock);
+		std::pair< uint64_t,std::set<Address> > &g = _got[mcGuid];
+		g.first = now;
+		g.second.insert(peer);
 	}
 
 	/**
-	 * Update the most recent LIKE time for an address in a given multicast group on a given network
-	 *
-	 * @param nwid Network ID
-	 * @param mg Multicast group
-	 * @param addr Address that likes group on given network
-	 * @param now Current timestamp
+	 * Erase entries for expired LIKEs
 	 */
-	inline void likesMulticastGroup(const uint64_t nwid,const MulticastGroup &mg,const Address &addr,const uint64_t now)
+	inline void clean(uint64_t now)
 	{
-		Mutex::Lock _l(_multicastMemberships_m);
-		std::vector<MulticastMembership> &memberships = _multicastMemberships[MulticastChannel(nwid,mg)];
-		for(std::vector<MulticastMembership>::iterator mm(memberships.begin());mm!=memberships.end();++mm) {
-			if (mm->first == addr) {
-				mm->second = now;
-				return;
-			}
+		Mutex::Lock _l(_lock);
+
+		for(std::map< uint64_t,std::pair< uint64_t,std::set<Address> > >::iterator g(_got.begin());g!=_got.end();) {
+			if ((now - g->second.first) > ZT_MULTICAST_MAGNET_STATE_EXPIRE)
+				_got.erase(g++);
+			else ++g;
 		}
-		memberships.push_back(MulticastMembership(addr,now));
-	}
 
-	/**
-	 * Choose peers for multicast propagation via random selection
-	 *
-	 * @param prng Random source
-	 * @param topology Topology object or mock thereof
-	 * @param nwid Network ID
-	 * @param mg Multicast group
-	 * @param originalSubmitter Original submitter of multicast message to network
-	 * @param upstream Address from which message originated, or null (0) address if none
-	 * @param bf Bloom filter, updated in place with sums of addresses in chosen peers and/or decay
-	 * @param max Maximum number of peers to pick
-	 * @param peers Array of objects of type P to fill with up to [max] peers
-	 * @param now Current timestamp
-	 * @return Number of peers actually stored in peers array
-	 * @tparam T Type of topology, which is Topology in running code or a mock in simulation
-	 * @tparam P Type of peers, which is SharedPtr<Peer> in running code or a mock in simulation (mock must behave like a pointer type)
-	 */
-	template<typename T,typename P>
-	inline unsigned int pickRandomPropagationPeers(
-		CMWC4096 &prng,
-		T &topology,
-		uint64_t nwid,
-		const MulticastGroup &mg,
-		const Address &originalSubmitter,
-		const Address &upstream,
-		MulticastBloomFilter &bf,
-		unsigned int max,
-		P *peers,
-		uint64_t now)
-	{
-		unsigned int chosen = 0;
-		Mutex::Lock _l(_multicastMemberships_m);
-		std::map< MulticastChannel,std::vector<MulticastMembership> >::iterator mm(_multicastMemberships.find(MulticastChannel(nwid,mg)));
-		if ((mm != _multicastMemberships.end())&&(!mm->second.empty())) {
-			for(unsigned int stries=0,stmax=(max*10);((stries<stmax)&&(chosen < max));++stries) {
-				MulticastMembership &m = mm->second[prng.next32() % mm->second.size()];
-				unsigned int sum = m.first.sum();
-				if (
-				     ((now - m.second) < ZT_MULTICAST_LIKE_EXPIRE)&& /* LIKE is not expired */
-				     (!bf.contains(sum))&&                           /* Not in propagation bloom */
-				     (m.first != originalSubmitter)&&                /* Not the original submitter */
-				     (m.first != upstream) ) {                       /* Not where the frame came from */
-					P peer(topology.getPeer(m.first));
-					if (peer) {
-						unsigned int chk = 0;
-						while (chk < chosen) {
-							if (peers[chk] == peer)
-								break;
-							++chk;
-						}
-						if (chk == chosen) { /* not already picked */
-							peers[chosen++] = peer;
-							bf.set(sum);
-						}
-					}
-				}
+		for(std::map< Address,_PeerInfo >::iterator pi(_peers.begin());pi!=_peers.end();) {
+			for(std::map< MulticastGroup,uint64_t >::iterator g(pi->second.groups.begin());g!=pi->second.groups.end();) {
+				if ((now - g->second) > ZT_MULTICAST_LIKE_EXPIRE)
+					pi->second.groups.erase(g++);
+				else ++g;
 			}
+			if (pi->second.groups.empty()) {
+				_proximity.erase(pi->second.proximitySlot);
+				_peers.erase(pi++);
+			} else ++pi;
 		}
-		return chosen;
 	}
 
 	/**
-	 * Choose peers for multicast propagation via implicit social switching
+	 * Pick next hops for a multicast by proximity
 	 *
-	 * @param prng Random source
-	 * @param topology Topology object or mock thereof
-	 * @param nwid Network ID
 	 * @param mg Multicast group
-	 * @param originalSubmitter Original submitter of multicast message to network
-	 * @param upstream Address from which message originated, or null (0) address if none
-	 * @param bf Bloom filter, updated in place with sums of addresses in chosen peers and/or decay
-	 * @param max Maximum number of peers to pick
-	 * @param peers Array of objects of type P to fill with up to [max] peers
-	 * @param now Current timestamp
-	 * @return Number of peers actually stored in peers array
-	 * @tparam T Type of topology, which is Topology in running code or a mock in simulation
-	 * @tparam P Type of peers, which is SharedPtr<Peer> in running code or a mock in simulation (mock must behave like a pointer type)
+	 * @param mcGuid Multicast message GUID (signer and signer unique ID)
+	 * @param nextHopFunc Function to call for each address, search stops if it returns false
 	 */
-	template<typename T,typename P>
-	inline unsigned int pickSocialPropagationPeers(
-		CMWC4096 &prng,
-		T &topology,
-		uint64_t nwid,
-		const MulticastGroup &mg,
-		const Address &originalSubmitter,
-		const Address &upstream,
-		MulticastBloomFilter &bf,
-		unsigned int max,
-		P *peers,
-		uint64_t now)
+	template<typename F>
+	inline void getNextHops(const MulticastGroup &mg,uint64_t mcGuid,F nextHopFunc)
 	{
-		typename std::set< P,_PeerPropagationPrioritySortOrder<P> > toConsider;
-
-		/* Pick up to ZT_MULTICAST_PICK_MAX_SAMPLE_SIZE peers that meet
-		 * our minimal criteria for this multicast group and place them
-		 * into a set that is sorted in descending order of time of most
-		 * recent unicast frame transfer (implicit social ordering). */
-		{
-			Mutex::Lock _l(_multicastMemberships_m);
-			std::map< MulticastChannel,std::vector<MulticastMembership> >::iterator mm(_multicastMemberships.find(MulticastChannel(nwid,mg)));
-			if ((mm != _multicastMemberships.end())&&(!mm->second.empty())) {
-				for(unsigned int stries=0,stmax=(max*10);stries<stmax;++stries) {
-					MulticastMembership &m = mm->second[prng.next32() % mm->second.size()];
-					if (
-					     ((now - m.second) < ZT_MULTICAST_LIKE_EXPIRE)&& /* LIKE is not expired */
-					     (!bf.contains(m.first.sum()))&&                 /* Not in propagation bloom */
-					     (m.first != originalSubmitter)&&                /* Not the original submitter */
-					     (m.first != upstream) ) {                       /* Not where the frame came from */
-						P peer(topology.getPeer(m.first));
-						if (peer)
-							toConsider.insert(peer); /* Consider propagating to this peer */
-					}
-				}
+		Mutex::Lock _l(_lock);
+		std::map< uint64_t,std::pair< uint64_t,std::set< Address > > > g(_got.find(mcGuid));
+		for(std::list< Address >::iterator a(_proximity.begin());a!=_proximity.end();++a) {
+			if (((g == _got.end())||(!g->second.second.count(*a)))&&(_peers.find(*a)->second.groups.count(mg))) {
+				if (!nextHopFunc(*a))
+					break;
 			}
 		}
-
-		/* The first peers in toConsider will be the "best" */
-		unsigned int chosen = 0;
-		for(typename std::set< P,_PeerPropagationPrioritySortOrder<P> >::iterator i(toConsider.begin());((i!=toConsider.end())&&(chosen < max));++i)
-			bf.set((peers[chosen++] = *i)->address().sum());
-
-		/* Tack on a supernode if we have no next hops */
-		if (!chosen) {
-			Address exclude[1];
-			exclude[0] = originalSubmitter; // if it came from a supernode, don't boomerang
-			P peer = topology.getBestSupernode(exclude,1,true);
-			if (peer)
-				peers[chosen++] = peer;
-		}
-
-		return chosen;
 	}
 
 private:
-	// Sort order for chosen propagation peers
-	template<typename P>
-	struct _PeerPropagationPrioritySortOrder
-	{
-		inline bool operator()(const P &p1,const P &p2) const
-		{
-			return (p1->lastUnicastFrame() > p2->lastUnicastFrame());
-		}
-	};
+	// GOTs by multicast GUID: time of last GOT, addresses that GOT
+	std::map< uint64_t,std::pair< uint64_t,std::set< Address > > > _got;
 
-	// ring buffer: [0] - CRC, [1] - timestamp
-	uint64_t _multicastHistory[ZT_MULTICAST_DEDUP_HISTORY_LENGTH][2];
-	volatile unsigned int _multicastHistoryPtr;
+	// Peer proximity ordering
+	std::list< Address > _proximity;
 
-	// A multicast channel, essentially a pub/sub channel. It consists of a
-	// network ID and a multicast group within that network.
-	typedef std::pair<uint64_t,MulticastGroup> MulticastChannel;
+	struct _PeerInfo
+	{
+		// Groups and time of last LIKE for each group
+		std::map< MulticastGroup,uint64_t > groups;
+
+		// Peer's slot in _proximity
+		std::list< Address >::iterator proximitySlot;
+	};
 
-	// A membership in a multicast channel, an address and time of last LIKE
-	typedef std::pair<Address,uint64_t> MulticastMembership;
+	// Time of last LIKE for each address's group subscriptions
+	std::map< Address,_PeerInfo > _peers;
 
-	// Network : MulticastGroup -> vector<Address : time of last LIKE>
-	std::map< MulticastChannel,std::vector<MulticastMembership> > _multicastMemberships;
-	Mutex _multicastMemberships_m;
+	Mutex _lock;
 };
 
 } // namespace ZeroTier
diff --git a/node/Packet.cpp b/node/Packet.cpp
index e287ae23..e6ae921d 100644
--- a/node/Packet.cpp
+++ b/node/Packet.cpp
@@ -40,8 +40,9 @@ const char *Packet::verbString(Verb v)
 		case VERB_WHOIS: return "WHOIS";
 		case VERB_RENDEZVOUS: return "RENDEZVOUS";
 		case VERB_FRAME: return "FRAME";
-		case VERB_MULTICAST_FRAME: return "MULTICAST_FRAME";
 		case VERB_MULTICAST_LIKE: return "MULTICAST_LIKE";
+		case VERB_MULTICAST_GOT: return "MULTICAST_GOT";
+		case VERB_MULTICAST_FRAME: return "MULTICAST_FRAME";
 		case VERB_NETWORK_MEMBERSHIP_CERTIFICATE: return "NETWORK_MEMBERSHIP_CERTIFICATE";
 		case VERB_NETWORK_CONFIG_REQUEST: return "NETWORK_CONFIG_REQUEST";
 		case VERB_NETWORK_CONFIG_REFRESH: return "NETWORK_CONFIG_REFRESH";
diff --git a/node/Packet.hpp b/node/Packet.hpp
index 9ddf2e6c..a52c3409 100644
--- a/node/Packet.hpp
+++ b/node/Packet.hpp
@@ -466,6 +466,7 @@ public:
 		VERB_MULTICAST_LIKE = 7,
 
 		/* Announce receipt of a multicast to propagation magnet node:
+		 *   <[8] 64-bit network ID>
 		 *   <[8] 64-bit multicast GUID>
 		 *
 		 * OK/ERROR are not generated.
diff --git a/node/RuntimeEnvironment.hpp b/node/RuntimeEnvironment.hpp
index c0b5bcbe..3a889eb0 100644
--- a/node/RuntimeEnvironment.hpp
+++ b/node/RuntimeEnvironment.hpp
@@ -42,7 +42,6 @@ class Demarc;
 class Switch;
 class Topology;
 class SysEnv;
-class Multicaster;
 class CMWC4096;
 class Service;
 class Node;
@@ -66,7 +65,6 @@ public:
 		shutdownInProgress(false),
 		log((Logger *)0),
 		prng((CMWC4096 *)0),
-		multicaster((Multicaster *)0),
 		sw((Switch *)0),
 		demarc((Demarc *)0),
 		topology((Topology *)0),
@@ -92,7 +90,6 @@ public:
 
 	Logger *log; // may be null
 	CMWC4096 *prng;
-	Multicaster *multicaster;
 	Switch *sw;
 	Demarc *demarc;
 	Topology *topology;