diff --git a/Tethering/apishim/30/com/android/networkstack/tethering/apishim/api30/BpfCoordinatorShimImpl.java b/Tethering/apishim/30/com/android/networkstack/tethering/apishim/api30/BpfCoordinatorShimImpl.java
index e21325e..dc5fd6d 100644
--- a/Tethering/apishim/30/com/android/networkstack/tethering/apishim/api30/BpfCoordinatorShimImpl.java
+++ b/Tethering/apishim/30/com/android/networkstack/tethering/apishim/api30/BpfCoordinatorShimImpl.java
@@ -65,6 +65,17 @@
     };
 
     @Override
+    public boolean tetherOffloadRuleRemove(@NonNull final Ipv6ForwardingRule rule) {
+        try {
+            mNetd.tetherOffloadRuleRemove(rule.toTetherOffloadRuleParcel());
+        } catch (RemoteException | ServiceSpecificException e) {
+            mLog.e("Could not remove IPv6 forwarding rule: ", e);
+            return false;
+        }
+        return true;
+    }
+
+    @Override
     @Nullable
     public SparseArray<TetherStatsValue> tetherOffloadGetStats() {
         final TetherStatsParcel[] tetherStatsList;
diff --git a/Tethering/apishim/31/com/android/networkstack/tethering/apishim/api31/BpfCoordinatorShimImpl.java b/Tethering/apishim/31/com/android/networkstack/tethering/apishim/api31/BpfCoordinatorShimImpl.java
index d00ccc2..f6630d6 100644
--- a/Tethering/apishim/31/com/android/networkstack/tethering/apishim/api31/BpfCoordinatorShimImpl.java
+++ b/Tethering/apishim/31/com/android/networkstack/tethering/apishim/api31/BpfCoordinatorShimImpl.java
@@ -18,6 +18,7 @@
 
 import android.net.util.SharedLog;
 import android.system.ErrnoException;
+import android.system.OsConstants;
 import android.util.SparseArray;
 
 import androidx.annotation.NonNull;
@@ -79,6 +80,22 @@
     }
 
     @Override
