diff --git a/Tethering/src/android/net/dhcp/DhcpServingParamsParcelExt.java b/Tethering/src/android/net/dhcp/DhcpServingParamsParcelExt.java
index 4f8ad8a..4710a30 100644
--- a/Tethering/src/android/net/dhcp/DhcpServingParamsParcelExt.java
+++ b/Tethering/src/android/net/dhcp/DhcpServingParamsParcelExt.java
@@ -173,6 +173,18 @@
         return this;
     }
 
+    /**
+     * Set whether the DHCP server should request a new prefix from IpServer when receiving
+     * DHCPDECLINE message in certain particular link (e.g. there is only one downstream USB
+     * tethering client). If it's false, process DHCPDECLINE message as RFC2131#4.3.3 suggests.
+     *
+     * <p>If not set, the default value is false.
+     */
+    public DhcpServingParamsParcelExt setChangePrefixOnDecline(boolean changePrefixOnDecline) {
+        this.changePrefixOnDecline = changePrefixOnDecline;
+        return this;
+    }
+
     private static int[] toIntArray(@NonNull Collection<Inet4Address> addrs) {
         int[] res = new int[addrs.size()];
         int i = 0;
diff --git a/Tethering/src/android/net/ip/IpServer.java b/Tethering/src/android/net/ip/IpServer.java
index d993306..de53787 100644
--- a/Tethering/src/android/net/ip/IpServer.java
+++ b/Tethering/src/android/net/ip/IpServer.java
@@ -50,6 +50,7 @@
 import android.net.shared.RouteUtils;
 import android.net.util.InterfaceParams;
 import android.net.util.InterfaceSet;
+import android.net.util.PrefixUtils;
 import android.net.util.SharedLog;
 import android.os.Handler;
 import android.os.Looper;
@@ -60,6 +61,7 @@
 import android.util.SparseArray;
 
 import androidx.annotation.NonNull;
+import androidx.annotation.Nullable;
 
 import com.android.internal.util.MessageUtils;
 import com.android.internal.util.State;
@@ -115,6 +117,15 @@
     private static final String ETHERNET_IFACE_ADDR = "192.168.50.1";
     private static final int ETHERNET_IFACE_PREFIX_LENGTH = 24;
 
+    // TODO: remove this constant after introducing PrivateAddressCoordinator.
+    private static final List<IpPrefix> NCM_PREFIXES = Collections.unmodifiableList(
+            Arrays.asList(
+                    new IpPrefix("192.168.42.0/24"),
+                    new IpPrefix("192.168.51.0/24"),
+                    new IpPrefix("192.168.52.0/24"),
+                    new IpPrefix("192.168.53.0/24")
+    ));
+
     // TODO: have PanService use some visible version of this constant
     private static final String BLUETOOTH_IFACE_ADDR = "192.168.44.1";
     private static final int BLUETOOTH_DHCP_PREFIX_LENGTH = 24;
@@ -212,6 +223,8 @@
     public static final int CMD_IPV6_TETHER_UPDATE          = BASE_IPSERVER + 10;
     // new neighbor cache entry on our interface
     public static final int CMD_NEIGHBOR_EVENT              = BASE_IPSERVER + 11;
+    // request from DHCP server that it wants to have a new prefix
+    public static final int CMD_NEW_PREFIX_REQUEST          = BASE_IPSERVER + 12;
 
     private final State mInitialState;
     private final State mLocalHotspotState;
@@ -462,7 +475,7 @@
                                 handleError();
                             }
                         }
-                    }, new DhcpLeaseCallback());
+                    }, new DhcpEventCallback());
                 } catch (RemoteException e) {
                     throw new IllegalStateException(e);
                 }
@@ -475,7 +488,7 @@
         }
     }
 
