Ping the premier connection on each network with higher priority.

webrtc/p2p/base/p2ptransportchannel.cc

 /*
  *  Copyright 2004 The WebRTC Project Authors. All rights reserved.
  *
  *  Use of this source code is governed by a BSD-style license
  *  that can be found in the LICENSE file in the root of the source
  *  tree. An additional intellectual property rights grant can be found
  *  in the file PATENTS.  All contributing project authors may
  *  be found in the AUTHORS file in the root of the source tree.
  */
 
@@ skipping 48 matching lines @@
 }  // unnamed namespace
 
 namespace cricket {
 
 // When the socket is unwritable, we will use 10 Kbps (ignoring IP+UDP headers)
 // for pinging.  When the socket is writable, we will use only 1 Kbps because
 // we don't want to degrade the quality on a modem.  These numbers should work
 // well on a 28.8K modem, which is the slowest connection on which the voice
 // quality is reasonable at all.
 static const int PING_PACKET_SIZE = 60 * 8;
+
+// The next two ping intervals are at the channel level.
 // STRONG_PING_INTERVAL (480ms) is applied when the selected connection is both
 // writable and receiving.
 static const int STRONG_PING_INTERVAL = 1000 * PING_PACKET_SIZE / 1000;
 // WEAK_PING_INTERVAL (48ms) is applied when the selected connection is either
 // not writable or not receiving.
 const int WEAK_PING_INTERVAL = 1000 * PING_PACKET_SIZE / 10000;
 
-// Writable connections are pinged at a faster rate while stabilizing.
-const int STABILIZING_WRITABLE_CONNECTION_PING_INTERVAL = 900;  // ms
-
-// Writable connections are pinged at a slower rate once stabilized.
-const int STABLE_WRITABLE_CONNECTION_PING_INTERVAL = 2500;  // ms
+// The next two ping intervals are at the connection level.
+// Writable connections are pinged at a faster rate while the connections are
+// stabilizing or the channel is weak.
+const int WEAK_OR_STABILIZING_WRITABLE_CONNECTION_PING_INTERVAL = 900;  // ms
+// Writable connections are pinged at a slower rate once they are stabilized and
+// the channel is strongly connected.
+const int STRONG_AND_STABLE_WRITABLE_CONNECTION_PING_INTERVAL = 2500;  // ms
 
 static const int MIN_CHECK_RECEIVING_INTERVAL = 50;  // ms
 
 static const int RECEIVING_SWITCHING_DELAY = 1000;  // ms
 
 // We periodically check if any existing networks do not have any connection
 // and regather on those networks.
 static const int DEFAULT_REGATHER_ON_FAILED_NETWORKS_INTERVAL = 5 * 60 * 1000;
 
 static constexpr int DEFAULT_BACKUP_CONNECTION_PING_INTERVAL = 25 * 1000;
@@ skipping 18 matching lines @@
       sort_dirty_(false),
       remote_ice_mode_(ICEMODE_FULL),
       ice_role_(ICEROLE_UNKNOWN),
       tiebreaker_(0),
       gathering_state_(kIceGatheringNew),
       check_receiving_interval_(MIN_CHECK_RECEIVING_INTERVAL * 5),
       config_(MIN_CHECK_RECEIVING_INTERVAL * 50 /* receiving_timeout */,
               DEFAULT_BACKUP_CONNECTION_PING_INTERVAL,
               GATHER_ONCE /* continual_gathering_policy */,
               false /* prioritize_most_likely_candidate_pairs */,
-              STABLE_WRITABLE_CONNECTION_PING_INTERVAL,
+              STRONG_AND_STABLE_WRITABLE_CONNECTION_PING_INTERVAL,
               true /* presume_writable_when_fully_relayed */,
               DEFAULT_REGATHER_ON_FAILED_NETWORKS_INTERVAL,
               RECEIVING_SWITCHING_DELAY) {
   uint32_t weak_ping_interval = ::strtoul(
       webrtc::field_trial::FindFullName("WebRTC-StunInterPacketDelay").c_str(),
       nullptr, 10);
   if (weak_ping_interval) {
     weak_ping_interval_ = static_cast<int>(weak_ping_interval);
   }
 }
@@ skipping 1168 matching lines @@
   UpdateState();
 
   // Also possibly start pinging.
   // We could start pinging if:
   // * The first connection was created.
   // * ICE credentials were provided.
   // * A TCP connection became connected.
   MaybeStartPinging();
 }
 
+std::map<rtc::Network*, Connection*>