+    public boolean tetherOffloadRuleRemove(@NonNull final Ipv6ForwardingRule rule) {
+        if (!isInitialized()) return false;
+
+        try {
+            mBpfIngressMap.deleteEntry(rule.makeTetherIngressKey());
+        } catch (ErrnoException e) {
+            // Silent if the rule did not exist.
+            if (e.errno != OsConstants.ENOENT) {
+                mLog.e("Could not update entry: ", e);
+                return false;
+            }
+        }
+        return true;
+    }
+
+    @Override
     @Nullable
     public SparseArray<TetherStatsValue> tetherOffloadGetStats() {
         if (!isInitialized()) return null;
diff --git a/Tethering/apishim/common/com/android/networkstack/tethering/apishim/common/BpfCoordinatorShim.java b/Tethering/apishim/common/com/android/networkstack/tethering/apishim/common/BpfCoordinatorShim.java
index 97d3402..2ce3252 100644
--- a/Tethering/apishim/common/com/android/networkstack/tethering/apishim/common/BpfCoordinatorShim.java
+++ b/Tethering/apishim/common/com/android/networkstack/tethering/apishim/common/BpfCoordinatorShim.java
@@ -60,6 +60,17 @@
     public abstract boolean tetherOffloadRuleAdd(@NonNull Ipv6ForwardingRule rule);
 
     /**
+     * Deletes a tethering offload rule from the BPF map.
+     *
+     * Currently, only downstream /128 IPv6 entries are supported. An existing rule will be deleted
+     * if the destination IP address and the source interface match. It is not an error if there is
+     * no matching rule to delete.
+     *
+     * @param rule The rule to delete.
+     */
+    public abstract boolean tetherOffloadRuleRemove(@NonNull Ipv6ForwardingRule rule);
+
+    /**
      * Return BPF tethering offload statistics.
      *
      * @return an array of TetherStatsValue's, where each entry contains the upstream interface
diff --git a/Tethering/src/com/android/networkstack/tethering/BpfCoordinator.java b/Tethering/src/com/android/networkstack/tethering/BpfCoordinator.java
index 4afbed2..4f918ec 100644
--- a/Tethering/src/com/android/networkstack/tethering/BpfCoordinator.java
+++ b/Tethering/src/com/android/networkstack/tethering/BpfCoordinator.java
@@ -329,13 +329,7 @@
             @NonNull final IpServer ipServer, @NonNull final Ipv6ForwardingRule rule) {
         if (!isUsingBpf()) return;
 
-        try {
-            // TODO: Perhaps avoid to remove a non-existent rule.
-            mNetd.tetherOffloadRuleRemove(rule.toTetherOffloadRuleParcel());
-        } catch (RemoteException | ServiceSpecificException e) {
-            mLog.e("Could not remove IPv6 forwarding rule: ", e);
-            return;
-        }
+        if (!mBpfCoordinatorShim.tetherOffloadRuleRemove(rule)) return;
 
         LinkedHashMap<Inet6Address, Ipv6ForwardingRule> rules = mIpv6ForwardingRules.get(ipServer);
         if (rules == null) return;
diff --git a/Tethering/tests/unit/src/android/net/ip/IpServerTest.java b/Tethering/tests/unit/src/android/net/ip/IpServerTest.java
index 4ae1552..91a518e 100644
--- a/Tethering/tests/unit/src/android/net/ip/IpServerTest.java
+++ b/Tethering/tests/unit/src/android/net/ip/IpServerTest.java
@@ -810,6 +810,28 @@
         }
     }
 
+    private void verifyTetherOffloadRuleRemove(@Nullable InOrder inOrder, int upstreamIfindex,
+            @NonNull final InetAddress dst, @NonNull final MacAddress dstMac) throws Exception {
+        if (mBpfDeps.isAtLeastS()) {
+            verifyWithOrder(inOrder, mBpfIngressMap).deleteEntry(makeIngressKey(upstreamIfindex,
+                    dst));
+        } else {
+            // |dstMac| is not required for deleting rules. Used bacause tetherOffloadRuleRemove
+            // uses a whole rule to be a argument.
+            // See system/netd/server/TetherController.cpp/TetherController#removeOffloadRule.
+            verifyWithOrder(inOrder, mNetd).tetherOffloadRuleRemove(matches(upstreamIfindex, dst,
+                    dstMac));
+        }
+    }
+
+    private void verifyNeverTetherOffloadRuleRemove() throws Exception {
+        if (mBpfDeps.isAtLeastS()) {
+            verify(mBpfIngressMap, never()).deleteEntry(any());
+        } else {
+            verify(mNetd, never()).tetherOffloadRuleRemove(any());
+        }
+    }
+
     @NonNull
     private static TetherStatsParcel buildEmptyTetherStatsParcel(int ifIndex) {
         TetherStatsParcel parcel = new TetherStatsParcel();
@@ -877,14 +899,14 @@
         recvNewNeigh(myIfindex, neighA, NUD_FAILED, null);
         verify(mBpfCoordinator).tetherOffloadRuleRemove(
                 mIpServer, makeForwardingRule(UPSTREAM_IFINDEX, neighA, macNull));
-        verify(mNetd).tetherOffloadRuleRemove(matches(UPSTREAM_IFINDEX, neighA, macNull));
+        verifyTetherOffloadRuleRemove(null, UPSTREAM_IFINDEX, neighA, macNull);
         resetNetdBpfMapAndCoordinator();
 
         // A neighbor that is deleted causes the rule to be removed.
         recvDelNeigh(myIfindex, neighB, NUD_STALE, macB);
         verify(mBpfCoordinator).tetherOffloadRuleRemove(
                 mIpServer,  makeForwardingRule(UPSTREAM_IFINDEX, neighB, macNull));
-        verify(mNetd).tetherOffloadRuleRemove(matches(UPSTREAM_IFINDEX, neighB, macNull));
+        verifyTetherOffloadRuleRemove(null, UPSTREAM_IFINDEX, neighB, macNull);
         resetNetdBpfMapAndCoordinator();
 
         // Upstream changes result in updating the rules.
@@ -897,9 +919,9 @@
         lp.setInterfaceName(UPSTREAM_IFACE2);
         dispatchTetherConnectionChanged(UPSTREAM_IFACE2, lp, -1);
         verify(mBpfCoordinator).tetherOffloadRuleUpdate(mIpServer, UPSTREAM_IFINDEX2);
-        inOrder.verify(mNetd).tetherOffloadRuleRemove(matches(UPSTREAM_IFINDEX, neighA, macA));
+        verifyTetherOffloadRuleRemove(inOrder, UPSTREAM_IFINDEX, neighA, macA);
         verifyTetherOffloadRuleAdd(inOrder, UPSTREAM_IFINDEX2, neighA, macA);
-        inOrder.verify(mNetd).tetherOffloadRuleRemove(matches(UPSTREAM_IFINDEX, neighB, macB));
+        verifyTetherOffloadRuleRemove(inOrder, UPSTREAM_IFINDEX, neighB, macB);
         verifyTetherOffloadRuleAdd(inOrder, UPSTREAM_IFINDEX2, neighB, macB);
         resetNetdBpfMapAndCoordinator();
 
@@ -910,8 +932,8 @@
         // - processMessage CMD_IPV6_TETHER_UPDATE for the IPv6 upstream is lost.
         // See dispatchTetherConnectionChanged.
         verify(mBpfCoordinator, times(2)).tetherOffloadRuleClear(mIpServer);
-        verify(mNetd).tetherOffloadRuleRemove(matches(UPSTREAM_IFINDEX2, neighA, macA));
-        verify(mNetd).tetherOffloadRuleRemove(matches(UPSTREAM_IFINDEX2, neighB, macB));
+        verifyTetherOffloadRuleRemove(null, UPSTREAM_IFINDEX2, neighA, macA);
+        verifyTetherOffloadRuleRemove(null, UPSTREAM_IFINDEX2, neighB, macB);
         resetNetdBpfMapAndCoordinator();
 
         // If the upstream is IPv4-only, no rules are added.
@@ -937,7 +959,7 @@
         resetNetdBpfMapAndCoordinator();
         dispatchTetherConnectionChanged(UPSTREAM_IFACE, null, 0);
         verify(mBpfCoordinator).tetherOffloadRuleClear(mIpServer);
-        verify(mNetd).tetherOffloadRuleRemove(matches(UPSTREAM_IFINDEX, neighB, macB));
+        verifyTetherOffloadRuleRemove(null, UPSTREAM_IFINDEX, neighB, macB);
 
         // When the interface goes down, rules are removed.
         lp.setInterfaceName(UPSTREAM_IFACE);
@@ -955,8 +977,8 @@
         mIpServer.stop();
         mLooper.dispatchAll();
         verify(mBpfCoordinator).tetherOffloadRuleClear(mIpServer);
-        verify(mNetd).tetherOffloadRuleRemove(matches(UPSTREAM_IFINDEX, neighA, macA));
-        verify(mNetd).tetherOffloadRuleRemove(matches(UPSTREAM_IFINDEX, neighB, macB));
+        verifyTetherOffloadRuleRemove(null, UPSTREAM_IFINDEX, neighA, macA);
+        verifyTetherOffloadRuleRemove(null, UPSTREAM_IFINDEX, neighB, macB);
         verify(mIpNeighborMonitor).stop();
         resetNetdBpfMapAndCoordinator();
     }
@@ -990,7 +1012,7 @@
         recvDelNeigh(myIfindex, neigh, NUD_STALE, macA);
         verify(mBpfCoordinator).tetherOffloadRuleRemove(
                 mIpServer, makeForwardingRule(UPSTREAM_IFINDEX, neigh, macNull));
-        verify(mNetd).tetherOffloadRuleRemove(matches(UPSTREAM_IFINDEX, neigh, macNull));
+        verifyTetherOffloadRuleRemove(null, UPSTREAM_IFINDEX, neigh, macNull);
         resetNetdBpfMapAndCoordinator();
 
         // [2] Disable BPF offload.
@@ -1006,7 +1028,7 @@
 
         recvDelNeigh(myIfindex, neigh, NUD_STALE, macA);
         verify(mBpfCoordinator, never()).tetherOffloadRuleRemove(any(), any());
-        verify(mNetd, never()).tetherOffloadRuleRemove(any());
+        verifyNeverTetherOffloadRuleRemove();
         resetNetdBpfMapAndCoordinator();
     }
 
diff --git a/Tethering/tests/unit/src/com/android/networkstack/tethering/BpfCoordinatorTest.java b/Tethering/tests/unit/src/com/android/networkstack/tethering/BpfCoordinatorTest.java
index 058e199..5ca220c 100644
--- a/Tethering/tests/unit/src/com/android/networkstack/tethering/BpfCoordinatorTest.java
+++ b/Tethering/tests/unit/src/com/android/networkstack/tethering/BpfCoordinatorTest.java
@@ -308,13 +308,30 @@
         }
     }
 
+    private void verifyTetherOffloadRuleRemove(@Nullable InOrder inOrder,
+            @NonNull final Ipv6ForwardingRule rule) throws Exception {
+        if (mDeps.isAtLeastS()) {
+            verifyWithOrder(inOrder, mBpfIngressMap).deleteEntry(rule.makeTetherIngressKey());
+        } else {
+            verifyWithOrder(inOrder, mNetd).tetherOffloadRuleRemove(matches(rule));
+        }
+    }
+
+    private void verifyNeverTetherOffloadRuleRemove() throws Exception {
+        if (mDeps.isAtLeastS()) {
+            verify(mBpfIngressMap, never()).deleteEntry(any());
+        } else {
+            verify(mNetd, never()).tetherOffloadRuleRemove(any());
+        }
+    }
+
     // S+ and R api minimum tests.
     // The following tests are used to provide minimum checking for the APIs on different flow.
     // The auto merge is not enabled on mainline prod. The code flow R may be verified at the
     // late stage by manual cherry pick. It is risky if the R code flow has broken and be found at
     // the last minute.
     // TODO: remove once presubmit tests on R even the code is submitted on S.
-    private void checkTetherOffloadRuleAdd(boolean usingApiS) throws Exception {
+    private void checkTetherOffloadRuleAddAndRemove(boolean usingApiS) throws Exception {
         setupFunctioningNetdInterface();
 
         // Replace Dependencies#isAtLeastS() for testing R and S+ BPF map apis. Note that |mDeps|
@@ -330,18 +347,24 @@
         final Ipv6ForwardingRule rule = buildTestForwardingRule(mobileIfIndex, NEIGH_A, MAC_A);
         coordinator.tetherOffloadRuleAdd(mIpServer, rule);
         verifyTetherOffloadRuleAdd(null, rule);
+
+        // Removing the last rule on current upstream immediately sends the cleanup stuff to netd.
+        when(mNetd.tetherOffloadGetAndClearStats(mobileIfIndex))
+                .thenReturn(buildTestTetherStatsParcel(mobileIfIndex, 0, 0, 0, 0));
+        coordinator.tetherOffloadRuleRemove(mIpServer, rule);
+        verifyTetherOffloadRuleRemove(null, rule);
     }
 
     // TODO: remove once presubmit tests on R even the code is submitted on S.
     @Test
-    public void testTetherOffloadRuleAddSdkR() throws Exception {
-        checkTetherOffloadRuleAdd(false /* R */);
+    public void testTetherOffloadRuleAddAndRemoveSdkR() throws Exception {
+        checkTetherOffloadRuleAddAndRemove(false /* R */);
     }
 
     // TODO: remove once presubmit tests on R even the code is submitted on S.
     @Test