-    private class DhcpLeaseCallback extends IDhcpEventCallbacks.Stub {
+    private class DhcpEventCallback extends IDhcpEventCallbacks.Stub {
         @Override
         public void onLeasesChanged(List<DhcpLeaseParcelable> leaseParcelables) {
             final ArrayList<TetheredClient> leases = new ArrayList<>();
@@ -509,8 +522,9 @@
         }
 
         @Override
-        public void onNewPrefixRequest(IpPrefix currentPrefix) {
-            //TODO: add specific implementation.
+        public void onNewPrefixRequest(@NonNull final IpPrefix currentPrefix) {
+            Objects.requireNonNull(currentPrefix);
+            sendMessage(CMD_NEW_PREFIX_REQUEST, currentPrefix);
         }
 
         @Override
@@ -524,26 +538,38 @@
         }
     }
 
+    private RouteInfo getDirectConnectedRoute(@NonNull final LinkAddress ipv4Address) {
+        Objects.requireNonNull(ipv4Address);
+        return new RouteInfo(PrefixUtils.asIpPrefix(ipv4Address), null, mIfaceName, RTN_UNICAST);
+    }
+
+    private DhcpServingParamsParcel makeServingParams(@NonNull final Inet4Address defaultRouter,
+            @NonNull final Inet4Address dnsServer, @NonNull LinkAddress serverAddr,
+            @Nullable Inet4Address clientAddr) {
+        final boolean changePrefixOnDecline =
+                (mInterfaceType == TetheringManager.TETHERING_NCM && clientAddr == null);
+        return new DhcpServingParamsParcelExt()
+            .setDefaultRouters(defaultRouter)
+            .setDhcpLeaseTimeSecs(DHCP_LEASE_TIME_SECS)
+            .setDnsServers(dnsServer)
+            .setServerAddr(serverAddr)
+            .setMetered(true)
+            .setSingleClientAddr(clientAddr)
+            .setChangePrefixOnDecline(changePrefixOnDecline);
+            // TODO: also advertise link MTU
+    }
+
     private boolean startDhcp(final LinkAddress serverLinkAddr, final LinkAddress clientLinkAddr) {
         if (mUsingLegacyDhcp) {
             return true;
         }
 
         final Inet4Address addr = (Inet4Address) serverLinkAddr.getAddress();
-        final int prefixLen = serverLinkAddr.getPrefixLength();
         final Inet4Address clientAddr = clientLinkAddr == null ? null :
                 (Inet4Address) clientLinkAddr.getAddress();
 
-        final DhcpServingParamsParcel params;
-        params = new DhcpServingParamsParcelExt()
-                .setDefaultRouters(addr)
-                .setDhcpLeaseTimeSecs(DHCP_LEASE_TIME_SECS)
-                .setDnsServers(addr)
-                .setServerAddr(serverLinkAddr)
-                .setMetered(true)
-                .setSingleClientAddr(clientAddr);
-        // TODO: also advertise link MTU
-
+        final DhcpServingParamsParcel params = makeServingParams(addr /* defaultRouter */,
+                addr /* dnsServer */, serverLinkAddr, clientAddr);
         mDhcpServerStartIndex++;
         mDeps.makeDhcpServer(
                 mIfaceName, params, new DhcpServerCallbacksImpl(mDhcpServerStartIndex));
@@ -570,7 +596,7 @@
                 });
                 mDhcpServer = null;
             } catch (RemoteException e) {
-                mLog.e("Error stopping DHCP", e);
+                mLog.e("Error stopping DHCP server", e);
                 // Not much more we can do here
             }
         }
@@ -652,31 +678,33 @@
             return false;
         }
 
-        // Directly-connected route.
-        final IpPrefix ipv4Prefix = new IpPrefix(mIpv4Address.getAddress(),
-                mIpv4Address.getPrefixLength());
-        final RouteInfo route = new RouteInfo(ipv4Prefix, null, null, RTN_UNICAST);
         if (enabled) {
             mLinkProperties.addLinkAddress(mIpv4Address);
-            mLinkProperties.addRoute(route);
+            mLinkProperties.addRoute(getDirectConnectedRoute(mIpv4Address));
         } else {
             mLinkProperties.removeLinkAddress(mIpv4Address);
-            mLinkProperties.removeRoute(route);
+            mLinkProperties.removeRoute(getDirectConnectedRoute(mIpv4Address));
         }
-
         return configureDhcp(enabled, mIpv4Address, mStaticIpv4ClientAddr);
     }
 
