diff --git a/core/java/android/net/ConnectivityManager.java b/core/java/android/net/ConnectivityManager.java
index 91fefa2..b7ba970 100644
--- a/core/java/android/net/ConnectivityManager.java
+++ b/core/java/android/net/ConnectivityManager.java
@@ -3286,9 +3286,9 @@
 
         /**
          * Called if no network is found in the timeout time specified in
-         * {@link #requestNetwork(NetworkRequest, NetworkCallback, int)} call. This callback is not
-         * called for the version of {@link #requestNetwork(NetworkRequest, NetworkCallback)}
-         * without timeout. When this callback is invoked the associated
+         * {@link #requestNetwork(NetworkRequest, NetworkCallback, int)} call or if the
+         * requested network request cannot be fulfilled (whether or not a timeout was
+         * specified). When this callback is invoked the associated
          * {@link NetworkRequest} will have already been removed and released, as if
          * {@link #unregisterNetworkCallback(NetworkCallback)} had been called.
          */
diff --git a/services/core/java/com/android/server/ConnectivityService.java b/services/core/java/com/android/server/ConnectivityService.java
index 219cf33..dbfc327 100644
--- a/services/core/java/com/android/server/ConnectivityService.java
+++ b/services/core/java/com/android/server/ConnectivityService.java
@@ -1073,7 +1073,8 @@
             handleRegisterNetworkRequest(new NetworkRequestInfo(
                     null, networkRequest, new Binder()));
         } else {
-            handleReleaseNetworkRequest(networkRequest, Process.SYSTEM_UID);
+            handleReleaseNetworkRequest(networkRequest, Process.SYSTEM_UID,
+                    /* callOnUnavailable */ false);
         }
     }
 
@@ -2701,11 +2702,25 @@
             return true;
         }
 
+        private boolean maybeHandleNetworkFactoryMessage(Message msg) {
+            switch (msg.what) {
+                default:
+                    return false;
+                case android.net.NetworkFactory.EVENT_UNFULFILLABLE_REQUEST: {
+                    handleReleaseNetworkRequest((NetworkRequest) msg.obj, msg.sendingUid,
+                            /* callOnUnavailable */ true);
+                    break;
+                }
+            }
+            return true;
+        }
+
         @Override
         public void handleMessage(Message msg) {
-            if (!maybeHandleAsyncChannelMessage(msg) &&
-                    !maybeHandleNetworkMonitorMessage(msg) &&
-                    !maybeHandleNetworkAgentInfoMessage(msg)) {
+            if (!maybeHandleAsyncChannelMessage(msg)
+                    && !maybeHandleNetworkMonitorMessage(msg)
+                    && !maybeHandleNetworkAgentInfoMessage(msg)
+                    && !maybeHandleNetworkFactoryMessage(msg)) {
                 maybeHandleNetworkAgentMessage(msg);
             }
         }
@@ -2870,6 +2885,9 @@
         if (mNetworkFactoryInfos.containsKey(msg.replyTo)) {
             if (msg.arg1 == AsyncChannel.STATUS_SUCCESSFUL) {
                 if (VDBG) log("NetworkFactory connected");
+                // Finish setting up the full connection
+                mNetworkFactoryInfos.get(msg.replyTo).asyncChannel.sendMessage(
+                        AsyncChannel.CMD_CHANNEL_FULL_CONNECTION);
                 // A network factory has connected.  Send it all current NetworkRequests.
                 for (NetworkRequestInfo nri : mNetworkRequests.values()) {
                     if (nri.request.isListen()) continue;
@@ -3031,7 +3049,8 @@
         if (existingRequest != null) { // remove the existing request.
             if (DBG) log("Replacing " + existingRequest.request + " with "
                     + nri.request + " because their intents matched.");
-            handleReleaseNetworkRequest(existingRequest.request, getCallingUid());
+            handleReleaseNetworkRequest(existingRequest.request, getCallingUid(),
+                    /* callOnUnavailable */ false);
         }
         handleRegisterNetworkRequest(nri);
     }
@@ -3057,7 +3076,7 @@
             int callingUid) {
         NetworkRequestInfo nri = findExistingNetworkRequestInfo(pendingIntent);
         if (nri != null) {
-            handleReleaseNetworkRequest(nri.request, callingUid);
+            handleReleaseNetworkRequest(nri.request, callingUid, /* callOnUnavailable */ false);
         }
     }
 
@@ -3140,7 +3159,8 @@
         callCallbackForRequest(nri, null, ConnectivityManager.CALLBACK_UNAVAIL, 0);
     }
 
-    private void handleReleaseNetworkRequest(NetworkRequest request, int callingUid) {
+    private void handleReleaseNetworkRequest(NetworkRequest request, int callingUid,
+            boolean callOnUnavailable) {
         final NetworkRequestInfo nri =
                 getNriForAppRequest(request, callingUid, "release NetworkRequest");
         if (nri == null) {
@@ -3150,6 +3170,9 @@
             log("releasing " + nri.request + " (release request)");
         }
         handleRemoveNetworkRequest(nri);
+        if (callOnUnavailable) {
+            callCallbackForRequest(nri, null, ConnectivityManager.CALLBACK_UNAVAIL, 0);
+        }
     }
 
     private void handleRemoveNetworkRequest(final NetworkRequestInfo nri) {
@@ -3651,7 +3674,8 @@
                     break;
                 }
                 case EVENT_RELEASE_NETWORK_REQUEST: {
-                    handleReleaseNetworkRequest((NetworkRequest) msg.obj, msg.arg1);
+                    handleReleaseNetworkRequest((NetworkRequest) msg.obj, msg.arg1,
+                            /* callOnUnavailable */ false);
                     break;
                 }
                 case EVENT_SET_ACCEPT_UNVALIDATED: {
diff --git a/tests/net/java/com/android/server/ConnectivityServiceTest.java b/tests/net/java/com/android/server/ConnectivityServiceTest.java
index 70eb70b..83ef62e 100644
--- a/tests/net/java/com/android/server/ConnectivityServiceTest.java
+++ b/tests/net/java/com/android/server/ConnectivityServiceTest.java
@@ -154,6 +154,7 @@
 import android.text.TextUtils;
 import android.util.ArraySet;
 import android.util.Log;
+import android.util.SparseArray;
 
 import androidx.test.InstrumentationRegistry;
 import androidx.test.filters.SmallTest;
@@ -761,6 +762,10 @@
         // mExpectations is non-null.
         private boolean mExpectingAdditions;
 
+        // Used to collect the networks requests managed by this factory. This is a duplicate of
+        // the internal information stored in the NetworkFactory (which is private).
+        private SparseArray<NetworkRequest> mNetworkRequests = new SparseArray<>();
+
         public MockNetworkFactory(Looper looper, Context context, String logTag,
                 NetworkCapabilities filter) {
             super(looper, context, logTag, filter);
@@ -802,6 +807,7 @@
             }
 
             // Add the request.
+            mNetworkRequests.put(request.requestId, request);
             super.handleAddRequest(request, score);
 
             // Reduce the number of request additions we're waiting for.
@@ -819,6 +825,7 @@
             }
 
             // Remove the request.
+            mNetworkRequests.remove(request.requestId);
             super.handleRemoveRequest(request);
 
             // Reduce the number of request removals we're waiting for.
@@ -828,6 +835,11 @@
             }
         }
 
