Implemented PatriciaTrie.match and put an interface PTrie in BgpRoute. Minor bug fixes to Prefix and RibEntry
diff --git a/src/main/java/net/onrc/onos/ofcontroller/bgproute/BgpRoute.java b/src/main/java/net/onrc/onos/ofcontroller/bgproute/BgpRoute.java
index 827c8d2..c978d44 100644
--- a/src/main/java/net/onrc/onos/ofcontroller/bgproute/BgpRoute.java
+++ b/src/main/java/net/onrc/onos/ofcontroller/bgproute/BgpRoute.java
@@ -89,6 +89,7 @@
//protected static Ptree ptree;
protected IPatriciaTrie<RibEntry> ptree;
+ protected IPatriciaTrie<Interface> interfacePtrie;
protected BlockingQueue<RibUpdate> ribUpdates;
protected String bgpdRestIp;
@@ -219,6 +220,22 @@
log.error("Error reading JSON file", e);
System.exit(1);
}
+
+ //Populate the interface Patricia Trie
+ for (Interface intf : interfaces.values()) {
+ Prefix prefix = new Prefix(intf.getIpAddress().getAddress(), intf.getPrefixLength());
+ interfacePtrie.put(prefix, intf);
+ }
+
+ /*
+ Iterator<IPatriciaTrie.Entry<Interface>> it = interfacePtrie.iterator();
+ while (it.hasNext()) {
+ IPatriciaTrie.Entry<Interface> entry = it.next();
+ Interface intf = entry.getValue();
+ log.debug("Interface at prefix {}, switchport {}/{}",
+ new Object[] {entry.getPrefix(), HexString.toHexString(intf.getDpid()), intf.getPort()});
+ }
+ */
}
@Override
@@ -254,6 +271,7 @@
//ptree = new Ptree(32);
ptree = new PatriciaTrie<RibEntry>(32);
+ interfacePtrie = new PatriciaTrie<Interface>(32);
ribUpdates = new LinkedBlockingQueue<RibUpdate>();
diff --git a/src/main/java/net/onrc/onos/ofcontroller/bgproute/PatriciaTrie.java b/src/main/java/net/onrc/onos/ofcontroller/bgproute/PatriciaTrie.java
index 28093fc..89dfb30 100644
--- a/src/main/java/net/onrc/onos/ofcontroller/bgproute/PatriciaTrie.java
+++ b/src/main/java/net/onrc/onos/ofcontroller/bgproute/PatriciaTrie.java
@@ -101,8 +101,6 @@
/*exact match*/
@Override
public synchronized V lookup(Prefix prefix) {
- //TODO
-
if (prefix.getPrefixLength() > maxPrefixLength) {
return null;
}
@@ -135,7 +133,13 @@
@Override
public synchronized V match(Prefix prefix) {
//TODO
- return null;
+ if (prefix.getPrefixLength() > maxPrefixLength) {
+ return null;
+ }
+
+ Node closestNode = findClosestNode(prefix);
+
+ return closestNode == null ? null : closestNode.value;
}
@Override
@@ -226,6 +230,27 @@
return null;
}
+ private Node findClosestNode(Prefix prefix) {
+ Node node = top;
+ Node match = null;
+
+ while (node != null
+ && node.prefix.getPrefixLength() <= prefix.getPrefixLength()
+ && key_match(node.prefix.getAddress(), node.prefix.getPrefixLength(), prefix.getAddress(), prefix.getPrefixLength()) == true) {
+ if (!node.isAggregate()) {
+ match = node;
+ }
+
+ if (bit_check(prefix.getAddress(), node.prefix.getPrefixLength()) == true) {
+ node = node.right;
+ } else {
+ node = node.left;
+ }
+ }
+
+ return match;
+ }
+
/*
* Receives a 1-based bit index
* Returns a 1-based byte index
diff --git a/src/main/java/net/onrc/onos/ofcontroller/bgproute/Prefix.java b/src/main/java/net/onrc/onos/ofcontroller/bgproute/Prefix.java
index 21dd45c..05ce0a4 100644
--- a/src/main/java/net/onrc/onos/ofcontroller/bgproute/Prefix.java
+++ b/src/main/java/net/onrc/onos/ofcontroller/bgproute/Prefix.java
@@ -4,6 +4,8 @@
import java.net.UnknownHostException;
import java.util.Arrays;
+import com.google.common.net.InetAddresses;
+
public class Prefix {
private final int MAX_BYTES = 4;
@@ -31,11 +33,7 @@
public Prefix(String strAddress, int prefixLength) {
byte[] addr = null;
- try {
- addr = InetAddress.getByName(strAddress).getAddress();
- } catch (UnknownHostException e) {
- throw new IllegalArgumentException("Invalid IP inetAddress argument");
- }
+ addr = InetAddresses.forString(strAddress).getAddress();
if (addr == null || addr.length != MAX_BYTES ||
prefixLength < 0 || prefixLength > MAX_BYTES * Byte.SIZE) {
diff --git a/src/main/java/net/onrc/onos/ofcontroller/bgproute/RibEntry.java b/src/main/java/net/onrc/onos/ofcontroller/bgproute/RibEntry.java
index c27f962..8087471 100644
--- a/src/main/java/net/onrc/onos/ofcontroller/bgproute/RibEntry.java
+++ b/src/main/java/net/onrc/onos/ofcontroller/bgproute/RibEntry.java
@@ -1,7 +1,8 @@
package net.onrc.onos.ofcontroller.bgproute;
import java.net.InetAddress;
-import java.net.UnknownHostException;
+
+import com.google.common.net.InetAddresses;
public class RibEntry {
private InetAddress routerId;
@@ -13,12 +14,8 @@
}
public RibEntry(String routerId, String nextHop) {
- try {
- this.routerId = InetAddress.getByName(routerId);
- this.nextHop = InetAddress.getByName(nextHop);
- } catch (UnknownHostException e) {
- throw new IllegalArgumentException("Invalid address format");
- }
+ this.routerId = InetAddresses.forString(routerId);
+ this.nextHop = InetAddresses.forString(nextHop);
}
public InetAddress getNextHop() {