-    private String getRandomWifiIPv4Address() {
+    private Inet4Address getRandomIPv4Address(@NonNull final byte[] rawAddr) {
+        final byte[] ipv4Addr = rawAddr;
+        ipv4Addr[3] = getRandomSanitizedByte(DOUG_ADAMS, asByte(0), asByte(1), FF);
         try {
-            byte[] bytes = parseNumericAddress(WIFI_HOST_IFACE_ADDR).getAddress();
-            bytes[3] = getRandomSanitizedByte(DOUG_ADAMS, asByte(0), asByte(1), FF);
-            return InetAddress.getByAddress(bytes).getHostAddress();
-        } catch (Exception e) {
-            return WIFI_HOST_IFACE_ADDR;
+            return (Inet4Address) InetAddress.getByAddress(ipv4Addr);
+        } catch (UnknownHostException e) {
+            mLog.e("Failed to construct Inet4Address from raw IPv4 addr");
+            return null;
         }
     }
 
+    private String getRandomWifiIPv4Address() {
+        final Inet4Address ipv4Addr =
+                getRandomIPv4Address(parseNumericAddress(WIFI_HOST_IFACE_ADDR).getAddress());
+        return ipv4Addr != null ? ipv4Addr.getHostAddress() : WIFI_HOST_IFACE_ADDR;
+    }
+
     private boolean startIPv6() {
         mInterfaceParams = mDeps.getInterfaceParams(mIfaceName);
         if (mInterfaceParams == null) {
@@ -761,21 +789,43 @@
         mLastIPv6UpstreamIfindex = upstreamIfindex;
     }
 
+    private void removeRoutesFromLocalNetwork(@NonNull final List<RouteInfo> toBeRemoved) {
+        final int removalFailures = RouteUtils.removeRoutesFromLocalNetwork(
+                mNetd, toBeRemoved);
+        if (removalFailures > 0) {
+            mLog.e(String.format("Failed to remove %d IPv6 routes from local table.",
+                    removalFailures));
+        }
+
+        for (RouteInfo route : toBeRemoved) mLinkProperties.removeRoute(route);
+    }
+
+    private void addRoutesToLocalNetwork(@NonNull final List<RouteInfo> toBeAdded) {
+        try {
+            // It's safe to call networkAddInterface() even if
+            // the interface is already in the local_network.
+            mNetd.networkAddInterface(INetd.LOCAL_NET_ID, mIfaceName);
+            try {
+                // Add routes from local network. Note that adding routes that
+                // already exist does not cause an error (EEXIST is silently ignored).
+                RouteUtils.addRoutesToLocalNetwork(mNetd, mIfaceName, toBeAdded);
+            } catch (IllegalStateException e) {
+                mLog.e("Failed to add IPv4/v6 routes to local table: " + e);
+                return;
+            }
+        } catch (ServiceSpecificException | RemoteException e) {
+            mLog.e("Failed to add " + mIfaceName + " to local table: ", e);
+            return;
+        }
+
+        for (RouteInfo route : toBeAdded) mLinkProperties.addRoute(route);
+    }
+
     private void configureLocalIPv6Routes(
             HashSet<IpPrefix> deprecatedPrefixes, HashSet<IpPrefix> newPrefixes) {
         // [1] Remove the routes that are deprecated.
         if (!deprecatedPrefixes.isEmpty()) {
-            final ArrayList<RouteInfo> toBeRemoved =
-                    getLocalRoutesFor(mIfaceName, deprecatedPrefixes);
-            // Remove routes from local network.
-            final int removalFailures = RouteUtils.removeRoutesFromLocalNetwork(
-                    mNetd, toBeRemoved);
-            if (removalFailures > 0) {
-                mLog.e(String.format("Failed to remove %d IPv6 routes from local table.",
-                        removalFailures));
-            }
-
-            for (RouteInfo route : toBeRemoved) mLinkProperties.removeRoute(route);
+            removeRoutesFromLocalNetwork(getLocalRoutesFor(mIfaceName, deprecatedPrefixes));
         }
 
         // [2] Add only the routes that have not previously been added.
@@ -786,24 +836,7 @@
             }
 
             if (!addedPrefixes.isEmpty()) {
-                final ArrayList<RouteInfo> toBeAdded =
-                        getLocalRoutesFor(mIfaceName, addedPrefixes);
-                try {
-                    // It's safe to call networkAddInterface() even if
-                    // the interface is already in the local_network.
-                    mNetd.networkAddInterface(INetd.LOCAL_NET_ID, mIfaceName);
-                    try {
-                        // Add routes from local network. Note that adding routes that
-                        // already exist does not cause an error (EEXIST is silently ignored).
-                        RouteUtils.addRoutesToLocalNetwork(mNetd, mIfaceName, toBeAdded);
-                    } catch (IllegalStateException e) {
-                        mLog.e("Failed to add IPv6 routes to local table: " + e);
-                    }
-                } catch (ServiceSpecificException | RemoteException e) {
-                    mLog.e("Failed to add " + mIfaceName + " to local table: ", e);
-                }
-
-                for (RouteInfo route : toBeAdded) mLinkProperties.addRoute(route);
+                addRoutesToLocalNetwork(getLocalRoutesFor(mIfaceName, addedPrefixes));
             }
         }
     }
@@ -945,6 +978,80 @@
         }
     }
 
