diff --git a/apps/dhcprelay/src/main/java/org/onosproject/dhcprelay/Dhcp4HandlerImpl.java b/apps/dhcprelay/src/main/java/org/onosproject/dhcprelay/Dhcp4HandlerImpl.java
index 424b628..04a9967 100644
--- a/apps/dhcprelay/src/main/java/org/onosproject/dhcprelay/Dhcp4HandlerImpl.java
+++ b/apps/dhcprelay/src/main/java/org/onosproject/dhcprelay/Dhcp4HandlerImpl.java
@@ -1479,7 +1479,7 @@
             }
 
             Route route = new Route(Route.Source.DHCP, ip.toIpPrefix(), nextHopIp);
-            routeStore.updateRoute(route);
+            routeStore.replaceRoute(route);
         }
     }
 
diff --git a/apps/dhcprelay/src/main/java/org/onosproject/dhcprelay/Dhcp6HandlerImpl.java b/apps/dhcprelay/src/main/java/org/onosproject/dhcprelay/Dhcp6HandlerImpl.java
index d70476a..3cfcb68 100644
--- a/apps/dhcprelay/src/main/java/org/onosproject/dhcprelay/Dhcp6HandlerImpl.java
+++ b/apps/dhcprelay/src/main/java/org/onosproject/dhcprelay/Dhcp6HandlerImpl.java
@@ -966,7 +966,7 @@
                 if (isMsgReply) {
                     Route routeForIP = new Route(Route.Source.DHCP, ipInfo.ip6Address.toIpPrefix(), nextHopIp);
                     log.debug("adding Route of 128 address for indirectly connected.");
-                    routeStore.updateRoute(routeForIP);
+                    routeStore.replaceRoute(routeForIP);
                 }
             }
 
