diff --git a/app/src/main/java/org/onosproject/segmentrouting/DefaultRoutingHandler.java b/app/src/main/java/org/onosproject/segmentrouting/DefaultRoutingHandler.java
index 1ce8874..8a2e353 100644
--- a/app/src/main/java/org/onosproject/segmentrouting/DefaultRoutingHandler.java
+++ b/app/src/main/java/org/onosproject/segmentrouting/DefaultRoutingHandler.java
@@ -42,6 +42,7 @@
 import org.onosproject.segmentrouting.config.DeviceConfiguration;
 import org.onosproject.segmentrouting.grouphandler.DefaultGroupHandler;
 import org.onosproject.store.serializers.KryoNamespaces;
+import org.onosproject.store.service.ConsistentMultimap;
 import org.onosproject.store.service.Serializer;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
@@ -54,6 +55,7 @@
 import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
+import java.util.Map.Entry;
 import java.util.Objects;
 import java.util.Optional;
 import java.util.Set;
@@ -110,6 +112,10 @@
     Map<Set<DeviceId>, NodeId> shouldProgram;
     Map<DeviceId, Boolean> shouldProgramCache;
 
+    // Distributed routes store to keep track of the routes already seen
+    // destination device is the key and target sw is the value
+    ConsistentMultimap<DeviceId, DeviceId> seenBeforeRoutes;
+
     // Local store to keep track of all devices that this instance was responsible
     // for programming in the last run. Helps to determine if mastership changed
     // during a run - only relevant for programming as a result of topo change.
@@ -140,6 +146,11 @@
                 .withSerializer(Serializer.using(KryoNamespaces.API))
                 .withRelaxedReadConsistency()
                 .build().asJavaMap();
+        this.seenBeforeRoutes = srManager.storageService.<DeviceId, DeviceId>consistentMultimapBuilder()
+                .withName("programmed-routes")
+                .withSerializer(Serializer.using(KryoNamespaces.API))
+                .withRelaxedReadConsistency()
+                .build();
         this.shouldProgramCache = Maps.newConcurrentMap();
         update(srManager);
         this.routePopulators = new PredictableExecutor(DEFAULT_THREADS,
@@ -278,6 +289,7 @@
                 }
             }
 
+            log.debug("seenBeforeRoutes size {}", seenBeforeRoutes.size());
             if (!redoRouting(routeChanges, edgePairs, null)) {
                 log.debug("populateAllRoutingRules: populationStatus is ABORTED");
                 populationStatus = Status.ABORTED;
@@ -339,6 +351,7 @@
                     log.trace("  Current/Existing SPG: {}", entry.getValue());
                 }
             });
+            log.debug("seenBeforeRoutes size {}", seenBeforeRoutes.size());
             Set<EdgePair> edgePairs = new HashSet<>();
             Set<ArrayList<DeviceId>> routeChanges = new HashSet<>();
             boolean handleRouting = false;
@@ -491,6 +504,7 @@
             Set<ArrayList<DeviceId>> routeChanges;
             log.debug("populateRoutingRulesForLinkStatusChange: "
                     + "populationStatus is STARTED");
+            log.debug("seenBeforeRoutes size {}", seenBeforeRoutes.size());
             populationStatus = Status.STARTED;
             rulePopulator.resetCounter(); //XXX maybe useful to have a rehash ctr
             boolean hashGroupsChanged = false;
@@ -619,17 +633,29 @@
             return false;
         }
 
+        // Temporary stores the changed routes
+        Set<ArrayList<DeviceId>> tempRoutes = ImmutableSet.copyOf(changedRoutes);
         // now process changedRoutes according to edgePairs
         if (!redoRoutingEdgePairs(edgePairs, subnets, changedRoutes)) {
             return false; //abort routing and fail fast
         }
+        // Calculate the programmed routes pointing to the pairs
+        Set<ArrayList<DeviceId>> programmedPairRoutes = Sets.difference(tempRoutes, changedRoutes);
+        log.debug("Evaluating programmed pair routes");
+        storeSeenBeforeRoutes(programmedPairRoutes);
 
+        // Temporary stores the left routes
+        tempRoutes = ImmutableSet.copyOf(changedRoutes);
         // whatever is left in changedRoutes is now processed for individual dsts.
         Set<DeviceId> updatedDevices = Sets.newHashSet();
         if (!redoRoutingIndividualDests(subnets, changedRoutes,
                                         updatedDevices)) {
             return false; //abort routing and fail fast
         }
