diff --git a/services/core/java/com/android/server/ConnectivityService.java b/services/core/java/com/android/server/ConnectivityService.java
index d85827e..5530143 100644
--- a/services/core/java/com/android/server/ConnectivityService.java
+++ b/services/core/java/com/android/server/ConnectivityService.java
@@ -1942,7 +1942,7 @@
                             networkCapabilities.hasCapability(NET_CAPABILITY_VALIDATED)) {
                         Slog.wtf(TAG, "BUG: " + nai + " has CS-managed capability.");
                     }
-                    if (nai.created && !nai.networkCapabilities.equalImmutableCapabilities(
+                    if (nai.everConnected && !nai.networkCapabilities.equalImmutableCapabilities(
                             networkCapabilities)) {
                         Slog.wtf(TAG, "BUG: " + nai + " changed immutable capabilities: "
                                 + nai.networkCapabilities + " -> " + networkCapabilities);
@@ -1953,13 +1953,14 @@
                 case NetworkAgent.EVENT_NETWORK_PROPERTIES_CHANGED: {
                     if (VDBG) {
                         log("Update of LinkProperties for " + nai.name() +
-                                "; created=" + nai.created);
+                                "; created=" + nai.created +
+                                "; everConnected=" + nai.everConnected);
                     }
                     LinkProperties oldLp = nai.linkProperties;
                     synchronized (nai) {
                         nai.linkProperties = (LinkProperties)msg.obj;
                     }
-                    if (nai.created) updateLinkProperties(nai, oldLp);
+                    if (nai.everConnected) updateLinkProperties(nai, oldLp);
                     break;
                 }
                 case NetworkAgent.EVENT_NETWORK_INFO_CHANGED: {
@@ -1991,8 +1992,8 @@
                     break;
                 }
                 case NetworkAgent.EVENT_SET_EXPLICITLY_SELECTED: {
-                    if (nai.created && !nai.networkMisc.explicitlySelected) {
-                        loge("ERROR: created network explicitly selected.");
+                    if (nai.everConnected && !nai.networkMisc.explicitlySelected) {
+                        loge("ERROR: already-connected network explicitly selected.");
                     }
                     nai.networkMisc.explicitlySelected = true;
                     nai.networkMisc.acceptUnvalidated = (boolean) msg.obj;
@@ -2277,7 +2278,7 @@
     // This is whether it is satisfying any NetworkRequests or were it to become validated,
     // would it have a chance of satisfying any NetworkRequests.
     private boolean unneeded(NetworkAgentInfo nai) {
-        if (!nai.created || nai.isVPN() || nai.lingering) return false;
+        if (!nai.everConnected || nai.isVPN() || nai.lingering) return false;
         for (NetworkRequestInfo nri : mNetworkRequests.values()) {
             // If this Network is already the highest scoring Network for a request, or if
             // there is hope for it to become one if it validated, then it is needed.
@@ -2761,9 +2762,9 @@
                     ") by " + uid);
         }
         synchronized (nai) {
-            // Validating an uncreated network could result in a call to rematchNetworkAndRequests()
-            // which isn't meant to work on uncreated networks.
-            if (!nai.created) return;
+            // Validating a network that has not yet connected could result in a call to
+            // rematchNetworkAndRequests() which is not meant to work on such networks.
+            if (!nai.everConnected) return;
 
             if (isNetworkWithLinkPropertiesBlocked(nai.linkProperties, uid)) return;
 
@@ -4505,7 +4506,7 @@
     //               validated) of becoming the highest scoring network.
     private void rematchNetworkAndRequests(NetworkAgentInfo newNetwork,
             ReapUnvalidatedNetworks reapUnvalidatedNetworks) {
-        if (!newNetwork.created) return;
+        if (!newNetwork.everConnected) return;
         boolean keep = newNetwork.isVPN();
         boolean isNewDefault = false;
         NetworkAgentInfo oldDefaultNetwork = null;
@@ -4804,7 +4805,9 @@
                     " to " + state);
         }
 
-        if (state == NetworkInfo.State.CONNECTED && !networkAgent.created) {
+        if (!networkAgent.created
+                && (state == NetworkInfo.State.CONNECTED
+                || (state == NetworkInfo.State.CONNECTING && networkAgent.isVPN()))) {
             try {
                 // This should never fail.  Specifying an already in use NetID will cause failure.
                 if (networkAgent.isVPN()) {
@@ -4824,6 +4827,11 @@
                 return;
             }
             networkAgent.created = true;
+        }
+
+        if (!networkAgent.everConnected && state == NetworkInfo.State.CONNECTED) {
+            networkAgent.everConnected = true;
+
             updateLinkProperties(networkAgent, null);
             notifyIfacesChangedForNetworkStats();
 
diff --git a/services/core/java/com/android/server/connectivity/NetworkAgentInfo.java b/services/core/java/com/android/server/connectivity/NetworkAgentInfo.java
index 3201060..d487bd0 100644
--- a/services/core/java/com/android/server/connectivity/NetworkAgentInfo.java
+++ b/services/core/java/com/android/server/connectivity/NetworkAgentInfo.java
@@ -48,15 +48,21 @@
 // 1. registered, uncreated, disconnected, unvalidated
 //    This state is entered when a NetworkFactory registers a NetworkAgent in any state except
 //    the CONNECTED state.
-// 2. registered, uncreated, connected, unvalidated
-//    This state is entered when a registered NetworkAgent transitions to the CONNECTED state
-//    ConnectivityService will tell netd to create the network and immediately transition to
-//    state #3.
-// 3. registered, created, connected, unvalidated
+// 2. registered, uncreated, connecting, unvalidated
+//    This state is entered when a registered NetworkAgent for a VPN network transitions to the
+//    CONNECTING state (TODO: go through this state for every network, not just VPNs).
+//    ConnectivityService will tell netd to create the network early in order to add extra UID
+//    routing rules referencing the netID. These rules need to be in place before the network is
+//    connected to avoid racing against client apps trying to connect to a half-setup network.
+// 3. registered, uncreated, connected, unvalidated
+//    This state is entered when a registered NetworkAgent transitions to the CONNECTED state.
+//    ConnectivityService will tell netd to create the network if it was not already created, and
+//    immediately transition to state #4.
+// 4. registered, created, connected, unvalidated
 //    If this network can satisfy the default NetworkRequest, then NetworkMonitor will
 //    probe for Internet connectivity.
 //    If this network cannot satisfy the default NetworkRequest, it will immediately be
-//    transitioned to state #4.
+//    transitioned to state #5.
 //    A network may remain in this state if NetworkMonitor fails to find Internet connectivity,
 //    for example:
 //    a. a captive portal is present, or
@@ -64,14 +70,14 @@
 //    c. a wireless connection stops transfering packets temporarily (e.g. device is in elevator
 //       or tunnel) but does not disconnect from the AP/cell tower, or
 //    d. a stand-alone device offering a WiFi AP without an uplink for configuration purposes.
-// 4. registered, created, connected, validated
+// 5. registered, created, connected, validated
 //
 // The device's default network connection:
 // ----------------------------------------
-// Networks in states #3 and #4 may be used as a device's default network connection if they
+// Networks in states #4 and #5 may be used as a device's default network connection if they
 // satisfy the default NetworkRequest.
-// A network, that satisfies the default NetworkRequest, in state #4 should always be chosen
-// in favor of a network, that satisfies the default NetworkRequest, in state #3.
+// A network, that satisfies the default NetworkRequest, in state #5 should always be chosen
+// in favor of a network, that satisfies the default NetworkRequest, in state #4.
 // When deciding between two networks, that both satisfy the default NetworkRequest, to select
 // for the default network connection, the one with the higher score should be chosen.
 //
@@ -83,14 +89,14 @@
 // c. airplane mode is turned on, or
 // d. a wireless connection disconnects from AP/cell tower entirely (e.g. device is out of range
 //    of AP for an extended period of time, or switches to another AP without roaming)
-// then that network can transition from any state (#1-#4) to unregistered.  This happens by
+// then that network can transition from any state (#1-#5) to unregistered.  This happens by
 // the transport disconnecting their NetworkAgent's AsyncChannel with ConnectivityManager.
 // ConnectivityService also tells netd to destroy the network.
 //
 // When ConnectivityService disconnects a network:
 // -----------------------------------------------
 // If a network has no chance of satisfying any requests (even if it were to become validated
-// and enter state #4), ConnectivityService will disconnect the NetworkAgent's AsyncChannel.
+// and enter state #5), ConnectivityService will disconnect the NetworkAgent's AsyncChannel.
 // If the network ever for any period of time had satisfied a NetworkRequest (i.e. had been
 // the highest scoring that satisfied the NetworkRequest's constraints), but is no longer the
 // highest scoring network for any NetworkRequest, then there will be a 30s pause before
@@ -110,10 +116,14 @@
     public NetworkCapabilities networkCapabilities;
     public final NetworkMonitor networkMonitor;
     public final NetworkMisc networkMisc;
-    // Indicates if netd has been told to create this Network.  Once created the appropriate routing
-    // rules are setup and routes are added so packets can begin flowing over the Network.
+    // Indicates if netd has been told to create this Network. From this point on the appropriate
+    // routing rules are setup and routes are added so packets can begin flowing over the Network.
     // This is a sticky bit; once set it is never cleared.
     public boolean created;
+    // Set to true after the first time this network is marked as CONNECTED. Once set, the network
+    // shows up in API calls, is able to satisfy NetworkRequests and can become the default network.
+    // This is a sticky bit; once set it is never cleared.
+    public boolean everConnected;
     // Set to true if this Network successfully passed validation or if it did not satisfy the
     // default NetworkRequest in which case validation will not be attempted.
     // This is a sticky bit; once set it is never cleared even if future validation attempts fail.