@@ -977,7 +977,7 @@
                 if (isMsgReply) {
                     Route routeForPrefix = new Route(Route.Source.DHCP, pdInfo.pdPrefix, nextHopIp);
                     log.debug("adding Route of PD for indirectly connected.");
-                    routeStore.updateRoute(routeForPrefix);
+                    routeStore.replaceRoute(routeForPrefix);
                     if (this.dhcpFpmEnabled) {
                         FpmRecord fpmRecord = new FpmRecord(pdInfo.pdPrefix, nextHopIp, FpmRecord.Type.DHCP_RELAY);
                         dhcpFpmPrefixStore.addFpmRecord(pdInfo.pdPrefix, fpmRecord);
diff --git a/apps/dhcprelay/src/test/java/org/onosproject/dhcprelay/DhcpRelayManagerTest.java b/apps/dhcprelay/src/test/java/org/onosproject/dhcprelay/DhcpRelayManagerTest.java
index 25f7b67..9d86606 100644
--- a/apps/dhcprelay/src/test/java/org/onosproject/dhcprelay/DhcpRelayManagerTest.java
+++ b/apps/dhcprelay/src/test/java/org/onosproject/dhcprelay/DhcpRelayManagerTest.java
@@ -930,6 +930,11 @@
         public void removeRoute(Route route) {
             routes.remove(route);
         }
+
+        public void replaceRoute(Route route) {
+            routes.remove(route);
+            routes.add(route);
+        }
     }
 
     private class MockInterfaceService extends InterfaceServiceAdapter {
diff --git a/apps/route-service/api/src/main/java/org/onosproject/routeservice/RouteStore.java b/apps/route-service/api/src/main/java/org/onosproject/routeservice/RouteStore.java
index 6866762..5eaa898 100644
--- a/apps/route-service/api/src/main/java/org/onosproject/routeservice/RouteStore.java
+++ b/apps/route-service/api/src/main/java/org/onosproject/routeservice/RouteStore.java
@@ -17,6 +17,7 @@
 package org.onosproject.routeservice;
 
 import com.google.common.annotations.Beta;
+import org.apache.commons.lang3.NotImplementedException;
 import org.onlab.packet.IpAddress;
 import org.onlab.packet.IpPrefix;
 import org.onosproject.store.Store;
@@ -44,6 +45,16 @@
     void removeRoute(Route route);
 
     /**
+     * Replaces the all the routes for a prefix
+     * with the given route.
+     *
+     * @param route route
+     */
+    default void replaceRoute(Route route) {
+        throw new NotImplementedException("replaceRoute is not implemented");
+    }
+
+    /**
      * Returns the IDs for all route tables in the store.
      *
      * @return route table IDs
diff --git a/apps/route-service/api/src/test/java/org/onosproject/routeservice/RouteStoreAdapter.java b/apps/route-service/api/src/test/java/org/onosproject/routeservice/RouteStoreAdapter.java
index bf9e527..117a98b 100644
--- a/apps/route-service/api/src/test/java/org/onosproject/routeservice/RouteStoreAdapter.java
+++ b/apps/route-service/api/src/test/java/org/onosproject/routeservice/RouteStoreAdapter.java
@@ -36,6 +36,11 @@
     }
 
     @Override
+    public void replaceRoute(Route route) {
+
+    }
+
+    @Override
     public Set<RouteTableId> getRouteTables() {
         return null;
     }
diff --git a/apps/route-service/app/src/main/java/org/onosproject/routeservice/store/DefaultRouteTable.java b/apps/route-service/app/src/main/java/org/onosproject/routeservice/store/DefaultRouteTable.java
index ad1ef854..476f3c0 100644
--- a/apps/route-service/app/src/main/java/org/onosproject/routeservice/store/DefaultRouteTable.java
+++ b/apps/route-service/app/src/main/java/org/onosproject/routeservice/store/DefaultRouteTable.java
@@ -24,6 +24,7 @@
 import java.util.stream.Collectors;
 
 import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Sets;
 import org.onlab.packet.IpAddress;
 import org.onlab.packet.IpPrefix;
 import org.onlab.util.KryoNamespace;
@@ -129,6 +130,11 @@
     }
 
     @Override
+    public void replace(Route route) {
+        routes.replaceValues(route.prefix(), Sets.newHashSet(route));
+    }
+
+    @Override
     public Collection<RouteSet> getRoutes() {
         return routes.stream()
             .map(Map.Entry::getValue)
diff --git a/apps/route-service/app/src/main/java/org/onosproject/routeservice/store/DistributedRouteStore.java b/apps/route-service/app/src/main/java/org/onosproject/routeservice/store/DistributedRouteStore.java
index feacb82..efdb792 100644
--- a/apps/route-service/app/src/main/java/org/onosproject/routeservice/store/DistributedRouteStore.java
+++ b/apps/route-service/app/src/main/java/org/onosproject/routeservice/store/DistributedRouteStore.java
@@ -121,6 +121,11 @@
     }
 
     @Override
+    public void replaceRoute(Route route) {
+        getDefaultRouteTable(route).replace(route);
+    }
+
+    @Override
     public Set<RouteTableId> getRouteTables() {
         return ImmutableSet.copyOf(masterRouteTable);
     }
diff --git a/apps/route-service/app/src/main/java/org/onosproject/routeservice/store/EmptyRouteTable.java b/apps/route-service/app/src/main/java/org/onosproject/routeservice/store/EmptyRouteTable.java
index 3786675..8bee10e 100644
--- a/apps/route-service/app/src/main/java/org/onosproject/routeservice/store/EmptyRouteTable.java
+++ b/apps/route-service/app/src/main/java/org/onosproject/routeservice/store/EmptyRouteTable.java
@@ -57,6 +57,11 @@
     }
 
     @Override
+    public void replace(Route route) {
+
+    }
+
+    @Override
     public RouteTableId id() {
         return id;
     }
diff --git a/apps/route-service/app/src/main/java/org/onosproject/routeservice/store/LocalRouteStore.java b/apps/route-service/app/src/main/java/org/onosproject/routeservice/store/LocalRouteStore.java
index 7884783..04b0f38 100644
--- a/apps/route-service/app/src/main/java/org/onosproject/routeservice/store/LocalRouteStore.java
+++ b/apps/route-service/app/src/main/java/org/onosproject/routeservice/store/LocalRouteStore.java
@@ -87,6 +87,11 @@
     }
 
     @Override
+    public void replaceRoute(Route route) {
+        getDefaultRouteTable(route).replace(route);
+    }
+
+    @Override
     public Set<RouteTableId> getRouteTables() {
         return routeTables.keySet();
     }
@@ -175,6 +180,13 @@
         }
 
         /**
+         * Replace the route in the route table.
+         */
+        public void replace(Route route) {
+            update(route);
+        }
+
+        /**
          * Returns the routes pointing to a particular next hop.
          *
          * @param ip next hop IP address
diff --git a/apps/route-service/app/src/main/java/org/onosproject/routeservice/store/RouteStoreImpl.java b/apps/route-service/app/src/main/java/org/onosproject/routeservice/store/RouteStoreImpl.java
index 5c18b54..7e3ea9f 100644
--- a/apps/route-service/app/src/main/java/org/onosproject/routeservice/store/RouteStoreImpl.java
+++ b/apps/route-service/app/src/main/java/org/onosproject/routeservice/store/RouteStoreImpl.java
@@ -142,6 +142,11 @@
     }
 
     @Override
+    public void replaceRoute(Route route) {
+        currentRouteStore.replaceRoute(route);
+    }
+
+    @Override
     public Set<RouteTableId> getRouteTables() {
         return currentRouteStore.getRouteTables();
     }
diff --git a/apps/route-service/app/src/main/java/org/onosproject/routeservice/store/RouteTable.java b/apps/route-service/app/src/main/java/org/onosproject/routeservice/store/RouteTable.java
index fbe32c0..130654b 100644
--- a/apps/route-service/app/src/main/java/org/onosproject/routeservice/store/RouteTable.java
+++ b/apps/route-service/app/src/main/java/org/onosproject/routeservice/store/RouteTable.java
@@ -44,6 +44,13 @@
     void remove(Route route);
 
     /**
+     * Replaces a route in the route table.
+     *
+     * @param route route
+     */
+    void replace(Route route);
+
+    /**
      * Returns the route table ID.
      *
      * @return route table ID