From 770fbaf4b276f9d4dd616941ed7460398f70c634 Mon Sep 17 00:00:00 2001 From: Adam Ierymenko Date: Sat, 21 Sep 2013 16:46:00 -0400 Subject: New multicast algorithm work in progress... --- node/Constants.hpp | 25 +-- node/Multicaster.hpp | 361 ++++++++++---------------------------------- node/Packet.cpp | 3 +- node/Packet.hpp | 1 + node/RuntimeEnvironment.hpp | 3 - 5 files changed, 87 insertions(+), 306 deletions(-) (limited to 'node') diff --git a/node/Constants.hpp b/node/Constants.hpp index 926bac6f..a46937ed 100644 --- a/node/Constants.hpp +++ b/node/Constants.hpp @@ -230,26 +230,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 * @@ -264,6 +244,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 */ 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 #include -#include -#include #include #include -#include #include -#include +#include +#include #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 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::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
> &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 &memberships = _multicastMemberships[MulticastChannel(nwid,mg)]; - for(std::vector::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
> >::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 in running code or a mock in simulation (mock must behave like a pointer type) - */ - template - 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 >::iterator mm(_multicastMemberships.find(MulticastChannel(nwid,mg))); - if ((mm != _multicastMemberships.end())&&(!mm->second.empty())) { - for(unsigned int stries=0,stmax=(max*10);((striessecond[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 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 - 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 + inline void getNextHops(const MulticastGroup &mg,uint64_t mcGuid,F nextHopFunc) { - typename std::set< P,_PeerPropagationPrioritySortOrder

> 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 >::iterator mm(_multicastMemberships.find(MulticastChannel(nwid,mg))); - if ((mm != _multicastMemberships.end())&&(!mm->second.empty())) { - for(unsigned int stries=0,stmax=(max*10);striessecond[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

>::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 - 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 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 MulticastMembership; + // Time of last LIKE for each address's group subscriptions + std::map< Address,_PeerInfo > _peers; - // Network : MulticastGroup -> vector

- std::map< MulticastChannel,std::vector > _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; -- cgit v1.2.3