-    public void testTetherOffloadRuleAddAtLeastSdkS() throws Exception {
-        checkTetherOffloadRuleAdd(true /* S+ */);
+    public void testTetherOffloadRuleAddAndRemoveAtLeastSdkS() throws Exception {
+        checkTetherOffloadRuleAddAndRemove(true /* S+ */);
     }
 
     // TODO: remove once presubmit tests on R even the code is submitted on S.
@@ -634,14 +657,14 @@
 
         // Removing the second rule on current upstream does not send the quota to netd.
         coordinator.tetherOffloadRuleRemove(mIpServer, ruleB);
-        inOrder.verify(mNetd).tetherOffloadRuleRemove(matches(ruleB));
+        verifyTetherOffloadRuleRemove(inOrder, ruleB);
         inOrder.verify(mNetd, never()).tetherOffloadSetInterfaceQuota(anyInt(), anyLong());
 
         // Removing the last rule on current upstream immediately sends the cleanup stuff to netd.
         when(mNetd.tetherOffloadGetAndClearStats(mobileIfIndex))
                 .thenReturn(buildTestTetherStatsParcel(mobileIfIndex, 0, 0, 0, 0));
         coordinator.tetherOffloadRuleRemove(mIpServer, ruleA);
-        inOrder.verify(mNetd).tetherOffloadRuleRemove(matches(ruleA));
+        verifyTetherOffloadRuleRemove(inOrder, ruleA);
         inOrder.verify(mNetd).tetherOffloadGetAndClearStats(mobileIfIndex);
         inOrder.verifyNoMoreInteractions();
     }
