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