diff --git a/services/core/java/com/android/server/ConnectivityService.java b/services/core/java/com/android/server/ConnectivityService.java
index b3b1722..175c33b 100644
--- a/services/core/java/com/android/server/ConnectivityService.java
+++ b/services/core/java/com/android/server/ConnectivityService.java
@@ -155,7 +155,6 @@
 import android.security.KeyStore;
 import android.telephony.TelephonyManager;
 import android.text.TextUtils;
-import android.util.ArrayMap;
 import android.util.ArraySet;
 import android.util.LocalLog;
 import android.util.Log;
@@ -195,6 +194,7 @@
 import com.android.server.connectivity.NetworkDiagnostics;
 import com.android.server.connectivity.NetworkNotificationManager;
 import com.android.server.connectivity.NetworkNotificationManager.NotificationType;
+import com.android.server.connectivity.NetworkRanker;
 import com.android.server.connectivity.PermissionMonitor;
 import com.android.server.connectivity.ProxyTracker;
 import com.android.server.connectivity.Vpn;
@@ -231,6 +231,7 @@
 import java.util.Objects;
 import java.util.Set;
 import java.util.SortedSet;
+import java.util.StringJoiner;
 import java.util.TreeSet;
 import java.util.concurrent.atomic.AtomicInteger;
 
@@ -579,6 +580,7 @@
     final ConnectivityDiagnosticsHandler mConnectivityDiagnosticsHandler;
 
     private final DnsManager mDnsManager;
+    private final NetworkRanker mNetworkRanker;
 
     private boolean mSystemReady;
     private Intent mInitialBroadcast;
@@ -727,9 +729,9 @@
         private void maybeLogBroadcast(NetworkAgentInfo nai, DetailedState state, int type,
                 boolean isDefaultNetwork) {
             if (DBG) {
-                log("Sending " + state +
-                        " broadcast for type " + type + " " + nai.name() +
-                        " isDefaultNetwork=" + isDefaultNetwork);
+                log("Sending " + state
+                        + " broadcast for type " + type + " " + nai.toShortString()
+                        + " isDefaultNetwork=" + isDefaultNetwork);
             }
         }
 
@@ -809,14 +811,6 @@
             }
         }
 
-        private String naiToString(NetworkAgentInfo nai) {
-            String name = nai.name();
-            String state = (nai.networkInfo != null) ?
-                    nai.networkInfo.getState() + "/" + nai.networkInfo.getDetailedState() :
-                    "???/???";
-            return name + " " + state;
-        }
-
         public void dump(IndentingPrintWriter pw) {
             pw.println("mLegacyTypeTracker:");
             pw.increaseIndent();
@@ -831,7 +825,7 @@
                 for (int type = 0; type < mTypeLists.length; type++) {
                     if (mTypeLists[type] == null || mTypeLists[type].isEmpty()) continue;
                     for (NetworkAgentInfo nai : mTypeLists[type]) {
-                        pw.println(type + " " + naiToString(nai));
+                        pw.println(type + " " + nai.toShortString());
                     }
                 }
             }
@@ -966,6 +960,7 @@
 
         mMetricsLog = logger;
         mDefaultRequest = createDefaultInternetRequestForTransport(-1, NetworkRequest.Type.REQUEST);
+        mNetworkRanker = new NetworkRanker();
         NetworkRequestInfo defaultNRI = new NetworkRequestInfo(null, mDefaultRequest, new Binder());
         mNetworkRequests.put(mDefaultRequest, defaultNRI);
         mNetworkRequestInfoLogs.log("REGISTER " + defaultNRI);
