diff --git a/services/core/java/com/android/server/ConnectivityService.java b/services/core/java/com/android/server/ConnectivityService.java
index c997e2a..8958909 100644
--- a/services/core/java/com/android/server/ConnectivityService.java
+++ b/services/core/java/com/android/server/ConnectivityService.java
@@ -1281,14 +1281,22 @@
 
         mPermissionMonitor = new PermissionMonitor(mContext, mNetd);
 
+        mUserAllContext = mContext.createContextAsUser(UserHandle.ALL, 0 /* flags */);
         // Listen for user add/removes to inform PermissionMonitor.
         // Should run on mHandler to avoid any races.
-        IntentFilter intentFilter = new IntentFilter();
-        intentFilter.addAction(Intent.ACTION_USER_ADDED);
-        intentFilter.addAction(Intent.ACTION_USER_REMOVED);
+        final IntentFilter userIntentFilter = new IntentFilter();
+        userIntentFilter.addAction(Intent.ACTION_USER_ADDED);
+        userIntentFilter.addAction(Intent.ACTION_USER_REMOVED);
+        mUserAllContext.registerReceiver(mUserIntentReceiver, userIntentFilter,
+                null /* broadcastPermission */, mHandler);
 
-        mUserAllContext = mContext.createContextAsUser(UserHandle.ALL, 0 /* flags */);
-        mUserAllContext.registerReceiver(mIntentReceiver, intentFilter,
+        // Listen to package add/removes for netd
+        final IntentFilter packageIntentFilter = new IntentFilter();
+        packageIntentFilter.addAction(Intent.ACTION_PACKAGE_ADDED);
+        packageIntentFilter.addAction(Intent.ACTION_PACKAGE_REMOVED);
+        packageIntentFilter.addAction(Intent.ACTION_PACKAGE_REPLACED);
+        packageIntentFilter.addDataScheme("package");
+        mUserAllContext.registerReceiver(mPackageIntentReceiver, packageIntentFilter,
                 null /* broadcastPermission */, mHandler);
 
         mNetworkActivityTracker = new LegacyNetworkActivityTracker(mContext, mHandler, mNetd);
@@ -5303,14 +5311,14 @@
         }
     }
 
