diff --git a/Tethering/src/com/android/networkstack/tethering/PrivateAddressCoordinator.java b/Tethering/src/com/android/networkstack/tethering/PrivateAddressCoordinator.java
index 6f3e865..528991f 100644
--- a/Tethering/src/com/android/networkstack/tethering/PrivateAddressCoordinator.java
+++ b/Tethering/src/com/android/networkstack/tethering/PrivateAddressCoordinator.java
@@ -189,7 +189,10 @@
             return cachedAddress;
         }
 
-        for (IpPrefix prefixRange : mTetheringPrefixes) {
+        final int prefixIndex = getStartedPrefixIndex();
+        for (int i = 0; i < mTetheringPrefixes.size(); i++) {
+            final IpPrefix prefixRange = mTetheringPrefixes.get(
+                    (prefixIndex + i) % mTetheringPrefixes.size());
             final LinkAddress newAddress = chooseDownstreamAddress(prefixRange);
             if (newAddress != null) {
                 mDownstreams.add(ipServer);
@@ -202,6 +205,28 @@
         return null;
     }
 
+    private int getStartedPrefixIndex() {
+        if (!mConfig.isRandomPrefixBaseEnabled()) return 0;
+
+        final int random = getRandomInt() & 0xffffff;
+        // This is to select the starting prefix range (/8, /12, or /16) instead of the actual
+        // LinkAddress. To avoid complex operations in the selection logic and make the selected
+        // rate approximate consistency with that /8 is around 2^4 times of /12 and /12 is around
+        // 2^4 times of /16, we simply define a map between the value and the prefix value like
+        // this:
+        //
+        // Value 0 ~ 0xffff (65536/16777216 = 0.39%) -> 192.168.0.0/16
+        // Value 0x10000 ~ 0xfffff (983040/16777216 = 5.86%) -> 172.16.0.0/12
+        // Value 0x100000 ~ 0xffffff (15728640/16777216 = 93.7%) -> 10.0.0.0/8
+        if (random > 0xfffff) {
+            return 2;
+        } else if (random > 0xffff) {
+            return 1;
+        } else {
+            return 0;
+        }
+    }
+
     private int getPrefixBaseAddress(final IpPrefix prefix) {
         return inet4AddressToIntHTH((Inet4Address) prefix.getAddress());
     }
diff --git a/Tethering/src/com/android/networkstack/tethering/TetheringConfiguration.java b/Tethering/src/com/android/networkstack/tethering/TetheringConfiguration.java
index 502fee8..0678525 100644
--- a/Tethering/src/com/android/networkstack/tethering/TetheringConfiguration.java
+++ b/Tethering/src/com/android/networkstack/tethering/TetheringConfiguration.java
@@ -130,6 +130,8 @@
     public static final String TETHER_ENABLE_WEAR_TETHERING =
             "tether_enable_wear_tethering";
 
+    public static final String TETHER_FORCE_RANDOM_PREFIX_BASE_SELECTION =
+            "tether_force_random_prefix_base_selection";
     /**
      * Default value that used to periodic polls tether offload stats from tethering offload HAL
      * to make the data warnings work.
@@ -171,6 +173,7 @@
     private final int mP2pLeasesSubnetPrefixLength;
 
     private final boolean mEnableWearTethering;
+    private final boolean mRandomPrefixBase;
 
     private final int mUsbTetheringFunction;
     protected final ContentResolver mContentResolver;
@@ -288,6 +291,8 @@
 
         mEnableWearTethering = shouldEnableWearTethering(ctx);
 
+        mRandomPrefixBase = mDeps.isFeatureEnabled(ctx, TETHER_FORCE_RANDOM_PREFIX_BASE_SELECTION);
+
         configLog.log(toString());
     }
 
@@ -376,6 +381,10 @@
         return mEnableWearTethering;
     }
 
+    public boolean isRandomPrefixBaseEnabled() {
+        return mRandomPrefixBase;
+    }
+
     /** Does the dumping.*/
     public void dump(PrintWriter pw) {
         pw.print("activeDataSubId: ");
@@ -426,6 +435,9 @@
 
         pw.print("mUsbTetheringFunction: ");
         pw.println(isUsingNcm() ? "NCM" : "RNDIS");
+
+        pw.print("mRandomPrefixBase: ");
+        pw.println(mRandomPrefixBase);
     }
 
     /** Returns the string representation of this object.*/
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 6ebd6ae..2298a1a 100644
--- a/Tethering/tests/unit/src/com/android/networkstack/tethering/PrivateAddressCoordinatorTest.java
+++ b/Tethering/tests/unit/src/com/android/networkstack/tethering/PrivateAddressCoordinatorTest.java
@@ -30,6 +30,7 @@
 
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertNotEquals;
+import static org.junit.Assert.assertTrue;
 import static org.mockito.Mockito.never;
 import static org.mockito.Mockito.reset;
 import static org.mockito.Mockito.spy;
@@ -104,6 +105,7 @@
         when(mContext.getSystemService(Context.CONNECTIVITY_SERVICE)).thenReturn(mConnectivityMgr);
         when(mConnectivityMgr.getAllNetworks()).thenReturn(mAllNetworks);
         when(mConfig.shouldEnableWifiP2pDedicatedIp()).thenReturn(false);
+        when(mConfig.isRandomPrefixBaseEnabled()).thenReturn(false);
         setUpIpServers();
         mPrivateAddressCoordinator = spy(new PrivateAddressCoordinator(mContext, mConfig));
     }
@@ -572,4 +574,41 @@
         assertEquals("Wrong local hotspot prefix: ", new LinkAddress("192.168.134.5/24"),
                 localHotspotAddress);
     }
+
+    @Test
+    public void testStartedPrefixRange() throws Exception {
+        when(mConfig.isRandomPrefixBaseEnabled()).thenReturn(true);
+
+        startedPrefixBaseTest("192.168.0.0/16", 0);
+
+        startedPrefixBaseTest("192.168.0.0/16", 1);
+
+        startedPrefixBaseTest("192.168.0.0/16", 0xffff);
+
+        startedPrefixBaseTest("172.16.0.0/12", 0x10000);
+
+        startedPrefixBaseTest("172.16.0.0/12", 0x11111);
+
+        startedPrefixBaseTest("172.16.0.0/12", 0xfffff);
+
+        startedPrefixBaseTest("10.0.0.0/8", 0x100000);
+
+        startedPrefixBaseTest("10.0.0.0/8", 0x1fffff);
+
+        startedPrefixBaseTest("10.0.0.0/8", 0xffffff);
+
+        startedPrefixBaseTest("192.168.0.0/16", 0x1000000);
+    }
+
+    private void startedPrefixBaseTest(final String expected, final int randomIntForPrefixBase)
+            throws Exception {
+        mPrivateAddressCoordinator = spy(new PrivateAddressCoordinator(mContext, mConfig));
+        when(mPrivateAddressCoordinator.getRandomInt()).thenReturn(randomIntForPrefixBase);
+        final LinkAddress address = requestDownstreamAddress(mHotspotIpServer,
+                CONNECTIVITY_SCOPE_GLOBAL, false /* useLastAddress */);
+        final IpPrefix prefixBase = new IpPrefix(expected);
+        assertTrue(address + " is not part of " + prefixBase,
+                prefixBase.containsPrefix(asIpPrefix(address)));
+
+    }
 }