diff --git a/core/java/android/net/LinkProperties.java b/core/java/android/net/LinkProperties.java
index 2c356e4..7ff954b 100644
--- a/core/java/android/net/LinkProperties.java
+++ b/core/java/android/net/LinkProperties.java
@@ -690,9 +690,9 @@
             route.getMtu());
     }
 
-    private int findRouteIndexByDestination(RouteInfo route) {
+    private int findRouteIndexByRouteKey(RouteInfo route) {
         for (int i = 0; i < mRoutes.size(); i++) {
-            if (mRoutes.get(i).isSameDestinationAs(route)) {
+            if (mRoutes.get(i).getRouteKey().equals(route.getRouteKey())) {
                 return i;
             }
         }
@@ -701,11 +701,11 @@
 
     /**
      * Adds a {@link RouteInfo} to this {@code LinkProperties}, if a {@link RouteInfo}
-     * with the same destination exists with different properties (e.g., different MTU),
-     * it will be updated. If the {@link RouteInfo} had an interface name set and
-     * that differs from the interface set for this {@code LinkProperties} an
-     * {@link IllegalArgumentException} will be thrown.  The proper
-     * course is to add either un-named or properly named {@link RouteInfo}.
+     * with the same {@link RouteInfo.RouteKey} with different properties
+     * (e.g., different MTU), it will be updated. If the {@link RouteInfo} had an
+     * interface name set and that differs from the interface set for this
+     * {@code LinkProperties} an {@link IllegalArgumentException} will be thrown.
+     * The proper course is to add either un-named or properly named {@link RouteInfo}.
      *
      * @param route A {@link RouteInfo} to add to this object.
      * @return {@code true} was added or updated, false otherwise.
@@ -719,7 +719,7 @@
         }
         route = routeWithInterface(route);
 
-        int i = findRouteIndexByDestination(route);
+        int i = findRouteIndexByRouteKey(route);
         if (i == -1) {
             // Route was not present. Add it.
             mRoutes.add(route);
diff --git a/core/java/android/net/RouteInfo.java b/core/java/android/net/RouteInfo.java
index fec2df4..dbdaa4c 100644
--- a/core/java/android/net/RouteInfo.java
+++ b/core/java/android/net/RouteInfo.java
@@ -26,6 +26,7 @@
 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;
@@ -527,23 +528,27 @@
     }
 
     /**
-     * Compares this RouteInfo object against the specified object and indicates if the
-     * destinations of both routes are equal.
-     * @return {@code true} if the route destinations are equal, {@code false} otherwise.
+     * A helper class that contains the destination and the gateway in a {@code RouteInfo},
+     * used by {@link ConnectivityService#updateRoutes} or
+     * {@link LinkProperties#addRoute} to calculate the list to be updated.
      *
      * @hide
      */
-    public boolean isSameDestinationAs(@Nullable Object obj) {
-        if (this == obj) return true;
-
-        if (!(obj instanceof RouteInfo)) return false;
-
-        RouteInfo target = (RouteInfo) obj;
-
-        if (Objects.equals(mDestination, target.getDestination())) {
-            return true;
+    public static class RouteKey extends Pair<IpPrefix, InetAddress> {
+        RouteKey(@NonNull IpPrefix destination, @Nullable InetAddress gateway) {
+            super(destination, gateway);
         }
-        return false;
+    }
+
+    /**
+     * Get {@code RouteKey} of this {@code RouteInfo}.
+     * @return a {@code RouteKey} object.
+     *
+     * @hide
+     */
+    @NonNull
+    public RouteKey getRouteKey() {
+        return new RouteKey(mDestination, mGateway);
     }
 
     /**
diff --git a/services/core/java/com/android/server/ConnectivityService.java b/services/core/java/com/android/server/ConnectivityService.java
index 1ec4bc3..63be13c 100644
--- a/services/core/java/com/android/server/ConnectivityService.java
+++ b/services/core/java/com/android/server/ConnectivityService.java
@@ -236,7 +236,6 @@
 import java.util.StringJoiner;
 import java.util.TreeSet;
 import java.util.concurrent.atomic.AtomicInteger;
-import java.util.function.Function;
 
 /**
  * @hide
@@ -5982,12 +5981,12 @@
      * @return true if routes changed between oldLp and newLp
      */
     private boolean updateRoutes(LinkProperties newLp, LinkProperties oldLp, int netId) {
-        Function<RouteInfo, IpPrefix> getDestination = (r) -> r.getDestination();
         // compare the route diff to determine which routes have been updated
-        CompareOrUpdateResult<IpPrefix, RouteInfo> routeDiff = new CompareOrUpdateResult<>(
-                oldLp != null ? oldLp.getAllRoutes() : null,
-                newLp != null ? newLp.getAllRoutes() : null,
-                getDestination);
+        final CompareOrUpdateResult<RouteInfo.RouteKey, RouteInfo> routeDiff =
+                new CompareOrUpdateResult<>(
+                        oldLp != null ? oldLp.getAllRoutes() : null,
+                        newLp != null ? newLp.getAllRoutes() : null,
+                        (r) -> r.getRouteKey());
 
         // add routes before removing old in case it helps with continuous connectivity