diff --git a/service/src/com/android/server/ConnectivityService.java b/service/src/com/android/server/ConnectivityService.java
index dd92a18..d483341 100644
--- a/service/src/com/android/server/ConnectivityService.java
+++ b/service/src/com/android/server/ConnectivityService.java
@@ -3502,6 +3502,12 @@
         return false;
     }
 
+    private boolean isDisconnectRequest(Message msg) {
+        if (msg.what != NetworkAgent.EVENT_NETWORK_INFO_CHANGED) return false;
+        final NetworkInfo info = (NetworkInfo) ((Pair) msg.obj).second;
+        return info.getState() == NetworkInfo.State.DISCONNECTED;
+    }
+
     // must be stateless - things change under us.
     private class NetworkStateTrackerHandler extends Handler {
         public NetworkStateTrackerHandler(Looper looper) {
@@ -3518,6 +3524,11 @@
                 return;
             }
 
+            // If the network has been destroyed, the only thing that it can do is disconnect.
+            if (nai.destroyed && !isDisconnectRequest(msg)) {
+                return;
+            }
+
             switch (msg.what) {
                 case NetworkAgent.EVENT_NETWORK_CAPABILITIES_CHANGED: {
                     final NetworkCapabilities networkCapabilities = new NetworkCapabilities(
@@ -3619,12 +3630,60 @@
                     }
                     break;
                 }
+                case NetworkAgent.EVENT_DESTROY_AND_AWAIT_REPLACEMENT: {
+                    // If nai is not yet created, or is already destroyed, ignore.
+                    if (!shouldDestroyNativeNetwork(nai)) break;
+
+                    final int timeoutMs = (int) arg.second;
+                    if (timeoutMs < 0 || timeoutMs > NetworkAgent.MAX_TEARDOWN_DELAY_MS) {
+                        Log.e(TAG, "Invalid network replacement timer " + timeoutMs
+                                + ", must be between 0 and " + NetworkAgent.MAX_TEARDOWN_DELAY_MS);
+                    }
+
+                    // Marking a network awaiting replacement is used to ensure that any requests
+                    // satisfied by the network do not switch to another network until a
+                    // replacement is available or the wait for a replacement times out.
+                    // If the network is inactive (i.e., nascent or lingering), then there are no
+                    // such requests, and there is no point keeping it. Just tear it down.
+                    // Note that setLingerDuration(0) cannot be used to do this because the network
+                    // could be nascent.
+                    nai.clearInactivityState();
+                    if (unneeded(nai, UnneededFor.TEARDOWN)) {
+                        Log.d(TAG, nai.toShortString()
+                                + " marked awaiting replacement is unneeded, tearing down instead");
+                        teardownUnneededNetwork(nai);
+                        break;
+                    }
+
+                    Log.d(TAG, "Marking " + nai.toShortString()
+                            + " destroyed, awaiting replacement within " + timeoutMs + "ms");
+                    destroyNativeNetwork(nai);
+
+                    // TODO: deduplicate this call with the one in disconnectAndDestroyNetwork.
+                    // This is not trivial because KeepaliveTracker#handleStartKeepalive does not
+                    // consider the fact that the network could already have disconnected or been
+                    // destroyed. Fix the code to send ERROR_INVALID_NETWORK when this happens
+                    // (taking care to ensure no dup'd FD leaks), then remove the code duplication
+                    // and move this code to a sensible location (destroyNativeNetwork perhaps?).
+                    mKeepaliveTracker.handleStopAllKeepalives(nai,
+                            SocketKeepalive.ERROR_INVALID_NETWORK);
+
+                    nai.updateScoreForNetworkAgentUpdate();
+                    // This rematch is almost certainly not going to result in any changes, because
+                    // the destroyed flag is only just above the "current satisfier wins"
+                    // tie-breaker. But technically anything that affects scoring should rematch.
+                    rematchAllNetworksAndRequests();
+                    mHandler.postDelayed(() -> nai.disconnect(), timeoutMs);
+                    break;
+                }
             }
         }
 
         private boolean maybeHandleNetworkMonitorMessage(Message msg) {
             final int netId = msg.arg2;
             final NetworkAgentInfo nai = getNetworkAgentInfoForNetId(netId);
+            // If a network has already been destroyed, all NetworkMonitor updates are ignored.
+            if (nai != null && nai.destroyed) return true;
             switch (msg.what) {
                 default:
                     return false;
@@ -4124,6 +4183,10 @@
         }
     }
 