@@ -2786,7 +2781,7 @@
                         nai.everCaptivePortalDetected |= visible;
                         if (nai.lastCaptivePortalDetected &&
                             Settings.Global.CAPTIVE_PORTAL_MODE_AVOID == getCaptivePortalMode()) {
-                            if (DBG) log("Avoiding captive portal network: " + nai.name());
+                            if (DBG) log("Avoiding captive portal network: " + nai.toShortString());
                             nai.asyncChannel.sendMessage(
                                     NetworkAgent.CMD_PREVENT_AUTOMATIC_RECONNECT);
                             teardownUnneededNetwork(nai);
@@ -2845,7 +2840,7 @@
                 final String logMsg = !TextUtils.isEmpty(redirectUrl)
                         ? " with redirect to " + redirectUrl
                         : "";
-                log(nai.name() + " validation " + (valid ? "passed" : "failed") + logMsg);
+                log(nai.toShortString() + " validation " + (valid ? "passed" : "failed") + logMsg);
             }
             if (valid != nai.lastValidated) {
                 if (wasDefault) {
@@ -3126,13 +3121,13 @@
         //    one lingered request, start lingering.
         nai.updateLingerTimer();
         if (nai.isLingering() && nai.numForegroundNetworkRequests() > 0) {
-            if (DBG) log("Unlingering " + nai.name());
+            if (DBG) log("Unlingering " + nai.toShortString());
             nai.unlinger();
             logNetworkEvent(nai, NetworkEvent.NETWORK_UNLINGER);
         } else if (unneeded(nai, UnneededFor.LINGER) && nai.getLingerExpiry() > 0) {
             if (DBG) {
                 final int lingerTime = (int) (nai.getLingerExpiry() - now);
-                log("Lingering " + nai.name() + " for " + lingerTime + "ms");
+                log("Lingering " + nai.toShortString() + " for " + lingerTime + "ms");
             }
             nai.linger();
             logNetworkEvent(nai, NetworkEvent.NETWORK_LINGER);
@@ -3196,7 +3191,7 @@
     private void disconnectAndDestroyNetwork(NetworkAgentInfo nai) {
         ensureRunningOnConnectivityServiceThread();
         if (DBG) {
-            log(nai.name() + " got DISCONNECTED, was satisfying " + nai.numNetworkRequests());
+            log(nai.toShortString() + " disconnected, was satisfying " + nai.numNetworkRequests());
         }
         // Clear all notifications of this network.
         mNotifier.clearNotification(nai.network.netId);
@@ -3254,7 +3249,7 @@
             mDefaultNetworkNai = null;
             updateDataActivityTracking(null /* newNetwork */, nai);
             notifyLockdownVpn(nai);
-            ensureNetworkTransitionWakelock(nai.name());
+            ensureNetworkTransitionWakelock(nai.toShortString());
         }
         mLegacyTypeTracker.remove(nai, wasDefault);
         if (!nai.networkCapabilities.hasTransport(TRANSPORT_VPN)) {
@@ -3477,8 +3472,8 @@
                 boolean wasBackgroundNetwork = nai.isBackgroundNetwork();
                 nai.removeRequest(nri.request.requestId);
                 if (VDBG || DDBG) {
-                    log(" Removing from current network " + nai.name() +
-                            ", leaving " + nai.numNetworkRequests() + " requests.");
+                    log(" Removing from current network " + nai.toShortString()
+                            + ", leaving " + nai.numNetworkRequests() + " requests.");
                 }
                 // If there are still lingered requests on this network, don't tear it down,
                 // but resume lingering instead.
@@ -3487,7 +3482,7 @@
                     notifyNetworkLosing(nai, now);
                 }
                 if (unneeded(nai, UnneededFor.TEARDOWN)) {
-                    if (DBG) log("no live requests for " + nai.name() + "; disconnecting");
+                    if (DBG) log("no live requests for " + nai.toShortString() + "; disconnecting");
                     teardownUnneededNetwork(nai);
                 } else {
                     wasKept = true;
@@ -3822,7 +3817,7 @@
         pw.increaseIndent();
         for (NetworkAgentInfo nai : networksSortedById()) {
             if (nai.avoidUnvalidated) {
-                pw.println(nai.name());
+                pw.println(nai.toShortString());
             }
         }
         pw.decreaseIndent();
@@ -3934,7 +3929,7 @@
 
     private void handleNetworkUnvalidated(NetworkAgentInfo nai) {
         NetworkCapabilities nc = nai.networkCapabilities;
-        if (DBG) log("handleNetworkUnvalidated " + nai.name() + " cap=" + nc);
+        if (DBG) log("handleNetworkUnvalidated " + nai.toShortString() + " cap=" + nc);
 
         if (!nc.hasTransport(NetworkCapabilities.TRANSPORT_WIFI)) {
             return;
@@ -5348,7 +5343,7 @@
                 detail = reason;
             }
             log(String.format("updateSignalStrengthThresholds: %s, sending %s to %s",
-                    detail, Arrays.toString(thresholdsArray.toArray()), nai.name()));
+                    detail, Arrays.toString(thresholdsArray.toArray()), nai.toShortString()));
         }
 
         nai.asyncChannel.sendMessage(
@@ -6272,9 +6267,9 @@
         // newLp is already a defensive copy.
         newLp.ensureDirectlyConnectedRoutes();
         if (VDBG || DDBG) {
-            log("Update of LinkProperties for " + nai.name() +
-                    "; created=" + nai.created +
-                    "; everConnected=" + nai.everConnected);
+            log("Update of LinkProperties for " + nai.toShortString()
+                    + "; created=" + nai.created
+                    + "; everConnected=" + nai.everConnected);
         }
         updateLinkProperties(nai, newLp, new LinkProperties(nai.linkProperties));
     }
@@ -6444,7 +6439,7 @@
             loge("Unknown NetworkAgentInfo in handleLingerComplete");
             return;
         }
-        if (DBG) log("handleLingerComplete for " + oldNetwork.name());
+        if (DBG) log("handleLingerComplete for " + oldNetwork.toShortString());
 
         // If we get here it means that the last linger timeout for this network expired. So there
         // must be no other active linger timers, and we must stop lingering.
@@ -6517,18 +6512,7 @@
     }
 
     // An accumulator class to gather the list of changes that result from a rematch.
-    // TODO : enrich to represent an entire set of changes to apply.
     private static class NetworkReassignment {
-        static class NetworkBgStatePair {
-            @NonNull final NetworkAgentInfo mNetwork;
-            final boolean mOldBackground;
-            NetworkBgStatePair(@NonNull final NetworkAgentInfo network,
-                    final boolean oldBackground) {
-                mNetwork = network;
-                mOldBackground = oldBackground;
-            }
-        }
-
         static class RequestReassignment {
             @NonNull public final NetworkRequestInfo mRequest;
             @Nullable public final NetworkAgentInfo mOldNetwork;
@@ -6540,44 +6524,34 @@
                 mOldNetwork = oldNetwork;
                 mNewNetwork = newNetwork;
             }
+
+            public String toString() {
+                return mRequest.request.requestId + " : "
+                        + (null != mOldNetwork ? mOldNetwork.network.netId : "null")
+                        + " → " + (null != mNewNetwork ? mNewNetwork.network.netId : "null");
+            }
         }
 
