Refactor route subsystem to support multiple routes for each prefix.

This resulted in a substantial refatoring of the route subsystem, including
some minor external API changes. The interface between the manager and the
store has been changed to deal with multiple routes per prefix. The distributed
route store has been updated to be able to distribute route table information.
The route subsystem no longer stores next hop information in the route store.
This information is already available from the host store so the routes system
simply fetches it from there.

Change-Id: I7657b3efb6dcb76afa6f17c931f154a970a16528
diff --git a/cli/src/main/java/org/onosproject/cli/net/RoutesListCommand.java b/cli/src/main/java/org/onosproject/cli/net/RoutesListCommand.java
index 780a9ab..5ea316e 100644
--- a/cli/src/main/java/org/onosproject/cli/net/RoutesListCommand.java
+++ b/cli/src/main/java/org/onosproject/cli/net/RoutesListCommand.java
@@ -1,5 +1,5 @@
 /*
- * Copyright 2016-present Open Networking Laboratory
+ * Copyright 2017-present Open Networking Laboratory
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -20,32 +20,29 @@
 import com.fasterxml.jackson.databind.node.ArrayNode;
 import com.fasterxml.jackson.databind.node.ObjectNode;
 import org.apache.karaf.shell.commands.Command;
-import org.apache.karaf.shell.commands.Option;
 import org.onosproject.cli.AbstractShellCommand;
+import org.onosproject.incubator.net.routing.ResolvedRoute;
 import org.onosproject.incubator.net.routing.Route;
+import org.onosproject.incubator.net.routing.RouteInfo;
 import org.onosproject.incubator.net.routing.RouteService;
 import org.onosproject.incubator.net.routing.RouteTableId;
 
 import java.util.Collection;
-import java.util.Map;
+import java.util.Comparator;
+import java.util.Objects;
+import java.util.Optional;
 
 /**
  * Command to show the routes in the routing tables.
  */
 @Command(scope = "onos", name = "routes",
-        description = "Lists all routes in the route store")
+        description = "Lists routes in the route store")
 public class RoutesListCommand extends AbstractShellCommand {
 
-    @Option(name = "-s", aliases = "--summary",
-            description = "Show summary of routes")
-    private boolean summary = false;
-
-    private static final String FORMAT_SUMMARY =
-            "Number of routes in table %s: %s";
     private static final String FORMAT_HEADER =
-        "   Network            Next Hop        Source";
+        "    Network            Next Hop        Source";
     private static final String FORMAT_ROUTE =
-        "   %-18s %-15s %-10s";
+            "%-1s   %-18s %-15s %-10s";
 
     private static final String FORMAT_TABLE = "Table: %s";
     private static final String FORMAT_TOTAL = "   Total: %d";
@@ -54,38 +51,38 @@
     protected void execute() {
         RouteService service = AbstractShellCommand.get(RouteService.class);
 
-        Map<RouteTableId, Collection<Route>> allRoutes = service.getAllRoutes();
-
-        if (summary) {
-            if (outputJson()) {
-                ObjectMapper mapper = new ObjectMapper();
-                ObjectNode result = mapper.createObjectNode();
-                result.put("totalRoutes4", allRoutes.get(new RouteTableId("ipv4")).size());
-                result.put("totalRoutes6", allRoutes.get(new RouteTableId("ipv6")).size());
-                print("%s", result);
-            } else {
-                allRoutes.forEach((id, routes) -> print(FORMAT_SUMMARY, id, routes.size()));
-            }
-
-            return;
-        }
-
         if (outputJson()) {
             ObjectMapper mapper = new ObjectMapper();
             ObjectNode result = mapper.createObjectNode();
-            result.set("routes4", json(allRoutes.get(new RouteTableId("ipv4"))));
-            result.set("routes6", json(allRoutes.get(new RouteTableId("ipv6"))));
+            result.set("routes4", json(service.getRoutes(new RouteTableId("ipv4"))));
+            result.set("routes6", json(service.getRoutes(new RouteTableId("ipv6"))));
             print("%s", result);
         } else {
-            allRoutes.forEach((id, routes) -> {
+            service.getRouteTables().forEach(id -> {
                 print(FORMAT_TABLE, id);
                 print(FORMAT_HEADER);
-                routes.forEach(r -> print(FORMAT_ROUTE, r.prefix(), r.nextHop(), r.source()));
-                print(FORMAT_TOTAL, routes.size());
+                Collection<RouteInfo> tableRoutes = service.getRoutes(id);
+
+                tableRoutes.stream()
+                        .sorted(Comparator.comparing(r -> r.prefix().address()))
+                        .forEach(this::print);
+
+                print(FORMAT_TOTAL, tableRoutes.size());
                 print("");
             });
         }
+    }
 
+    private void print(RouteInfo routeInfo) {
+        routeInfo.allRoutes()
+                .forEach(r -> print(FORMAT_ROUTE, isBestRoute(routeInfo.bestRoute(), r) ? ">" : "",
+                        r.prefix(), r.nextHop(), Route.Source.UNDEFINED));
+    }
+
+
+
+    private boolean isBestRoute(Optional<ResolvedRoute> bestRoute, ResolvedRoute route) {
+        return Objects.equals(bestRoute.orElse(null), route);
     }
 
     /**
@@ -94,13 +91,14 @@
      * @param routes the routes with the data
      * @return JSON array with the routes
      */
-    private JsonNode json(Collection<Route> routes) {
+    private JsonNode json(Collection<RouteInfo> routes) {
         ObjectMapper mapper = new ObjectMapper();
         ArrayNode result = mapper.createArrayNode();
 
-        for (Route route : routes) {
-            result.add(json(mapper, route));
-        }
+        routes.stream()
+                .flatMap(ri -> ri.allRoutes().stream())
+                .forEach(r -> result.add(json(mapper, r)));
+
         return result;
     }
 
@@ -111,7 +109,7 @@
      * @param route the route with the data
      * @return JSON object for the route
      */
-    private ObjectNode json(ObjectMapper mapper, Route route) {
+    private ObjectNode json(ObjectMapper mapper, ResolvedRoute route) {
         ObjectNode result = mapper.createObjectNode();
 
         result.put("prefix", route.prefix().toString());
diff --git a/incubator/api/src/main/java/org/onosproject/incubator/net/routing/InternalRouteEvent.java b/incubator/api/src/main/java/org/onosproject/incubator/net/routing/InternalRouteEvent.java
new file mode 100644
index 0000000..0a70bb0
--- /dev/null
+++ b/incubator/api/src/main/java/org/onosproject/incubator/net/routing/InternalRouteEvent.java
@@ -0,0 +1,55 @@
+/*
+ * Copyright 2017-present Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.onosproject.incubator.net.routing;
+
+import org.onosproject.event.AbstractEvent;
+
+/**
+ * Route event for signalling between the store and the manager.
+ */
+public class InternalRouteEvent extends
+        AbstractEvent<InternalRouteEvent.Type, RouteSet> {
+
+    /**
+     * Internal route event type.
+     */
+    public enum Type {
+        /**
+         * Indicates a route was added to the store.
+         */
+        ROUTE_ADDED,
+
+        /**
+         * Indicates a route was removed from the store.
+         */
+        ROUTE_REMOVED
+    }
+
+    /**
+     * Creates a new internal route event.
+     *
+     * @param type route event type
+     * @param subject route set
+     */
+    public InternalRouteEvent(Type type, RouteSet subject) {
+        super(type, subject);
+    }
+
+    protected InternalRouteEvent(Type type, RouteSet subject, long time) {
+        super(type, subject, time);
+    }
+}
diff --git a/incubator/api/src/main/java/org/onosproject/incubator/net/routing/RouteInfo.java b/incubator/api/src/main/java/org/onosproject/incubator/net/routing/RouteInfo.java
new file mode 100644
index 0000000..c970681
--- /dev/null
+++ b/incubator/api/src/main/java/org/onosproject/incubator/net/routing/RouteInfo.java
@@ -0,0 +1,100 @@
+/*
+ * Copyright 2017-present Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.onosproject.incubator.net.routing;
+
+import com.google.common.annotations.Beta;
+import org.onlab.packet.IpPrefix;
+
+import java.util.Objects;
+import java.util.Optional;
+import java.util.Set;
+
+import static com.google.common.base.Preconditions.checkNotNull;
+
+/**
+ * Routing information for a given prefix.
+ */
+@Beta
+public class RouteInfo {
+
+    private final IpPrefix prefix;
+    private final ResolvedRoute bestRoute;
+    private final Set<ResolvedRoute> allRoutes;
+
+    /**
+     * Creates a new route info object.
+     *
+     * @param prefix IP prefix
+     * @param bestRoute best route for this prefix if one exists
+     * @param allRoutes all known routes for this prefix
+     */
+    @Beta
+    public RouteInfo(IpPrefix prefix, ResolvedRoute bestRoute, Set<ResolvedRoute> allRoutes) {
+        this.prefix = checkNotNull(prefix);
+        this.bestRoute = bestRoute;
+        this.allRoutes = checkNotNull(allRoutes);
+    }
+
+    /**
+     * Returns the IP prefix.
+     *
+     * @return IP prefix
+     */
+    public IpPrefix prefix() {
+        return prefix;
+    }
+
+    /**
+     * Returns the best route for this prefix if one exists.
+     *
+     * @return optional best route
+     */
+    public Optional<ResolvedRoute> bestRoute() {
+        return Optional.ofNullable(bestRoute);
+    }
+
+    /**
+     * Returns all routes for this prefix.
+     *
+     * @return all routes
+     */
+    public Set<ResolvedRoute> allRoutes() {
+        return allRoutes;
+    }
+
+    @Override
+    public int hashCode() {
+        return Objects.hash(prefix, bestRoute, allRoutes);
+    }
+
+    @Override
+    public boolean equals(Object other) {
+        if (this == other) {
+            return true;
+        }
+
+        if (!(other instanceof RouteInfo)) {
+            return false;
+        }
+
+        RouteInfo that = (RouteInfo) other;
+
+        return Objects.equals(this.prefix, that.prefix) &&
+                Objects.equals(this.bestRoute, that.bestRoute) &&
+                Objects.equals(this.allRoutes, that.allRoutes);
+    }
+}
diff --git a/incubator/api/src/main/java/org/onosproject/incubator/net/routing/RouteService.java b/incubator/api/src/main/java/org/onosproject/incubator/net/routing/RouteService.java
index 4fd99d4..4a298ba 100644
--- a/incubator/api/src/main/java/org/onosproject/incubator/net/routing/RouteService.java
+++ b/incubator/api/src/main/java/org/onosproject/incubator/net/routing/RouteService.java
@@ -21,6 +21,7 @@
 
 import java.util.Collection;
 import java.util.Map;
+import java.util.Optional;
 import java.util.Set;
 
 /**
@@ -32,25 +33,55 @@
      * Returns all routes for all route tables in the system.
      *
      * @return map of route table name to routes in that table
+     * @deprecated in Kingfisher release. Use {@link #getRoutes(RouteTableId)}
+     * instead.
      */
+    @Deprecated
     Map<RouteTableId, Collection<Route>> getAllRoutes();
 
     /**
+     * Returns information about all routes in the given route table.
+     *
+     * @param id route table ID
+     * @return collection of route information
+     */
+    Collection<RouteInfo> getRoutes(RouteTableId id);
+
+    /**
+     * Returns the set of route tables in the system.
+     *
+     * @return collection of route table IDs.
+     */
+    Collection<RouteTableId> getRouteTables();
+
+    /**
      * Performs a longest prefix match on the given IP address. The call will
      * return the route with the most specific prefix that contains the given
      * IP address.
      *
      * @param ip IP address
      * @return longest prefix matched route
+     * @deprecated in Kingfisher release. Use {{@link #longestPrefixLookup(IpAddress)}}
+     * instead.
      */
+    @Deprecated
     Route longestPrefixMatch(IpAddress ip);
 
     /**
+     * Performs a longest prefix lookup on the given IP address.
+     *
+     * @param ip IP address to look up
+     * @return most specific matching route, if one exists
+     */
+    Optional<ResolvedRoute> longestPrefixLookup(IpAddress ip);
+
+    /**
      * Returns the routes for the given next hop.
      *
      * @param nextHop next hop IP address
      * @return routes for this next hop
      */
+    @Deprecated
     Collection<Route> getRoutesForNextHop(IpAddress nextHop);
 
     /**
@@ -58,6 +89,7 @@
      *
      * @return set of next hops
      */
+    @Deprecated
     Set<NextHop> getNextHops();
 
 }
diff --git a/incubator/api/src/main/java/org/onosproject/incubator/net/routing/RouteSet.java b/incubator/api/src/main/java/org/onosproject/incubator/net/routing/RouteSet.java
new file mode 100644
index 0000000..89c3ce3
--- /dev/null
+++ b/incubator/api/src/main/java/org/onosproject/incubator/net/routing/RouteSet.java
@@ -0,0 +1,97 @@
+/*
+ * Copyright 2017-present Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.onosproject.incubator.net.routing;
+
+import com.google.common.collect.ImmutableSet;
+import org.onlab.packet.IpPrefix;
+
+import java.util.Objects;
+import java.util.Set;
+
+import static com.google.common.base.Preconditions.checkNotNull;
+
+/**
+ * A set of routes for a particular prefix in a route table.
+ */
+public class RouteSet {
+    private final RouteTableId tableId;
+
+    private final IpPrefix prefix;
+    private final Set<Route> routes;
+
+    /**
+     * Creates a new route set.
+     *
+     * @param tableId route table ID
+     * @param prefix IP prefix
+     * @param routes routes for the given prefix
+     */
+    public RouteSet(RouteTableId tableId, IpPrefix prefix, Set<Route> routes) {
+        this.tableId = checkNotNull(tableId);
+        this.prefix = checkNotNull(prefix);
+        this.routes = ImmutableSet.copyOf(checkNotNull(routes));
+    }
+
+    /**
+     * Returns the route table ID.
+     *
+     * @return route table ID
+     */
+    public RouteTableId tableId() {
+        return tableId;
+    }
+
+    /**
+     * Returns the IP prefix.
+     *
+     * @return IP prefix
+     */
+    public IpPrefix prefix() {
+        return prefix;
+    }
+
+    /**
+     * Returns the set of routes.
+     *
+     * @return routes
+     */
+    public Set<Route> routes() {
+        return routes;
+    }
+
+    @Override
+    public int hashCode() {
+        return Objects.hash(tableId, prefix, routes);
+    }
+
+    @Override
+    public boolean equals(Object other) {
+        if (this == other) {
+            return true;
+        }
+
+        if (!(other instanceof RouteSet)) {
+            return false;
+        }
+
+        RouteSet that = (RouteSet) other;
+
+        return Objects.equals(this.tableId, that.tableId) &&
+                Objects.equals(this.prefix, that.prefix) &&
+                Objects.equals(this.routes, that.routes);
+    }
+}
diff --git a/incubator/api/src/main/java/org/onosproject/incubator/net/routing/RouteStore.java b/incubator/api/src/main/java/org/onosproject/incubator/net/routing/RouteStore.java
index 22a6285..27ec1c3 100644
--- a/incubator/api/src/main/java/org/onosproject/incubator/net/routing/RouteStore.java
+++ b/incubator/api/src/main/java/org/onosproject/incubator/net/routing/RouteStore.java
@@ -1,5 +1,5 @@
 /*
- * Copyright 2016-present Open Networking Laboratory
+ * Copyright 2017-present Open Networking Laboratory
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -16,7 +16,9 @@
 
 package org.onosproject.incubator.net.routing;
 
+import com.google.common.annotations.Beta;
 import org.onlab.packet.IpAddress;
+import org.onlab.packet.IpPrefix;
 import org.onosproject.store.Store;
 
 import java.util.Collection;
@@ -26,7 +28,7 @@
 /**
  * Unicast route store.
  */
-public interface RouteStore extends Store<RouteEvent, RouteStoreDelegate> {
+public interface RouteStore extends Store<InternalRouteEvent, RouteStoreDelegate> {
 
     /**
      * Adds or updates the given route in the store.
@@ -50,20 +52,12 @@
     Set<RouteTableId> getRouteTables();
 
     /**
-     * Returns the routes for a particular route table.
+     * Returns the routes in the given route table, grouped by prefix.
      *
-     * @param table route table
-     * @return collection of route in the table
+     * @param table route table ID
+     * @return routes
      */
-    Collection<Route> getRoutes(RouteTableId table);
-
-    /**
-     * Performs a longest prefix match with the given IP address.
-     *
-     * @param ip IP to look up
-     * @return longest prefix match route
-     */
-    Route longestPrefixMatch(IpAddress ip);
+    Collection<RouteSet> getRoutes(RouteTableId table);
 
     /**
      * Returns the routes that point to the given next hop IP address.
@@ -71,14 +65,26 @@
      * @param ip IP address of the next hop
      * @return routes for the given next hop
      */
+    // TODO think about including route table info
     Collection<Route> getRoutesForNextHop(IpAddress ip);
 
     /**
+     * Returns the set of routes in the default route table for the given prefix.
+     *
+     * @param prefix IP prefix
+     * @return route set
+     */
+    // TODO needs to be generalizable across route tables
+    @Beta
+    RouteSet getRoutes(IpPrefix prefix);
+
+    /**
      * Updates a next hop information in the store.
      *
      * @param ip IP address
      * @param nextHopData Information of the next hop
      */
+    @Deprecated
     void updateNextHop(IpAddress ip, NextHopData nextHopData);
 
     /**
@@ -87,6 +93,7 @@
      * @param ip IP address
      * @param nextHopData Information of the next hop
      */
+    @Deprecated
     void removeNextHop(IpAddress ip, NextHopData nextHopData);
 
     /**
@@ -95,6 +102,7 @@
      * @param ip next hop IP
      * @return Information of the next hop
      */
+    @Deprecated
     NextHopData getNextHop(IpAddress ip);
 
     /**
@@ -102,5 +110,17 @@
      *
      * @return next hops
      */
+    @Deprecated
     Map<IpAddress, NextHopData> getNextHops();
+
+    /**
+     * Performs a longest prefix match with the given IP address.
+     *
+     * @param ip IP to look up
+     * @return longest prefix match route
+     * @deprecated in Kingfisher release. Now handled by the manager instead of
+     * the store
+     */
+    @Deprecated
+    Route longestPrefixMatch(IpAddress ip);
 }
diff --git a/incubator/api/src/main/java/org/onosproject/incubator/net/routing/RouteStoreDelegate.java b/incubator/api/src/main/java/org/onosproject/incubator/net/routing/RouteStoreDelegate.java
index 8b94d82..29a6ee7 100644
--- a/incubator/api/src/main/java/org/onosproject/incubator/net/routing/RouteStoreDelegate.java
+++ b/incubator/api/src/main/java/org/onosproject/incubator/net/routing/RouteStoreDelegate.java
@@ -1,5 +1,5 @@
 /*
- * Copyright 2016-present Open Networking Laboratory
+ * Copyright 2017-present Open Networking Laboratory
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -21,5 +21,5 @@
 /**
  * Route store delegate abstraction.
  */
-public interface RouteStoreDelegate extends StoreDelegate<RouteEvent> {
+public interface RouteStoreDelegate extends StoreDelegate<InternalRouteEvent> {
 }
diff --git a/incubator/api/src/test/java/org/onosproject/incubator/net/routing/RouteServiceAdapter.java b/incubator/api/src/test/java/org/onosproject/incubator/net/routing/RouteServiceAdapter.java
index 26bb641..a13f5c8 100644
--- a/incubator/api/src/test/java/org/onosproject/incubator/net/routing/RouteServiceAdapter.java
+++ b/incubator/api/src/test/java/org/onosproject/incubator/net/routing/RouteServiceAdapter.java
@@ -20,6 +20,7 @@
 
 import java.util.Collection;
 import java.util.Map;
+import java.util.Optional;
 import java.util.Set;
 
 /**
@@ -42,11 +43,26 @@
     }
 
     @Override
+    public Collection<RouteInfo> getRoutes(RouteTableId id) {
+        return null;
+    }
+
+    @Override
+    public Collection<RouteTableId> getRouteTables() {
+        return null;
+    }
+
+    @Override
     public Route longestPrefixMatch(IpAddress ip) {
         return null;
     }
 
     @Override
+    public Optional<ResolvedRoute> longestPrefixLookup(IpAddress ip) {
+        return null;
+    }
+
+    @Override
     public Collection<Route> getRoutesForNextHop(IpAddress nextHop) {
         return null;
     }
diff --git a/incubator/net/BUCK b/incubator/net/BUCK
index 17fa793..9790bed 100644
--- a/incubator/net/BUCK
+++ b/incubator/net/BUCK
@@ -4,6 +4,7 @@
     '//incubator/api:onos-incubator-api',
     '//incubator/store:onos-incubator-store',
     '//utils/rest:onlab-rest',
+    '//lib:concurrent-trees',
 ]
 
 TEST_DEPS = [
@@ -12,7 +13,6 @@
     '//core/api:onos-api-tests',
     '//core/common:onos-core-common-tests',
     '//core/store/serializers:onos-core-serializers',
-    '//lib:concurrent-trees',
 ]
 
 osgi_jar_with_tests (
diff --git a/incubator/net/pom.xml b/incubator/net/pom.xml
index ece69a7..686a679 100644
--- a/incubator/net/pom.xml
+++ b/incubator/net/pom.xml
@@ -100,6 +100,12 @@
             <classifier>tests</classifier>
             <scope>test</scope>
         </dependency>
+
+        <dependency>
+            <groupId>com.googlecode.concurrent-trees</groupId>
+            <artifactId>concurrent-trees</artifactId>
+            <version>2.6.0</version>
+        </dependency>
     </dependencies>
 
     <build>
diff --git a/incubator/net/src/main/java/org/onosproject/incubator/net/routing/impl/DefaultResolvedRouteStore.java b/incubator/net/src/main/java/org/onosproject/incubator/net/routing/impl/DefaultResolvedRouteStore.java
new file mode 100644
index 0000000..d3f97b9
--- /dev/null
+++ b/incubator/net/src/main/java/org/onosproject/incubator/net/routing/impl/DefaultResolvedRouteStore.java
@@ -0,0 +1,190 @@
+/*
+ * Copyright 2017-present Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.onosproject.incubator.net.routing.impl;
+
+import com.googlecode.concurrenttrees.common.KeyValuePair;
+import com.googlecode.concurrenttrees.radix.node.concrete.DefaultByteArrayNodeFactory;
+import com.googlecode.concurrenttrees.radixinverted.ConcurrentInvertedRadixTree;
+import com.googlecode.concurrenttrees.radixinverted.InvertedRadixTree;
+import org.onlab.packet.IpAddress;
+import org.onlab.packet.IpPrefix;
+import org.onlab.util.GuavaCollectors;
+import org.onlab.util.Tools;
+import org.onosproject.incubator.net.routing.ResolvedRoute;
+import org.onosproject.incubator.net.routing.RouteEvent;
+import org.onosproject.incubator.net.routing.RouteTableId;
+
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Map;
+import java.util.Optional;
+import java.util.Set;
+import java.util.concurrent.ConcurrentHashMap;
+
+import static org.onosproject.incubator.net.routing.RouteTools.createBinaryString;
+
+/**
+ * Stores routes that have been resolved.
+ */
+public class DefaultResolvedRouteStore implements ResolvedRouteStore {
+
+    private Map<RouteTableId, RouteTable> routeTables;
+    private static final RouteTableId IPV4 = new RouteTableId("ipv4");
+    private static final RouteTableId IPV6 = new RouteTableId("ipv6");
+
+    /**
+     * Creates a new resolved route store.
+     */
+    public DefaultResolvedRouteStore() {
+        routeTables = new ConcurrentHashMap<>();
+
+        routeTables.put(IPV4, new RouteTable());
+        routeTables.put(IPV6, new RouteTable());
+    }
+
+    @Override
+    public RouteEvent updateRoute(ResolvedRoute route) {
+        return getDefaultRouteTable(route).update(route);
+    }
+
+    @Override
+    public RouteEvent removeRoute(IpPrefix prefix) {
+        RouteTable table = getDefaultRouteTable(prefix.address());
+        return table.remove(prefix);
+    }
+
+    @Override
+    public Set<RouteTableId> getRouteTables() {
+        return routeTables.keySet();
+    }
+
+    @Override
+    public Collection<ResolvedRoute> getRoutes(RouteTableId table) {
+        RouteTable routeTable = routeTables.get(table);
+        if (routeTable == null) {
+            return Collections.emptySet();
+        }
+        return routeTable.getRoutes();
+    }
+
+    @Override
+    public Optional<ResolvedRoute> getRoute(IpPrefix prefix) {
+        return getDefaultRouteTable(prefix.address()).getRoute(prefix);
+    }
+
+    @Override
+    public Optional<ResolvedRoute> longestPrefixMatch(IpAddress ip) {
+        return getDefaultRouteTable(ip).longestPrefixMatch(ip);
+    }
+
+    private RouteTable getDefaultRouteTable(ResolvedRoute route) {
+        return getDefaultRouteTable(route.prefix().address());
+    }
+
+    private RouteTable getDefaultRouteTable(IpAddress ip) {
+        RouteTableId routeTableId = (ip.isIp4()) ? IPV4 : IPV6;
+        return routeTables.get(routeTableId);
+    }
+
+    /**
+     * Route table into which routes can be placed.
+     */
+    private class RouteTable {
+        private final InvertedRadixTree<ResolvedRoute> routeTable;
+
+        /**
+         * Creates a new route table.
+         */
+        public RouteTable() {
+            routeTable = new ConcurrentInvertedRadixTree<>(
+                    new DefaultByteArrayNodeFactory());
+        }
+
+        /**
+         * Adds or updates the route in the route table.
+         *
+         * @param route route to update
+         */
+        public RouteEvent update(ResolvedRoute route) {
+            synchronized (this) {
+                ResolvedRoute oldRoute = routeTable.put(createBinaryString(route.prefix()), route);
+
+                // No need to proceed if the new route is the same
+                if (route.equals(oldRoute)) {
+                    return null;
+                }
+
+                if (oldRoute == null) {
+                    return new RouteEvent(RouteEvent.Type.ROUTE_ADDED, route);
+                } else {
+                    return new RouteEvent(RouteEvent.Type.ROUTE_UPDATED, route, oldRoute);
+                }
+            }
+        }
+
+        /**
+         * Removes the route from the route table.
+         *
+         * @param prefix prefix to remove
+         */
+        public RouteEvent remove(IpPrefix prefix) {
+            synchronized (this) {
+                String key = createBinaryString(prefix);
+
+                ResolvedRoute route = routeTable.getValueForExactKey(key);
+
+                if (route != null) {
+                    routeTable.remove(key);
+                    return new RouteEvent(RouteEvent.Type.ROUTE_REMOVED, route);
+                }
+                return null;
+            }
+        }
+
+        /**
+         * Returns all routes in the route table.
+         *
+         * @return all routes
+         */
+        public Collection<ResolvedRoute> getRoutes() {
+            return Tools.stream(routeTable.getKeyValuePairsForKeysStartingWith(""))
+                    .map(KeyValuePair::getValue)
+                    .collect(GuavaCollectors.toImmutableList());
+        }
+
+        /**
+         * Returns the best route for the given prefix, if one exists.
+         *
+         * @param prefix IP prefix
+         * @return best route
+         */
+        public Optional<ResolvedRoute> getRoute(IpPrefix prefix) {
+            return Optional.ofNullable(routeTable.getValueForExactKey(createBinaryString(prefix)));
+        }
+
+        /**
+         * Performs a longest prefix match with the given IP in the route table.
+         *
+         * @param ip IP address to look up
+         * @return most specific prefix containing the given
+         */
+        public Optional<ResolvedRoute> longestPrefixMatch(IpAddress ip) {
+            return Tools.stream(routeTable.getValuesForKeysPrefixing(createBinaryString(ip.toIpPrefix())))
+                    .reduce((a, b) -> b); // reduces to the last element in the stream
+        }
+    }
+}
diff --git a/incubator/net/src/main/java/org/onosproject/incubator/net/routing/impl/ResolvedRouteStore.java b/incubator/net/src/main/java/org/onosproject/incubator/net/routing/impl/ResolvedRouteStore.java
new file mode 100644
index 0000000..55ca3f9
--- /dev/null
+++ b/incubator/net/src/main/java/org/onosproject/incubator/net/routing/impl/ResolvedRouteStore.java
@@ -0,0 +1,80 @@
+/*
+ * Copyright 2017-present Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.onosproject.incubator.net.routing.impl;
+
+import org.onlab.packet.IpAddress;
+import org.onlab.packet.IpPrefix;
+import org.onosproject.incubator.net.routing.ResolvedRoute;
+import org.onosproject.incubator.net.routing.RouteEvent;
+import org.onosproject.incubator.net.routing.RouteTableId;
+
+import java.util.Collection;
+import java.util.Optional;
+import java.util.Set;
+
+/**
+ * Stores resolved routes and best route decisions.
+ */
+public interface ResolvedRouteStore {
+
+    /**
+     * Adds or updates the best route for the given prefix.
+     *
+     * @param route new best route for this prefix
+     * @return event describing the change
+     */
+    RouteEvent updateRoute(ResolvedRoute route);
+
+    /**
+     * Removes the best route for the given prefix.
+     *
+     * @param prefix IP prefix
+     * @return event describing the change
+     */
+    RouteEvent removeRoute(IpPrefix prefix);
+
+    /**
+     * Gets the set of route tables.
+     *
+     * @return set of route table IDs
+     */
+    Set<RouteTableId> getRouteTables();
+
+    /**
+     * Returns the best routes for a give route table.
+     *
+     * @param table route table ID
+     * @return collection of selected routes
+     */
+    Collection<ResolvedRoute> getRoutes(RouteTableId table);
+
+    /**
+     * Returns the best selected route for the given IP prefix.
+     *
+     * @param prefix IP prefix
+     * @return optional best route
+     */
+    Optional<ResolvedRoute> getRoute(IpPrefix prefix);
+
+    /**
+     * Performs a longest prefix match of the best routes on the given IP address.
+     *
+     * @param ip IP address
+     * @return optional longest matching route
+     */
+    Optional<ResolvedRoute> longestPrefixMatch(IpAddress ip);
+}
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 368d65e..dab0418 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
@@ -1,5 +1,5 @@
 /*
- * Copyright 2016-present Open Networking Laboratory
+ * Copyright 2017-present Open Networking Laboratory
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -24,14 +24,16 @@
 import org.apache.felix.scr.annotations.Service;
 import org.onlab.packet.IpAddress;
 import org.onosproject.event.ListenerService;
+import org.onosproject.incubator.net.routing.InternalRouteEvent;
 import org.onosproject.incubator.net.routing.NextHop;
-import org.onosproject.incubator.net.routing.NextHopData;
 import org.onosproject.incubator.net.routing.ResolvedRoute;
 import org.onosproject.incubator.net.routing.Route;
 import org.onosproject.incubator.net.routing.RouteAdminService;
 import org.onosproject.incubator.net.routing.RouteEvent;
+import org.onosproject.incubator.net.routing.RouteInfo;
 import org.onosproject.incubator.net.routing.RouteListener;
 import org.onosproject.incubator.net.routing.RouteService;
+import org.onosproject.incubator.net.routing.RouteSet;
 import org.onosproject.incubator.net.routing.RouteStore;
 import org.onosproject.incubator.net.routing.RouteStoreDelegate;
 import org.onosproject.incubator.net.routing.RouteTableId;
@@ -45,8 +47,10 @@
 import javax.annotation.concurrent.GuardedBy;
 import java.util.Collection;
 import java.util.Collections;
+import java.util.Comparator;
 import java.util.HashMap;
 import java.util.Map;
+import java.util.Objects;
 import java.util.Optional;
 import java.util.Set;
 import java.util.concurrent.BlockingQueue;
@@ -78,6 +82,8 @@
     @Reference(cardinality = ReferenceCardinality.MANDATORY_UNARY)
     protected HostService hostService;
 
+    private ResolvedRouteStore resolvedRouteStore;
+
     @GuardedBy(value = "this")
     private Map<RouteListener, ListenerQueue> listeners = new HashMap<>();
 
@@ -87,13 +93,19 @@
     protected void activate() {
         threadFactory = groupedThreads("onos/route", "listener-%d", log);
 
+        resolvedRouteStore = new DefaultResolvedRouteStore();
+
         routeStore.setDelegate(delegate);
         hostService.addListener(hostListener);
+
+        routeStore.getRouteTables().stream()
+                .flatMap(id -> routeStore.getRoutes(id).stream())
+                .forEach(this::resolve);
     }
 
     @Deactivate
     protected void deactivate() {
-        listeners.values().forEach(l -> l.stop());
+        listeners.values().forEach(ListenerQueue::stop);
 
         routeStore.unsetDelegate(delegate);
         hostService.removeListener(hostListener);
@@ -114,19 +126,11 @@
         synchronized (this) {
             log.debug("Synchronizing current routes to new listener");
             ListenerQueue l = createListenerQueue(listener);
-            routeStore.getRouteTables().forEach(table -> {
-                Collection<Route> routes = routeStore.getRoutes(table);
-                if (routes != null) {
-                    routes.forEach(route -> {
-                        NextHopData nextHopData = routeStore.getNextHop(route.nextHop());
-                        if (nextHopData != null) {
-                            l.post(new RouteEvent(RouteEvent.Type.ROUTE_ADDED,
-                                                  new ResolvedRoute(route, nextHopData.mac(),
-                                                                    nextHopData.location())));
-                        }
-                    });
-                }
-            });
+            resolvedRouteStore.getRouteTables().stream()
+                    .map(resolvedRouteStore::getRoutes)
+                    .flatMap(Collection::stream)
+                    .map(route -> new RouteEvent(RouteEvent.Type.ROUTE_ADDED, route))
+                    .forEach(l::post);
 
             listeners.put(listener, l);
 
@@ -151,9 +155,11 @@
      * @param event event
      */
     private void post(RouteEvent event) {
-        log.debug("Sending event {}", event);
-        synchronized (this) {
-            listeners.values().forEach(l -> l.post(event));
+        if (event != null) {
+            log.debug("Sending event {}", event);
+            synchronized (this) {
+                listeners.values().forEach(l -> l.post(event));
+            }
         }
     }
 
@@ -162,12 +168,49 @@
         return routeStore.getRouteTables().stream()
                 .collect(Collectors.toMap(Function.identity(),
                         table -> (table == null) ?
-                                 Collections.emptySet() : routeStore.getRoutes(table)));
+                                 Collections.emptySet() : reformatRoutes(routeStore.getRoutes(table))));
+    }
+
+    private Collection<Route> reformatRoutes(Collection<RouteSet> routeSets) {
+        return routeSets.stream().flatMap(r -> r.routes().stream()).collect(Collectors.toList());
+    }
+
+    public Collection<RouteTableId> getRouteTables() {
+        return routeStore.getRouteTables();
+    }
+
+    @Override
+    public Collection<RouteInfo> getRoutes(RouteTableId id) {
+        return routeStore.getRoutes(id).stream()
+                .map(routeSet -> new RouteInfo(routeSet.prefix(),
+                        resolvedRouteStore.getRoute(routeSet.prefix()).orElse(null), resolveRouteSet(routeSet)))
+                .collect(Collectors.toList());
+    }
+
+    private Set<ResolvedRoute> resolveRouteSet(RouteSet routeSet) {
+        return routeSet.routes().stream()
+                .map(this::tryResolve)
+                .collect(Collectors.toSet());
+    }
+
+    private ResolvedRoute tryResolve(Route route) {
+        ResolvedRoute resolvedRoute = resolve(route);
+        if (resolvedRoute == null) {
+            resolvedRoute = new ResolvedRoute(route, null, null);
+        }
+        return resolvedRoute;
     }
 
     @Override
     public Route longestPrefixMatch(IpAddress ip) {
-        return routeStore.longestPrefixMatch(ip);
+        return longestPrefixLookup(ip)
+                .map(r -> new Route(Route.Source.STATIC, r.prefix(), r.nextHop()))
+                .orElse(null);
+    }
+
+    @Override
+    public Optional<ResolvedRoute> longestPrefixLookup(IpAddress ip) {
+        return resolvedRouteStore.longestPrefixMatch(ip);
     }
 
     @Override
@@ -188,7 +231,6 @@
             routes.forEach(route -> {
                 log.debug("Received update {}", route);
                 routeStore.updateRoute(route);
-                resolve(route);
             });
         }
     }
@@ -203,37 +245,55 @@
         }
     }
 
-    private void resolve(Route route) {
-        // Monitor the IP address for updates of the MAC address
+    private ResolvedRoute resolve(Route route) {
         hostService.startMonitoringIp(route.nextHop());
+        Set<Host> hosts = hostService.getHostsByIp(route.nextHop());
 
-        NextHopData nextHopData = routeStore.getNextHop(route.nextHop());
-        if (nextHopData == null) {
-            Set<Host> hosts = hostService.getHostsByIp(route.nextHop());
-            Optional<Host> host = hosts.stream().findFirst();
-            if (host.isPresent()) {
-                nextHopData = NextHopData.fromHost(host.get());
-            }
+        Optional<Host> host = hosts.stream().findFirst();
+        if (host.isPresent()) {
+            return new ResolvedRoute(route, host.get().mac(), host.get().location());
+        } else {
+            return null;
         }
+    }
 
-        if (nextHopData != null) {
-            routeStore.updateNextHop(route.nextHop(), nextHopData);
+    private ResolvedRoute decide(ResolvedRoute route1, ResolvedRoute route2) {
+        return Comparator.<ResolvedRoute, IpAddress>comparing(route -> route.nextHop())
+                       .compare(route1, route2) <= 0 ? route1 : route2;
+    }
+
+    private void store(ResolvedRoute route) {
+        post(resolvedRouteStore.updateRoute(route));
+    }
+
+    private void resolve(RouteSet routes) {
+        Optional<ResolvedRoute> resolvedRoute =
+        routes.routes().stream()
+                    .map(this::resolve)
+                    .filter(Objects::nonNull)
+                    .reduce(this::decide);
+
+        if (resolvedRoute.isPresent()) {
+            this.store(resolvedRoute.get());
+        } else {
+            post(resolvedRouteStore.removeRoute(routes.prefix()));
         }
     }
 
     private void hostUpdated(Host host) {
-        synchronized (this) {
-            for (IpAddress ip : host.ipAddresses()) {
-                routeStore.updateNextHop(ip, NextHopData.fromHost(host));
-            }
-        }
+        hostChanged(host);
     }
 
     private void hostRemoved(Host host) {
+        hostChanged(host);
+    }
+
+    private void hostChanged(Host host) {
         synchronized (this) {
-            for (IpAddress ip : host.ipAddresses()) {
-                routeStore.removeNextHop(ip, NextHopData.fromHost(host));
-            }
+            host.ipAddresses().stream()
+                    .flatMap(ip -> routeStore.getRoutesForNextHop(ip).stream())
+                    .map(route -> routeStore.getRoutes(route.prefix()))
+                    .forEach(this::resolve);
         }
     }
 
@@ -294,7 +354,6 @@
                 }
             }
         }
-
     }
 
     /**
@@ -302,8 +361,17 @@
      */
     private class InternalRouteStoreDelegate implements RouteStoreDelegate {
         @Override
-        public void notify(RouteEvent event) {
-            post(event);
+        public void notify(InternalRouteEvent event) {
+            switch (event.type()) {
+            case ROUTE_ADDED:
+                resolve(event.subject());
+                break;
+            case ROUTE_REMOVED:
+                resolve(event.subject());
+                break;
+            default:
+                break;
+            }
         }
     }
 
diff --git a/incubator/net/src/test/java/org/onosproject/incubator/net/routing/impl/RouteManagerTest.java b/incubator/net/src/test/java/org/onosproject/incubator/net/routing/impl/RouteManagerTest.java
index ba73cde..aeb2ff1 100644
--- a/incubator/net/src/test/java/org/onosproject/incubator/net/routing/impl/RouteManagerTest.java
+++ b/incubator/net/src/test/java/org/onosproject/incubator/net/routing/impl/RouteManagerTest.java
@@ -215,10 +215,10 @@
     public void testRouteUpdate() {
         Route route = new Route(Route.Source.STATIC, V4_PREFIX1, V4_NEXT_HOP1);
         Route updatedRoute = new Route(Route.Source.STATIC, V4_PREFIX1, V4_NEXT_HOP2);
-        ResolvedRoute resolvedRoute = new ResolvedRoute(updatedRoute, MAC1, CP1);
+        ResolvedRoute resolvedRoute = new ResolvedRoute(route, MAC1, CP1);
         ResolvedRoute updatedResolvedRoute = new ResolvedRoute(updatedRoute, MAC2, CP1);
 
-        verifyRouteRemoveThenAdd(route, updatedRoute, resolvedRoute, updatedResolvedRoute);
+        verifyRouteUpdated(route, updatedRoute, resolvedRoute, updatedResolvedRoute);
 
         // Different prefix pointing to the same next hop.
         // In this case we expect to receive a ROUTE_UPDATED event.
@@ -234,36 +234,7 @@
         resolvedRoute = new ResolvedRoute(route, MAC3, CP1);
         updatedResolvedRoute = new ResolvedRoute(updatedRoute, MAC4, CP1);
 
-        verifyRouteRemoveThenAdd(route, updatedRoute, resolvedRoute, updatedResolvedRoute);
-    }
-
-    /**
-     * Tests updating a route and verifies that the route listener receives a
-     * route remove event followed by a route add event.
-     *
-     * @param original original route
-     * @param updated updated route
-     * @param resolvedRoute resolved route before update
-     * @param updatedResolvedRoute resolved route that is expected to be sent to
-     *                             the route listener
-     */
-    private void verifyRouteRemoveThenAdd(Route original, Route updated,
-                                          ResolvedRoute resolvedRoute,
-                                          ResolvedRoute updatedResolvedRoute) {
-        // First add the original route
-        addRoute(original);
-
-        routeListener.event(new RouteEvent(RouteEvent.Type.ROUTE_REMOVED,
-                new ResolvedRoute(original, resolvedRoute.nextHopMac(), resolvedRoute.location())));
-        expectLastCall().once();
-        routeListener.event(new RouteEvent(RouteEvent.Type.ROUTE_ADDED, updatedResolvedRoute));
-        expectLastCall().once();
-
-        replay(routeListener);
-
-        routeManager.update(Collections.singleton(updated));
-
-        verify(routeListener);
+        verifyRouteUpdated(route, updatedRoute, resolvedRoute, updatedResolvedRoute);
     }
 
     /**
@@ -345,6 +316,7 @@
         expect(hostService.getHostsByIp(anyObject(IpAddress.class))).andReturn(
                 Collections.emptySet()).anyTimes();
         hostService.startMonitoringIp(V4_NEXT_HOP1);
+        expectLastCall().anyTimes();
         replay(hostService);
 
         // Initially when we add the route, no route event will be sent because
@@ -361,8 +333,17 @@
                 new ResolvedRoute(route, MAC1, CP1)));
         replay(routeListener);
 
-        // Send in the host event
         Host host = createHost(MAC1, V4_NEXT_HOP1);
+
+        // Set up the host service with a host
+        reset(hostService);
+        expect(hostService.getHostsByIp(V4_NEXT_HOP1)).andReturn(
+                Collections.singleton(host)).anyTimes();
+        hostService.startMonitoringIp(V4_NEXT_HOP1);
+        expectLastCall().anyTimes();
+        replay(hostService);
+
+        // Send in the host event
         hostListener.event(new HostEvent(HostEvent.Type.HOST_ADDED, host));
 
         verify(routeListener);
diff --git a/incubator/store/src/main/java/org/onosproject/incubator/store/routing/impl/DefaultRouteTable.java b/incubator/store/src/main/java/org/onosproject/incubator/store/routing/impl/DefaultRouteTable.java
new file mode 100644
index 0000000..e9537d9
--- /dev/null
+++ b/incubator/store/src/main/java/org/onosproject/incubator/store/routing/impl/DefaultRouteTable.java
@@ -0,0 +1,189 @@
+/*
+ * Copyright 2017-present Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.onosproject.incubator.store.routing.impl;
+
+import org.onlab.packet.IpAddress;
+import org.onlab.packet.IpPrefix;
+import org.onlab.util.KryoNamespace;
+import org.onosproject.incubator.net.routing.InternalRouteEvent;
+import org.onosproject.incubator.net.routing.Route;
+import org.onosproject.incubator.net.routing.RouteSet;
+import org.onosproject.incubator.net.routing.RouteStoreDelegate;
+import org.onosproject.incubator.net.routing.RouteTableId;
+import org.onosproject.store.serializers.KryoNamespaces;
+import org.onosproject.store.service.ConsistentMap;
+import org.onosproject.store.service.MapEvent;
+import org.onosproject.store.service.MapEventListener;
+import org.onosproject.store.service.Serializer;
+import org.onosproject.store.service.StorageService;
+import org.onosproject.store.service.Versioned;
+
+import java.util.Collection;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Set;
+import java.util.stream.Collectors;
+
+import static com.google.common.base.Preconditions.checkNotNull;
+
+/**
+ * Default implementation of a route table based on a consistent map.
+ */
+public class DefaultRouteTable implements RouteTable {
+
+    private final RouteTableId id;
+    private final ConsistentMap<IpPrefix, Set<Route>> routes;
+    private final RouteStoreDelegate delegate;
+    private final RouteTableListener listener = new RouteTableListener();
+
+    /**
+     * Creates a new route table.
+     *
+     * @param id route table ID
+     * @param delegate route store delegate to notify of events
+     * @param storageService storage service
+     */
+    public DefaultRouteTable(RouteTableId id, RouteStoreDelegate delegate,
+                             StorageService storageService) {
+        this.delegate = checkNotNull(delegate);
+        this.id = checkNotNull(id);
+        this.routes = buildRouteMap(checkNotNull(storageService));
+
+        routes.entrySet().stream()
+                .map(e -> new InternalRouteEvent(InternalRouteEvent.Type.ROUTE_ADDED,
+                        new RouteSet(id, e.getKey(), e.getValue().value())))
+                .forEach(delegate::notify);
+
+        routes.addListener(listener);
+    }
+
+    private ConsistentMap<IpPrefix, Set<Route>> buildRouteMap(StorageService storageService) {
+        KryoNamespace routeTableSerializer = KryoNamespace.newBuilder()
+                .register(KryoNamespaces.API)
+                .register(Route.class)
+                .register(Route.Source.class)
+                .build();
+        return storageService.<IpPrefix, Set<Route>>consistentMapBuilder()
+                .withName("onos-routes-" + id.name())
+                .withRelaxedReadConsistency()
+                .withSerializer(Serializer.using(routeTableSerializer))
+                .build();
+    }
+
+    @Override
+    public RouteTableId id() {
+        return id;
+    }
+
+    @Override
+    public void shutdown() {
+        routes.removeListener(listener);
+    }
+
+    @Override
+    public void destroy() {
+        shutdown();
+        routes.destroy();
+    }
+
+    @Override
+    public void update(Route route) {
+        routes.compute(route.prefix(), (prefix, set) -> {
+            if (set == null) {
+                set = new HashSet<>();
+            }
+            set.add(route);
+            return set;
+        });
+    }
+
+    @Override
+    public void remove(Route route) {
+        routes.compute(route.prefix(), (prefix, set) -> {
+            if (set != null) {
+                set.remove(route);
+                if (set.isEmpty()) {
+                    return null;
+                }
+                return set;
+            }
+            return null;
+        });
+    }
+
+    @Override
+    public Collection<RouteSet> getRoutes() {
+        return routes.entrySet().stream()
+                .map(e -> new RouteSet(id, e.getKey(), e.getValue().value()))
+                .collect(Collectors.toSet());
+    }
+
+    @Override
+    public RouteSet getRoutes(IpPrefix prefix) {
+        Versioned<Set<Route>> routeSet = routes.get(prefix);
+
+        if (routeSet != null) {
+            return new RouteSet(id, prefix, routeSet.value());
+        }
+        return null;
+    }
+
+    @Override
+    public Collection<Route> getRoutesForNextHop(IpAddress nextHop) {
+        // TODO index
+        return routes.values().stream()
+                .flatMap(v -> v.value().stream())
+                .filter(r -> r.nextHop().equals(nextHop))
+                .collect(Collectors.toSet());
+    }
+
+    private class RouteTableListener
+            implements MapEventListener<IpPrefix, Set<Route>> {
+
+        private InternalRouteEvent createRouteEvent(
+                InternalRouteEvent.Type type, MapEvent<IpPrefix, Set<Route>> event) {
+            Set<Route> currentRoutes =
+                    (event.newValue() == null) ? Collections.emptySet() : event.newValue().value();
+            return new InternalRouteEvent(type, new RouteSet(id, event.key(), currentRoutes));
+        }
+
+        @Override
+        public void event(MapEvent<IpPrefix, Set<Route>> event) {
+            InternalRouteEvent ire = null;
+            switch (event.type()) {
+            case INSERT:
+                ire = createRouteEvent(InternalRouteEvent.Type.ROUTE_ADDED, event);
+                break;
+            case UPDATE:
+                if (event.newValue().value().size() > event.oldValue().value().size()) {
+                    ire = createRouteEvent(InternalRouteEvent.Type.ROUTE_ADDED, event);
+                } else {
+                    ire = createRouteEvent(InternalRouteEvent.Type.ROUTE_REMOVED, event);
+                }
+                break;
+            case REMOVE:
+                ire = createRouteEvent(InternalRouteEvent.Type.ROUTE_REMOVED, event);
+                break;
+            default:
+                break;
+            }
+            if (ire != null) {
+                delegate.notify(ire);
+            }
+        }
+    }
+}
diff --git a/incubator/store/src/main/java/org/onosproject/incubator/store/routing/impl/DistributedRouteStore.java b/incubator/store/src/main/java/org/onosproject/incubator/store/routing/impl/DistributedRouteStore.java
index 98c2993..6901041 100644
--- a/incubator/store/src/main/java/org/onosproject/incubator/store/routing/impl/DistributedRouteStore.java
+++ b/incubator/store/src/main/java/org/onosproject/incubator/store/routing/impl/DistributedRouteStore.java
@@ -16,70 +16,56 @@
 
 package org.onosproject.incubator.store.routing.impl;
 
-import com.google.common.collect.Maps;
-import com.googlecode.concurrenttrees.radix.node.concrete.DefaultByteArrayNodeFactory;
-import com.googlecode.concurrenttrees.radixinverted.ConcurrentInvertedRadixTree;
-import com.googlecode.concurrenttrees.radixinverted.InvertedRadixTree;
+import com.google.common.collect.ImmutableSet;
 import org.onlab.packet.IpAddress;
 import org.onlab.packet.IpPrefix;
 import org.onlab.util.KryoNamespace;
+import org.onosproject.incubator.net.routing.InternalRouteEvent;
 import org.onosproject.incubator.net.routing.NextHopData;
-import org.onosproject.incubator.net.routing.ResolvedRoute;
 import org.onosproject.incubator.net.routing.Route;
-import org.onosproject.incubator.net.routing.RouteEvent;
+import org.onosproject.incubator.net.routing.RouteSet;
 import org.onosproject.incubator.net.routing.RouteStore;
 import org.onosproject.incubator.net.routing.RouteStoreDelegate;
 import org.onosproject.incubator.net.routing.RouteTableId;
 import org.onosproject.store.AbstractStore;
-import org.onosproject.store.serializers.KryoNamespaces;
-import org.onosproject.store.service.ConsistentMap;
-import org.onosproject.store.service.MapEvent;
-import org.onosproject.store.service.MapEventListener;
+import org.onosproject.store.service.DistributedSet;
 import org.onosproject.store.service.Serializer;
+import org.onosproject.store.service.SetEvent;
+import org.onosproject.store.service.SetEventListener;
 import org.onosproject.store.service.StorageService;
-import org.onosproject.store.service.Versioned;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
 
 import java.util.Collection;
 import java.util.Collections;
-import java.util.Iterator;
 import java.util.Map;
 import java.util.Set;
+import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.ExecutorService;
 import java.util.concurrent.Executors;
-import java.util.stream.Collectors;
-
-import static com.google.common.base.Preconditions.checkNotNull;
-import static org.onosproject.incubator.net.routing.RouteEvent.Type.ROUTE_ADDED;
-import static org.onosproject.incubator.net.routing.RouteEvent.Type.ROUTE_REMOVED;
-import static org.onosproject.incubator.net.routing.RouteTools.createBinaryString;
 
 /**
  * Route store based on distributed storage.
  */
-public class DistributedRouteStore extends AbstractStore<RouteEvent, RouteStoreDelegate>
+public class DistributedRouteStore extends AbstractStore<InternalRouteEvent, RouteStoreDelegate>
         implements RouteStore {
-    public StorageService storageService;
+
+    protected StorageService storageService;
 
     private static final RouteTableId IPV4 = new RouteTableId("ipv4");
     private static final RouteTableId IPV6 = new RouteTableId("ipv6");
     private static final Logger log = LoggerFactory.getLogger(DistributedRouteStore.class);
-    private final MapEventListener<IpPrefix, Route> routeTableListener = new RouteTableListener();
-    private final MapEventListener<IpAddress, NextHopData> nextHopListener = new NextHopListener();
+    private final SetEventListener<RouteTableId> masterRouteTableListener =
+            new MasterRouteTableListener();
+    private final RouteStoreDelegate ourDelegate = new InternalRouteStoreDelegate();
 
-    // TODO: ConsistentMap may not scale with high frequency route update
-    private final Map<RouteTableId, ConsistentMap<IpPrefix, Route>> routeTables =
-            Maps.newHashMap();
-    // NOTE: We cache local route tables with InvertedRadixTree for longest prefix matching
-    private final Map<RouteTableId, InvertedRadixTree<Route>> localRouteTables =
-            Maps.newHashMap();
-    private ConsistentMap<IpAddress, NextHopData> nextHops;
+    // Stores the route tables that have been created
+    private DistributedSet<RouteTableId> masterRouteTable;
+    // Local memory map to store route table object
+    private Map<RouteTableId, RouteTable> routeTables;
 
-    /**
-     * Constructs a distributed route store.
-     *
-     * @param storageService storage service should be passed from RouteStoreImpl
-     */
+    private ExecutorService executor;
+
     public DistributedRouteStore(StorageService storageService) {
         this.storageService = storageService;
     }
@@ -88,19 +74,26 @@
      * Sets up distributed route store.
      */
     public void activate() {
-        // Creates and stores maps
-        ConsistentMap<IpPrefix, Route> ipv4RouteTable = createRouteTable(IPV4);
-        ConsistentMap<IpPrefix, Route> ipv6RouteTable = createRouteTable(IPV6);
-        routeTables.put(IPV4, ipv4RouteTable);
-        routeTables.put(IPV6, ipv6RouteTable);
-        localRouteTables.put(IPV4, createLocalRouteTable());
-        localRouteTables.put(IPV6, createLocalRouteTable());
-        nextHops = createNextHopTable();
+        routeTables = new ConcurrentHashMap<>();
+        executor = Executors.newSingleThreadExecutor();
 
-        // Adds map listeners
-        routeTables.values().forEach(routeTable ->
-                routeTable.addListener(routeTableListener, Executors.newSingleThreadExecutor()));
-        nextHops.addListener(nextHopListener, Executors.newSingleThreadExecutor());
+        KryoNamespace masterRouteTableSerializer = KryoNamespace.newBuilder()
+                .register(RouteTableId.class)
+                .build();
+
+        masterRouteTable = storageService.<RouteTableId>setBuilder()
+                .withName("onos-master-route-table")
+                .withSerializer(Serializer.using(masterRouteTableSerializer))
+                .build()
+                .asDistributedSet();
+
+        masterRouteTable.forEach(this::createRouteTable);
+
+        masterRouteTable.addListener(masterRouteTableListener);
+
+        // Add default tables (add is idempotent)
+        masterRouteTable.add(IPV4);
+        masterRouteTable.add(IPV6);
 
         log.info("Started");
     }
@@ -109,257 +102,115 @@
      * Cleans up distributed route store.
      */
     public void deactivate() {
-        routeTables.values().forEach(routeTable -> {
-            routeTable.removeListener(routeTableListener);
-            routeTable.destroy();
-        });
-        nextHops.removeListener(nextHopListener);
-        nextHops.destroy();
+        masterRouteTable.removeListener(masterRouteTableListener);
 
-        routeTables.clear();
-        localRouteTables.clear();
-        nextHops.clear();
+        routeTables.values().forEach(RouteTable::shutdown);
 
         log.info("Stopped");
     }
 
     @Override
     public void updateRoute(Route route) {
-        getDefaultRouteTable(route).put(route.prefix(), route);
+        getDefaultRouteTable(route).update(route);
     }
 
     @Override
     public void removeRoute(Route route) {
-        getDefaultRouteTable(route).remove(route.prefix());
-
-        if (getRoutesForNextHop(route.nextHop()).isEmpty()) {
-            nextHops.remove(route.nextHop());
-        }
+        getDefaultRouteTable(route).remove(route);
     }
 
     @Override
     public Set<RouteTableId> getRouteTables() {
-        return routeTables.keySet();
+        return ImmutableSet.copyOf(masterRouteTable);
     }
 
     @Override
-    public Collection<Route> getRoutes(RouteTableId table) {
-        ConsistentMap<IpPrefix, Route> routeTable = routeTables.get(table);
-        return (routeTable != null) ?
-                routeTable.values().stream().map(Versioned::value).collect(Collectors.toSet()) :
-                Collections.emptySet();
+    public Collection<RouteSet> getRoutes(RouteTableId table) {
+        RouteTable routeTable = routeTables.get(table);
+        if (routeTable == null) {
+            return Collections.emptySet();
+        } else {
+            return ImmutableSet.copyOf(routeTable.getRoutes());
+        }
     }
 
     @Override
     public Route longestPrefixMatch(IpAddress ip) {
-        Iterable<Route> prefixes = getDefaultLocalRouteTable(ip)
-                .getValuesForKeysPrefixing(createBinaryString(ip.toIpPrefix()));
-        Iterator<Route> it = prefixes.iterator();
-
-        Route route = null;
-        while (it.hasNext()) {
-            route = it.next();
-        }
-
-        return route;
+        // Not supported
+        return null;
     }
 
     @Override
     public Collection<Route> getRoutesForNextHop(IpAddress ip) {
-        return getDefaultRouteTable(ip).values().stream()
-                .filter(route -> route.nextHop().equals(ip))
-                .collect(Collectors.toList());
+        return getDefaultRouteTable(ip).getRoutesForNextHop(ip);
+    }
+
+    @Override
+    public RouteSet getRoutes(IpPrefix prefix) {
+        return getDefaultRouteTable(prefix.address()).getRoutes(prefix);
     }
 
     @Override
     public void updateNextHop(IpAddress ip, NextHopData nextHopData) {
-        checkNotNull(ip);
-        checkNotNull(nextHopData);
-        Collection<Route> routes = getRoutesForNextHop(ip);
-        if (!routes.isEmpty() && !nextHopData.equals(getNextHop(ip))) {
-            nextHops.put(ip, nextHopData);
-        }
+        // Not supported
     }
 
     @Override
     public void removeNextHop(IpAddress ip, NextHopData nextHopData) {
-        checkNotNull(ip);
-        checkNotNull(nextHopData);
-        nextHops.remove(ip, nextHopData);
+        // Not supported
     }
 
     @Override
     public NextHopData getNextHop(IpAddress ip) {
-        return Versioned.valueOrNull(nextHops.get(ip));
+        // Not supported
+        return null;
     }
 
     @Override
     public Map<IpAddress, NextHopData> getNextHops() {
-        return nextHops.asJavaMap();
+        // Not supported
+        return Collections.emptyMap();
     }
 
-    private ConsistentMap<IpPrefix, Route> createRouteTable(RouteTableId tableId) {
-        KryoNamespace routeTableSerializer = KryoNamespace.newBuilder()
-                .register(KryoNamespaces.API)
-                .register(Route.class)
-                .register(Route.Source.class)
-                .build();
-        return storageService.<IpPrefix, Route>consistentMapBuilder()
-                .withName("onos-routes-" + tableId.name())
-                .withRelaxedReadConsistency()
-                .withSerializer(Serializer.using(routeTableSerializer))
-                .build();
+    private void createRouteTable(RouteTableId tableId) {
+        routeTables.computeIfAbsent(tableId, id -> new DefaultRouteTable(id, ourDelegate, storageService));
     }
 
-    private ConcurrentInvertedRadixTree<Route> createLocalRouteTable() {
-        return new ConcurrentInvertedRadixTree<>(new DefaultByteArrayNodeFactory());
+    private void destroyRouteTable(RouteTableId tableId) {
+        RouteTable table = routeTables.remove(tableId);
+        if (table != null) {
+            table.destroy();
+        }
     }
 
-    private ConsistentMap<IpAddress, NextHopData> createNextHopTable() {
-        KryoNamespace.Builder nextHopSerializer = KryoNamespace.newBuilder()
-                .register(KryoNamespaces.API)
-                .register(NextHopData.class);
-        return storageService.<IpAddress, NextHopData>consistentMapBuilder()
-                .withName("onos-nexthops")
-                .withRelaxedReadConsistency()
-                .withSerializer(Serializer.using(nextHopSerializer.build()))
-                .build();
-    }
-
-    private Map<IpPrefix, Route> getDefaultRouteTable(Route route) {
+    private RouteTable getDefaultRouteTable(Route route) {
         return getDefaultRouteTable(route.prefix().address());
     }
 
-    private Map<IpPrefix, Route> getDefaultRouteTable(IpAddress ip) {
+    private RouteTable getDefaultRouteTable(IpAddress ip) {
         RouteTableId routeTableId = (ip.isIp4()) ? IPV4 : IPV6;
-        return routeTables.get(routeTableId).asJavaMap();
+        return routeTables.getOrDefault(routeTableId, EmptyRouteTable.instance());
     }
 
-    private InvertedRadixTree<Route> getDefaultLocalRouteTable(IpAddress ip) {
-        RouteTableId routeTableId = (ip.isIp4()) ? IPV4 : IPV6;
-        return localRouteTables.get(routeTableId);
-    }
-
-    private class RouteTableListener implements MapEventListener<IpPrefix, Route> {
+    private class InternalRouteStoreDelegate implements RouteStoreDelegate {
         @Override
-        public void event(MapEvent<IpPrefix, Route> event) {
-            Route route, prevRoute;
-            NextHopData nextHopData, prevNextHopData;
-            switch (event.type()) {
-                case INSERT:
-                    route = checkNotNull(event.newValue().value());
-                    nextHopData = getNextHop(route.nextHop());
-
-                    // Update local cache
-                    getDefaultLocalRouteTable(route.nextHop())
-                            .put(createBinaryString(route.prefix()), route);
-
-                    // Send ROUTE_ADDED only when the next hop is resolved
-                    if (nextHopData != null) {
-                        notifyDelegate(new RouteEvent(ROUTE_ADDED,
-                                new ResolvedRoute(route,
-                                        nextHopData.mac(), nextHopData.location())));
-                    }
-                    break;
-                case UPDATE:
-                    route = checkNotNull(event.newValue().value());
-                    prevRoute = checkNotNull(event.oldValue().value());
-                    nextHopData = getNextHop(route.nextHop());
-                    prevNextHopData = getNextHop(prevRoute.nextHop());
-
-                    // Update local cache
-                    getDefaultLocalRouteTable(route.nextHop())
-                            .put(createBinaryString(route.prefix()), route);
-
-                    if (nextHopData == null && prevNextHopData != null) {
-                        notifyDelegate(new RouteEvent(RouteEvent.Type.ROUTE_REMOVED,
-                                new ResolvedRoute(prevRoute,
-                                        prevNextHopData.mac(), prevNextHopData.location())));
-                    } else if (nextHopData != null && prevNextHopData != null) {
-                        notifyDelegate(new RouteEvent(RouteEvent.Type.ROUTE_UPDATED,
-                                new ResolvedRoute(route,
-                                        nextHopData.mac(), nextHopData.location()),
-                                new ResolvedRoute(prevRoute,
-                                        prevNextHopData.mac(), prevNextHopData.location())));
-                    }
-
-                    cleanupNextHop(prevRoute.nextHop());
-                    break;
-                case REMOVE:
-                    prevRoute = checkNotNull(event.oldValue().value());
-                    prevNextHopData = getNextHop(prevRoute.nextHop());
-
-                    // Update local cache
-                    getDefaultLocalRouteTable(prevRoute.nextHop())
-                            .remove(createBinaryString(prevRoute.prefix()));
-
-                    // Send ROUTE_REMOVED only when the next hop is resolved
-                    if (prevNextHopData != null) {
-                       notifyDelegate(new RouteEvent(ROUTE_REMOVED,
-                               new ResolvedRoute(prevRoute,
-                                       prevNextHopData.mac(), prevNextHopData.location())));
-                    }
-
-                    cleanupNextHop(prevRoute.nextHop());
-                    break;
-                default:
-                    log.warn("Unknown MapEvent type: {}", event.type());
-            }
-        }
-
-        /**
-         * Cleanup a nexthop when there is no routes reference to it.
-         */
-        private void cleanupNextHop(IpAddress ip) {
-            if (getDefaultRouteTable(ip).values().stream().noneMatch(route ->
-                    route.nextHop().equals(ip))) {
-                nextHops.remove(ip);
-            }
+        public void notify(InternalRouteEvent event) {
+            executor.execute(() -> DistributedRouteStore.this.notifyDelegate(event));
         }
     }
 
-    private class NextHopListener implements MapEventListener<IpAddress, NextHopData> {
+    private class MasterRouteTableListener implements SetEventListener<RouteTableId> {
         @Override
-        public void event(MapEvent<IpAddress, NextHopData> event) {
-            NextHopData nextHopData, oldNextHopData;
-            Collection<Route> routes = getRoutesForNextHop(event.key());
-
+        public void event(SetEvent<RouteTableId> event) {
             switch (event.type()) {
-                case INSERT:
-                    nextHopData = checkNotNull(event.newValue().value());
-                    routes.forEach(route ->
-                        notifyDelegate(new RouteEvent(RouteEvent.Type.ROUTE_ADDED,
-                                new ResolvedRoute(route,
-                                        nextHopData.mac(), nextHopData.location())))
-                    );
-                    break;
-                case UPDATE:
-                    nextHopData = checkNotNull(event.newValue().value());
-                    oldNextHopData = checkNotNull(event.oldValue().value());
-                    routes.forEach(route -> {
-                        if (oldNextHopData == null) {
-                            notifyDelegate(new RouteEvent(RouteEvent.Type.ROUTE_ADDED,
-                                    new ResolvedRoute(route,
-                                            nextHopData.mac(), nextHopData.location())));
-                        } else if (!oldNextHopData.equals(nextHopData)) {
-                            notifyDelegate(new RouteEvent(RouteEvent.Type.ROUTE_UPDATED,
-                                    new ResolvedRoute(route,
-                                            nextHopData.mac(), nextHopData.location()),
-                                    new ResolvedRoute(route,
-                                            oldNextHopData.mac(), oldNextHopData.location())));
-                        }
-                    });
-                    break;
-                case REMOVE:
-                    oldNextHopData = checkNotNull(event.oldValue().value());
-                    routes.forEach(route ->
-                        notifyDelegate(new RouteEvent(RouteEvent.Type.ROUTE_REMOVED,
-                                new ResolvedRoute(route,
-                                        oldNextHopData.mac(), oldNextHopData.location())))
-                    );
-                    break;
-                default:
-                    log.warn("Unknown MapEvent type: {}", event.type());
+            case ADD:
+                executor.execute(() -> createRouteTable(event.entry()));
+                break;
+            case REMOVE:
+                executor.execute(() -> destroyRouteTable(event.entry()));
+                break;
+            default:
+                break;
             }
         }
     }
diff --git a/incubator/store/src/main/java/org/onosproject/incubator/store/routing/impl/EmptyRouteTable.java b/incubator/store/src/main/java/org/onosproject/incubator/store/routing/impl/EmptyRouteTable.java
new file mode 100644
index 0000000..55ace40
--- /dev/null
+++ b/incubator/store/src/main/java/org/onosproject/incubator/store/routing/impl/EmptyRouteTable.java
@@ -0,0 +1,88 @@
+/*
+ * Copyright 2017-present Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.onosproject.incubator.store.routing.impl;
+
+import org.onlab.packet.IpAddress;
+import org.onlab.packet.IpPrefix;
+import org.onosproject.incubator.net.routing.Route;
+import org.onosproject.incubator.net.routing.RouteSet;
+import org.onosproject.incubator.net.routing.RouteTableId;
+
+import java.util.Collection;
+import java.util.Collections;
+
+/**
+ * Route table that contains no routes.
+ */
+public final class EmptyRouteTable implements RouteTable {
+
+    private final RouteTableId id = new RouteTableId("empty");
+
+    private static final EmptyRouteTable INSTANCE = new EmptyRouteTable();
+
+    /**
+     * Returns the instance of the empty route table.
+     *
+     * @return empty route table
+     */
+    public static EmptyRouteTable instance() {
+        return INSTANCE;
+    }
+
+    private EmptyRouteTable() {
+    }
+
+    @Override
+    public void update(Route route) {
+
+    }
+
+    @Override
+    public void remove(Route route) {
+
+    }
+
+    @Override
+    public RouteTableId id() {
+        return id;
+    }
+
+    @Override
+    public Collection<RouteSet> getRoutes() {
+        return Collections.emptyList();
+    }
+
+    @Override
+    public RouteSet getRoutes(IpPrefix prefix) {
+        return null;
+    }
+
+    @Override
+    public Collection<Route> getRoutesForNextHop(IpAddress nextHop) {
+        return Collections.emptyList();
+    }
+
+    @Override
+    public void shutdown() {
+
+    }
+
+    @Override
+    public void destroy() {
+
+    }
+}
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 46346d7..508c2f1 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
@@ -16,20 +16,16 @@
 
 package org.onosproject.incubator.store.routing.impl;
 
-import com.google.common.collect.HashMultimap;
-import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.Multimap;
-import com.google.common.collect.Multimaps;
 import com.googlecode.concurrenttrees.common.KeyValuePair;
 import com.googlecode.concurrenttrees.radix.node.concrete.DefaultByteArrayNodeFactory;
 import com.googlecode.concurrenttrees.radixinverted.ConcurrentInvertedRadixTree;
 import com.googlecode.concurrenttrees.radixinverted.InvertedRadixTree;
 import org.onlab.packet.IpAddress;
 import org.onlab.packet.IpPrefix;
+import org.onosproject.incubator.net.routing.InternalRouteEvent;
 import org.onosproject.incubator.net.routing.NextHopData;
-import org.onosproject.incubator.net.routing.ResolvedRoute;
 import org.onosproject.incubator.net.routing.Route;
-import org.onosproject.incubator.net.routing.RouteEvent;
+import org.onosproject.incubator.net.routing.RouteSet;
 import org.onosproject.incubator.net.routing.RouteStore;
 import org.onosproject.incubator.net.routing.RouteStoreDelegate;
 import org.onosproject.incubator.net.routing.RouteTableId;
@@ -45,6 +41,7 @@
 import java.util.Map;
 import java.util.Set;
 import java.util.concurrent.ConcurrentHashMap;
+import java.util.stream.Collectors;
 
 import static com.google.common.base.Preconditions.checkNotNull;
 import static org.onosproject.incubator.net.routing.RouteTools.createBinaryString;
@@ -52,7 +49,7 @@
 /**
  * Route store based on in-memory storage.
  */
-public class LocalRouteStore extends AbstractStore<RouteEvent, RouteStoreDelegate>
+public class LocalRouteStore extends AbstractStore<InternalRouteEvent, RouteStoreDelegate>
         implements RouteStore {
 
     private Logger log = LoggerFactory.getLogger(getClass());
@@ -61,22 +58,20 @@
     private static final RouteTableId IPV4 = new RouteTableId("ipv4");
     private static final RouteTableId IPV6 = new RouteTableId("ipv6");
 
-    private Map<IpAddress, NextHopData> nextHops = new ConcurrentHashMap<>();
-
     /**
      * Sets up local route store.
      */
     public void activate() {
         routeTables = new ConcurrentHashMap<>();
 
-        routeTables.put(IPV4, new RouteTable());
-        routeTables.put(IPV6, new RouteTable());
+        routeTables.put(IPV4, new RouteTable(IPV4));
+        routeTables.put(IPV6, new RouteTable(IPV6));
 
         log.info("Started");
     }
 
     /**
-     * Cleans up local route store. Currently nothing is done here.
+     * Cleans up local route store.
      */
     public void deactivate() {
         log.info("Stopped");
@@ -89,13 +84,7 @@
 
     @Override
     public void removeRoute(Route route) {
-        RouteTable table = getDefaultRouteTable(route);
-        table.remove(route);
-        Collection<Route> routes = table.getRoutesForNextHop(route.nextHop());
-
-        if (routes.isEmpty()) {
-            nextHops.remove(route.nextHop());
-        }
+        getDefaultRouteTable(route).remove(route);
     }
 
     @Override
@@ -104,12 +93,12 @@
     }
 
     @Override
-    public Collection<Route> getRoutes(RouteTableId table) {
+    public Collection<RouteSet> getRoutes(RouteTableId table) {
         RouteTable routeTable = routeTables.get(table);
-        if (routeTable == null) {
-            return Collections.emptySet();
+        if (routeTable != null) {
+            return routeTable.getRouteSets();
         }
-        return routeTable.getRoutes();
+        return null;
     }
 
     @Override
@@ -123,48 +112,30 @@
     }
 
     @Override
+    public RouteSet getRoutes(IpPrefix prefix) {
+        return getDefaultRouteTable(prefix.address()).getRoutes(prefix);
+    }
+
+    @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))) {
-            NextHopData oldNextHopData = nextHops.put(ip, nextHopData);
-
-            for (Route route : routes) {
-                if (oldNextHopData == null) {
-                    notifyDelegate(new RouteEvent(RouteEvent.Type.ROUTE_ADDED,
-                            new ResolvedRoute(route, nextHopData.mac(), nextHopData.location())));
-                } else {
-                    notifyDelegate(new RouteEvent(RouteEvent.Type.ROUTE_UPDATED,
-                            new ResolvedRoute(route, nextHopData.mac(), nextHopData.location()),
-                            new ResolvedRoute(route, oldNextHopData.mac(), oldNextHopData.location())));
-                }
-            }
-        }
+        // No longer needed
     }
 
     @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) {
-                notifyDelegate(new RouteEvent(RouteEvent.Type.ROUTE_REMOVED,
-                        new ResolvedRoute(route, nextHopData.mac(), nextHopData.location())));
-            }
-        }
+        // No longer needed
     }
 
     @Override
     public NextHopData getNextHop(IpAddress ip) {
-        return nextHops.get(ip);
+        // No longer needed
+        return null;
     }
 
     @Override
     public Map<IpAddress, NextHopData> getNextHops() {
-        return ImmutableMap.copyOf(nextHops);
+        // No longer needed
+        return Collections.emptyMap();
     }
 
     private RouteTable getDefaultRouteTable(Route route) {
@@ -181,15 +152,14 @@
      */
     private class RouteTable {
         private final InvertedRadixTree<Route> routeTable;
-
         private final Map<IpPrefix, Route> routes = new ConcurrentHashMap<>();
-        private final Multimap<IpAddress, Route> reverseIndex =
-                Multimaps.synchronizedMultimap(HashMultimap.create());
+        private final RouteTableId id;
 
         /**
          * Creates a new route table.
          */
-        public RouteTable() {
+        public RouteTable(RouteTableId id) {
+            this.id = checkNotNull(id);
             routeTable = new ConcurrentInvertedRadixTree<>(
                     new DefaultByteArrayNodeFactory());
         }
@@ -208,51 +178,10 @@
                     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
-
-                reverseIndex.put(route.nextHop(), route);
-
-                if (oldRoute != null) {
-                    reverseIndex.remove(oldRoute.nextHop(), oldRoute);
-
-                    if (reverseIndex.get(oldRoute.nextHop()).isEmpty()) {
-                        nextHops.remove(oldRoute.nextHop());
-                    }
-                }
-
-                NextHopData nextHopData = nextHops.get(route.nextHop());
-
-                if (oldRoute != null && !oldRoute.nextHop().equals(route.nextHop())) {
-                    // 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));
-                    // 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));
-                    }
-                    return;
-                }
-
-                if (nextHopData != null) {
-                    notifyDelegate(new RouteEvent(RouteEvent.Type.ROUTE_ADDED,
-                            new ResolvedRoute(route, nextHopData.mac(), nextHopData.location())));
-                }
+                notifyDelegate(new InternalRouteEvent(
+                        InternalRouteEvent.Type.ROUTE_ADDED, singletonRouteSet(route)));
             }
         }
 
@@ -267,14 +196,8 @@
                 routeTable.remove(createBinaryString(route.prefix()));
 
                 if (removed != null) {
-                    reverseIndex.remove(removed.nextHop(), removed);
-                    NextHopData oldNextHopData = getNextHop(removed.nextHop());
-                    // 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())));
-                    }
+                    notifyDelegate(new InternalRouteEvent(
+                            InternalRouteEvent.Type.ROUTE_REMOVED, emptyRouteSet(route.prefix())));
                 }
             }
         }
@@ -286,7 +209,24 @@
          * @return routes for the next hop
          */
         public Collection<Route> getRoutesForNextHop(IpAddress ip) {
-            return reverseIndex.get(ip);
+            return routes.values()
+                    .stream()
+                    .filter(route -> route.nextHop().equals(ip))
+                    .collect(Collectors.toSet());
+        }
+
+        public RouteSet getRoutes(IpPrefix prefix) {
+            Route route = routes.get(prefix);
+            if (route != null) {
+                return singletonRouteSet(route);
+            }
+            return null;
+        }
+
+        public Collection<RouteSet> getRouteSets() {
+            return routes.values().stream()
+                    .map(this::singletonRouteSet)
+                    .collect(Collectors.toSet());
         }
 
         /**
@@ -327,6 +267,14 @@
 
             return route;
         }
+
+        private RouteSet singletonRouteSet(Route route) {
+            return new RouteSet(id, route.prefix(), Collections.singleton(route));
+        }
+
+        private RouteSet emptyRouteSet(IpPrefix prefix) {
+            return new RouteSet(id, prefix, Collections.emptySet());
+        }
     }
 
 }
diff --git a/incubator/store/src/main/java/org/onosproject/incubator/store/routing/impl/RouteStoreImpl.java b/incubator/store/src/main/java/org/onosproject/incubator/store/routing/impl/RouteStoreImpl.java
index 747007e..f182489 100644
--- a/incubator/store/src/main/java/org/onosproject/incubator/store/routing/impl/RouteStoreImpl.java
+++ b/incubator/store/src/main/java/org/onosproject/incubator/store/routing/impl/RouteStoreImpl.java
@@ -24,11 +24,13 @@
 import org.apache.felix.scr.annotations.ReferenceCardinality;
 import org.apache.felix.scr.annotations.Service;
 import org.onlab.packet.IpAddress;
+import org.onlab.packet.IpPrefix;
 import org.onlab.util.Tools;
 import org.onosproject.cfg.ComponentConfigService;
+import org.onosproject.incubator.net.routing.InternalRouteEvent;
 import org.onosproject.incubator.net.routing.NextHopData;
 import org.onosproject.incubator.net.routing.Route;
-import org.onosproject.incubator.net.routing.RouteEvent;
+import org.onosproject.incubator.net.routing.RouteSet;
 import org.onosproject.incubator.net.routing.RouteStore;
 import org.onosproject.incubator.net.routing.RouteStoreDelegate;
 import org.onosproject.incubator.net.routing.RouteTableId;
@@ -52,7 +54,7 @@
  */
 @Service
 @Component
-public class RouteStoreImpl extends AbstractStore<RouteEvent, RouteStoreDelegate>
+public class RouteStoreImpl extends AbstractStore<InternalRouteEvent, RouteStoreDelegate>
         implements RouteStore {
 
     @Reference(cardinality = ReferenceCardinality.MANDATORY_UNARY)
@@ -155,7 +157,7 @@
     }
 
     @Override
-    public Collection<Route> getRoutes(RouteTableId table) {
+    public Collection<RouteSet> getRoutes(RouteTableId table) {
         return currentRouteStore.getRoutes(table);
     }
 
@@ -170,6 +172,11 @@
     }
 
     @Override
+    public RouteSet getRoutes(IpPrefix prefix) {
+        return currentRouteStore.getRoutes(prefix);
+    }
+
+    @Override
     public void updateNextHop(IpAddress ip, NextHopData nextHopData) {
         currentRouteStore.updateNextHop(ip, nextHopData);
     }
diff --git a/incubator/store/src/main/java/org/onosproject/incubator/store/routing/impl/RouteTable.java b/incubator/store/src/main/java/org/onosproject/incubator/store/routing/impl/RouteTable.java
new file mode 100644
index 0000000..4d27d71
--- /dev/null
+++ b/incubator/store/src/main/java/org/onosproject/incubator/store/routing/impl/RouteTable.java
@@ -0,0 +1,86 @@
+/*
+ * Copyright 2017-present Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.onosproject.incubator.store.routing.impl;
+
+import org.onlab.packet.IpAddress;
+import org.onlab.packet.IpPrefix;
+import org.onosproject.incubator.net.routing.Route;
+import org.onosproject.incubator.net.routing.RouteSet;
+import org.onosproject.incubator.net.routing.RouteTableId;
+
+import java.util.Collection;
+
+/**
+ * Represents a route table that stores routes.
+ */
+public interface RouteTable {
+
+    /**
+     * Adds a route to the route table.
+     *
+     * @param route route
+     */
+    void update(Route route);
+
+    /**
+     * Removes a route from the route table.
+     *
+     * @param route route
+     */
+    void remove(Route route);
+
+    /**
+     * Returns the route table ID.
+     *
+     * @return route table ID
+     */
+    RouteTableId id();
+
+    /**
+     * Returns all routes in the route table.
+     *
+     * @return collection of routes, grouped by prefix
+     */
+    Collection<RouteSet> getRoutes();
+
+    /**
+     * Returns the routes in this table pertaining to a given prefix.
+     *
+     * @param prefix IP prefix
+     * @return routes for the prefix
+     */
+    RouteSet getRoutes(IpPrefix prefix);
+
+    /**
+     * Returns all routes that have the given next hop.
+     *
+     * @param nextHop next hop IP address
+     * @return collection of routes
+     */
+    Collection<Route> getRoutesForNextHop(IpAddress nextHop);
+
+    /**
+     * Releases route table resources held locally.
+     */
+    void shutdown();
+
+    /**
+     * Releases route table resources across the entire cluster.
+     */
+    void destroy();
+
+}