-    private void onUserAdded(UserHandle user) {
+    private void onUserAdded(@NonNull final UserHandle user) {
         mPermissionMonitor.onUserAdded(user);
         if (mOemNetworkPreferences.getNetworkPreferences().size() > 0) {
             handleSetOemNetworkPreference(mOemNetworkPreferences, null);
         }
     }
 
-    private void onUserRemoved(UserHandle user) {
+    private void onUserRemoved(@NonNull final UserHandle user) {
         mPermissionMonitor.onUserRemoved(user);
         // If there was a network preference for this user, remove it.
         handleSetProfileNetworkPreference(new ProfileNetworkPreferences.Preference(user, null),
@@ -5320,7 +5328,18 @@
         }
     }
 
-    private BroadcastReceiver mIntentReceiver = new BroadcastReceiver() {
+    private void onPackageChanged(@NonNull final String packageName) {
+        // This is necessary in case a package is added or removed, but also when it's replaced to
+        // run as a new UID by its manifest rules. Also, if a separate package shares the same UID
+        // as one in the preferences, then it should follow the same routing as that other package,
+        // which means updating the rules is never to be needed in this case (whether it joins or
+        // leaves a UID with a preference).
+        if (isMappedInOemNetworkPreference(packageName)) {
+            handleSetOemNetworkPreference(mOemNetworkPreferences, null);
+        }
+    }
+
+    private final BroadcastReceiver mUserIntentReceiver = new BroadcastReceiver() {
         @Override
         public void onReceive(Context context, Intent intent) {
             ensureRunningOnConnectivityServiceThread();
@@ -5343,6 +5362,22 @@
         }
     };
 
+    private final BroadcastReceiver mPackageIntentReceiver = new BroadcastReceiver() {
+        @Override
+        public void onReceive(Context context, Intent intent) {
+            ensureRunningOnConnectivityServiceThread();
+            switch (intent.getAction()) {
+                case Intent.ACTION_PACKAGE_ADDED:
+                case Intent.ACTION_PACKAGE_REMOVED:
+                case Intent.ACTION_PACKAGE_REPLACED:
+                    onPackageChanged(intent.getData().getSchemeSpecificPart());
+                    break;
+                default:
+                    Log.wtf(TAG, "received unexpected intent: " + intent.getAction());
+            }
+        }
+    };
+
     private final HashMap<Messenger, NetworkProviderInfo> mNetworkProviderInfos = new HashMap<>();
     private final HashMap<NetworkRequest, NetworkRequestInfo> mNetworkRequests = new HashMap<>();
 
@@ -6166,6 +6201,15 @@
     @NonNull
     private ProfileNetworkPreferences mProfileNetworkPreferences = new ProfileNetworkPreferences();
 
+    /**
+     * Determine whether a given package has a mapping in the current OemNetworkPreferences.
+     * @param packageName the package name to check existence of a mapping for.
+     * @return true if a mapping exists, false otherwise
+     */
+    private boolean isMappedInOemNetworkPreference(@NonNull final String packageName) {
+        return mOemNetworkPreferences.getNetworkPreferences().containsKey(packageName);
+    }
+
     // The always-on request for an Internet-capable network that apps without a specific default
     // fall back to.
     @VisibleForTesting
@@ -6186,7 +6230,7 @@
      * @return the NetworkRequestInfo tracking the given uid.
      */
     @NonNull
-    private NetworkRequestInfo getDefaultRequestTrackingUid(@NonNull final int uid) {
+    private NetworkRequestInfo getDefaultRequestTrackingUid(final int uid) {
         for (final NetworkRequestInfo nri : mDefaultNetworkRequests) {
             if (nri == mDefaultRequest) {
                 continue;
@@ -9593,7 +9637,6 @@
                 new OemNetworkRequestFactory().createNrisFromOemNetworkPreferences(preference);
         replaceDefaultNetworkRequestsForPreference(nris);
         mOemNetworkPreferences = preference;
-        // TODO http://b/176496396 persist data to shared preferences.
 
         if (null != listener) {
             try {
@@ -9750,7 +9793,6 @@
                     // packages are sent on a network preference as the system will watch for
                     // package installations associated with this network preference and update
                     // accordingly. This is done so as to minimize race conditions on app install.
-                    // TODO b/177092163 add app install watching.
                     continue;
                 }
             }
diff --git a/tests/net/java/com/android/server/ConnectivityServiceTest.java b/tests/net/java/com/android/server/ConnectivityServiceTest.java
index 2ed11e0..daf4e61 100644
--- a/tests/net/java/com/android/server/ConnectivityServiceTest.java
+++ b/tests/net/java/com/android/server/ConnectivityServiceTest.java
@@ -21,6 +21,9 @@
 import static android.Manifest.permission.NETWORK_FACTORY;
 import static android.Manifest.permission.NETWORK_SETTINGS;
 import static android.app.PendingIntent.FLAG_IMMUTABLE;
+import static android.content.Intent.ACTION_PACKAGE_ADDED;
+import static android.content.Intent.ACTION_PACKAGE_REMOVED;
+import static android.content.Intent.ACTION_PACKAGE_REPLACED;
 import static android.content.Intent.ACTION_USER_ADDED;
 import static android.content.Intent.ACTION_USER_REMOVED;
 import static android.content.Intent.ACTION_USER_UNLOCKED;
@@ -2793,10 +2796,14 @@
     }
 
     private void grantUsingBackgroundNetworksPermissionForUid(final int uid) throws Exception {
-        final String myPackageName = mContext.getPackageName();
-        when(mPackageManager.getPackageInfo(eq(myPackageName), eq(GET_PERMISSIONS)))
+        grantUsingBackgroundNetworksPermissionForUid(uid, mContext.getPackageName());
+    }
+
+    private void grantUsingBackgroundNetworksPermissionForUid(
+            final int uid, final String packageName) throws Exception {
+        when(mPackageManager.getPackageInfo(eq(packageName), eq(GET_PERMISSIONS)))
                 .thenReturn(buildPackageInfo(true, uid));
-        mService.mPermissionMonitor.onPackageAdded(myPackageName, uid);
+        mService.mPermissionMonitor.onPackageAdded(packageName, uid);
     }
 
     @Test
@@ -10255,6 +10262,12 @@
                 .thenReturn(applicationInfo);
     }
 
+    private void mockGetApplicationInfoThrowsNameNotFound(@NonNull final String packageName)
+            throws Exception {
+        when(mPackageManager.getApplicationInfo(eq(packageName), anyInt()))
+                .thenThrow(new PackageManager.NameNotFoundException(packageName));
+    }
+
     private void mockHasSystemFeature(@NonNull final String featureName,
             @NonNull final boolean hasFeature) {
         when(mPackageManager.hasSystemFeature(eq(featureName)))
@@ -10711,15 +10724,23 @@
             @NonNull final UidRangeParcel[] uidRanges,
             @NonNull final String testPackageName)
             throws Exception {
-        mockHasSystemFeature(PackageManager.FEATURE_AUTOMOTIVE, true);
-
         // These tests work off a single UID therefore using 'start' is valid.
         mockGetApplicationInfo(testPackageName, uidRanges[0].start);
 
+        setOemNetworkPreference(networkPrefToSetup, testPackageName);
+    }
+
+    private void setOemNetworkPreference(final int networkPrefToSetup,
+            @NonNull final String... testPackageNames)
+            throws Exception {
+        mockHasSystemFeature(PackageManager.FEATURE_AUTOMOTIVE, true);
+
         // Build OemNetworkPreferences object
-        final OemNetworkPreferences pref = new OemNetworkPreferences.Builder()
-                .addNetworkPreference(testPackageName, networkPrefToSetup)
-                .build();
+        final OemNetworkPreferences.Builder builder = new OemNetworkPreferences.Builder();
+        for (final String packageName : testPackageNames) {
+            builder.addNetworkPreference(packageName, networkPrefToSetup);
+        }
+        final OemNetworkPreferences pref = builder.build();
 
         // Act on ConnectivityService.setOemNetworkPreference()
         final TestOemListenerCallback oemPrefListener = new TestOemListenerCallback();
@@ -11318,8 +11339,7 @@
         // Arrange PackageManager mocks
         final int secondUserTestPackageUid = UserHandle.getUid(secondUser, TEST_PACKAGE_UID);
         final UidRangeParcel[] uidRangesSingleUser =
-                toUidRangeStableParcels(
-                        uidRangesForUids(TEST_PACKAGE_UID));
+                toUidRangeStableParcels(uidRangesForUids(TEST_PACKAGE_UID));
         final UidRangeParcel[] uidRangesBothUsers =
                 toUidRangeStableParcels(
                         uidRangesForUids(TEST_PACKAGE_UID, secondUserTestPackageUid));
@@ -11366,6 +11386,84 @@
                 false /* shouldDestroyNetwork */);
     }
 
+    @Test
+    public void testMultilayerForPackageChangesEvaluatesCorrectly()
+            throws Exception {
+        @OemNetworkPreferences.OemNetworkPreference final int networkPref =
+                OEM_NETWORK_PREFERENCE_OEM_PAID;
+        final String packageScheme = "package:";
+
+        // Arrange PackageManager mocks
+        final String packageToInstall = "package.to.install";
+        final int packageToInstallUid = 81387;
+        final UidRangeParcel[] uidRangesSinglePackage =
+                toUidRangeStableParcels(uidRangesForUids(TEST_PACKAGE_UID));
+        mockGetApplicationInfo(TEST_PACKAGE_NAME, TEST_PACKAGE_UID);
+        mockGetApplicationInfoThrowsNameNotFound(packageToInstall);
+        setOemNetworkPreference(networkPref, TEST_PACKAGE_NAME, packageToInstall);
+        grantUsingBackgroundNetworksPermissionForUid(Binder.getCallingUid(), packageToInstall);
+
+        // Verify the starting state. No networks should be connected.
+        verifySetOemNetworkPreferenceForPreference(uidRangesSinglePackage,
+                OEM_PREF_ANY_NET_ID, 0 /* times */,
+                OEM_PREF_ANY_NET_ID, 0 /* times */,
+                false /* shouldDestroyNetwork */);
+
+        // Test that we correctly add the expected values for installed packages.
+        setOemNetworkPreferenceAgentConnected(TRANSPORT_CELLULAR, true);
+        verifySetOemNetworkPreferenceForPreference(uidRangesSinglePackage,
+                mCellNetworkAgent.getNetwork().netId, 1 /* times */,
+                OEM_PREF_ANY_NET_ID, 0 /* times */,
+                false /* shouldDestroyNetwork */);
+
+        // Set the system to recognize the package to be installed
+        mockGetApplicationInfo(packageToInstall, packageToInstallUid);
+        final UidRangeParcel[] uidRangesAllPackages =
+                toUidRangeStableParcels(uidRangesForUids(TEST_PACKAGE_UID, packageToInstallUid));
+
+        // Send a broadcast indicating a package was installed.
+        final Intent addedIntent = new Intent(ACTION_PACKAGE_ADDED);
+        addedIntent.setData(Uri.parse(packageScheme + packageToInstall));
+        processBroadcast(addedIntent);
+
+        // Test the single package is removed and the combined packages are added.
+        verifySetOemNetworkPreferenceForPreference(uidRangesAllPackages, uidRangesSinglePackage,
+                mCellNetworkAgent.getNetwork().netId, 1 /* times */,
+                mCellNetworkAgent.getNetwork().netId, 1 /* times */,
+                false /* shouldDestroyNetwork */);
+
+        // Set the system to no longer recognize the package to be installed
+        mockGetApplicationInfoThrowsNameNotFound(packageToInstall);
+
+        // Send a broadcast indicating a package was removed.
+        final Intent removedIntent = new Intent(ACTION_PACKAGE_REMOVED);
+        removedIntent.setData(Uri.parse(packageScheme + packageToInstall));
+        processBroadcast(removedIntent);
+
+        // Test the combined packages are removed and the single package is added.
+        verifySetOemNetworkPreferenceForPreference(uidRangesSinglePackage, uidRangesAllPackages,
+                mCellNetworkAgent.getNetwork().netId, 1 /* times */,
+                mCellNetworkAgent.getNetwork().netId, 1 /* times */,
+                false /* shouldDestroyNetwork */);
+
+        // Set the system to change the installed package's uid
+        final int replacedTestPackageUid = TEST_PACKAGE_UID + 1;
+        mockGetApplicationInfo(TEST_PACKAGE_NAME, replacedTestPackageUid);
+        final UidRangeParcel[] uidRangesReplacedPackage =
+                toUidRangeStableParcels(uidRangesForUids(replacedTestPackageUid));
+
+        // Send a broadcast indicating a package was replaced.
+        final Intent replacedIntent = new Intent(ACTION_PACKAGE_REPLACED);
+        replacedIntent.setData(Uri.parse(packageScheme + TEST_PACKAGE_NAME));
+        processBroadcast(replacedIntent);
+
+        // Test the original uid is removed and is replaced with the new uid.
+        verifySetOemNetworkPreferenceForPreference(uidRangesReplacedPackage, uidRangesSinglePackage,
+                mCellNetworkAgent.getNetwork().netId, 1 /* times */,
+                mCellNetworkAgent.getNetwork().netId, 1 /* times */,
+                false /* shouldDestroyNetwork */);
+    }
+
     /**
      * Test network priority for preference OEM_NETWORK_PREFERENCE_OEM_PAID in the following order:
      * NET_CAPABILITY_NOT_METERED -> NET_CAPABILITY_OEM_PAID -> fallback