[pthatcher1, 2016/10/24 20:49:05]

You don't need to return a map. You could instead return just a list of
connections, since you can get the network from the connection.  

[honghaiz3, 2016/10/24 23:35:08]

I wonder what was the concern about using a map. A std::map is based on
red-black tree which should not be much slower than a vector if its size is
small. 
Later we will need to find the best connection based on the network, using a map
will be more readable. 
If you are worried about the cost of copying and moving the map, we can pass in
a map pointer as an argument. 

[pthatcher1, 2016/10/25 17:00:06]

I thought it might be more readable.  But what you have here now is good.

+P2PTransportChannel::GetPremierConnectionsByNetwork() const {

[pthatcher1, 2016/10/24 20:49:05]

I'm not really a fan of the word "premier", since it sounds just like "best".  I
think we need to be clear that we're getting the best connection for each
network.  So perhaps just call this method "GetBestConnectionOfEachNetwork"

[honghaiz3, 2016/10/24 23:35:08]

Done. Changed Premier to best. 

+  // |connections_| has been sorted, so the first one in the list on a given
+  // network is the premier connection, except that the selected connection
+  // is always the premier connection on the network.
+  std::map<rtc::Network*, Connection*> premier_connections_by_network;
+  if (selected_connection_) {
+    premier_connections_by_network[selected_connection_->port()->Network()] =
+        selected_connection_;
+  }
+  for (Connection* conn : connections_) {
+    rtc::Network* network = conn->port()->Network();
+    // This only inserts when the network does not exist in the map.
+    premier_connections_by_network.insert(std::make_pair(network, conn));

[pthatcher1, 2016/10/24 20:49:05]

Instead of inserting in the map, you could just iterate over the list of
connections already added and see if the network is in there.  Since the vector
will be very small, it would (2? 3?), it will most likely be faster than a map. 
And you can even allocate the number of connections to return to the number of
networks.

+  }
+  return premier_connections_by_network;
+}
+
 void P2PTransportChannel::PruneConnections() {
   // We can prune any connection for which there is a connected, writable
   // connection on the same network with better or equal priority.  We leave
   // those with better priority just in case they become writable later (at
   // which point, we would prune out the current selected connection).  We leave
   // connections on other networks because they may not be using the same
   // resources and they may represent very distinct paths over which we can
   // switch. If the |premier| connection is not connected, we may be
   // reconnecting a TCP connection and temporarily do not prune connections in
   // this network. See the big comment in CompareConnectionStates.
-
-  // Get a list of the networks that we are using.
-  std::set<rtc::Network*> networks;
-  for (const Connection* conn : connections_) {
-    networks.insert(conn->port()->Network());
-  }
-  for (rtc::Network* network : networks) {
-    Connection* premier = GetBestConnectionOnNetwork(network);
-    // Do not prune connections if the current selected connection is weak on
+  auto premier_connections_by_network = GetPremierConnectionsByNetwork();
+  for (Connection* conn : connections_) {
+    // Do not prune connections if the current premier connection is weak on
     // this network. Otherwise, it may delete connections prematurely.
-    if (!premier || premier->weak()) {
-      continue;
-    }
-
-    for (Connection* conn : connections_) {
-      if ((conn != premier) && (conn->port()->Network() == network) &&
-          (CompareConnectionCandidates(premier, conn) >= 0)) {
-        conn->Prune();
-      }
+    Connection* premier =
+        premier_connections_by_network[conn->port()->Network()];

[pthatcher1, 2016/10/24 20:49:05]

If GetBestConnectionForEachNetwork returns a vector, you can just test if the
connection is in the vector, which should be very fast.  And the variable could
be "bool best_for_this_network".

[honghaiz3, 2016/10/24 23:35:09]

Actually that is not enough. We will need to find the best connection on the
same network and than compare the best connection and this connection. If this
connection has higher cost or lower priority, then prune it. To find the best
connection on the same network, we will need to iterate over the list of best
connections if it is represented by a vector. This is primary place where I
think map would be more readable than a vector. 

[pthatcher1, 2016/10/25 17:00:06]

OK, I see the logic now. 

+    if (premier && conn != premier && !premier->weak() &&
+        CompareConnectionCandidates(premier, conn) >= 0) {
+      conn->Prune();
     }
   }
 }
 
 // Change the selected connection, and let listeners know.
 void P2PTransportChannel::SwitchSelectedConnection(Connection* conn) {
   // Note: if conn is NULL, the previous |selected_connection_| has been
   // destroyed, so don't use it.
   Connection* old_selected_connection = selected_connection_;
   selected_connection_ = conn;
@@ skipping 117 matching lines @@
 bool P2PTransportChannel::ReadyToSend(Connection* connection) const {
   // Note that we allow sending on an unreliable connection, because it's
   // possible that it became unreliable simply due to bad chance.
   // So this shouldn't prevent attempting to send media.
   return connection != nullptr &&
          (connection->writable() ||
           connection->write_state() == Connection::STATE_WRITE_UNRELIABLE ||
           PresumedWritable(connection));
 }
 
-// If we have a selected connection, return it, otherwise return top one in the
-// list (later we will mark it best).
-Connection* P2PTransportChannel::GetBestConnectionOnNetwork(
-    rtc::Network* network) const {
-  // If the selected connection is on this network, then it wins.
-  if (selected_connection_ &&
-      (selected_connection_->port()->Network() == network)) {
-    return selected_connection_;
-  }
-
-  // Otherwise, we return the top-most in sorted order.
-  for (size_t i = 0; i < connections_.size(); ++i) {
-    if (connections_[i]->port()->Network() == network) {
-      return connections_[i];
-    }
-  }
-
-  return NULL;
-}
-
 // Handle any queued up requests
 void P2PTransportChannel::OnMessage(rtc::Message *pmsg) {
   switch (pmsg->message_id) {
     case MSG_SORT_AND_UPDATE_STATE:
       SortConnectionsAndUpdateState();
       break;
     case MSG_CHECK_AND_PING:
       OnCheckAndPing();
       break;
     case MSG_REGATHER_ON_FAILED_NETWORKS:
@@ skipping 85 matching lines @@
   if (!conn->writable()) {
     return true;
   }
 
   // Ping writable, active connections if it's been long enough since the last
   // ping.
   int ping_interval = CalculateActiveWritablePingInterval(conn, now);
   return (now >= conn->last_ping_sent() + ping_interval);
 }
 
-bool P2PTransportChannel::IsSelectedConnectionPingable(int64_t now) {
-  if (!selected_connection_ || !selected_connection_->connected() ||
-      !selected_connection_->writable()) {
+// TODO(honghaiz): Re-thinking the way of prioritizing connections for ping
+// requests.
+Connection* P2PTransportChannel::FindBestPremierConnectionToPing(int64_t now) {

[pthatcher1, 2016/10/24 20:49:05]

Why not just put all of this logic into FindNextPingableConnection?  That would
avoid this weird name (FindBestPremierX) which sounds like FindBestBestX.

[honghaiz3, 2016/10/24 23:35:09]

Done.

+  // If the selected connection is pingable, select it to ping.
+  if (IsPremierConnectionPingable(selected_connection_, now)) {
+    return selected_connection_;
+  }
+  // If the selected connection is strongly connected, don't bother to ping

[pthatcher1, 2016/10/24 20:49:05]

bother to ping => bother pinging

[honghaiz3, 2016/10/24 23:35:08]

Done.

+  // premier connections on other networks at a higher priority. This prevents
+  // a few premier connections from saturating all transmission slots for ping
+  // and also prevents the backup connections from being pinged frequently.
+  if (!weak()) {
+    return nullptr;
+  }
+
+  // Otherwise, find the premier connection that has not been pinged for the
+  // longest time.
+  auto premier_connections_by_network = GetPremierConnectionsByNetwork();
+  Connection* oldest_pingable_premier_connection = nullptr;
+  for (auto kv : premier_connections_by_network) {

[pthatcher1, 2016/10/24 20:49:05]

If GetBestConnectionForEachNetwork returned a vector, you just need to do
std::max(best_connection_for_each_network) with a proper "old" metric.

+    Connection* conn = kv.second;
+    if (conn == nullptr || conn == selected_connection_) {
+      continue;
+    }
+    if (IsPremierConnectionPingable(conn, now) &&
+        (!oldest_pingable_premier_connection ||
+         conn->last_ping_sent() <
+             oldest_pingable_premier_connection->last_ping_sent())) {
+      oldest_pingable_premier_connection = conn;
+    }
+  }
+  return oldest_pingable_premier_connection;
+}
+
+bool P2PTransportChannel::IsPremierConnectionPingable(

[pthatcher1, 2016/10/24 20:49:05]

Can't this just be IsConnectionPingable?

[honghaiz3, 2016/10/24 23:35:09]

No. In this method, it is critical to ping connection once every XX (1 or 2.5)
seconds. Otherwise, the set of best connections will utilize all slots for ping
transmissions. 

[pthatcher1, 2016/10/25 17:00:06]

What I mean is that since you're already passing in a connection, there's
nothing about the method specific to "premier" connections.  It's logic that can
apply to any connection.  

The logic in the method really "a connection is pingable if we can send a ping
and we haven't sent a ping very recently", which seems to apply to any
connection.

[Taylor Brandstetter, 2016/10/25 18:29:28]

Except there's a completely different method, "IsPingable" for determining if a
"normal" connection should be pinged. This method is really "Should this premier
connection be pinged in place of a normal connection, since the channel is
currently weakly connected?"

When I mentioned that this logic is getting confusing, this is the kind of thing
I meant. It's spread across many methods and it's hard to tell how an individual
method is used given just its name.

[honghaiz3, 2016/10/25 22:01:24]

IsPremierConnectionPingable (now it is called
IsPerNetworkBestConnectionPingable) is specifically used for
PerNetworkBestConnections. IsPingable is used for a normal connection everywhere
else. We have to differentiate these two as I explained, similar to the
differentiation we had for IsSelectedConnectionPingable vs IsPingable. 

[pthatcher1, 2016/10/26 22:37:50]

I agree with Taylor that this is confusing.  IsPingable has clear meaning. 
ShouldBePingedWithHigherPriorityBecauseWereWeaklyConnected is more awkward.  

Let's step back a bit and realize that this is all just to implement 
FindNextPingableConnection().    In fact we now have several methods which just
exist to implement FindNextPingableConnection:

FindConnectionToPing
FindOldestConnectionNeedingTriggeredCheck
SelectMostPingableConnection
FindBestPremierConnectionToPing
IsPremierConnectionPingable


Perhaps we should rethink how we want FindNextPingableConnection to work. 
Perhaps we don't need all these separate methods after all and can simplify
between them.  

[honghaiz3, 2016/10/27 19:20:58]

FindNextPingableConnection has the following steps in order:
1. If the selected connection is pingable, ping it. 
2. If weak, and the premier connection (PerNetworkBestConnection) is pingable,
ping it 
3. If there is ping needed for triggered check, then ping it. 
4. Ping every connection (using normal order or finding the connection that is
most likely to work). 
Only step 2 (and it is sort of similar to step 1) was added in this CL. 
I don't see an easy way to simplify them without behavior changing. Maybe we can
do something like assigning each connection a ping score and then find the one
with the highest score. But we will still need to decide the score based on all
four steps above. Because we have the 64 bit timestamp as part of the score, we
will need something like tuple to represent the score. 
We can potentially merge some steps (possibly 3 and 4) with some behavior
changing. But if we just want to merge 3 and 4, we should leave it in a separate
CL.  
We can discuss more on this. 

[Taylor Brandstetter, 2016/10/27 21:04:54]

I had an idea similar to the "ping score" concept. Basically, break things apart
into the following phases:

1. For each connection, check if it's eligible to be pinged (based on state,
type of connection, when it was last pinged, etc.).
2. Use a sorting function to sort the eligible connections according to how
badly we want to ping them.
3. Ping the topmost one.

However, any of the refactoring being discussed would only make sense in a
standalone CL, so I think this is fine as-is; it at least matches the current
conventions.

[honghaiz3, 2016/10/27 21:45:09]

Note a few details:
1. The eligibility of a connection (i.e. Pingable) may be different depending on
the stage. For example, as a premier connection or selected connection, it may
not be pingable if a connection was pinged in the past second. This prevents a
few premier connections including the selected connection from saturating all
transmission slots. But as a normal connection, it is pingable as long as the
current selected connection is weak so that it can use all allocated
transmission slots to find a better connection when the present connection is
weak. 
2. If our goal is to find the topmost connection, we don't need sort for this
and for finding the selected connection. 
Using std::max/min should be sufficient.  
These details can be further discussed in a separate CL. 

+    Connection* premier_connection,
+    int64_t now) {
+  if (!premier_connection || !premier_connection->connected() ||
+      !premier_connection->writable()) {
     return false;
   }
 
-  int interval = CalculateActiveWritablePingInterval(selected_connection_, now);
-  return selected_connection_->last_ping_sent() + interval <= now;
+  int interval = CalculateActiveWritablePingInterval(premier_connection, now);
+  return premier_connection->last_ping_sent() + interval <= now;
 }
 
 int P2PTransportChannel::CalculateActiveWritablePingInterval(
     const Connection* conn,
     int64_t now) const {
   // Ping each connection at a higher rate at least
   // MIN_PINGS_AT_WEAK_PING_INTERVAL times.
   if (conn->num_pings_sent() < MIN_PINGS_AT_WEAK_PING_INTERVAL) {
     return weak_ping_interval_;
   }
 
   int stable_interval = config_.stable_writable_connection_ping_interval;
-  int stablizing_interval =
-      std::min(stable_interval, STABILIZING_WRITABLE_CONNECTION_PING_INTERVAL);
-
-  return conn->stable(now) ? stable_interval : stablizing_interval;
+  int weak_or_stablizing_interval = std::min(
+      stable_interval, WEAK_OR_STABILIZING_WRITABLE_CONNECTION_PING_INTERVAL);
+  // If the channel is weak or the connection is not stable yet, use the
+  // weak_or_stablizing_interval.
+  return (!weak() && conn->stable(now)) ? stable_interval
+                                        : weak_or_stablizing_interval;
 }
 
 // Returns the next pingable connection to ping.  This will be the oldest
 // pingable connection unless we have a connected, writable connection that is
 // past the writable ping interval. When reconnecting a TCP
 // connection, the selected connection is disconnected, although still WRITABLE
 // while reconnecting. The newly created connection should be selected as the
 // ping target to become writable instead. See the big comment in
 // CompareConnectionStates.
 Connection* P2PTransportChannel::FindNextPingableConnection() {
   int64_t now = rtc::TimeMillis();
-  Connection* conn_to_ping = nullptr;
-  if (IsSelectedConnectionPingable(now)) {
-    conn_to_ping = selected_connection_;
-  } else {
+  Connection* conn_to_ping = FindBestPremierConnectionToPing(now);
+  if (!conn_to_ping) {
     conn_to_ping = FindConnectionToPing(now);
   }
   return conn_to_ping;
 }
 
 void P2PTransportChannel::MarkConnectionPinged(Connection* conn) {
   if (conn && pinged_connections_.insert(conn).second) {
     unpinged_connections_.erase(conn);
   }
 }
@@ skipping 94 matching lines @@
   // use it.
 
   // Remove this connection from the list.
   std::vector<Connection*>::iterator iter =
       std::find(connections_.begin(), connections_.end(), connection);
   ASSERT(iter != connections_.end());
   pinged_connections_.erase(*iter);
   unpinged_connections_.erase(*iter);
   connections_.erase(iter);
 
-  LOG_J(LS_INFO, this) << "Removed connection ("
-    << static_cast<int>(connections_.size()) << " remaining)";
+  LOG_J(LS_INFO, this) << "Removed connection " << std::hex << connection
+                       << std::dec << " (" << connections_.size()
+                       << " remaining)";
 
   // If this is currently the selected connection, then we need to pick a new
   // one. The call to SortConnectionsAndUpdateState will pick a new one. It
   // looks at the current selected connection in order to avoid switching
   // between fairly similar ones. Since this connection is no longer an option,
   // we can just set selected to nullptr and re-choose a best assuming that
   // there was no selected connection.
   if (selected_connection_ == connection) {
     LOG(LS_INFO) << "Selected connection destroyed. Will choose a new one.";
     SwitchSelectedConnection(nullptr);
@@ skipping 107 matching lines @@
 }
 
 void P2PTransportChannel::OnReadyToSend(Connection* connection) {
   if (connection == selected_connection_ && writable()) {
     SignalReadyToSend(this);
   }
 }
 
 // Find "triggered checks".  We ping first those connections that have
 // received a ping but have not sent a ping since receiving it
-// (last_received_ping > last_sent_ping).  But we shouldn't do
+// (last_ping_received > last_ping_sent).  But we shouldn't do
 // triggered checks if the connection is already writable.
 Connection* P2PTransportChannel::FindOldestConnectionNeedingTriggeredCheck(
     int64_t now) {
   Connection* oldest_needing_triggered_check = nullptr;
   for (auto conn : connections_) {
     if (!IsPingable(conn, now)) {
       continue;
     }
     bool needs_triggered_check =
         (!conn->writable() &&
@@ skipping 95 matching lines @@
 
   // During the initial state when nothing has been pinged yet, return the first
   // one in the ordered |connections_|.
   return *(std::find_if(connections_.begin(), connections_.end(),
                         [conn1, conn2](Connection* conn) {
                           return conn == conn1 || conn == conn2;
                         }));
 }
 
 }  // namespace cricket