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();
+
+}