Replaced our old Patricia tree with Google's concurrent radix tree
This required some changes to the Prefix class to store a binary string
representation of the prefix to use as a key in the radix tree.
Also unrelated, bounds checking of the Prefix class has been improved and some
Prefix unit tests have been added.
Change-Id: I56f5b69346801ec70535ed470ae064b1fdf8cfdf
diff --git a/src/main/java/net/onrc/onos/apps/sdnip/ISdnIpService.java b/src/main/java/net/onrc/onos/apps/sdnip/ISdnIpService.java
index 21ee3d3..6189aa7 100644
--- a/src/main/java/net/onrc/onos/apps/sdnip/ISdnIpService.java
+++ b/src/main/java/net/onrc/onos/apps/sdnip/ISdnIpService.java
@@ -2,6 +2,8 @@
import net.floodlightcontroller.core.module.IFloodlightService;
+import com.googlecode.concurrenttrees.radix.RadixTree;
+
/**
* The API exported by the main SDN-IP class. This is the interface between the
* REST handlers and the SDN-IP module.
@@ -9,13 +11,14 @@
public interface ISdnIpService extends IFloodlightService {
/**
- * Gets a reference to SDN-IP's PATRICIA tree which stores the route table.
+ * Gets a reference to SDN-IP's radix tree which stores the route table
+ * learnt through BGP.
*
* XXX This is a poor API because it exposes internal state of SDN-IP.
*
- * @return the PATRICIA tree.
+ * @return the radix tree
*/
- public IPatriciaTree<RibEntry> getPtree();
+ public RadixTree<RibEntry> getPtree();
/**
* Gets the IP address of REST server on the BGPd side. This is used to
diff --git a/src/main/java/net/onrc/onos/apps/sdnip/Prefix.java b/src/main/java/net/onrc/onos/apps/sdnip/Prefix.java
index 91510b1..d4e730d 100644
--- a/src/main/java/net/onrc/onos/apps/sdnip/Prefix.java
+++ b/src/main/java/net/onrc/onos/apps/sdnip/Prefix.java
@@ -19,10 +19,18 @@
/**
* The length of addresses this class can represent prefixes of, in bytes.
*/
- public static final int ADDRESS_LENGTH = 4;
+ public static final int ADDRESS_LENGTH_BYTES = 4;
+
+ /**
+ * The length of addresses this class can represent prefixes of, in bits.
+ */
+ public static final int MAX_PREFIX_LENGTH = Byte.SIZE * ADDRESS_LENGTH_BYTES;
+
+ public static final int MIN_PREFIX_LENGTH = 0;
private final int prefixLength;
private final byte[] address;
+ private final String binaryString;
// For verifying the arguments and pretty printing
private final InetAddress inetAddress;
@@ -32,26 +40,28 @@
* a prefix length.
* <p/>
* The valid values for addr and prefixLength are bounded by
- * {@link #ADDRESS_LENGTH}.
+ * {@link #ADDRESS_LENGTH_BYTES}.
* <p/>
* A valid addr array satisfies
- * {@code addr.length == }{@value #ADDRESS_LENGTH}.
+ * {@code addr.length == }{@value #ADDRESS_LENGTH_BYTES}.
* <p/>
* A valid prefixLength satisfies
- * {@code (prefixLength > 0 && prefixLength <=} {@link Byte#SIZE}
- * {@code * }{@value #ADDRESS_LENGTH}{@code )}.
+ * {@code (prefixLength >= 0 && prefixLength <=} {@link Byte#SIZE}
+ * {@code * }{@value #ADDRESS_LENGTH_BYTES}{@code )}.
*
* @param addr a byte array representing the address
* @param prefixLength length of the prefix of the specified address
*/
public Prefix(byte[] addr, int prefixLength) {
- if (addr == null || addr.length != ADDRESS_LENGTH ||
- prefixLength < 0 || prefixLength > ADDRESS_LENGTH * Byte.SIZE) {
+ if (addr == null || addr.length != ADDRESS_LENGTH_BYTES ||
+ prefixLength < MIN_PREFIX_LENGTH ||
+ prefixLength > MAX_PREFIX_LENGTH) {
throw new IllegalArgumentException();
}
address = canonicalizeAddress(addr, prefixLength);
this.prefixLength = prefixLength;
+ binaryString = createBinaryString();
try {
inetAddress = InetAddress.getByAddress(address);
@@ -71,13 +81,15 @@
byte[] addr = null;
addr = InetAddresses.forString(strAddress).getAddress();
- if (addr == null || addr.length != ADDRESS_LENGTH ||
- prefixLength < 0 || prefixLength > ADDRESS_LENGTH * Byte.SIZE) {
+ if (addr == null || addr.length != ADDRESS_LENGTH_BYTES ||
+ prefixLength < MIN_PREFIX_LENGTH ||
+ prefixLength > MAX_PREFIX_LENGTH) {
throw new IllegalArgumentException();
}
address = canonicalizeAddress(addr, prefixLength);
this.prefixLength = prefixLength;
+ binaryString = createBinaryString();
try {
inetAddress = InetAddress.getByAddress(address);
@@ -86,12 +98,28 @@
}
}
+ /**
+ * This method takes a byte array passed in by the user and ensures it
+ * conforms to the format we want. The byte array can contain anything,
+ * but only some of the bits are significant. The bits after
+ * prefixLengthValue are not significant, and this method will zero them
+ * out in order to ensure there is a canonical representation for each
+ * prefix. This simplifies the equals and hashcode methods, because once we
+ * have a canonical byte array representation we can simply compare byte
+ * arrays to test equality.
+ *
+ * @param addressValue the byte array to canonicalize
+ * @param prefixLengthValue The length of the prefix. Bits up to and including
+ * prefixLength are significant, bits following prefixLength are not
+ * significant and will be zeroed out.
+ * @return the canonicalized representation of the prefix
+ */
private byte[] canonicalizeAddress(byte[] addressValue,
int prefixLengthValue) {
byte[] result = new byte[addressValue.length];
if (prefixLengthValue == 0) {
- for (int i = 0; i < ADDRESS_LENGTH; i++) {
+ for (int i = 0; i < ADDRESS_LENGTH_BYTES; i++) {
result[i] = 0;
}
@@ -102,7 +130,7 @@
//Set all bytes after the end of the prefix to 0
int lastByteIndex = (prefixLengthValue - 1) / Byte.SIZE;
- for (int i = lastByteIndex; i < ADDRESS_LENGTH; i++) {
+ for (int i = lastByteIndex; i < ADDRESS_LENGTH_BYTES; i++) {
result[i] = 0;
}
@@ -122,6 +150,31 @@
}
/**
+ * Creates the binary string representation of the prefix.
+ * The strings length is equal to prefixLength.
+ *
+ * @return the binary string representation
+ */
+ private String createBinaryString() {
+ if (prefixLength == 0) {
+ return "";
+ }
+
+ StringBuilder result = new StringBuilder(prefixLength);
+ for (int i = 0; i < address.length; i++) {
+ byte b = address[i];
+ for (int j = 0; j < Byte.SIZE; j++) {
+ byte mask = (byte) (0x80 >>> j);
+ result.append(((b & mask) == 0) ? "0" : "1");
+ if (i * Byte.SIZE + j == prefixLength - 1) {
+ return result.toString();
+ }
+ }
+ }
+ return result.toString();
+ }
+
+ /**
* Gets the length of the prefix of the address.
*
* @return the prefix length
@@ -165,6 +218,15 @@
}
/**
+ * Gets a binary string representation of the prefix.
+ *
+ * @return a binary string representation
+ */
+ public String toBinaryString() {
+ return binaryString;
+ }
+
+ /**
* Print the prefix to a String showing the bits of the address.
*
* @return the bit-string of the prefix
diff --git a/src/main/java/net/onrc/onos/apps/sdnip/SdnIp.java b/src/main/java/net/onrc/onos/apps/sdnip/SdnIp.java
index 3b56468..745e27b 100644
--- a/src/main/java/net/onrc/onos/apps/sdnip/SdnIp.java
+++ b/src/main/java/net/onrc/onos/apps/sdnip/SdnIp.java
@@ -6,6 +6,7 @@
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
+import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
@@ -29,6 +30,7 @@
import net.onrc.onos.apps.proxyarp.IArpRequester;
import net.onrc.onos.apps.proxyarp.IProxyArpService;
import net.onrc.onos.apps.sdnip.RibUpdate.Operation;
+import net.onrc.onos.apps.sdnip.web.SdnIpWebRoutable;
import net.onrc.onos.apps.sdnip.web.SdnIpWebRoutableNew;
import net.onrc.onos.core.intent.IntentOperation;
import net.onrc.onos.core.intent.IntentOperationList;
@@ -55,6 +57,7 @@
import net.onrc.onos.core.util.PortNumber;
import net.onrc.onos.core.util.SwitchPort;
import net.sf.json.JSONArray;
+import net.sf.json.JSONException;
import net.sf.json.JSONObject;
import net.sf.json.JSONSerializer;
@@ -78,6 +81,10 @@
import com.google.common.collect.SetMultimap;
import com.google.common.net.InetAddresses;
import com.google.common.util.concurrent.ThreadFactoryBuilder;
+import com.googlecode.concurrenttrees.radix.RadixTree;
+import com.googlecode.concurrenttrees.radix.node.concrete.DefaultByteArrayNodeFactory;
+import com.googlecode.concurrenttrees.radixinverted.ConcurrentInvertedRadixTree;
+import com.googlecode.concurrenttrees.radixinverted.InvertedRadixTree;
public class SdnIp implements IFloodlightModule, ISdnIpService,
IArpRequester,
@@ -90,8 +97,9 @@
private IRestApiService restApi;
private IProxyArpService proxyArp;
- private IPatriciaTree<RibEntry> ptree;
- private IPatriciaTree<Interface> interfacePtree;
+ private InvertedRadixTree<RibEntry> bgpRoutes;
+ private InvertedRadixTree<Interface> interfaceRoutes;
+
private BlockingQueue<RibUpdate> ribUpdates;
private String bgpdRestIp;
@@ -236,8 +244,9 @@
// Populate the interface Patricia Tree
for (Interface intf : interfaces.values()) {
- Prefix prefix = new Prefix(intf.getIpAddress().getAddress(), intf.getPrefixLength());
- interfacePtree.put(prefix, intf);
+ Prefix prefix = new Prefix(intf.getIpAddress().getAddress(),
+ intf.getPrefixLength());
+ interfaceRoutes.put(prefix.toBinaryString(), intf);
}
}
@@ -274,8 +283,10 @@
public void init(FloodlightModuleContext context)
throws FloodlightModuleException {
- ptree = new PatriciaTree<RibEntry>(32);
- interfacePtree = new PatriciaTree<Interface>(32);
+ bgpRoutes = new ConcurrentInvertedRadixTree<>(
+ new DefaultByteArrayNodeFactory());
+ interfaceRoutes = new ConcurrentInvertedRadixTree<>(
+ new DefaultByteArrayNodeFactory());
ribUpdates = new LinkedBlockingQueue<RibUpdate>();
@@ -335,7 +346,7 @@
@Override
public void startUp(FloodlightModuleContext context) {
- //restApi.addRestletRoutable(new SdnIpWebRoutable());
+ restApi.addRestletRoutable(new SdnIpWebRoutable());
restApi.addRestletRoutable(new SdnIpWebRoutableNew());
floodlightProvider.addOFSwitchListener(this);
@@ -344,13 +355,13 @@
}
@Override
- public IPatriciaTree<RibEntry> getPtree() {
- return ptree;
+ public RadixTree<RibEntry> getPtree() {
+ return bgpRoutes;
}
@Override
public void clearPtree() {
- ptree = new PatriciaTree<RibEntry>(32);
+ log.warn("Clear table operation not supported");
}
@Override
@@ -371,43 +382,48 @@
return;
}
- response = response.replaceAll("\"", "'");
- JSONObject jsonObj = (JSONObject) JSONSerializer.toJSON(response);
- JSONArray ribArray = jsonObj.getJSONArray("rib");
- String inboundRouterId = jsonObj.getString("router-id");
+ try {
+ response = response.replaceAll("\"", "'");
+ JSONObject jsonObj = (JSONObject) JSONSerializer.toJSON(response);
+ JSONArray ribArray = jsonObj.getJSONArray("rib");
+ String inboundRouterId = jsonObj.getString("router-id");
- int size = ribArray.size();
+ int size = ribArray.size();
- log.info("Retrived RIB of {} entries from BGPd", size);
+ log.info("Retrived RIB of {} entries from BGPd", size);
- for (int j = 0; j < size; j++) {
- JSONObject ribEntry = ribArray.getJSONObject(j);
- String prefix = ribEntry.getString("prefix");
- String nexthop = ribEntry.getString("nexthop");
+ for (int j = 0; j < size; j++) {
+ JSONObject ribEntry = ribArray.getJSONObject(j);
+ String prefix = ribEntry.getString("prefix");
+ String nexthop = ribEntry.getString("nexthop");
- // Insert each rib entry into the local rib
- String[] substring = prefix.split("/");
- String prefix1 = substring[0];
- String mask1 = substring[1];
+ // Insert each rib entry into the local rib
+ String[] substring = prefix.split("/");
+ String prefix1 = substring[0];
+ String mask1 = substring[1];
- Prefix p;
- try {
- p = new Prefix(prefix1, Integer.parseInt(mask1));
- } catch (NumberFormatException e) {
- log.warn("Wrong mask format in RIB JSON: {}", mask1);
- continue;
- } catch (IllegalArgumentException e1) {
- log.warn("Wrong prefix format in RIB JSON: {}", prefix1);
- continue;
+ Prefix p;
+ try {
+ p = new Prefix(prefix1, Integer.parseInt(mask1));
+ } catch (NumberFormatException e) {
+ log.warn("Wrong mask format in RIB JSON: {}", mask1);
+ continue;
+ } catch (IllegalArgumentException e1) {
+ log.warn("Wrong prefix format in RIB JSON: {}", prefix1);
+ continue;
+ }
+
+ RibEntry rib = new RibEntry(inboundRouterId, nexthop);
+
+ try {
+ ribUpdates.put(new RibUpdate(Operation.UPDATE, p, rib));
+ } catch (InterruptedException e) {
+ log.debug("Interrupted while pushing onto update queue");
+ }
}
-
- RibEntry rib = new RibEntry(inboundRouterId, nexthop);
-
- try {
- ribUpdates.put(new RibUpdate(Operation.UPDATE, p, rib));
- } catch (InterruptedException e) {
- log.debug("Interrupted while pushing onto update queue");
- }
+ } catch (JSONException e) {
+ // TODO don't parse JSON manually
+ log.error("Error parsing inital route table JSON:", e);
}
}
@@ -427,7 +443,7 @@
log.debug("Processing prefix add {}", prefix);
- RibEntry rib = ptree.put(prefix, update.getRibEntry());
+ RibEntry rib = bgpRoutes.put(prefix.toBinaryString(), update.getRibEntry());
if (rib != null && !rib.equals(update.getRibEntry())) {
// There was an existing nexthop for this prefix. This update supersedes that,
@@ -611,7 +627,10 @@
synchronized (this) {
Prefix prefix = update.getPrefix();
- if (ptree.remove(prefix, update.getRibEntry())) {
+ //if (ptree.remove(prefix, update.getRibEntry())) {
+ // TODO check the change of logic here - remove doesn't check that the
+ // rib entry was what we expected (and we can't do this concurrently)
+ if (bgpRoutes.remove(prefix.toBinaryString())) {
/*
* Only delete flows if an entry was actually removed from the tree.
* If no entry was removed, the <prefix, nexthop> wasn't there so
@@ -868,8 +887,8 @@
srcPort.dpid().value(), srcPort.port().value(), ShortestPathIntent.EMPTYMACADDRESS, srcIP,
dstPort.dpid().value(), dstPort.port().value(), ShortestPathIntent.EMPTYMACADDRESS, dstIP);
ShortestPathIntent bwdIntent = new ShortestPathIntent(bwdIntentId,
- srcPort.dpid().value(), srcPort.port().value(), ShortestPathIntent.EMPTYMACADDRESS, dstIP,
- dstPort.dpid().value(), dstPort.port().value(), ShortestPathIntent.EMPTYMACADDRESS, srcIP);
+ dstPort.dpid().value(), dstPort.port().value(), ShortestPathIntent.EMPTYMACADDRESS, dstIP,
+ srcPort.dpid().value(), srcPort.port().value(), ShortestPathIntent.EMPTYMACADDRESS, srcIP);
IntentOperation.Operator operator = IntentOperation.Operator.ADD;
operations.add(operator, fwdIntent);
operations.add(operator, bwdIntent);
@@ -1118,7 +1137,8 @@
for (RibUpdate update : prefixesToPush) {
// These will always be adds
- RibEntry rib = ptree.lookup(update.getPrefix());
+ RibEntry rib = bgpRoutes.getValueForExactKey(
+ update.getPrefix().toBinaryString());
if (rib != null && rib.equals(update.getRibEntry())) {
log.debug("Pushing prefix {} next hop {}", update.getPrefix(),
rib.getNextHop().getHostAddress());
@@ -1352,7 +1372,8 @@
private boolean validateUpdate(RibUpdate update) {
RibEntry newEntry = update.getRibEntry();
- RibEntry oldEntry = ptree.lookup(update.getPrefix());
+ RibEntry oldEntry = bgpRoutes.getValueForExactKey(
+ update.getPrefix().toBinaryString());
//If there is no existing entry we must assume this is the most recent
//update. However this might not always be the case as we might have a
@@ -1376,6 +1397,21 @@
newEntry.getSequenceNum() > oldEntry.getSequenceNum();
}
+ private Interface longestInterfacePrefixMatch(InetAddress address) {
+ Prefix prefixToSearchFor = new Prefix(address.getAddress(),
+ Prefix.MAX_PREFIX_LENGTH);
+ Iterator<Interface> it =
+ interfaceRoutes.getValuesForKeysPrefixing(
+ prefixToSearchFor.toBinaryString()).iterator();
+ Interface intf = null;
+ // Find the last prefix, which will be the longest prefix
+ while (it.hasNext()) {
+ intf = it.next();
+ }
+
+ return intf;
+ }
+
// The code below should be reimplemented after removal of Floodlight's
// ITopologyService API. It should be implemented on top of network graph
// notifications. (It was pretty hacky anyway...)
@@ -1430,7 +1466,7 @@
@Override
public String getName() {
- return "SdnIp";
+ return "sdnip";
}
/*
@@ -1439,13 +1475,13 @@
@Override
public boolean isInterfaceAddress(InetAddress address) {
- Interface intf = interfacePtree.match(new Prefix(address.getAddress(), 32));
+ Interface intf = longestInterfacePrefixMatch(address);
return (intf != null && intf.getIpAddress().equals(address));
}
@Override
public boolean inConnectedNetwork(InetAddress address) {
- Interface intf = interfacePtree.match(new Prefix(address.getAddress(), 32));
+ Interface intf = longestInterfacePrefixMatch(address);
return (intf != null && !intf.getIpAddress().equals(address));
}
@@ -1461,7 +1497,7 @@
@Override
public Interface getOutgoingInterface(InetAddress dstIpAddress) {
- return interfacePtree.match(new Prefix(dstIpAddress.getAddress(), 32));
+ return longestInterfacePrefixMatch(dstIpAddress);
}
@Override
diff --git a/src/main/java/net/onrc/onos/apps/sdnip/web/IncomingRequestResource.java b/src/main/java/net/onrc/onos/apps/sdnip/web/IncomingRequestResource.java
index 690ec4d..5a35bb4 100644
--- a/src/main/java/net/onrc/onos/apps/sdnip/web/IncomingRequestResource.java
+++ b/src/main/java/net/onrc/onos/apps/sdnip/web/IncomingRequestResource.java
@@ -3,7 +3,6 @@
import java.util.Iterator;
import net.onrc.onos.apps.sdnip.ISdnIpService;
-import net.onrc.onos.apps.sdnip.IPatriciaTree;
import net.onrc.onos.apps.sdnip.Prefix;
import net.onrc.onos.apps.sdnip.RestClient;
import net.onrc.onos.apps.sdnip.RibEntry;
@@ -17,6 +16,9 @@
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
+import com.googlecode.concurrenttrees.common.KeyValuePair;
+import com.googlecode.concurrenttrees.radix.RadixTree;
+
/**
* REST resource that handles REST calls from BGPd. This is the interface BGPd
* uses to push RIB entries (routes) to SDN-IP.
@@ -38,27 +40,26 @@
get(ISdnIpService.class.getCanonicalName());
if (dest == null) {
- IPatriciaTree<RibEntry> ptree = sdnIp.getPtree();
+ RadixTree<RibEntry> radixTree = sdnIp.getPtree();
output.append("{\n \"rib\": [\n");
boolean printed = false;
- synchronized (ptree) {
- Iterator<IPatriciaTree.Entry<RibEntry>> it = ptree.iterator();
- while (it.hasNext()) {
- IPatriciaTree.Entry<RibEntry> entry = it.next();
+ Iterator<KeyValuePair<RibEntry>> it =
+ radixTree.getKeyValuePairsForKeysStartingWith("").iterator();
+ while (it.hasNext()) {
+ KeyValuePair<RibEntry> entry = it.next();
- if (printed) {
- output.append(",\n");
- }
-
- output.append(" {\"prefix\": \"");
- output.append(entry.getPrefix());
- output.append("\", \"nexthop\": \"");
- output.append(entry.getValue().getNextHop().getHostAddress());
- output.append("\"}");
-
- printed = true;
+ if (printed) {
+ output.append(",\n");
}
+
+ output.append(" {\"prefix\": \"");
+ output.append(entry.getKey());
+ output.append("\", \"nexthop\": \"");
+ output.append(entry.getValue().getNextHop().getHostAddress());
+ output.append("\"}");
+
+ printed = true;
}
output.append("\n ]\n}\n");
diff --git a/src/main/java/net/onrc/onos/apps/sdnip/web/SdnIpWebRoutableNew.java b/src/main/java/net/onrc/onos/apps/sdnip/web/SdnIpWebRoutableNew.java
index 250b4da..5b6928a 100644
--- a/src/main/java/net/onrc/onos/apps/sdnip/web/SdnIpWebRoutableNew.java
+++ b/src/main/java/net/onrc/onos/apps/sdnip/web/SdnIpWebRoutableNew.java
@@ -21,6 +21,6 @@
@Override
public String basePath() {
- return "/wm/bgpNew";
+ return "/wm/sdnip";
}
}