-        @NonNull private final Set<NetworkBgStatePair> mRematchedNetworks = new ArraySet<>();
-        @NonNull private final Map<NetworkRequestInfo, RequestReassignment> mReassignments =
-                new ArrayMap<>();
-
-        @NonNull Iterable<NetworkBgStatePair> getRematchedNetworks() {
-            return mRematchedNetworks;
-        }
+        @NonNull private final ArrayList<RequestReassignment> mReassignments = new ArrayList<>();
 
         @NonNull Iterable<RequestReassignment> getRequestReassignments() {
-            return mReassignments.values();
+            return mReassignments;
         }
 
         void addRequestReassignment(@NonNull final RequestReassignment reassignment) {
-            final RequestReassignment oldChange = mReassignments.get(reassignment.mRequest);
-            if (null == oldChange) {
-                mReassignments.put(reassignment.mRequest, reassignment);
-                return;
+            if (!Build.IS_USER) {
+                // The code is never supposed to add two reassignments of the same request. Make
+                // sure this stays true, but without imposing this expensive check on all
+                // reassignments on all user devices.
+                for (final RequestReassignment existing : mReassignments) {
+                    if (existing.mRequest.equals(reassignment.mRequest)) {
+                        throw new IllegalStateException("Trying to reassign ["
+                                + reassignment + "] but already have ["
+                                + existing + "]");
+                    }
+                }
             }
-            if (oldChange.mNewNetwork != reassignment.mOldNetwork) {
-                throw new IllegalArgumentException("Reassignment <" + reassignment.mRequest + "> ["
-                        + reassignment.mOldNetwork + " -> " + reassignment.mNewNetwork
-                        + "] conflicts with ["
-                        + oldChange.mOldNetwork + " -> " + oldChange.mNewNetwork + "]");
-            }
-            // There was already a note to reassign this request from a network A to a network B,
-            // and a reassignment is added from network B to some other network C. The following
-            // synthesizes the merged reassignment that goes A -> C. An interesting (but not
-            // special) case to think about is when B is null, which can happen when the rematch
-            // loop notices the current satisfier doesn't satisfy the request any more, but
-            // hasn't yet encountered another network that could.
-            mReassignments.put(reassignment.mRequest, new RequestReassignment(reassignment.mRequest,
-                    oldChange.mOldNetwork, reassignment.mNewNetwork));
-        }
-
-        void addRematchedNetwork(@NonNull final NetworkBgStatePair network) {
-            mRematchedNetworks.add(network);
+            mReassignments.add(reassignment);
         }
 
         // Will return null if this reassignment does not change the network assigned to
@@ -6589,98 +6563,25 @@
             }
             return null;
         }
-    }
 
