From 4c455876f92c629b015cbfc6d904dc8c2d12eca2 Mon Sep 17 00:00:00 2001 From: Adam Ierymenko Date: Tue, 19 Apr 2016 09:22:51 -0700 Subject: Revise peer path weighting to always prioritize cluster-optimal paths. --- node/IncomingPacket.cpp | 23 +++++++++++++--- node/Packet.cpp | 4 +-- node/Packet.hpp | 4 +-- node/Path.hpp | 71 ++++++++++++++++++++++++++++++++----------------- node/Peer.cpp | 11 +++++--- node/Peer.hpp | 44 ++++++++++++++++++++---------- 6 files changed, 107 insertions(+), 50 deletions(-) diff --git a/node/IncomingPacket.cpp b/node/IncomingPacket.cpp index 8c3aac9a..e4427f06 100644 --- a/node/IncomingPacket.cpp +++ b/node/IncomingPacket.cpp @@ -70,9 +70,8 @@ bool IncomingPacket::tryDecode(const RuntimeEnvironment *RR,bool deferred) return true; } - //TRACE("<< %s from %s(%s)",Packet::verbString(v),sourceAddress.toString().c_str(),_remoteAddress.toString().c_str()); - const Packet::Verb v = verb(); + //TRACE("<< %s from %s(%s)",Packet::verbString(v),sourceAddress.toString().c_str(),_remoteAddress.toString().c_str()); switch(v) { //case Packet::VERB_NOP: default: // ignore unknown verbs, but if they pass auth check they are "received" @@ -933,7 +932,15 @@ bool IncomingPacket::_doPUSH_DIRECT_PATHS(const RuntimeEnvironment *RR,const Sha switch(addrType) { case 4: { InetAddress a(field(ptr,4),4,at(ptr + 4)); - if ( ((flags & ZT_PUSH_DIRECT_PATHS_FLAG_FORGET_PATH) == 0) && ( ((flags & ZT_PUSH_DIRECT_PATHS_FLAG_CLUSTER_REDIRECT) != 0) || (!peer->hasActivePathTo(now,a)) ) && (RR->node->shouldUsePathForZeroTierTraffic(_localAddress,a)) ) { + + bool redundant = false; + if ((flags & ZT_PUSH_DIRECT_PATHS_FLAG_CLUSTER_REDIRECT) != 0) { + peer->setClusterOptimalPathForAddressFamily(a); + } else { + redundant = peer->hasActivePathTo(now,a); + } + + if ( ((flags & ZT_PUSH_DIRECT_PATHS_FLAG_FORGET_PATH) == 0) && (!redundant) && (RR->node->shouldUsePathForZeroTierTraffic(_localAddress,a)) ) { if (++countPerScope[(int)a.ipScope()][0] <= ZT_PUSH_DIRECT_PATHS_MAX_PER_SCOPE_AND_FAMILY) { TRACE("attempting to contact %s at pushed direct path %s",peer->address().toString().c_str(),a.toString().c_str()); peer->sendHELLO(InetAddress(),a,now); @@ -944,7 +951,15 @@ bool IncomingPacket::_doPUSH_DIRECT_PATHS(const RuntimeEnvironment *RR,const Sha } break; case 6: { InetAddress a(field(ptr,16),16,at(ptr + 16)); - if ( ((flags & ZT_PUSH_DIRECT_PATHS_FLAG_FORGET_PATH) == 0) && ( ((flags & ZT_PUSH_DIRECT_PATHS_FLAG_CLUSTER_REDIRECT) != 0) || (!peer->hasActivePathTo(now,a)) ) && (RR->node->shouldUsePathForZeroTierTraffic(_localAddress,a)) ) { + + bool redundant = false; + if ((flags & ZT_PUSH_DIRECT_PATHS_FLAG_CLUSTER_REDIRECT) != 0) { + peer->setClusterOptimalPathForAddressFamily(a); + } else { + redundant = peer->hasActivePathTo(now,a); + } + + if ( ((flags & ZT_PUSH_DIRECT_PATHS_FLAG_FORGET_PATH) == 0) && (!redundant) && (RR->node->shouldUsePathForZeroTierTraffic(_localAddress,a)) ) { if (++countPerScope[(int)a.ipScope()][1] <= ZT_PUSH_DIRECT_PATHS_MAX_PER_SCOPE_AND_FAMILY) { TRACE("attempting to contact %s at pushed direct path %s",peer->address().toString().c_str(),a.toString().c_str()); peer->sendHELLO(InetAddress(),a,now); diff --git a/node/Packet.cpp b/node/Packet.cpp index dae9ef5a..3330a927 100644 --- a/node/Packet.cpp +++ b/node/Packet.cpp @@ -22,7 +22,7 @@ namespace ZeroTier { const unsigned char Packet::ZERO_KEY[32] = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 }; -#ifdef ZT_TRACE +//#ifdef ZT_TRACE const char *Packet::verbString(Verb v) throw() @@ -68,7 +68,7 @@ const char *Packet::errorString(ErrorCode e) return "(unknown)"; } -#endif // ZT_TRACE +//#endif // ZT_TRACE void Packet::armor(const void *key,bool encryptPayload) { diff --git a/node/Packet.hpp b/node/Packet.hpp index 5c2e64c4..52be4f64 100644 --- a/node/Packet.hpp +++ b/node/Packet.hpp @@ -1052,12 +1052,12 @@ public: ERROR_UNWANTED_MULTICAST = 8 }; -#ifdef ZT_TRACE +//#ifdef ZT_TRACE static const char *verbString(Verb v) throw(); static const char *errorString(ErrorCode e) throw(); -#endif +//#endif template Packet(const Buffer &b) : diff --git a/node/Path.hpp b/node/Path.hpp index cb7622d3..c039f9db 100644 --- a/node/Path.hpp +++ b/node/Path.hpp @@ -31,13 +31,21 @@ /** * Flag indicating that this path is suboptimal * - * This is used in cluster mode to indicate that the peer has been directed - * to a better path. This path can continue to be used but shouldn't be kept - * or advertised to other cluster members. Not used if clustering is not - * built and enabled. + * Clusters set this flag on remote paths if GeoIP or other routing decisions + * indicate that a peer should be handed off to another cluster member. */ #define ZT_PATH_FLAG_CLUSTER_SUBOPTIMAL 0x0001 +/** + * Flag indicating that this path is optimal + * + * Peers set this flag on paths that are pushed by a cluster and indicated as + * optimal. A second flag is needed since we want to prioritize cluster optimal + * paths and de-prioritize sub-optimal paths and for new paths we don't know + * which one they are. So we want a trinary state: optimal, suboptimal, unknown. + */ +#define ZT_PATH_FLAG_CLUSTER_OPTIMAL 0x0002 + /** * Maximum return value of preferenceRank() */ @@ -176,17 +184,39 @@ public: */ inline InetAddress::IpScope ipScope() const throw() { return _ipScope; } + /** + * @param f Valuve of ZT_PATH_FLAG_CLUSTER_SUBOPTIMAL and inverse of ZT_PATH_FLAG_CLUSTER_OPTIMAL (both are changed) + */ + inline void setClusterSuboptimal(bool f) + { + if (f) { + _flags = (_flags | ZT_PATH_FLAG_CLUSTER_SUBOPTIMAL) & ~ZT_PATH_FLAG_CLUSTER_OPTIMAL; + } else { + _flags = (_flags | ZT_PATH_FLAG_CLUSTER_OPTIMAL) & ~ZT_PATH_FLAG_CLUSTER_SUBOPTIMAL; + } + } + + /** + * @return True if ZT_PATH_FLAG_CLUSTER_SUBOPTIMAL is set + */ + inline bool isClusterSuboptimal() const { return ((_flags & ZT_PATH_FLAG_CLUSTER_SUBOPTIMAL) != 0); } + + /** + * @return True if ZT_PATH_FLAG_CLUSTER_OPTIMAL is set + */ + inline bool isClusterOptimal() const { return ((_flags & ZT_PATH_FLAG_CLUSTER_OPTIMAL) != 0); } + /** * @return Preference rank, higher == better (will be less than 255) */ inline unsigned int preferenceRank() const throw() { - // First, since the scope enum values in InetAddress.hpp are in order of - // use preference rank, we take that. Then we multiple by two, yielding - // a sequence like 0, 2, 4, 6, etc. Then if it's IPv6 we add one. This - // makes IPv6 addresses of a given scope outrank IPv4 addresses of the - // same scope -- e.g. 1 outranks 0. This makes us prefer IPv6, but not - // if the address scope/class is of a fundamentally lower rank. + /* First, since the scope enum values in InetAddress.hpp are in order of + * use preference rank, we take that. Then we multiple by two, yielding + * a sequence like 0, 2, 4, 6, etc. Then if it's IPv6 we add one. This + * makes IPv6 addresses of a given scope outrank IPv4 addresses of the + * same scope -- e.g. 1 outranks 0. This makes us prefer IPv6, but not + * if the address scope/class is of a fundamentally lower rank. */ return ( ((unsigned int)_ipScope << 1) | (unsigned int)(_addr.ss_family == AF_INET6) ); } @@ -199,8 +229,13 @@ public: * received something) scaled/corrected by the preference rank within the * ping keepalive window. That way higher ranking paths are preferred but * not to the point of overriding timeouts and choosing potentially dead - * paths. */ - return (_lastReceived + (preferenceRank() * (ZT_PEER_DIRECT_PING_DELAY / ZT_PATH_MAX_PREFERENCE_RANK))); + * paths. Finally we increase the score for known to be cluster optimal + * paths and decrease it for paths known to be suboptimal. */ + uint64_t score = _lastReceived + ZT_PEER_DIRECT_PING_DELAY; // make sure it's never less than ZT_PEER_DIRECT_PING_DELAY to prevent integer underflow + score += preferenceRank() * (ZT_PEER_DIRECT_PING_DELAY / ZT_PATH_MAX_PREFERENCE_RANK); + score += (uint64_t)(_flags & ZT_PATH_FLAG_CLUSTER_OPTIMAL) * (ZT_PEER_DIRECT_PING_DELAY / 2); // /2 because CLUSTER_OPTIMAL is flag 0x0002 + score -= (uint64_t)(_flags & ZT_PATH_FLAG_CLUSTER_SUBOPTIMAL) * ZT_PEER_DIRECT_PING_DELAY; + return score; } /** @@ -259,18 +294,6 @@ public: return false; } -#ifdef ZT_ENABLE_CLUSTER - /** - * @param f New value of ZT_PATH_FLAG_CLUSTER_SUBOPTIMAL - */ - inline void setClusterSuboptimal(bool f) { _flags = ((f) ? (_flags | ZT_PATH_FLAG_CLUSTER_SUBOPTIMAL) : (_flags & (~ZT_PATH_FLAG_CLUSTER_SUBOPTIMAL))); } - - /** - * @return True if ZT_PATH_FLAG_CLUSTER_SUBOPTIMAL is set - */ - inline bool isClusterSuboptimal() const { return ((_flags & ZT_PATH_FLAG_CLUSTER_SUBOPTIMAL) != 0); } -#endif - /** * @return Current path probation count (for dead path detect) */ diff --git a/node/Peer.cpp b/node/Peer.cpp index 6c935e0a..ce4401cd 100644 --- a/node/Peer.cpp +++ b/node/Peer.cpp @@ -144,14 +144,17 @@ void Peer::received( if (np < ZT_MAX_PEER_NETWORK_PATHS) { slot = &(_paths[np++]); } else { - uint64_t slotLRmin = 0xffffffffffffffffULL; + uint64_t slotWorstScore = 0xffffffffffffffffULL; for(unsigned int p=0;p