diff --git a/Tethering/src/com/android/networkstack/tethering/PrivateAddressCoordinator.java b/Tethering/src/com/android/networkstack/tethering/PrivateAddressCoordinator.java
index 160a166..aa58a4b 100644
--- a/Tethering/src/com/android/networkstack/tethering/PrivateAddressCoordinator.java
+++ b/Tethering/src/com/android/networkstack/tethering/PrivateAddressCoordinator.java
@@ -15,6 +15,8 @@
  */
 package com.android.networkstack.tethering;
 
+import static java.util.Arrays.asList;
+
 import android.content.Context;
 import android.net.ConnectivityManager;
 import android.net.IpPrefix;
@@ -34,9 +36,10 @@
 import java.net.InetAddress;
 import java.net.UnknownHostException;
 import java.util.ArrayList;
-import java.util.Arrays;
+import java.util.HashSet;
 import java.util.List;
 import java.util.Random;
+import java.util.Set;
 
 /**
  * This class coordinate IP addresses conflict problem.
@@ -60,8 +63,8 @@
     // Upstream monitor would be stopped when tethering is down. When tethering restart, downstream
     // address may be requested before coordinator get current upstream notification. To ensure
     // coordinator do not select conflict downstream prefix, mUpstreamPrefixMap would not be cleared
-    // when tethering is down. Instead coordinator would remove all depcreted upstreams from
-    // mUpstreamPrefixMap when tethering is starting. See #maybeRemoveDeprectedUpstreams().
+    // when tethering is down. Instead tethering would remove all deprecated upstreams from
+    // mUpstreamPrefixMap when tethering is starting. See #maybeRemoveDeprecatedUpstreams().
     private final ArrayMap<Network, List<IpPrefix>> mUpstreamPrefixMap;
     private final ArraySet<IpServer> mDownstreams;
     // IANA has reserved the following three blocks of the IP address space for private intranets:
@@ -124,15 +127,16 @@
         mUpstreamPrefixMap.remove(network);
     }
 
-    private void maybeRemoveDeprectedUpstreams() {
-        if (!mDownstreams.isEmpty() || mUpstreamPrefixMap.isEmpty()) return;
+    /**
+     * Maybe remove deprecated upstream records, this would be called once tethering started without
+     * any exiting tethered downstream.
+     */
+    public void maybeRemoveDeprecatedUpstreams() {
+        if (mUpstreamPrefixMap.isEmpty()) return;
 
-        final ArrayList<Network> toBeRemoved = new ArrayList<>();
-        List<Network> allNetworks = Arrays.asList(mConnectivityMgr.getAllNetworks());
-        for (int i = 0; i < mUpstreamPrefixMap.size(); i++) {
-            final Network network = mUpstreamPrefixMap.keyAt(i);
-            if (!allNetworks.contains(network)) toBeRemoved.add(network);
-        }
+        // Remove all upstreams that are no longer valid networks
+        final Set<Network> toBeRemoved = new HashSet<>(mUpstreamPrefixMap.keySet());
+        toBeRemoved.removeAll(asList(mConnectivityMgr.getAllNetworks()));
 
         mUpstreamPrefixMap.removeAll(toBeRemoved);
     }
@@ -143,8 +147,6 @@
      */
     @Nullable
     public LinkAddress requestDownstreamAddress(final IpServer ipServer) {
-        maybeRemoveDeprectedUpstreams();
-
         // Address would be 192.168.[subAddress]/24.
         final byte[] bytes = mTetheringPrefix.getRawAddress();
         final int subAddress = getRandomSubAddr();
@@ -237,7 +239,6 @@
     }
 
     void dump(final IndentingPrintWriter pw) {
-        pw.decreaseIndent();
         pw.println("mUpstreamPrefixMap:");
         pw.increaseIndent();
         for (int i = 0; i < mUpstreamPrefixMap.size(); i++) {
diff --git a/Tethering/src/com/android/networkstack/tethering/Tethering.java b/Tethering/src/com/android/networkstack/tethering/Tethering.java
index a3597f1..8deac53 100644
--- a/Tethering/src/com/android/networkstack/tethering/Tethering.java
+++ b/Tethering/src/com/android/networkstack/tethering/Tethering.java
@@ -1698,6 +1698,7 @@
                     return;
                 }
 
+                mPrivateAddressCoordinator.maybeRemoveDeprecatedUpstreams();
                 mUpstreamNetworkMonitor.startObserveAllNetworks();
 
                 // TODO: De-duplicate with updateUpstreamWanted() below.
diff --git a/Tethering/tests/unit/src/com/android/networkstack/tethering/PrivateAddressCoordinatorTest.java b/Tethering/tests/unit/src/com/android/networkstack/tethering/PrivateAddressCoordinatorTest.java
index 93efd49..2c0df6f 100644
--- a/Tethering/tests/unit/src/com/android/networkstack/tethering/PrivateAddressCoordinatorTest.java
+++ b/Tethering/tests/unit/src/com/android/networkstack/tethering/PrivateAddressCoordinatorTest.java
@@ -127,10 +127,15 @@
         mPrivateAddressCoordinator.releaseDownstream(mHotspotIpServer);
     }
 