-    // TODO : remove this when it's useless
-    @NonNull private NetworkReassignment computeInitialReassignment() {
-        final NetworkReassignment change = new NetworkReassignment();
-        for (NetworkRequestInfo nri : mNetworkRequests.values()) {
-            change.addRequestReassignment(new NetworkReassignment.RequestReassignment(nri,
-                    nri.mSatisfier, nri.mSatisfier));
-        }
-        return change;
-    }
-
-    private ArrayMap<NetworkRequestInfo, NetworkAgentInfo> computeRequestReassignmentForNetwork(
-            @NonNull final NetworkReassignment changes,
-            @NonNull final NetworkAgentInfo newNetwork) {
-        final int score = newNetwork.getCurrentScore();
-        final ArrayMap<NetworkRequestInfo, NetworkAgentInfo> reassignedRequests = new ArrayMap<>();
-        for (NetworkRequestInfo nri : mNetworkRequests.values()) {
-            // Process requests in the first pass and listens in the second pass. This allows us to
-            // change a network's capabilities depending on which requests it has. This is only
-            // correct if the change in capabilities doesn't affect whether the network satisfies
-            // requests or not, and doesn't affect the network's score.
-            if (nri.request.isListen()) continue;
-
-            // The reassignment has been seeded with the initial assignment, therefore
-            // getReassignment can't be null and mNewNetwork is only null if there was no
-            // satisfier in the first place or there was an explicit reassignment to null.
-            final NetworkAgentInfo currentNetwork = changes.getReassignment(nri).mNewNetwork;
-            final boolean satisfies = newNetwork.satisfies(nri.request);
-            if (newNetwork == currentNetwork && satisfies) continue;
-
-            // check if it satisfies the NetworkCapabilities
-            if (VDBG) log("  checking if request is satisfied: " + nri.request);
-            if (satisfies) {
-                // next check if it's better than any current network we're using for
-                // this request
-                if (VDBG || DDBG) {
-                    log("currentScore = "
-                            + (currentNetwork != null ? currentNetwork.getCurrentScore() : 0)
-                            + ", newScore = " + score);
-                }
-                if (currentNetwork == null || currentNetwork.getCurrentScore() < score) {
-                    reassignedRequests.put(nri, newNetwork);
-                    changes.addRequestReassignment(new NetworkReassignment.RequestReassignment(
-                            nri, currentNetwork, newNetwork));
-                }
-            } else if (newNetwork == currentNetwork) {
-                reassignedRequests.put(nri, null);
-                changes.addRequestReassignment(new NetworkReassignment.RequestReassignment(
-                        nri, currentNetwork, null));
+        public String toString() {
+            final StringJoiner sj = new StringJoiner(", " /* delimiter */,
+                    "NetReassign [" /* prefix */, "]" /* suffix */);
+            if (mReassignments.isEmpty()) return sj.add("no changes").toString();
+            for (final RequestReassignment rr : getRequestReassignments()) {
+                sj.add(rr.toString());
             }
+            return sj.toString();
         }
 
-        return reassignedRequests;
-    }
-
-    // Handles a network appearing or improving its score.
-    //
-    // - Evaluates all current NetworkRequests that can be
-    //   satisfied by newNetwork, and reassigns to newNetwork
-    //   any such requests for which newNetwork is the best.
-    //
-    // - Writes into the passed reassignment object all changes that should be done for
-    //   rematching this network with all requests, to be applied later.
-    //
-    // TODO : stop writing to the passed reassignment. This is temporarily more useful, but
-    // it's unidiomatic Java and it's hard to read.
-    //
-    // @param changes a currently-building list of changes to write to
-    // @param newNetwork is the network to be matched against NetworkRequests.
-    // @param now the time the rematch starts, as returned by SystemClock.elapsedRealtime();
-    private void rematchNetworkAndRequests(@NonNull final NetworkReassignment changes,
-            @NonNull final NetworkAgentInfo newNetwork, final long now) {
-        ensureRunningOnConnectivityServiceThread();
-        if (!newNetwork.everConnected) return;
-
-        changes.addRematchedNetwork(new NetworkReassignment.NetworkBgStatePair(newNetwork,
-                newNetwork.isBackgroundNetwork()));
-
-        if (VDBG || DDBG) log("rematching " + newNetwork.name());
-
-        final ArrayMap<NetworkRequestInfo, NetworkAgentInfo> reassignedRequests =
-                computeRequestReassignmentForNetwork(changes, newNetwork);
-
-        // Find and migrate to this Network any NetworkRequests for
-        // which this network is now the best.
-        for (final Map.Entry<NetworkRequestInfo, NetworkAgentInfo> entry :
-                reassignedRequests.entrySet()) {
-            final NetworkRequestInfo nri = entry.getKey();
-            final NetworkAgentInfo previousSatisfier = nri.mSatisfier;
-            final NetworkAgentInfo newSatisfier = entry.getValue();
-            updateSatisfiersForRematchRequest(nri, previousSatisfier, newSatisfier, now);
+        public String debugString() {
+            final StringBuilder sb = new StringBuilder();
+            sb.append("NetworkReassignment :");
+            if (mReassignments.isEmpty()) return sb.append(" no changes").toString();
+            for (final RequestReassignment rr : getRequestReassignments()) {
+                sb.append("\n  ").append(rr);
+            }
+            return sb.append("\n").toString();
         }
     }
 
@@ -6689,10 +6590,10 @@
             @Nullable final NetworkAgentInfo newSatisfier,
             final long now) {
         if (newSatisfier != null) {
-            if (VDBG) log("rematch for " + newSatisfier.name());
+            if (VDBG) log("rematch for " + newSatisfier.toShortString());
             if (previousSatisfier != null) {
                 if (VDBG || DDBG) {
-                    log("   accepting network in place of " + previousSatisfier.name());
+                    log("   accepting network in place of " + previousSatisfier.toShortString());
                 }
                 previousSatisfier.removeRequest(nri.request.requestId);
                 previousSatisfier.lingerRequest(nri.request, now, mLingerDelayMs);
@@ -6701,11 +6602,12 @@
             }
             newSatisfier.unlingerRequest(nri.request);
             if (!newSatisfier.addRequest(nri.request)) {
-                Slog.wtf(TAG, "BUG: " + newSatisfier.name() + " already has " + nri.request);
+                Slog.wtf(TAG, "BUG: " + newSatisfier.toShortString() + " already has "
+                        + nri.request);
             }
         } else {
             if (DBG) {
-                log("Network " + previousSatisfier.name() + " stopped satisfying"
+                log("Network " + previousSatisfier.toShortString() + " stopped satisfying"
                         + " request " + nri.request.requestId);
             }
             previousSatisfier.removeRequest(nri.request.requestId);
@@ -6713,30 +6615,67 @@
         nri.mSatisfier = newSatisfier;
     }
 
+    @NonNull
+    private NetworkReassignment computeNetworkReassignment() {
+        ensureRunningOnConnectivityServiceThread();
+        final NetworkReassignment changes = new NetworkReassignment();
+
+        // Gather the list of all relevant agents and sort them by score.
+        final ArrayList<NetworkAgentInfo> nais = new ArrayList<>();
+        for (final NetworkAgentInfo nai : mNetworkAgentInfos.values()) {
+            if (!nai.everConnected) continue;
+            nais.add(nai);
+        }
+
+        for (final NetworkRequestInfo nri : mNetworkRequests.values()) {
+            if (nri.request.isListen()) continue;
+            final NetworkAgentInfo bestNetwork = mNetworkRanker.getBestNetwork(nri.request, nais);
+            if (bestNetwork != nri.mSatisfier) {
+                // bestNetwork may be null if no network can satisfy this request.
+                changes.addRequestReassignment(new NetworkReassignment.RequestReassignment(
+                        nri, nri.mSatisfier, bestNetwork));
+            }
+        }
+        return changes;
+    }
+
     /**
      * Attempt to rematch all Networks with NetworkRequests.  This may result in Networks
      * being disconnected.
      */
     private void rematchAllNetworksAndRequests() {
-        // TODO: This may be slow, and should be optimized. Unfortunately at this moment the
-        // processing is network-major instead of request-major (the code iterates through all
-        // networks, then for each it iterates for all requests), which is a problem for re-scoring
-        // requests. Once the code has switched to a request-major iteration style, this can
-        // be optimized to only do the processing needed.
+        // TODO: This may be slow, and should be optimized.
         final long now = SystemClock.elapsedRealtime();
-        final NetworkAgentInfo oldDefaultNetwork = getDefaultNetwork();
+        final NetworkReassignment changes = computeNetworkReassignment();
+        if (VDBG || DDBG) {
+            log(changes.debugString());
+        } else if (DBG) {
+            log(changes.toString()); // Shorter form, only one line of log
+        }
+        applyNetworkReassignment(changes, now);
+    }
 
-        final NetworkAgentInfo[] nais = mNetworkAgentInfos.values().toArray(
-                new NetworkAgentInfo[mNetworkAgentInfos.size()]);
-        // Rematch higher scoring networks first to prevent requests first matching a lower
-        // scoring network and then a higher scoring network, which could produce multiple
-        // callbacks.
-        Arrays.sort(nais);
-        final NetworkReassignment changes = computeInitialReassignment();
+    private void applyNetworkReassignment(@NonNull final NetworkReassignment changes,
+            final long now) {
+        final Collection<NetworkAgentInfo> nais = mNetworkAgentInfos.values();
+
+        // Since most of the time there are only 0 or 1 background networks, it would probably
+        // be more efficient to just use an ArrayList here. TODO : measure performance
+        final ArraySet<NetworkAgentInfo> oldBgNetworks = new ArraySet<>();
         for (final NetworkAgentInfo nai : nais) {
-            rematchNetworkAndRequests(changes, nai, now);
+            if (nai.isBackgroundNetwork()) oldBgNetworks.add(nai);
         }
 
+        // First, update the lists of satisfied requests in the network agents. This is necessary
+        // because some code later depends on this state to be correct, most prominently computing
+        // the linger status.
+        for (final NetworkReassignment.RequestReassignment event :
+                changes.getRequestReassignments()) {
+            updateSatisfiersForRematchRequest(event.mRequest, event.mOldNetwork,
+                    event.mNewNetwork, now);
+        }
+
+        final NetworkAgentInfo oldDefaultNetwork = getDefaultNetwork();
         final NetworkRequestInfo defaultRequestInfo = mNetworkRequests.get(mDefaultRequest);
         final NetworkReassignment.RequestReassignment reassignment =
                 changes.getReassignment(defaultRequestInfo);
@@ -6761,8 +6700,6 @@
         // before LegacyTypeTracker sends legacy broadcasts
         for (final NetworkReassignment.RequestReassignment event :
                 changes.getRequestReassignments()) {
-            if (event.mOldNetwork == event.mNewNetwork) continue;
-
             // Tell NetworkProviders about the new score, so they can stop
             // trying to connect if they know they cannot match it.
             // TODO - this could get expensive if there are a lot of outstanding requests for this
@@ -6777,17 +6714,10 @@
             }
         }
 
-        for (final NetworkReassignment.NetworkBgStatePair event : changes.getRematchedNetworks()) {
-            // Process listen requests and update capabilities if the background state has
-            // changed for this network. For consistency with previous behavior, send onLost
-            // callbacks before onAvailable.
-            processNewlyLostListenRequests(event.mNetwork);
-            if (event.mOldBackground != event.mNetwork.isBackgroundNetwork()) {
-                applyBackgroundChangeForRematch(event.mNetwork);
-            }
-            processNewlySatisfiedListenRequests(event.mNetwork);
-        }
-
+        // Update the linger state before processing listen callbacks, because the background
+        // computation depends on whether the network is lingering. Don't send the LOSING callbacks
+        // just yet though, because they have to be sent after the listens are processed to keep
+        // backward compatibility.
         final ArrayList<NetworkAgentInfo> lingeredNetworks = new ArrayList<>();
         for (final NetworkAgentInfo nai : nais) {
             // Rematching may have altered the linger state of some networks, so update all linger
@@ -6800,6 +6730,19 @@
             }
         }
 
+        for (final NetworkAgentInfo nai : nais) {
+            if (!nai.everConnected) continue;
+            final boolean oldBackground = oldBgNetworks.contains(nai);
+            // Process listen requests and update capabilities if the background state has
+            // changed for this network. For consistency with previous behavior, send onLost
+            // callbacks before onAvailable.
+            processNewlyLostListenRequests(nai);
+            if (oldBackground != nai.isBackgroundNetwork()) {
+                applyBackgroundChangeForRematch(nai);
+            }
+            processNewlySatisfiedListenRequests(nai);
+        }
+
         for (final NetworkAgentInfo nai : lingeredNetworks) {
             notifyNetworkLosing(nai, now);
         }
@@ -6821,7 +6764,7 @@
                         notifyNetworkLosing(nai, now);
                     }
                 } else {
-                    if (DBG) log("Reaping " + nai.name());
+                    if (DBG) log("Reaping " + nai.toShortString());
                     teardownUnneededNetwork(nai);
                 }
             }