+    // TODO: call PrivateAddressCoordinator.requestDownstreamAddress instead of this temporary
+    // logic.
+    private Inet4Address requestDownstreamAddress(@NonNull final IpPrefix currentPrefix) {
+        final int oldIndex = NCM_PREFIXES.indexOf(currentPrefix);
+        if (oldIndex == -1) {
+            mLog.e("current prefix isn't supported for NCM link: " + currentPrefix);
+            return null;
+        }
+
+        final IpPrefix newPrefix = NCM_PREFIXES.get((oldIndex + 1) % NCM_PREFIXES.size());
+        return getRandomIPv4Address(newPrefix.getRawAddress());
+    }
+
+    private void handleNewPrefixRequest(@NonNull final IpPrefix currentPrefix) {
+        if (!currentPrefix.contains(mIpv4Address.getAddress())
+                || currentPrefix.getPrefixLength() != mIpv4Address.getPrefixLength()) {
+            Log.e(TAG, "Invalid prefix: " + currentPrefix);
+            return;
+        }
+
+        final LinkAddress deprecatedLinkAddress = mIpv4Address;
+        final Inet4Address srvAddr = requestDownstreamAddress(currentPrefix);
+        if (srvAddr == null) {
+            mLog.e("Fail to request a new downstream prefix");
+            return;
+        }
+        mIpv4Address = new LinkAddress(srvAddr, currentPrefix.getPrefixLength());
+
+        // Add new IPv4 address on the interface.
+        if (!mInterfaceCtrl.addAddress(srvAddr, currentPrefix.getPrefixLength())) {
+            mLog.e("Failed to add new IP " + srvAddr);
+            return;
+        }
+
+        // Remove deprecated routes from local network.
+        removeRoutesFromLocalNetwork(
+                Collections.singletonList(getDirectConnectedRoute(deprecatedLinkAddress)));
+        mLinkProperties.removeLinkAddress(deprecatedLinkAddress);
+
+        // Add new routes to local network.
+        addRoutesToLocalNetwork(
+                Collections.singletonList(getDirectConnectedRoute(mIpv4Address)));
+        mLinkProperties.addLinkAddress(mIpv4Address);
+
+        // Update local DNS caching server with new IPv4 address, otherwise, dnsmasq doesn't
+        // listen on the interface configured with new IPv4 address, that results DNS validation
+        // failure of downstream client even if appropriate routes have been configured.
+        try {
+            mNetd.tetherApplyDnsInterfaces();
+        } catch (ServiceSpecificException | RemoteException e) {
+            mLog.e("Failed to update local DNS caching server");
+            return;
+        }
+        sendLinkProperties();
+
+        // Notify DHCP server that new prefix/route has been applied on IpServer.
+        final Inet4Address clientAddr = mStaticIpv4ClientAddr == null ? null :
+                (Inet4Address) mStaticIpv4ClientAddr.getAddress();
+        final DhcpServingParamsParcel params = makeServingParams(srvAddr /* defaultRouter */,
+                srvAddr /* dnsServer */, mIpv4Address /* serverLinkAddress */, clientAddr);
+        try {
+            mDhcpServer.updateParams(params, new OnHandlerStatusCallback() {
+                    @Override
+                    public void callback(int statusCode) {
+                        if (statusCode != STATUS_SUCCESS) {
+                            mLog.e("Error updating DHCP serving params: " + statusCode);
+                        }
+                    }
+            });
+        } catch (RemoteException e) {
+            mLog.e("Error updating DHCP serving params", e);
+        }
+    }
+
     private byte getHopLimit(String upstreamIface) {
         try {
             int upstreamHopLimit = Integer.parseUnsignedInt(
@@ -1056,11 +1163,9 @@
             }
 
             try {
-                final IpPrefix ipv4Prefix = new IpPrefix(mIpv4Address.getAddress(),
-                        mIpv4Address.getPrefixLength());
-                NetdUtils.tetherInterface(mNetd, mIfaceName, ipv4Prefix);
+                NetdUtils.tetherInterface(mNetd, mIfaceName, PrefixUtils.asIpPrefix(mIpv4Address));
             } catch (RemoteException | ServiceSpecificException | IllegalStateException e) {
-                mLog.e("Error Tethering: " + e);
+                mLog.e("Error Tethering", e);
                 mLastError = TetheringManager.TETHER_ERROR_TETHER_IFACE_ERROR;
                 return;
             }
@@ -1115,6 +1220,9 @@
                     mLastError = TetheringManager.TETHER_ERROR_INTERNAL_ERROR;
                     transitionTo(mInitialState);
                     break;
+                case CMD_NEW_PREFIX_REQUEST:
+                    handleNewPrefixRequest((IpPrefix) message.obj);
+                    break;
                 default:
                     return false;
             }