diff --git a/incubator/api/src/main/java/org/onosproject/incubator/net/routing/RouteEvent.java b/incubator/api/src/main/java/org/onosproject/incubator/net/routing/RouteEvent.java
index fc5199d..ef56145 100644
--- a/incubator/api/src/main/java/org/onosproject/incubator/net/routing/RouteEvent.java
+++ b/incubator/api/src/main/java/org/onosproject/incubator/net/routing/RouteEvent.java
@@ -36,7 +36,7 @@
     public enum Type {
 
         /**
-         * Route is new.
+         * Route is new and the next hop is resolved.
          * <p>
          * The subject of this event should be the route being added.
          * The prevSubject of this event should be null.
@@ -52,7 +52,7 @@
         ROUTE_UPDATED,
 
         /**
-         * Route was removed.
+         * Route was removed or the next hop becomes unresolved.
          * <p>
          * The subject of this event should be the route being removed.
          * The prevSubject of this event should be null.
diff --git a/incubator/net/src/main/java/org/onosproject/incubator/net/routing/impl/RouteManager.java b/incubator/net/src/main/java/org/onosproject/incubator/net/routing/impl/RouteManager.java
index acca731..c266de0 100644
--- a/incubator/net/src/main/java/org/onosproject/incubator/net/routing/impl/RouteManager.java
+++ b/incubator/net/src/main/java/org/onosproject/incubator/net/routing/impl/RouteManager.java
@@ -196,7 +196,7 @@
     public void withdraw(Collection<Route> routes) {
         synchronized (this) {
             routes.forEach(route -> {
-                log.debug("Received withdraw {}", routes);
+                log.debug("Received withdraw {}", route);
                 routeStore.removeRoute(route);
             });
         }
diff --git a/incubator/store/src/main/java/org/onosproject/incubator/store/routing/impl/LocalRouteStore.java b/incubator/store/src/main/java/org/onosproject/incubator/store/routing/impl/LocalRouteStore.java
index 70bca92..78d1610 100644
--- a/incubator/store/src/main/java/org/onosproject/incubator/store/routing/impl/LocalRouteStore.java
+++ b/incubator/store/src/main/java/org/onosproject/incubator/store/routing/impl/LocalRouteStore.java
@@ -49,6 +49,8 @@
 import java.util.Set;
 import java.util.concurrent.ConcurrentHashMap;
 
+import static com.google.common.base.Preconditions.checkNotNull;
+
 /**
  * Route store based on in-memory storage.
  */
@@ -115,6 +117,8 @@
 
     @Override
     public void updateNextHop(IpAddress ip, NextHopData nextHopData) {
+        checkNotNull(ip);
+        checkNotNull(nextHopData);
         Collection<Route> routes = getDefaultRouteTable(ip).getRoutesForNextHop(ip);
 
         if (!routes.isEmpty() && !nextHopData.equals(nextHops.get(ip))) {
@@ -135,6 +139,8 @@
 
     @Override
     public void removeNextHop(IpAddress ip, NextHopData nextHopData) {
+        checkNotNull(ip);
+        checkNotNull(nextHopData);
         if (nextHops.remove(ip, nextHopData)) {
             Collection<Route> routes = getDefaultRouteTable(ip).getRoutesForNextHop(ip);
             for (Route route : routes) {
@@ -203,10 +209,24 @@
          * @param route route to update
          */
         public void update(Route route) {
-            NextHopData oldNextHopData = null;
-
             synchronized (this) {
                 Route oldRoute = routes.put(route.prefix(), route);
+
+                // No need to proceed if the new route is the same
+                if (route.equals(oldRoute)) {
+                    return;
+                }
+
+                NextHopData oldNextHopData = null;
+                ResolvedRoute oldResolvedRoute = null;
+                if (oldRoute != null) {
+                    oldNextHopData = nextHops.get(oldRoute.nextHop());
+                    if (oldNextHopData != null) {
+                        oldResolvedRoute = new ResolvedRoute(oldRoute,
+                                oldNextHopData.mac(), oldNextHopData.location());
+                    }
+                }
+
                 routeTable.put(createBinaryString(route.prefix()), route);
 
                 // TODO manage routes from multiple providers
@@ -217,29 +237,20 @@
                     reverseIndex.remove(oldRoute.nextHop(), oldRoute);
 
                     if (reverseIndex.get(oldRoute.nextHop()).isEmpty()) {
-                        oldNextHopData = nextHops.remove(oldRoute.nextHop());
+                        nextHops.remove(oldRoute.nextHop());
                     }
                 }
 
-                if (route.equals(oldRoute)) {
-                    // No need to send events if the new route is the same
-                    return;
-                }
-
                 NextHopData nextHopData = nextHops.get(route.nextHop());
 
                 if (oldRoute != null && !oldRoute.nextHop().equals(route.nextHop())) {
-                    ResolvedRoute oldResolvedRoute =
-                            new ResolvedRoute(oldRoute,
-                                    (oldNextHopData == null) ? null : oldNextHopData.mac(),
-                                    (oldNextHopData == null) ? null : oldNextHopData.location());
-
-                    if (nextHopData == null) {
-                        // We don't know the new MAC address yet so delete the route
+                    // We don't know the new MAC address yet so delete the route
+                    // Don't send ROUTE_REMOVED if the route was unresolved
+                    if (nextHopData == null && oldNextHopData != null) {
                         notifyDelegate(new RouteEvent(RouteEvent.Type.ROUTE_REMOVED,
                                 oldResolvedRoute));
-                    } else {
-                        // We know the new MAC address so update the route
+                    // We know the new MAC address so update the route
+                    } else if (nextHopData != null && oldNextHopData != null) {
                         notifyDelegate(new RouteEvent(RouteEvent.Type.ROUTE_UPDATED,
                                 new ResolvedRoute(route, nextHopData.mac(), nextHopData.location()),
                                 oldResolvedRoute));
@@ -247,7 +258,6 @@
                     return;
                 }
 
-
                 if (nextHopData != null) {
                     notifyDelegate(new RouteEvent(RouteEvent.Type.ROUTE_ADDED,
                             new ResolvedRoute(route, nextHopData.mac(), nextHopData.location())));
@@ -268,9 +278,12 @@
                 if (removed != null) {
                     reverseIndex.remove(removed.nextHop(), removed);
                     NextHopData oldNextHopData = getNextHop(removed.nextHop());
-                    notifyDelegate(new RouteEvent(RouteEvent.Type.ROUTE_REMOVED,
-                            new ResolvedRoute(route, oldNextHopData.mac(),
-                                    oldNextHopData.location())));
+                    // Don't send ROUTE_REMOVED if the route was unresolved
+                    if (oldNextHopData != null) {
+                        notifyDelegate(new RouteEvent(RouteEvent.Type.ROUTE_REMOVED,
+                                new ResolvedRoute(route, oldNextHopData.mac(),
+                                        oldNextHopData.location())));
+                    }
                 }
             }
         }