Implementation of the route service
Change-Id: I4e905cf868ad69c426e4f4155dfd83e1f8b00335
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
new file mode 100644
index 0000000..ad60577
--- /dev/null
+++ b/incubator/store/src/main/java/org/onosproject/incubator/store/routing/impl/LocalRouteStore.java
@@ -0,0 +1,250 @@
+/*
+ * Copyright 2016 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 com.google.common.collect.HashMultimap;
+import com.google.common.collect.Multimap;
+import com.google.common.collect.Multimaps;
+import com.googlecode.concurrenttrees.radix.node.concrete.DefaultByteArrayNodeFactory;
+import com.googlecode.concurrenttrees.radixinverted.ConcurrentInvertedRadixTree;
+import com.googlecode.concurrenttrees.radixinverted.InvertedRadixTree;
+import org.apache.felix.scr.annotations.Activate;
+import org.apache.felix.scr.annotations.Component;
+import org.apache.felix.scr.annotations.Service;
+import org.onlab.packet.IpAddress;
+import org.onlab.packet.IpPrefix;
+import org.onlab.packet.MacAddress;
+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.RouteStore;
+import org.onosproject.incubator.net.routing.RouteStoreDelegate;
+import org.onosproject.incubator.net.routing.RouteTableId;
+import org.onosproject.store.AbstractStore;
+
+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;
+
+/**
+ * Route store based on in-memory storage.
+ */
+@Service
+@Component
+public class LocalRouteStore extends AbstractStore<RouteEvent, RouteStoreDelegate>
+ implements RouteStore {
+
+ private Map<RouteTableId, RouteTable> routeTables;
+ private static final RouteTableId IPV4 = new RouteTableId("ipv4");
+ private static final RouteTableId IPV6 = new RouteTableId("ipv6");
+
+ private Map<IpAddress, MacAddress> nextHops = new ConcurrentHashMap<>();
+
+ @Activate
+ protected void activate() {
+ routeTables = new ConcurrentHashMap<>();
+
+ routeTables.put(IPV4, new RouteTable());
+ routeTables.put(IPV6, new RouteTable());
+ }
+
+ @Override
+ public void updateRoute(Route route) {
+ getDefaultRouteTable(route).update(route);
+ }
+
+ @Override
+ public void removeRoute(Route route) {
+ RouteTable table = getDefaultRouteTable(route);
+ table.remove(route);
+ if (table.getRoutesForNextHop(route.nextHop()).isEmpty()) {
+ nextHops.remove(route.nextHop());
+ }
+ }
+
+ @Override
+ public Set<RouteTableId> getRouteTables() {
+ return routeTables.keySet();
+ }
+
+ @Override
+ public Collection<Route> getRoutes(RouteTableId table) {
+ RouteTable routeTable = routeTables.get(table);
+ if (routeTable == null) {
+ return Collections.emptySet();
+ }
+ return routeTable.getRoutes();
+ }
+
+ @Override
+ public Route longestPrefixMatch(IpAddress ip) {
+ return getDefaultRouteTable(ip).longestPrefixMatch(ip);
+ }
+
+ @Override
+ public void updateNextHop(IpAddress ip, MacAddress mac) {
+ Collection<Route> routes = getDefaultRouteTable(ip).getRoutesForNextHop(ip);
+ if (!routes.isEmpty() && !mac.equals(nextHops.get(ip))) {
+ nextHops.put(ip, mac);
+
+ for (Route route : routes) {
+ notifyDelegate(new RouteEvent(RouteEvent.Type.ROUTE_UPDATED, new ResolvedRoute(route, mac)));
+ }
+ }
+ }
+
+ @Override
+ public void removeNextHop(IpAddress ip, MacAddress mac) {
+ if (nextHops.remove(ip, mac)) {
+ Collection<Route> routes = getDefaultRouteTable(ip).getRoutesForNextHop(ip);
+ for (Route route : routes) {
+ notifyDelegate(new RouteEvent(RouteEvent.Type.ROUTE_REMOVED, new ResolvedRoute(route, null)));
+ }
+ }
+ }
+
+ @Override
+ public MacAddress getNextHop(IpAddress ip) {
+ return nextHops.get(ip);
+ }
+
+ private RouteTable getDefaultRouteTable(Route route) {
+ return getDefaultRouteTable(route.prefix().address());
+ }
+
+ private RouteTable getDefaultRouteTable(IpAddress ip) {
+ RouteTableId routeTableId = (ip.isIp4()) ? IPV4 : IPV6;
+ return routeTables.get(routeTableId);
+ }
+
+ private static String createBinaryString(IpPrefix ipPrefix) {
+ byte[] octets = ipPrefix.address().toOctets();
+ StringBuilder result = new StringBuilder(ipPrefix.prefixLength());
+ result.append("0");
+ for (int i = 0; i < ipPrefix.prefixLength(); i++) {
+ int byteOffset = i / Byte.SIZE;
+ int bitOffset = i % Byte.SIZE;
+ int mask = 1 << (Byte.SIZE - 1 - bitOffset);
+ byte value = octets[byteOffset];
+ boolean isSet = ((value & mask) != 0);
+ result.append(isSet ? "1" : "0");
+ }
+
+ return result.toString();
+ }
+
+ /**
+ * Route table into which routes can be placed.
+ */
+ 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());
+
+ /**
+ * 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 void update(Route route) {
+ synchronized (this) {
+ Route oldRoute = routes.put(route.prefix(), route);
+ routeTable.put(createBinaryString(route.prefix()), route);
+
+ // TODO manage routes from multiple providers
+ reverseIndex.remove(route.nextHop(), oldRoute);
+ reverseIndex.put(route.nextHop(), route);
+
+ if (oldRoute != null && !oldRoute.nextHop().equals(route.nextHop())) {
+ // Remove old route because new one is different
+ // TODO ROUTE_UPDATED?
+ notifyDelegate(new RouteEvent(RouteEvent.Type.ROUTE_REMOVED, new ResolvedRoute(oldRoute, null)));
+ }
+ }
+ }
+
+ /**
+ * Removes the route from the route table.
+ *
+ * @param route route to remove
+ */
+ public void remove(Route route) {
+ synchronized (this) {
+ Route removed = routes.remove(route.prefix());
+ routeTable.remove(createBinaryString(route.prefix()));
+ reverseIndex.remove(route.nextHop(), route);
+
+ if (removed != null) {
+ notifyDelegate(new RouteEvent(RouteEvent.Type.ROUTE_REMOVED, new ResolvedRoute(route, null)));
+ }
+ }
+ }
+
+ /**
+ * Returns the routes pointing to a particular next hop.
+ *
+ * @param ip next hop IP address
+ * @return routes for the next hop
+ */
+ public Collection<Route> getRoutesForNextHop(IpAddress ip) {
+ return reverseIndex.get(ip);
+ }
+
+ /**
+ * Returns all routes in the route table.
+ *
+ * @return all routes
+ */
+ public Collection<Route> getRoutes() {
+ return routes.values();
+ }
+
+ /**
+ * 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 Route longestPrefixMatch(IpAddress ip) {
+ Iterable<Route> prefixes =
+ routeTable.getValuesForKeysPrefixing(createBinaryString(ip.toIpPrefix()));
+
+ Iterator<Route> it = prefixes.iterator();
+
+ Route route = null;
+ while (it.hasNext()) {
+ route = it.next();
+ }
+
+ return route;
+ }
+ }
+
+}