diff --git a/services/core/java/com/android/server/VcnManagementService.java b/services/core/java/com/android/server/VcnManagementService.java
index 77e8e96..c191a78 100644
--- a/services/core/java/com/android/server/VcnManagementService.java
+++ b/services/core/java/com/android/server/VcnManagementService.java
@@ -25,8 +25,6 @@
 import android.app.AppOpsManager;
 import android.content.Context;
 import android.net.ConnectivityManager;
-import android.net.NetworkProvider;
-import android.net.NetworkRequest;
 import android.net.vcn.IVcnManagementService;
 import android.net.vcn.VcnConfig;
 import android.os.Binder;
@@ -50,6 +48,7 @@
 import com.android.server.vcn.TelephonySubscriptionTracker;
 import com.android.server.vcn.Vcn;
 import com.android.server.vcn.VcnContext;
+import com.android.server.vcn.VcnNetworkProvider;
 import com.android.server.vcn.util.PersistableBundleUtils;
 
 import java.io.IOException;
@@ -390,6 +389,9 @@
     private void startVcnLocked(@NonNull ParcelUuid subscriptionGroup, @NonNull VcnConfig config) {
         Slog.v(TAG, "Starting VCN config for subGrp: " + subscriptionGroup);
 
+        // TODO(b/176939047): Support multiple VCNs active at the same time, or limit to one active
+        //                    VCN.
+
         final Vcn newInstance = mDeps.newVcn(mVcnContext, subscriptionGroup, config);
         mVcns.put(subscriptionGroup, newInstance);
     }
@@ -493,24 +495,4 @@
             return Collections.unmodifiableMap(mVcns);
         }
     }
-
-    /**
-     * Network provider for VCN networks.
-     *
-     * @hide
-     */
-    public class VcnNetworkProvider extends NetworkProvider {
-        VcnNetworkProvider(Context context, Looper looper) {
-            super(context, looper, VcnNetworkProvider.class.getSimpleName());
-        }
-
-        @Override
-        public void onNetworkRequested(@NonNull NetworkRequest request, int score, int providerId) {
-            synchronized (mLock) {
-                for (Vcn instance : mVcns.values()) {
-                    instance.onNetworkRequested(request, score, providerId);
-                }
-            }
-        }
-    }
 }
diff --git a/services/core/java/com/android/server/vcn/Vcn.java b/services/core/java/com/android/server/vcn/Vcn.java
index 493761b..9d21b92 100644
--- a/services/core/java/com/android/server/vcn/Vcn.java
+++ b/services/core/java/com/android/server/vcn/Vcn.java
@@ -16,32 +16,69 @@
 
 package com.android.server.vcn;
 
+
 import android.annotation.NonNull;
+import android.net.NetworkCapabilities;
 import android.net.NetworkRequest;
 import android.net.vcn.VcnConfig;
+import android.net.vcn.VcnGatewayConnectionConfig;
 import android.os.Handler;
 import android.os.Message;
 import android.os.ParcelUuid;
+import android.util.Slog;
 