+        // Trigger releasing the request as unfulfillable
+        public void triggerUnfulfillable(NetworkRequest r) {
+            super.releaseRequestAsUnfulfillableByAnyFactory(r);
+        }
+
         private void assertNoExpectations() {
             if (mExpectations != null) {
                 fail("Can't add expectation, " + mExpectations.getCount() + " already pending");
@@ -860,9 +872,11 @@
             mExpectations = null;
         }
 
-        public void waitForNetworkRequests(final int count) throws InterruptedException {
+        public SparseArray<NetworkRequest> waitForNetworkRequests(final int count)
+                throws InterruptedException {
             waitForRequests();
             assertEquals(count, getMyRequestCount());
+            return mNetworkRequests;
         }
     }
 
@@ -3636,6 +3650,55 @@
         networkCallback.assertNoCallback();
     }
 
+    /**
+     * Validate the callback flow for a factory releasing a request as unfulfillable.
+     */
+    @Test
+    public void testUnfulfillableNetworkRequest() throws Exception {
+        NetworkRequest nr = new NetworkRequest.Builder().addTransportType(
+                NetworkCapabilities.TRANSPORT_WIFI).build();
+        final TestNetworkCallback networkCallback = new TestNetworkCallback();
+
+        final HandlerThread handlerThread = new HandlerThread("testUnfulfillableNetworkRequest");
+        handlerThread.start();
+        NetworkCapabilities filter = new NetworkCapabilities()
+                .addTransportType(TRANSPORT_WIFI)
+                .addCapability(NET_CAPABILITY_INTERNET);
+        final MockNetworkFactory testFactory = new MockNetworkFactory(handlerThread.getLooper(),
+                mServiceContext, "testFactory", filter);
+        testFactory.setScoreFilter(40);
+
+        // Register the factory and expect it to receive the default request.
+        testFactory.expectAddRequests(1);
+        testFactory.register();
+        SparseArray<NetworkRequest> requests = testFactory.waitForNetworkRequests(1);
+
+        assertEquals(1, requests.size()); // have 1 request at this point
+        int origRequestId = requests.valueAt(0).requestId;
+
+        // Now file the test request and expect it.
+        testFactory.expectAddRequests(1);
+        mCm.requestNetwork(nr, networkCallback);
+        requests = testFactory.waitForNetworkRequests(2); // have 2 requests at this point
+
+        int newRequestId = 0;
+        for (int i = 0; i < requests.size(); ++i) {
+            if (requests.valueAt(i).requestId != origRequestId) {
+                newRequestId = requests.valueAt(i).requestId;
+                break;
+            }
+        }
+
+        // Simulate the factory releasing the request as unfulfillable and expect onUnavailable!
+        testFactory.expectRemoveRequests(1);
+        testFactory.triggerUnfulfillable(requests.get(newRequestId));
+        networkCallback.expectCallback(CallbackState.UNAVAILABLE, null);
+        testFactory.waitForRequests();
+
+        testFactory.unregister();
+        handlerThread.quit();
+    }
+
     private static class TestKeepaliveCallback extends PacketKeepaliveCallback {
 
         public static enum CallbackType { ON_STARTED, ON_STOPPED, ON_ERROR };