@@ -693,10 +716,10 @@
         // Update the existing rules for upstream changes. The rules are removed and re-added one
         // by one for updating upstream interface index by #tetherOffloadRuleUpdate.
         coordinator.tetherOffloadRuleUpdate(mIpServer, mobileIfIndex);
-        inOrder.verify(mNetd).tetherOffloadRuleRemove(matches(ethernetRuleA));
+        verifyTetherOffloadRuleRemove(inOrder, ethernetRuleA);
         verifyTetherOffloadRuleAdd(inOrder, mobileRuleA);
         inOrder.verify(mNetd).tetherOffloadSetInterfaceQuota(mobileIfIndex, QUOTA_UNLIMITED);
-        inOrder.verify(mNetd).tetherOffloadRuleRemove(matches(ethernetRuleB));
+        verifyTetherOffloadRuleRemove(inOrder, ethernetRuleB);
         inOrder.verify(mNetd).tetherOffloadGetAndClearStats(ethIfIndex);
         verifyTetherOffloadRuleAdd(inOrder, mobileRuleB);
 
@@ -704,8 +727,8 @@
         when(mNetd.tetherOffloadGetAndClearStats(mobileIfIndex))
                 .thenReturn(buildTestTetherStatsParcel(mobileIfIndex, 50, 60, 70, 80));
         coordinator.tetherOffloadRuleClear(mIpServer);