+import java.util.HashMap;
+import java.util.Map;
 import java.util.Objects;
 
 /**
  * Represents an single instance of a VCN.
  *
- * <p>Each Vcn instance manages all tunnels for a given subscription group, including per-capability
- * networks, network selection, and multi-homing.
+ * <p>Each Vcn instance manages all {@link VcnGatewayConnection}(s) for a given subscription group,
+ * including per-capability networks, network selection, and multi-homing.
  *
  * @hide
  */
 public class Vcn extends Handler {
     private static final String TAG = Vcn.class.getSimpleName();
 
+    private static final int MSG_EVENT_BASE = 0;
+    private static final int MSG_CMD_BASE = 100;
+
+    /**
+     * A carrier app updated the configuration.
+     *
+     * <p>Triggers update of config, re-evaluating all active and underlying networks.
+     *
+     * @param obj VcnConfig
+     */
+    private static final int MSG_EVENT_CONFIG_UPDATED = MSG_EVENT_BASE;
+
+    /**
+     * A NetworkRequest was added or updated.
+     *
+     * <p>Triggers an evaluation of all active networks, bringing up a new one if necessary.
+     *
+     * @param obj NetworkRequest
+     */
+    private static final int MSG_EVENT_NETWORK_REQUESTED = MSG_EVENT_BASE + 1;
+
+    /** Triggers an immediate teardown of the entire Vcn, including GatewayConnections. */
+    private static final int MSG_CMD_TEARDOWN = MSG_CMD_BASE;
+
     @NonNull private final VcnContext mVcnContext;
     @NonNull private final ParcelUuid mSubscriptionGroup;
     @NonNull private final Dependencies mDeps;
+    @NonNull private final VcnNetworkRequestListener mRequestListener;
+
+    @NonNull
+    private final Map<VcnGatewayConnectionConfig, VcnGatewayConnection> mVcnGatewayConnections =
+            new HashMap<>();
 
     @NonNull private VcnConfig mConfig;
 
+    private boolean mIsRunning = true;
+
     public Vcn(
             @NonNull VcnContext vcnContext,
             @NonNull ParcelUuid subscriptionGroup,
@@ -58,31 +95,123 @@
         mVcnContext = vcnContext;
         mSubscriptionGroup = Objects.requireNonNull(subscriptionGroup, "Missing subscriptionGroup");
         mDeps = Objects.requireNonNull(deps, "Missing deps");
+        mRequestListener = new VcnNetworkRequestListener();
 
         mConfig = Objects.requireNonNull(config, "Missing config");
+
+        // Register to receive cached and future NetworkRequests
+        mVcnContext.getVcnNetworkProvider().registerListener(mRequestListener);
     }
 
     /** Asynchronously updates the configuration and triggers a re-evaluation of Networks */
     public void updateConfig(@NonNull VcnConfig config) {
         Objects.requireNonNull(config, "Missing config");
-        // TODO: Proxy to handler, and make config there.
+
+        sendMessage(obtainMessage(MSG_EVENT_CONFIG_UPDATED, config));
     }
 
-    /** Asynchronously tears down this Vcn instance, along with all tunnels and Networks */
+    /** Asynchronously tears down this Vcn instance, including VcnGatewayConnection(s) */
     public void teardownAsynchronously() {
-        // TODO: Proxy to handler, and teardown there.
+        sendMessageAtFrontOfQueue(obtainMessage(MSG_CMD_TEARDOWN));
     }
 
-    /** Notifies this Vcn instance of a new NetworkRequest */
-    public void onNetworkRequested(@NonNull NetworkRequest request, int score, int providerId) {
-        Objects.requireNonNull(request, "Missing request");
+    private class VcnNetworkRequestListener implements VcnNetworkProvider.NetworkRequestListener {
+        @Override
+        public void onNetworkRequested(@NonNull NetworkRequest request, int score, int providerId) {
+            Objects.requireNonNull(request, "Missing request");
 
-        // TODO: Proxy to handler, and handle there.
+            sendMessage(obtainMessage(MSG_EVENT_NETWORK_REQUESTED, score, providerId, request));
+        }
     }
 
     @Override
     public void handleMessage(@NonNull Message msg) {
-        // TODO: Do something
+        if (!mIsRunning) {
+            return;
+        }
+
+        switch (msg.what) {
+            case MSG_EVENT_CONFIG_UPDATED:
+                handleConfigUpdated((VcnConfig) msg.obj);
+                break;
+            case MSG_EVENT_NETWORK_REQUESTED:
+                handleNetworkRequested((NetworkRequest) msg.obj, msg.arg1, msg.arg2);
+                break;
+            case MSG_CMD_TEARDOWN:
+                handleTeardown();
+                break;
+            default:
+                Slog.wtf(getLogTag(), "Unknown msg.what: " + msg.what);
+        }
+    }
+
+    private void handleConfigUpdated(@NonNull VcnConfig config) {
+        // TODO: Add a dump function in VcnConfig that omits PII. Until then, use hashCode()
+        Slog.v(getLogTag(), String.format("Config updated: config = %s", config.hashCode()));
+
+        mConfig = config;
+
+        // TODO: Reevaluate active VcnGatewayConnection(s)
+    }
+
+    private void handleTeardown() {
+        mVcnContext.getVcnNetworkProvider().unregisterListener(mRequestListener);
+
+        for (VcnGatewayConnection gatewayConnection : mVcnGatewayConnections.values()) {
+            gatewayConnection.teardownAsynchronously();
+        }
+
+        mIsRunning = false;
+    }
+
+    private void handleNetworkRequested(
+            @NonNull NetworkRequest request, int score, int providerId) {
+        if (score > getNetworkScore()) {
+            Slog.v(getLogTag(),
+                    "Request " + request.requestId + " already satisfied by higher-scoring ("
+                            + score + ") network from provider " + providerId);
+            return;
+        }
+
+        // If preexisting VcnGatewayConnection(s) satisfy request, return
+        for (VcnGatewayConnectionConfig gatewayConnectionConfig : mVcnGatewayConnections.keySet()) {
+            if (requestSatisfiedByGatewayConnectionConfig(request, gatewayConnectionConfig)) {
+                Slog.v(getLogTag(),
+                        "Request " + request.requestId
+                                + " satisfied by existing VcnGatewayConnection");
+                return;
+            }
+        }
+
+        // If any supported (but not running) VcnGatewayConnection(s) can satisfy request, bring it
+        // up
+        for (VcnGatewayConnectionConfig gatewayConnectionConfig :
+                mConfig.getGatewayConnectionConfigs()) {
+            if (requestSatisfiedByGatewayConnectionConfig(request, gatewayConnectionConfig)) {
+                Slog.v(
+                        getLogTag(),
+                        "Bringing up new VcnGatewayConnection for request " + request.requestId);
+
+                final VcnGatewayConnection vcnGatewayConnection =
+                        new VcnGatewayConnection(
+                                mVcnContext, mSubscriptionGroup, gatewayConnectionConfig);
+                mVcnGatewayConnections.put(gatewayConnectionConfig, vcnGatewayConnection);
+            }
+        }
+    }
+
+    private boolean requestSatisfiedByGatewayConnectionConfig(
+            @NonNull NetworkRequest request, @NonNull VcnGatewayConnectionConfig config) {
+        final NetworkCapabilities configCaps = new NetworkCapabilities();
+        for (int cap : config.getAllExposedCapabilities()) {
+            configCaps.addCapability(cap);
+        }
+
+        return request.networkCapabilities.satisfiedByNetworkCapabilities(configCaps);
+    }
+
+    private String getLogTag() {
+        return String.format("%s [%d]", TAG, mSubscriptionGroup.hashCode());
     }
 
     /** Retrieves the network score for a VCN Network */
diff --git a/services/core/java/com/android/server/vcn/VcnContext.java b/services/core/java/com/android/server/vcn/VcnContext.java
index 8ab52931..dba59bd 100644
--- a/services/core/java/com/android/server/vcn/VcnContext.java
+++ b/services/core/java/com/android/server/vcn/VcnContext.java
@@ -20,8 +20,6 @@
 import android.content.Context;
 import android.os.Looper;
 
-import com.android.server.VcnManagementService.VcnNetworkProvider;
-
 import java.util.Objects;
 
 /**
diff --git a/services/core/java/com/android/server/vcn/VcnGatewayConnection.java b/services/core/java/com/android/server/vcn/VcnGatewayConnection.java
index 49c9b32..7ea8e04 100644
--- a/services/core/java/com/android/server/vcn/VcnGatewayConnection.java
+++ b/services/core/java/com/android/server/vcn/VcnGatewayConnection.java
@@ -65,8 +65,8 @@
                 mDeps.newUnderlyingNetworkTracker(mVcnContext, subscriptionGroup, this);
     }
 
-    /** Tears down this GatewayConnection, and any resources used */
-    public void teardown() {
+    /** Asynchronously tears down this GatewayConnection, and any resources used */
+    public void teardownAsynchronously() {
         mUnderlyingNetworkTracker.teardown();
     }
 
diff --git a/services/core/java/com/android/server/vcn/VcnNetworkProvider.java b/services/core/java/com/android/server/vcn/VcnNetworkProvider.java
new file mode 100644
index 0000000..7f5b23c
--- /dev/null
+++ b/services/core/java/com/android/server/vcn/VcnNetworkProvider.java
@@ -0,0 +1,108 @@
+/*
+ * 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.vcn;
+
+import android.annotation.NonNull;
+import android.content.Context;
+import android.net.NetworkProvider;
+import android.net.NetworkRequest;
+import android.os.Looper;
+import android.util.ArraySet;
+import android.util.Slog;
+import android.util.SparseArray;
+
+import java.util.Objects;
+import java.util.Set;
+
+/**
+ * VCN Network Provider routes NetworkRequests to listeners to bring up tunnels as needed.
+ *
+ * <p>The VcnNetworkProvider provides a caching layer to ensure that all listeners receive all
+ * active NetworkRequest(s), including ones that were filed prior to listener registration.
+ *
+ * @hide
+ */
+public class VcnNetworkProvider extends NetworkProvider {
+    private static final String TAG = VcnNetworkProvider.class.getSimpleName();
+
+    private final Set<NetworkRequestListener> mListeners = new ArraySet<>();
+    private final SparseArray<NetworkRequestEntry> mRequests = new SparseArray<>();
+
+    public VcnNetworkProvider(Context context, Looper looper) {
+        super(context, looper, VcnNetworkProvider.class.getSimpleName());
+    }
+
+    // Package-private
+    void registerListener(@NonNull NetworkRequestListener listener) {
+        mListeners.add(listener);
+
+        // Send listener all cached requests
+        for (int i = 0; i < mRequests.size(); i++) {
+            notifyListenerForEvent(listener, mRequests.valueAt(i));
+        }
+    }
+
+    // Package-private
+    void unregisterListener(@NonNull NetworkRequestListener listener) {
+        mListeners.remove(listener);
+    }
+
+    private void notifyListenerForEvent(
+            @NonNull NetworkRequestListener listener, @NonNull NetworkRequestEntry entry) {
+        listener.onNetworkRequested(entry.mRequest, entry.mScore, entry.mProviderId);
+    }
+
+    @Override
+    public void onNetworkRequested(@NonNull NetworkRequest request, int score, int providerId) {
+        Slog.v(
+                TAG,
+                String.format(
+                        "Network requested: Request = %s, score = %d, providerId = %d",
+                        request, score, providerId));
+
+        final NetworkRequestEntry entry = new NetworkRequestEntry(request, score, providerId);
+        mRequests.put(request.requestId, entry);
+
+        // TODO(b/176939047): Intelligently route requests to prioritized VcnInstances (based on
+        // Default Data Sub, or similar)
+        for (NetworkRequestListener listener : mListeners) {
+            notifyListenerForEvent(listener, entry);
+        }
+    }
+
+    @Override
+    public void onNetworkRequestWithdrawn(@NonNull NetworkRequest request) {
+        mRequests.remove(request.requestId);
+    }
+
+    private static class NetworkRequestEntry {
+        public final NetworkRequest mRequest;
+        public final int mScore;
+        public final int mProviderId;
+
+        private NetworkRequestEntry(@NonNull NetworkRequest request, int score, int providerId) {
+            mRequest = Objects.requireNonNull(request, "Missing request");
+            mScore = score;
+            mProviderId = providerId;
+        }
+    }
+
+    // package-private
+    interface NetworkRequestListener {
+        void onNetworkRequested(@NonNull NetworkRequest request, int score, int providerId);
+    }
+}
diff --git a/tests/vcn/java/com/android/server/VcnManagementServiceTest.java b/tests/vcn/java/com/android/server/VcnManagementServiceTest.java
index d2caa8f..696110f 100644
--- a/tests/vcn/java/com/android/server/VcnManagementServiceTest.java
+++ b/tests/vcn/java/com/android/server/VcnManagementServiceTest.java
@@ -49,10 +49,10 @@
 import androidx.test.filters.SmallTest;
 import androidx.test.runner.AndroidJUnit4;
 
-import com.android.server.VcnManagementService.VcnNetworkProvider;
 import com.android.server.vcn.TelephonySubscriptionTracker;
 import com.android.server.vcn.Vcn;
 import com.android.server.vcn.VcnContext;
+import com.android.server.vcn.VcnNetworkProvider;
 import com.android.server.vcn.util.PersistableBundleUtils;
 
 import org.junit.Test;
@@ -191,8 +191,7 @@
     public void testSystemReady() throws Exception {
         mVcnMgmtSvc.systemReady();
 
-        verify(mConnMgr)
-                .registerNetworkProvider(any(VcnManagementService.VcnNetworkProvider.class));
+        verify(mConnMgr).registerNetworkProvider(any(VcnNetworkProvider.class));
         verify(mSubscriptionTracker).register();
     }
 
@@ -309,7 +308,7 @@
         // Config cleared, SIM reloaded & config re-added right before teardown delay, staring new
         // vcnInstance.
         mTestLooper.moveTimeForward(
-                VcnManagementService.CARRIER_PRIVILEGES_LOST_TEARDOWN_DELAY_MS - 1);
+                VcnManagementService.CARRIER_PRIVILEGES_LOST_TEARDOWN_DELAY_MS / 2);
         mTestLooper.dispatchAll();
         mVcnMgmtSvc.clearVcnConfig(TEST_UUID_2);
         final Vcn newInstance = startAndGetVcnInstance(TEST_UUID_2);
diff --git a/tests/vcn/java/com/android/server/vcn/VcnNetworkProviderTest.java b/tests/vcn/java/com/android/server/vcn/VcnNetworkProviderTest.java
new file mode 100644
index 0000000..c2c6200
--- /dev/null
+++ b/tests/vcn/java/com/android/server/vcn/VcnNetworkProviderTest.java
@@ -0,0 +1,121 @@
+/*
+ * 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.vcn;
+
+import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.verify;
+import static org.mockito.Mockito.verifyNoMoreInteractions;
+
+import android.annotation.NonNull;
+import android.content.Context;
+import android.net.ConnectivityManager;
+import android.net.NetworkCapabilities;
+import android.net.NetworkRequest;
+import android.os.test.TestLooper;
+
+import androidx.test.filters.SmallTest;
+import androidx.test.runner.AndroidJUnit4;
+
+import com.android.server.vcn.VcnNetworkProvider.NetworkRequestListener;
+
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/** Tests for TelephonySubscriptionTracker */
+@RunWith(AndroidJUnit4.class)
+@SmallTest
+public class VcnNetworkProviderTest {
+    private static final int TEST_SCORE_UNSATISFIED = 0;
+    private static final int TEST_SCORE_HIGH = 100;
+    private static final int TEST_PROVIDER_ID = 1;
+    private static final int TEST_LEGACY_TYPE = ConnectivityManager.TYPE_MOBILE;
+    private static final NetworkRequest.Type TEST_REQUEST_TYPE = NetworkRequest.Type.REQUEST;
+
+    @NonNull private final Context mContext;
+    @NonNull private final TestLooper mTestLooper;
+
+    @NonNull private VcnNetworkProvider mVcnNetworkProvider;
+    @NonNull private NetworkRequestListener mListener;
+
+    public VcnNetworkProviderTest() {
+        mContext = mock(Context.class);
+        mTestLooper = new TestLooper();
+    }
+
+    @Before
+    public void setUp() throws Exception {
+        mVcnNetworkProvider = new VcnNetworkProvider(mContext, mTestLooper.getLooper());
+        mListener = mock(NetworkRequestListener.class);
+    }
+
+    @Test
+    public void testRequestsPassedToRegisteredListeners() throws Exception {
+        mVcnNetworkProvider.registerListener(mListener);
+
+        final NetworkRequest request = mock(NetworkRequest.class);
+        mVcnNetworkProvider.onNetworkRequested(request, TEST_SCORE_UNSATISFIED, TEST_PROVIDER_ID);
+        verify(mListener).onNetworkRequested(request, TEST_SCORE_UNSATISFIED, TEST_PROVIDER_ID);
+    }
+
+    @Test
+    public void testRequestsPassedToRegisteredListeners_satisfiedByHighScoringProvider()
+            throws Exception {
+        mVcnNetworkProvider.registerListener(mListener);
+
+        final NetworkRequest request = mock(NetworkRequest.class);
+        mVcnNetworkProvider.onNetworkRequested(request, TEST_SCORE_HIGH, TEST_PROVIDER_ID);
+        verify(mListener).onNetworkRequested(request, TEST_SCORE_HIGH, TEST_PROVIDER_ID);
+    }
+
+    @Test
+    public void testUnregisterListener() throws Exception {
+        mVcnNetworkProvider.registerListener(mListener);
+        mVcnNetworkProvider.unregisterListener(mListener);
+
+        final NetworkRequest request = mock(NetworkRequest.class);
+        mVcnNetworkProvider.onNetworkRequested(request, TEST_SCORE_UNSATISFIED, TEST_PROVIDER_ID);
+        verifyNoMoreInteractions(mListener);
+    }
+
+    @Test
+    public void testCachedRequestsPassedOnRegister() throws Exception {
+        final List<NetworkRequest> requests = new ArrayList<>();
+
+        for (int i = 0; i < 10; i++) {
+            final NetworkRequest request =
+                    new NetworkRequest(
+                            new NetworkCapabilities(),
+                            TEST_LEGACY_TYPE,
+                            i /* requestId */,
+                            TEST_REQUEST_TYPE);
+
+            requests.add(request);
+            mVcnNetworkProvider.onNetworkRequested(request, i, i + 1);
+        }
+
+        mVcnNetworkProvider.registerListener(mListener);
+        for (int i = 0; i < requests.size(); i++) {
+            final NetworkRequest request = requests.get(i);
+            verify(mListener).onNetworkRequested(request, i, i + 1);
+        }
+        verifyNoMoreInteractions(mListener);
+    }
+}