diff --git a/core/java/android/net/RouteInfo.java b/core/java/android/net/RouteInfo.java
index e550f85..9876076 100644
--- a/core/java/android/net/RouteInfo.java
+++ b/core/java/android/net/RouteInfo.java
@@ -26,7 +26,6 @@
 import android.os.Build;
 import android.os.Parcel;
 import android.os.Parcelable;
-import android.util.Pair;
 
 import java.lang.annotation.Retention;
 import java.lang.annotation.RetentionPolicy;
@@ -554,15 +553,45 @@
     }
 
     /**
-     * A helper class that contains the destination and the gateway in a {@code RouteInfo},
-     * used by {@link ConnectivityService#updateRoutes} or
+     * A helper class that contains the destination, the gateway and the interface in a
+     * {@code RouteInfo}, used by {@link ConnectivityService#updateRoutes} or
      * {@link LinkProperties#addRoute} to calculate the list to be updated.
+     * {@code RouteInfo} objects with different interfaces are treated as different routes because
+     * *usually* on Android different interfaces use different routing tables, and moving a route
+     * to a new routing table never constitutes an update, but is always a remove and an add.
      *
      * @hide
      */
-    public static class RouteKey extends Pair<IpPrefix, InetAddress> {
-        RouteKey(@NonNull IpPrefix destination, @Nullable InetAddress gateway) {
-            super(destination, gateway);
+    public static class RouteKey {
+        @NonNull private final IpPrefix mDestination;
+        @Nullable private final InetAddress mGateway;
+        @Nullable private final String mInterface;
+
+        RouteKey(@NonNull IpPrefix destination, @Nullable InetAddress gateway,
+                @Nullable String iface) {
+            mDestination = destination;
+            mGateway = gateway;
+            mInterface = iface;
+        }
+
+        @Override
+        public boolean equals(Object o) {
+            if (!(o instanceof RouteKey)) {
+                return false;
+            }
+            RouteKey p = (RouteKey) o;
+            // No need to do anything special for scoped addresses. Inet6Address#equals does not
+            // consider the scope ID, but the netd route IPCs (e.g., INetd#networkAddRouteParcel)
+            // and the kernel ignore scoped addresses both in the prefix and in the nexthop and only
+            // look at RTA_OIF.
+            return Objects.equals(p.mDestination, mDestination)
+                    && Objects.equals(p.mGateway, mGateway)
+                    && Objects.equals(p.mInterface, mInterface);
+        }
+
+        @Override
+        public int hashCode() {
+            return Objects.hash(mDestination, mGateway, mInterface);
         }
     }
 
@@ -574,7 +603,7 @@
      */
     @NonNull
     public RouteKey getRouteKey() {
-        return new RouteKey(mDestination, mGateway);
+        return new RouteKey(mDestination, mGateway, mInterface);
     }
 
     /**
diff --git a/tests/net/common/java/android/net/LinkPropertiesTest.java b/tests/net/common/java/android/net/LinkPropertiesTest.java
index 0fc9be3..6eba62e 100644
--- a/tests/net/common/java/android/net/LinkPropertiesTest.java
+++ b/tests/net/common/java/android/net/LinkPropertiesTest.java
@@ -16,6 +16,8 @@
 
 package android.net;
 
+import static android.net.RouteInfo.RTN_THROW;
+import static android.net.RouteInfo.RTN_UNICAST;
 import static android.net.RouteInfo.RTN_UNREACHABLE;
 
 import static com.android.testutils.ParcelUtilsKt.assertParcelSane;
@@ -1282,4 +1284,20 @@
         assertTrue(lp.hasIpv6UnreachableDefaultRoute());
         assertFalse(lp.hasIpv4UnreachableDefaultRoute());
     }
+
+    @Test @IgnoreUpTo(Build.VERSION_CODES.Q)
+    public void testRouteAddWithSameKey() throws Exception {
+        LinkProperties lp = new LinkProperties();
+        lp.setInterfaceName("wlan0");
+        final IpPrefix v6 = new IpPrefix("64:ff9b::/96");
+        lp.addRoute(new RouteInfo(v6, address("fe80::1"), "wlan0", RTN_UNICAST, 1280));
+        assertEquals(1, lp.getRoutes().size());
+        lp.addRoute(new RouteInfo(v6, address("fe80::1"), "wlan0", RTN_UNICAST, 1500));
+        assertEquals(1, lp.getRoutes().size());
+        final IpPrefix v4 = new IpPrefix("192.0.2.128/25");
+        lp.addRoute(new RouteInfo(v4, address("192.0.2.1"), "wlan0", RTN_UNICAST, 1460));
+        assertEquals(2, lp.getRoutes().size());
+        lp.addRoute(new RouteInfo(v4, address("192.0.2.1"), "wlan0", RTN_THROW, 1460));
+        assertEquals(2, lp.getRoutes().size());
+    }
 }
diff --git a/tests/net/common/java/android/net/RouteInfoTest.java b/tests/net/common/java/android/net/RouteInfoTest.java
index 8204b49..60cac0b 100644
--- a/tests/net/common/java/android/net/RouteInfoTest.java
+++ b/tests/net/common/java/android/net/RouteInfoTest.java
@@ -25,6 +25,7 @@
 
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotEquals;
 import static org.junit.Assert.assertNull;
 import static org.junit.Assert.assertTrue;
 import static org.junit.Assert.fail;
@@ -56,7 +57,7 @@
     private static final int INVALID_ROUTE_TYPE = -1;
 
     private InetAddress Address(String addr) {
-        return InetAddress.parseNumericAddress(addr);
+        return InetAddresses.parseNumericAddress(addr);
     }
 
     private IpPrefix Prefix(String prefix) {
@@ -391,4 +392,43 @@
         r = new RouteInfo(Prefix("0.0.0.0/0"), Address("0.0.0.0"), "wlan0");
         assertEquals(0, r.getMtu());
     }
+
+    @Test @IgnoreUpTo(Build.VERSION_CODES.Q)
+    public void testRouteKey() {
+        RouteInfo.RouteKey k1, k2;
+        // Only prefix, null gateway and null interface
+        k1 = new RouteInfo(Prefix("2001:db8::/128"), null).getRouteKey();
+        k2 = new RouteInfo(Prefix("2001:db8::/128"), null).getRouteKey();
+        assertEquals(k1, k2);
+        assertEquals(k1.hashCode(), k2.hashCode());
+
+        // With prefix, gateway and interface. Type and MTU does not affect RouteKey equality
+        k1 = new RouteInfo(Prefix("192.0.2.0/24"), Address("192.0.2.1"), "wlan0",
+                RTN_UNREACHABLE, 1450).getRouteKey();
+        k2 = new RouteInfo(Prefix("192.0.2.0/24"), Address("192.0.2.1"), "wlan0",
+                RouteInfo.RTN_UNICAST, 1400).getRouteKey();
+        assertEquals(k1, k2);
+        assertEquals(k1.hashCode(), k2.hashCode());
+
+        // Different scope IDs are ignored by the kernel, so we consider them equal here too.
+        k1 = new RouteInfo(Prefix("2001:db8::/64"), Address("fe80::1%1"), "wlan0").getRouteKey();
+        k2 = new RouteInfo(Prefix("2001:db8::/64"), Address("fe80::1%2"), "wlan0").getRouteKey();
+        assertEquals(k1, k2);
+        assertEquals(k1.hashCode(), k2.hashCode());
+
+        // Different prefix
+        k1 = new RouteInfo(Prefix("192.0.2.0/24"), null).getRouteKey();
+        k2 = new RouteInfo(Prefix("192.0.3.0/24"), null).getRouteKey();
+        assertNotEquals(k1, k2);
+
+        // Different gateway
+        k1 = new RouteInfo(Prefix("ff02::1/128"), Address("2001:db8::1"), null).getRouteKey();
+        k2 = new RouteInfo(Prefix("ff02::1/128"), Address("2001:db8::2"), null).getRouteKey();
+        assertNotEquals(k1, k2);
+
+        // Different interface
+        k1 = new RouteInfo(Prefix("ff02::1/128"), null, "tun0").getRouteKey();
+        k2 = new RouteInfo(Prefix("ff02::1/128"), null, "tun1").getRouteKey();
+        assertNotEquals(k1, k2);
+    }
 }