+        // Calculate the individual programmed routes
+        Set<ArrayList<DeviceId>> programmedIndividualRoutes = Sets.difference(tempRoutes, changedRoutes);
+        log.debug("Evaluating individual programmed routes");
+        storeSeenBeforeRoutes(programmedIndividualRoutes);
 
         // update ecmpSPG for all edge-pairs
         for (EdgePair ep : edgePairs) {
@@ -650,6 +676,31 @@
     }
 
     /**
+     * Stores the routes seen before. Routes are two-elements arrays.
+     * @param seenRoutes seen before routes
+     */
+    private void storeSeenBeforeRoutes(Set<ArrayList<DeviceId>> seenRoutes) {
+        Set<DeviceId> nextHops;
+        for (ArrayList<DeviceId> route : seenRoutes) {
+            log.debug("Route {} -> {} has been programmed", route.get(0), route.get(1));
+            nextHops = getNextHops(route.get(0), route.get(1));
+            // No valid next hops - cannot be considered a programmed route
+            if (nextHops.isEmpty()) {
+                log.debug("Could not find next hop from target:{} --> dst {} "
+                                  + "skipping this route", route.get(0), route.get(1));
+                continue;
+            }
+            // Already present - do not add again
+            if (seenBeforeRoutes.containsEntry(route.get(1), route.get(0))) {
+                log.debug("Route from target:{} --> dst {} " +
+                                  "already present, skipping this route", route.get(0), route.get(1));
+                continue;
+            }
+            seenBeforeRoutes.put(route.get(1), route.get(0));
+        }
+    }
+
+    /**
      * Programs targetSw in the changedRoutes for given prefixes reachable by
      * an edgePair. If no prefixes are given, the method will use configured
      * subnets/prefixes. If some configured subnets belong only to a specific
@@ -702,7 +753,7 @@
             // so now for this edgepair we have a per target set of routechanges
             // process target->edgePair route
             List<Future<Boolean>> futures = Lists.newArrayList();
-            for (Map.Entry<DeviceId, Set<ArrayList<DeviceId>>> entry :
+            for (Entry<DeviceId, Set<ArrayList<DeviceId>>> entry :
                             targetRoutes.entrySet()) {
                 log.debug("* redoRoutingDstPair Target:{} -> edge-pair {}",
                           entry.getKey(), ep);
@@ -869,6 +920,7 @@
                 log.debug("* redoRoutingIndiDst Target: {} -> dst: {}",
                           route.get(0), route.get(1));
                 futures.add(routePopulators.submit(new RedoRoutingIndividualDest(subnets, route)));
+                changedRoutes.remove(route);
             }
             // check the execution of each job
             if (!checkJobs(futures)) {
@@ -1092,6 +1144,7 @@
                 updatedDevices.add(targetSw);
                 updatedDevices.add(dstSw);
                 continue;
+
             }
             //linkfailed - update both sides
             if (success) {
@@ -1182,6 +1235,11 @@
             return false;
         }
         DeviceId destSw = route.get(1);
+        if (!seenBeforeRoutes.containsEntry(destSw, targetSw)) {
+            log.warn("Cannot fixHashGroupsForRoute {} -> {} has not been programmed before",
+                     targetSw, destSw);
+            return false;
+        }
         log.debug("* processing fixHashGroupsForRoute: Target {} -> Dest {}",
                   targetSw, destSw);
         // figure out the new next hops at the targetSw towards the destSw
@@ -1393,6 +1451,17 @@
         srManager.routingRulePopulator.processDoubleTaggedFilter(deviceId, outPort, outerVlan, innerVlan, false);
     }
 
+    /**
+     * Purges seen before routes for a given device.
+     * @param deviceId the device id
+     */
+    void purgeSeenBeforeRoutes(DeviceId deviceId) {
+        log.debug("Purging seen before routes having as target {}", deviceId);
+        Set<Entry<DeviceId, DeviceId>> routesToPurge = seenBeforeRoutes.stream()
+                .filter(entry -> entry.getValue().equals(deviceId))
+                .collect(Collectors.toSet());
+        routesToPurge.forEach(entry -> seenBeforeRoutes.remove(entry.getKey(), entry.getValue()));
+    }
 
     /**
      * Remove ECMP graph entry for the given device. Typically called when
@@ -1507,6 +1576,7 @@
                     for (Device dev : srManager.deviceService.getDevices()) {
                         if (shouldProgram(dev.id())) {
                             srManager.purgeHashedNextObjectiveStore(dev.id());
+                            seenBeforeRoutes.removeAll(dev.id());
                         }
                     }
                     // give small delay to ensure entire store is purged
diff --git a/app/src/main/java/org/onosproject/segmentrouting/SegmentRoutingManager.java b/app/src/main/java/org/onosproject/segmentrouting/SegmentRoutingManager.java
index 97436ab..745d2f8 100644
--- a/app/src/main/java/org/onosproject/segmentrouting/SegmentRoutingManager.java
+++ b/app/src/main/java/org/onosproject/segmentrouting/SegmentRoutingManager.java
@@ -1592,6 +1592,7 @@
 
         if (mastershipService.isLocalMaster(deviceId)) {
             defaultRoutingHandler.populatePortAddressingRules(deviceId);
+            defaultRoutingHandler.purgeSeenBeforeRoutes(deviceId);
             DefaultGroupHandler groupHandler = groupHandlerMap.get(deviceId);
             groupHandler.createGroupsFromVlanConfig();
             routingRulePopulator.populateSubnetBroadcastRule(deviceId);
diff --git a/app/src/test/java/org/onosproject/segmentrouting/DefaultRoutingHandlerTest.java b/app/src/test/java/org/onosproject/segmentrouting/DefaultRoutingHandlerTest.java
index 28847c6..a6278b2 100644
--- a/app/src/test/java/org/onosproject/segmentrouting/DefaultRoutingHandlerTest.java
+++ b/app/src/test/java/org/onosproject/segmentrouting/DefaultRoutingHandlerTest.java
@@ -28,6 +28,7 @@
 import org.onosproject.segmentrouting.config.DeviceConfiguration;
 import org.onosproject.store.service.StorageService;
 import org.onosproject.store.service.TestConsistentMap;
+import org.onosproject.store.service.TestConsistentMultimap;
 
 import java.util.Optional;
 
@@ -57,6 +58,8 @@
         srManager = createMock(SegmentRoutingManager.class);
         srManager.storageService = createMock(StorageService.class);
         expect(srManager.storageService.consistentMapBuilder()).andReturn(new TestConsistentMap.Builder<>()).anyTimes();
+        expect(srManager.storageService.consistentMultimapBuilder()).andReturn(
+                new TestConsistentMultimap.Builder<>()).anyTimes();
         replay(srManager.storageService);
         srManager.routingRulePopulator = createMock(RoutingRulePopulator.class);
         srManager.deviceService = createMock(DeviceService.class);
diff --git a/app/src/test/java/org/onosproject/segmentrouting/HostHandlerTest.java b/app/src/test/java/org/onosproject/segmentrouting/HostHandlerTest.java
index 0fa9217..dedd66f 100644
--- a/app/src/test/java/org/onosproject/segmentrouting/HostHandlerTest.java
+++ b/app/src/test/java/org/onosproject/segmentrouting/HostHandlerTest.java
@@ -55,6 +55,7 @@
 import org.onosproject.segmentrouting.config.SegmentRoutingDeviceConfig;
 import org.onosproject.store.service.StorageService;
 import org.onosproject.store.service.TestConsistentMap;
+import org.onosproject.store.service.TestConsistentMultimap;
 
 import java.util.Map;
 import java.util.Set;
@@ -233,6 +234,8 @@
         SegmentRoutingManager srManager = new MockSegmentRoutingManager(NEXT_TABLE);
         srManager.storageService = createMock(StorageService.class);
         expect(srManager.storageService.consistentMapBuilder()).andReturn(new TestConsistentMap.Builder<>()).anyTimes();
+        expect(srManager.storageService.consistentMultimapBuilder()).andReturn(
+                new TestConsistentMultimap.Builder<>()).anyTimes();
         replay(srManager.storageService);
         srManager.cfgService = new NetworkConfigRegistryAdapter();
         srManager.deviceConfiguration = new DeviceConfiguration(srManager);
diff --git a/app/src/test/java/org/onosproject/segmentrouting/RouteHandlerTest.java b/app/src/test/java/org/onosproject/segmentrouting/RouteHandlerTest.java
index 2d365a2..6332856 100644
--- a/app/src/test/java/org/onosproject/segmentrouting/RouteHandlerTest.java
+++ b/app/src/test/java/org/onosproject/segmentrouting/RouteHandlerTest.java
@@ -48,6 +48,7 @@
 import org.onosproject.segmentrouting.config.SegmentRoutingDeviceConfig;
 import org.onosproject.store.service.StorageService;
 import org.onosproject.store.service.TestConsistentMap;
+import org.onosproject.store.service.TestConsistentMultimap;
 
 import java.util.Map;
 import java.util.Set;
@@ -158,6 +159,8 @@
         srManager = new MockSegmentRoutingManager(NEXT_TABLE);
         srManager.storageService = createMock(StorageService.class);
         expect(srManager.storageService.consistentMapBuilder()).andReturn(new TestConsistentMap.Builder<>()).anyTimes();
+        expect(srManager.storageService.consistentMultimapBuilder()).andReturn(
+                new TestConsistentMultimap.Builder<>()).anyTimes();
         replay(srManager.storageService);
         srManager.cfgService = new NetworkConfigRegistryAdapter();
         srManager.deviceConfiguration = createMock(DeviceConfiguration.class);