+    private static boolean shouldDestroyNativeNetwork(@NonNull NetworkAgentInfo nai) {
+        return nai.created && !nai.destroyed;
+    }
+
     private void handleNetworkAgentDisconnected(Message msg) {
         NetworkAgentInfo nai = (NetworkAgentInfo) msg.obj;
         disconnectAndDestroyNetwork(nai);
@@ -4230,7 +4293,7 @@
     }
 
     private void destroyNetwork(NetworkAgentInfo nai) {
-        if (nai.created) {
+        if (shouldDestroyNativeNetwork(nai)) {
             // Tell netd to clean up the configuration for this network
             // (routing rules, DNS, etc).
             // This may be slow as it requires a lot of netd shelling out to ip and
@@ -4239,15 +4302,15 @@
             // network or service a new request from an app), so network traffic isn't interrupted
             // for an unnecessarily long time.
             destroyNativeNetwork(nai);
-            mDnsManager.removeNetwork(nai.network);
-
-            // clean up tc police filters on interface.
-            if (nai.everConnected && canNetworkBeRateLimited(nai) && mIngressRateLimit >= 0) {
-                mDeps.disableIngressRateLimit(nai.linkProperties.getInterfaceName());
-            }
+        }
+        if (!nai.created && !SdkLevel.isAtLeastT()) {
+            // Backwards compatibility: send onNetworkDestroyed even if network was never created.
+            // This can never run if the code above runs because shouldDestroyNativeNetwork is
+            // false if the network was never created.
+            // TODO: delete when S is no longer supported.
+            nai.onNetworkDestroyed();
         }
         mNetIdManager.releaseNetId(nai.network.getNetId());
-        nai.onNetworkDestroyed();
     }
 
     private boolean createNativeNetwork(@NonNull NetworkAgentInfo nai) {
@@ -4290,6 +4353,18 @@
         } catch (RemoteException | ServiceSpecificException e) {
             loge("Exception destroying network: " + e);
         }
+        // TODO: defer calling this until the network is removed from mNetworkAgentInfos.
+        // Otherwise, a private DNS configuration update for a destroyed network, or one that never
+        // gets created, could add data to DnsManager data structures that will never get deleted.
+        mDnsManager.removeNetwork(nai.network);
+
+        // clean up tc police filters on interface.
+        if (nai.everConnected && canNetworkBeRateLimited(nai) && mIngressRateLimit >= 0) {
+            mDeps.disableIngressRateLimit(nai.linkProperties.getInterfaceName());
+        }
+
+        nai.destroyed = true;
+        nai.onNetworkDestroyed();
     }
 
     // If this method proves to be too slow then we can maintain a separate
@@ -8542,11 +8617,19 @@
                     log("   accepting network in place of " + previousSatisfier.toShortString());
                 }
                 previousSatisfier.removeRequest(previousRequest.requestId);
-                if (canSupportGracefulNetworkSwitch(previousSatisfier, newSatisfier)) {
+                if (canSupportGracefulNetworkSwitch(previousSatisfier, newSatisfier)
+                        && !previousSatisfier.destroyed) {
                     // If this network switch can't be supported gracefully, the request is not
                     // lingered. This allows letting go of the network sooner to reclaim some
                     // performance on the new network, since the radio can't do both at the same
                     // time while preserving good performance.
+                    //
+                    // Also don't linger the request if the old network has been destroyed.
+                    // A destroyed network does not provide actual network connectivity, so
+                    // lingering it is not useful. In particular this ensures that a destroyed
+                    // network is outscored by its replacement,
+                    // then it is torn down immediately instead of being lingered, and any apps that
+                    // were using it immediately get onLost and can connect using the new network.
                     previousSatisfier.lingerRequest(previousRequest.requestId, now);
                 }
             } else {
diff --git a/service/src/com/android/server/connectivity/Nat464Xlat.java b/service/src/com/android/server/connectivity/Nat464Xlat.java
index c66a280..7b06682 100644
--- a/service/src/com/android/server/connectivity/Nat464Xlat.java
+++ b/service/src/com/android/server/connectivity/Nat464Xlat.java
@@ -132,8 +132,8 @@
         final boolean skip464xlat = (nai.netAgentConfig() != null)
                 && nai.netAgentConfig().skip464xlat;
 
-        return supported && connected && isIpv6OnlyNetwork && !skip464xlat
-            && (nai.networkCapabilities.hasTransport(TRANSPORT_CELLULAR)
+        return supported && connected && isIpv6OnlyNetwork && !skip464xlat && !nai.destroyed
+                && (nai.networkCapabilities.hasTransport(TRANSPORT_CELLULAR)
                 ? isCellular464XlatEnabled() : true);
     }
 
diff --git a/service/src/com/android/server/connectivity/NetworkAgentInfo.java b/service/src/com/android/server/connectivity/NetworkAgentInfo.java
index e29d616..ee45e5c 100644
--- a/service/src/com/android/server/connectivity/NetworkAgentInfo.java
+++ b/service/src/com/android/server/connectivity/NetworkAgentInfo.java
@@ -732,6 +732,12 @@
             mHandler.obtainMessage(NetworkAgent.EVENT_REMOVE_ALL_DSCP_POLICIES,
                     new Pair<>(NetworkAgentInfo.this, null)).sendToTarget();
         }
+
+        @Override
+        public void sendDestroyAndAwaitReplacement(final int timeoutMillis) {
+            mHandler.obtainMessage(NetworkAgent.EVENT_DESTROY_AND_AWAIT_REPLACEMENT,
+                    new Pair<>(NetworkAgentInfo.this, timeoutMillis)).sendToTarget();
+        }
     }
 
     /**
@@ -976,7 +982,7 @@
     /**
      * Update the ConnectivityService-managed bits in the score.
      *
-     * Call this after updating the network agent config.
+     * Call this after changing any data that might affect the score (e.g., agent config).
      */
     public void updateScoreForNetworkAgentUpdate() {
         mScore = mScore.mixInScore(networkCapabilities, networkAgentConfig,
@@ -1256,6 +1262,8 @@
                 + "network{" + network + "}  handle{" + network.getNetworkHandle() + "}  ni{"
                 + networkInfo.toShortString() + "} "
                 + mScore + " "
+                + (created ? " created" : "")
+                + (destroyed ? " destroyed" : "")
                 + (isNascent() ? " nascent" : (isLingering() ? " lingering" : ""))
                 + (everValidated ? " everValidated" : "")
                 + (lastValidated ? " lastValidated" : "")