-        inOrder.verify(mNetd).tetherOffloadRuleRemove(matches(mobileRuleA));
-        inOrder.verify(mNetd).tetherOffloadRuleRemove(matches(mobileRuleB));
+        verifyTetherOffloadRuleRemove(inOrder, mobileRuleA);
+        verifyTetherOffloadRuleRemove(inOrder, mobileRuleB);
         inOrder.verify(mNetd).tetherOffloadGetAndClearStats(mobileIfIndex);
 
         // [4] Force pushing stats update to verify that the last diff of stats is reported on all
@@ -755,21 +778,21 @@
         rules.put(rule.address, rule);
         coordinator.getForwardingRulesForTesting().put(mIpServer, rules);
         coordinator.tetherOffloadRuleRemove(mIpServer, rule);
-        verify(mNetd, never()).tetherOffloadRuleRemove(any());
+        verifyNeverTetherOffloadRuleRemove();
         rules = coordinator.getForwardingRulesForTesting().get(mIpServer);
         assertNotNull(rules);
         assertEquals(1, rules.size());
 
         // The rule can't be cleared.
         coordinator.tetherOffloadRuleClear(mIpServer);
-        verify(mNetd, never()).tetherOffloadRuleRemove(any());
+        verifyNeverTetherOffloadRuleRemove();
         rules = coordinator.getForwardingRulesForTesting().get(mIpServer);
         assertNotNull(rules);
         assertEquals(1, rules.size());
 
         // The rule can't be updated.
         coordinator.tetherOffloadRuleUpdate(mIpServer, rule.upstreamIfindex + 1 /* new */);
-        verify(mNetd, never()).tetherOffloadRuleRemove(any());
+        verifyNeverTetherOffloadRuleRemove();
         verifyNeverTetherOffloadRuleAdd();
         rules = coordinator.getForwardingRulesForTesting().get(mIpServer);
         assertNotNull(rules);