@@ -6849,7 +6792,7 @@
     private void updateLegacyTypeTrackerAndVpnLockdownForRematch(
             @Nullable final NetworkAgentInfo oldDefaultNetwork,
             @Nullable final NetworkAgentInfo newDefaultNetwork,
-            @NonNull final NetworkAgentInfo[] nais) {
+            @NonNull final Collection<NetworkAgentInfo> nais) {
         if (oldDefaultNetwork != newDefaultNetwork) {
             // Maintain the illusion : since the legacy API only understands one network at a time,
             // if the default network changed, apps should see a disconnected broadcast for the
@@ -6888,7 +6831,9 @@
         // they may get old info. Reverse this after the old startUsing api is removed.
         // This is on top of the multiple intent sequencing referenced in the todo above.
         for (NetworkAgentInfo nai : nais) {
-            addNetworkToLegacyTypeTracker(nai);
+            if (nai.everConnected) {
+                addNetworkToLegacyTypeTracker(nai);
+            }
         }
     }
 
@@ -6969,8 +6914,8 @@
         notifyLockdownVpn(networkAgent);
 
         if (DBG) {
-            log(networkAgent.name() + " EVENT_NETWORK_INFO_CHANGED, going from " +
-                    oldInfo.getState() + " to " + state);
+            log(networkAgent.toShortString() + " EVENT_NETWORK_INFO_CHANGED, going from "
+                    + oldInfo.getState() + " to " + state);
         }
 
         if (!networkAgent.created
@@ -6988,7 +6933,7 @@
             networkAgent.everConnected = true;
 
             if (networkAgent.linkProperties == null) {
-                Slog.wtf(TAG, networkAgent.name() + " connected with null LinkProperties");
+                Slog.wtf(TAG, networkAgent.toShortString() + " connected with null LinkProperties");
             }
 
             // NetworkCapabilities need to be set before sending the private DNS config to
@@ -7048,7 +6993,7 @@
     }
 
     private void updateNetworkScore(NetworkAgentInfo nai, NetworkScore ns) {
-        if (VDBG || DDBG) log("updateNetworkScore for " + nai.name() + " to " + ns);
+        if (VDBG || DDBG) log("updateNetworkScore for " + nai.toShortString() + " to " + ns);
         nai.setNetworkScore(ns);
         rematchAllNetworksAndRequests();
         sendUpdatedScoreToFactories(nai);
@@ -7194,14 +7139,12 @@
     protected void notifyNetworkCallbacks(NetworkAgentInfo networkAgent, int notifyType, int arg1) {
         if (VDBG || DDBG) {
             String notification = ConnectivityManager.getCallbackName(notifyType);
-            log("notifyType " + notification + " for " + networkAgent.name());
+            log("notifyType " + notification + " for " + networkAgent.toShortString());
         }
         for (int i = 0; i < networkAgent.numNetworkRequests(); i++) {
             NetworkRequest nr = networkAgent.requestAt(i);
             NetworkRequestInfo nri = mNetworkRequests.get(nr);
             if (VDBG) log(" sending notification for " + nr);
-            // TODO: if we're in the middle of a rematch, can we send a CAP_CHANGED callback for
-            // a network that no longer satisfies the listen?
             if (nri.mPendingIntent == null) {
                 callCallbackForRequest(nri, networkAgent, notifyType, arg1);
             } else {
diff --git a/services/core/java/com/android/server/connectivity/KeepaliveTracker.java b/services/core/java/com/android/server/connectivity/KeepaliveTracker.java
index af8a366..5059a48 100644
--- a/services/core/java/com/android/server/connectivity/KeepaliveTracker.java
+++ b/services/core/java/com/android/server/connectivity/KeepaliveTracker.java
@@ -325,7 +325,7 @@
             mSlot = slot;
             int error = isValid();
             if (error == SUCCESS) {
-                Log.d(TAG, "Starting keepalive " + mSlot + " on " + mNai.name());
+                Log.d(TAG, "Starting keepalive " + mSlot + " on " + mNai.toShortString());
                 switch (mType) {
                     case TYPE_NATT:
                         mNai.asyncChannel.sendMessage(
@@ -365,7 +365,8 @@
                     Log.e(TAG, "Cannot stop unowned keepalive " + mSlot + " on " + mNai.network);
                 }
             }
-            Log.d(TAG, "Stopping keepalive " + mSlot + " on " + mNai.name() + ": " + reason);
+            Log.d(TAG, "Stopping keepalive " + mSlot + " on " + mNai.toShortString()
+                    + ": " + reason);
             switch (mStartedState) {
                 case NOT_STARTED:
                     // Remove the reference of the keepalive that meet error before starting,
@@ -476,7 +477,7 @@
     }
 
     public void handleStopKeepalive(NetworkAgentInfo nai, int slot, int reason) {
-        String networkName = (nai == null) ? "(null)" : nai.name();
+        final String networkName = NetworkAgentInfo.toShortString(nai);
         HashMap <Integer, KeepaliveInfo> networkKeepalives = mKeepalives.get(nai);
         if (networkKeepalives == null) {
             Log.e(TAG, "Attempt to stop keepalive on nonexistent network " + networkName);
@@ -493,7 +494,7 @@
     }
 
     private void cleanupStoppedKeepalive(NetworkAgentInfo nai, int slot) {
-        String networkName = (nai == null) ? "(null)" : nai.name();
+        final String networkName = NetworkAgentInfo.toShortString(nai);
         HashMap<Integer, KeepaliveInfo> networkKeepalives = mKeepalives.get(nai);
         if (networkKeepalives == null) {
             Log.e(TAG, "Attempt to remove keepalive on nonexistent network " + networkName);
@@ -540,7 +541,7 @@
         } catch(NullPointerException e) {}
         if (ki == null) {
             Log.e(TAG, "Event " + message.what + "," + slot + "," + reason
-                    + " for unknown keepalive " + slot + " on " + nai.name());
+                    + " for unknown keepalive " + slot + " on " + nai.toShortString());
             return;
         }
 
@@ -562,7 +563,7 @@
         if (KeepaliveInfo.STARTING == ki.mStartedState) {
             if (SUCCESS == reason) {
                 // Keepalive successfully started.
-                Log.d(TAG, "Started keepalive " + slot + " on " + nai.name());
+                Log.d(TAG, "Started keepalive " + slot + " on " + nai.toShortString());
                 ki.mStartedState = KeepaliveInfo.STARTED;
                 try {
                     ki.mCallback.onStarted(slot);
@@ -570,14 +571,14 @@
                     Log.w(TAG, "Discarded onStarted(" + slot + ") callback");
                 }
             } else {
-                Log.d(TAG, "Failed to start keepalive " + slot + " on " + nai.name()
+                Log.d(TAG, "Failed to start keepalive " + slot + " on " + nai.toShortString()
                         + ": " + reason);
                 // The message indicated some error trying to start: do call handleStopKeepalive.
                 handleStopKeepalive(nai, slot, reason);
             }
         } else if (KeepaliveInfo.STOPPING == ki.mStartedState) {
             // The message indicated result of stopping : clean up keepalive slots.
-            Log.d(TAG, "Stopped keepalive " + slot + " on " + nai.name()
+            Log.d(TAG, "Stopped keepalive " + slot + " on " + nai.toShortString()
                     + " stopped: " + reason);
             ki.mStartedState = KeepaliveInfo.NOT_STARTED;
             cleanupStoppedKeepalive(nai, slot);
@@ -733,7 +734,7 @@
         pw.println("Socket keepalives:");
         pw.increaseIndent();
         for (NetworkAgentInfo nai : mKeepalives.keySet()) {
-            pw.println(nai.name());
+            pw.println(nai.toShortString());
             pw.increaseIndent();
             for (int slot : mKeepalives.get(nai).keySet()) {
                 KeepaliveInfo ki = mKeepalives.get(nai).get(slot);
diff --git a/services/core/java/com/android/server/connectivity/LingerMonitor.java b/services/core/java/com/android/server/connectivity/LingerMonitor.java
index 7071510..04c000f 100644
--- a/services/core/java/com/android/server/connectivity/LingerMonitor.java
+++ b/services/core/java/com/android/server/connectivity/LingerMonitor.java
@@ -200,8 +200,9 @@
         }
 
         if (DBG) {
-            Log.d(TAG, "Notifying switch from=" + fromNai.name() + " to=" + toNai.name() +
-                    " type=" + sNotifyTypeNames.get(notifyType, "unknown(" + notifyType + ")"));
+            Log.d(TAG, "Notifying switch from=" + fromNai.toShortString()
+                    + " to=" + toNai.toShortString()
+                    + " type=" + sNotifyTypeNames.get(notifyType, "unknown(" + notifyType + ")"));
         }
 
         mNotifications.put(fromNai.network.netId, toNai.network.netId);
@@ -222,10 +223,10 @@
     public void noteLingerDefaultNetwork(@NonNull final NetworkAgentInfo fromNai,
             @Nullable final NetworkAgentInfo toNai) {
         if (VDBG) {
-            Log.d(TAG, "noteLingerDefaultNetwork from=" + fromNai.name() +
-                    " everValidated=" + fromNai.everValidated +
-                    " lastValidated=" + fromNai.lastValidated +
-                    " to=" + toNai.name());
+            Log.d(TAG, "noteLingerDefaultNetwork from=" + fromNai.toShortString()
+                    + " everValidated=" + fromNai.everValidated
+                    + " lastValidated=" + fromNai.lastValidated
+                    + " to=" + toNai.toShortString());
         }
 
         // If we are currently notifying the user because the device switched to fromNai, now that
@@ -270,7 +271,8 @@
         // TODO: should we do this?
         if (everNotified(fromNai)) {
             if (VDBG) {
-                Log.d(TAG, "Not notifying handover from " + fromNai.name() + ", already notified");
+                Log.d(TAG, "Not notifying handover from " + fromNai.toShortString()
+                        + ", already notified");
             }
             return;
         }
diff --git a/services/core/java/com/android/server/connectivity/Nat464Xlat.java b/services/core/java/com/android/server/connectivity/Nat464Xlat.java
index f636d67..82465f8 100644
--- a/services/core/java/com/android/server/connectivity/Nat464Xlat.java
+++ b/services/core/java/com/android/server/connectivity/Nat464Xlat.java
@@ -174,7 +174,7 @@
         try {
             mNMService.registerObserver(this);
         } catch (RemoteException e) {
-            Slog.e(TAG, "Can't register interface observer for clat on " + mNetwork.name());
+            Slog.e(TAG, "Can't register iface observer for clat on " + mNetwork.toShortString());
             return;
         }
 
diff --git a/services/core/java/com/android/server/connectivity/NetworkAgentInfo.java b/services/core/java/com/android/server/connectivity/NetworkAgentInfo.java
index d66aec5..d30a320 100644
--- a/services/core/java/com/android/server/connectivity/NetworkAgentInfo.java
+++ b/services/core/java/com/android/server/connectivity/NetworkAgentInfo.java
@@ -16,7 +16,10 @@
 
 package com.android.server.connectivity;
 
+import static android.net.NetworkCapabilities.transportNamesOf;
+
 import android.annotation.NonNull;
+import android.annotation.Nullable;
 import android.content.Context;
 import android.net.IDnsResolver;
 import android.net.INetd;
@@ -372,7 +375,7 @@
             // Should only happen if the requestId wraps. If that happens lots of other things will
             // be broken as well.
             Log.wtf(TAG, String.format("Duplicate requestId for %s and %s on %s",
-                    networkRequest, existing, name()));
+                    networkRequest, existing, toShortString()));
             updateRequestCounts(REMOVE, existing);
         }
         mNetworkRequests.put(networkRequest.requestId, networkRequest);
@@ -542,11 +545,11 @@
             // Cannot happen. Once a request is lingering on a particular network, we cannot
             // re-linger it unless that network becomes the best for that request again, in which
             // case we should have unlingered it.
-            Log.wtf(TAG, this.name() + ": request " + request.requestId + " already lingered");
+            Log.wtf(TAG, toShortString() + ": request " + request.requestId + " already lingered");
         }
         final long expiryMs = now + duration;
         LingerTimer timer = new LingerTimer(request, expiryMs);
-        if (VDBG) Log.d(TAG, "Adding LingerTimer " + timer + " to " + this.name());
+        if (VDBG) Log.d(TAG, "Adding LingerTimer " + timer + " to " + toShortString());
         mLingerTimers.add(timer);
         mLingerTimerForRequest.put(request.requestId, timer);
     }
@@ -558,7 +561,7 @@
     public boolean unlingerRequest(NetworkRequest request) {
         LingerTimer timer = mLingerTimerForRequest.get(request.requestId);
         if (timer != null) {
-            if (VDBG) Log.d(TAG, "Removing LingerTimer " + timer + " from " + this.name());
+            if (VDBG) Log.d(TAG, "Removing LingerTimer " + timer + " from " + toShortString());
             mLingerTimers.remove(timer);
             mLingerTimerForRequest.remove(request.requestId);
             return true;
@@ -645,9 +648,16 @@
                 + "}";
     }
 
-    public String name() {
-        return "NetworkAgentInfo [" + networkInfo.getTypeName() + " (" +
-                networkInfo.getSubtypeName() + ") - " + Objects.toString(network) + "]";
+    /**
+     * Show a short string representing a Network.
+     *
+     * This is often not enough for debugging purposes for anything complex, but the full form
+     * is very long and hard to read, so this is useful when there isn't a lot of ambiguity.
+     * This represents the network with something like "[100 WIFI|VPN]" or "[108 MOBILE]".
+     */
+    public String toShortString() {
+        return "[" + network.netId + " "
+                + transportNamesOf(networkCapabilities.getTransportTypes()) + "]";
     }
 
     // Enables sorting in descending order of score.
@@ -655,4 +665,12 @@
     public int compareTo(NetworkAgentInfo other) {
         return other.getCurrentScore() - getCurrentScore();
     }
+
+    /**
+     * Null-guarding version of NetworkAgentInfo#toShortString()
+     */
+    @NonNull
+    public static String toShortString(@Nullable final NetworkAgentInfo nai) {
+        return null != nai ? nai.toShortString() : "[null]";
+    }
 }
diff --git a/services/core/java/com/android/server/connectivity/NetworkRanker.java b/services/core/java/com/android/server/connectivity/NetworkRanker.java
new file mode 100644
index 0000000..d0aabf9
--- /dev/null
+++ b/services/core/java/com/android/server/connectivity/NetworkRanker.java
@@ -0,0 +1,50 @@
+/*
+ * Copyright (C) 2020 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.connectivity;
+
+import android.annotation.NonNull;
+import android.annotation.Nullable;
+import android.net.NetworkRequest;
+
+import java.util.Collection;
+
+/**
+ * A class that knows how to find the best network matching a request out of a list of networks.
+ */
+public class NetworkRanker {
+    public NetworkRanker() { }
+
+    /**
+     * Find the best network satisfying this request among the list of passed networks.
+     */
+    // Almost equivalent to Collections.max(nais), but allows returning null if no network
+    // satisfies the request.
+    @Nullable
+    public NetworkAgentInfo getBestNetwork(@NonNull final NetworkRequest request,
+            @NonNull final Collection<NetworkAgentInfo> nais) {
+        NetworkAgentInfo bestNetwork = null;
+        int bestScore = Integer.MIN_VALUE;
+        for (final NetworkAgentInfo nai : nais) {
+            if (!nai.satisfies(request)) continue;
+            if (nai.getCurrentScore() > bestScore) {
+                bestNetwork = nai;
+                bestScore = nai.getCurrentScore();
+            }
+        }
+        return bestNetwork;
+    }
+}
diff --git a/tests/net/java/com/android/server/connectivity/NetworkRankerTest.kt b/tests/net/java/com/android/server/connectivity/NetworkRankerTest.kt
new file mode 100644
index 0000000..86c9116
--- /dev/null
+++ b/tests/net/java/com/android/server/connectivity/NetworkRankerTest.kt
@@ -0,0 +1,84 @@
+/*
+ * Copyright (C) 2020 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.connectivity
+
+import android.net.NetworkRequest
+import androidx.test.filters.SmallTest
+import androidx.test.runner.AndroidJUnit4
+import org.junit.Test
+import org.junit.runner.RunWith
+import org.mockito.ArgumentMatchers.any
+import org.mockito.Mockito.doReturn
+import org.mockito.Mockito.mock
+import kotlin.test.assertEquals
+import kotlin.test.assertNull
+
+@RunWith(AndroidJUnit4::class)
+@SmallTest
+class NetworkRankerTest {
+    private val ranker = NetworkRanker()
+
+    private fun makeNai(satisfy: Boolean, score: Int) = mock(NetworkAgentInfo::class.java).also {
+        doReturn(satisfy).`when`(it).satisfies(any())
+        doReturn(score).`when`(it).currentScore
+    }
+
+    @Test
+    fun testGetBestNetwork() {
+        val scores = listOf(20, 50, 90, 60, 23, 68)
+        val nais = scores.map { makeNai(true, it) }
+        val bestNetwork = nais[2] // The one with the top score
+        val someRequest = mock(NetworkRequest::class.java)
+        assertEquals(bestNetwork, ranker.getBestNetwork(someRequest, nais))
+    }
+
+    @Test
+    fun testIgnoreNonSatisfying() {
+        val nais = listOf(makeNai(true, 20), makeNai(true, 50), makeNai(false, 90),
+                makeNai(false, 60), makeNai(true, 23), makeNai(false, 68))
+        val bestNetwork = nais[1] // Top score that's satisfying
+        val someRequest = mock(NetworkRequest::class.java)
+        assertEquals(bestNetwork, ranker.getBestNetwork(someRequest, nais))
+    }
+
+    @Test
+    fun testNoMatch() {
+        val nais = listOf(makeNai(false, 20), makeNai(false, 50), makeNai(false, 90))
+        val someRequest = mock(NetworkRequest::class.java)
+        assertNull(ranker.getBestNetwork(someRequest, nais))
+    }
+
+    @Test
+    fun testEmpty() {
+        val someRequest = mock(NetworkRequest::class.java)
+        assertNull(ranker.getBestNetwork(someRequest, emptyList()))
+    }
+
+    // Make sure the ranker is "stable" (as in stable sort), that is, it always returns the FIRST
+    // network satisfying the request if multiple of them have the same score.
+    @Test
+    fun testStable() {
+        val nais1 = listOf(makeNai(true, 30), makeNai(true, 30), makeNai(true, 30),
+                makeNai(true, 30), makeNai(true, 30), makeNai(true, 30))
+        val someRequest = mock(NetworkRequest::class.java)
+        assertEquals(nais1[0], ranker.getBestNetwork(someRequest, nais1))
+
+        val nais2 = listOf(makeNai(true, 30), makeNai(true, 50), makeNai(true, 20),
+                makeNai(true, 50), makeNai(true, 50), makeNai(true, 40))
+        assertEquals(nais2[1], ranker.getBestNetwork(someRequest, nais2))
+    }
+}