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