+    private int getBluetoothSubAddress() {
+        final byte[] rawAddress = mBluetoothPrefix.getRawAddress();
+        int bluetoothSubNet = rawAddress[2] & 0xff;
+        return (bluetoothSubNet << 8) + 0x5;
+    }
+
     @Test
     public void testReserveBluetoothPrefix() throws Exception {
-        final int fakeSubAddr = 0x2c05;
-        when(mPrivateAddressCoordinator.getRandomSubAddr()).thenReturn(fakeSubAddr);
+        when(mPrivateAddressCoordinator.getRandomSubAddr()).thenReturn(getBluetoothSubAddress());
         LinkAddress address = mPrivateAddressCoordinator.requestDownstreamAddress(
                 mHotspotIpServer);
         final IpPrefix hotspotPrefix = PrefixUtils.asIpPrefix(address);
@@ -146,7 +151,7 @@
         LinkAddress address = mPrivateAddressCoordinator.requestDownstreamAddress(
                 mHotspotIpServer);
         final IpPrefix hotspotPrefix = PrefixUtils.asIpPrefix(address);
-        assertEquals("Wrong wifi perfix: ", predefinedPrefix, hotspotPrefix);
+        assertEquals("Wrong wifi prefix: ", predefinedPrefix, hotspotPrefix);
         when(mHotspotIpServer.getAddress()).thenReturn(address);
 
         address = mPrivateAddressCoordinator.requestDownstreamAddress(
@@ -159,7 +164,7 @@
         address = mPrivateAddressCoordinator.requestDownstreamAddress(
                 mUsbIpServer);
         final IpPrefix allowUseFreePrefix = PrefixUtils.asIpPrefix(address);
-        assertEquals("Fail to reselect available perfix: ", predefinedPrefix, allowUseFreePrefix);
+        assertEquals("Fail to reselect available prefix: ", predefinedPrefix, allowUseFreePrefix);
     }
 
     private LinkProperties buildUpstreamLinkProperties(boolean withIPv4, boolean withIPv6,
@@ -202,7 +207,7 @@
         final LinkAddress hotspotAddr = mPrivateAddressCoordinator.requestDownstreamAddress(
                 mHotspotIpServer);
         final IpPrefix hotspotPrefix = PrefixUtils.asIpPrefix(hotspotAddr);
-        assertEquals("Wrong wifi perfix: ", predefinedPrefix, hotspotPrefix);
+        assertEquals("Wrong wifi prefix: ", predefinedPrefix, hotspotPrefix);
         when(mHotspotIpServer.getAddress()).thenReturn(hotspotAddr);
         // 2. Update v6 only mobile network, hotspot prefix should not be removed.
         List<String> testConflicts;
diff --git a/Tethering/tests/unit/src/com/android/networkstack/tethering/TetheringTest.java b/Tethering/tests/unit/src/com/android/networkstack/tethering/TetheringTest.java
index 329d8a5..02dbd4c 100644
--- a/Tethering/tests/unit/src/com/android/networkstack/tethering/TetheringTest.java
+++ b/Tethering/tests/unit/src/com/android/networkstack/tethering/TetheringTest.java
@@ -1884,7 +1884,7 @@
                 0,
                 upstreamNetwork);
         mLooper.dispatchAll();
-        // verify trun off usb tethering
+        // verify turn off usb tethering
         verify(mUsbManager).setCurrentFunctions(UsbManager.FUNCTION_NONE);
         mTethering.interfaceRemoved(TEST_USB_IFNAME);
         mLooper.dispatchAll();
@@ -1922,9 +1922,9 @@
                 0,
                 upstreamNetwork);
         mLooper.dispatchAll();
-        // verify trun off usb tethering
+        // verify turn off usb tethering
         verify(mUsbManager).setCurrentFunctions(UsbManager.FUNCTION_NONE);
-        // verify trun off ethernet tethering
+        // verify turn off ethernet tethering
         verify(mockRequest).release();
         mTethering.interfaceRemoved(TEST_USB_IFNAME);
         ethCallback.onUnavailable();