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() {
diff --git a/src/test/java/net/onrc/onos/ofcontroller/bgproute/PatriciaTrieTest.java b/src/test/java/net/onrc/onos/ofcontroller/bgproute/PatriciaTrieTest.java
index 29bb201..571d37d 100644
--- a/src/test/java/net/onrc/onos/ofcontroller/bgproute/PatriciaTrieTest.java
+++ b/src/test/java/net/onrc/onos/ofcontroller/bgproute/PatriciaTrieTest.java
@@ -4,7 +4,6 @@
import static org.junit.Assert.assertNotNull;
import static org.junit.Assert.assertNull;
import static org.junit.Assert.assertTrue;
-import static org.junit.Assert.fail;
import java.util.HashMap;
import java.util.Iterator;
@@ -12,7 +11,6 @@
import org.junit.After;
import org.junit.Before;
-import org.junit.Ignore;
import org.junit.Test;
public class PatriciaTrieTest {
@@ -107,10 +105,27 @@
assertTrue(retval.equals(r2));
}
- @Ignore
+ //@Ignore
@Test
public void testMatch() {
- fail("Not yet implemented");
+ Prefix p1 = new Prefix("192.168.10.30", 32);
+ Prefix p2 = new Prefix("192.168.10.30", 31);
+ Prefix p3 = new Prefix("192.168.8.241", 32);
+ Prefix p4 = new Prefix("1.0.0.0", 32);
+ Prefix p5 = new Prefix("192.168.8.0", 22);
+ Prefix p6 = new Prefix("192.168.8.0", 21);
+
+ assertTrue(ptrie.match(p1).equals(mappings.get(prefixes[0])));
+ assertTrue(ptrie.match(p2).equals(mappings.get(prefixes[0])));
+ assertTrue(ptrie.match(p3).equals(mappings.get(prefixes[1])));
+ assertNull(ptrie.match(p4));
+ assertTrue(ptrie.match(p5).equals(mappings.get(prefixes[2])));
+ //System.out.println(ptrie.match(p6).getNextHop().getHostAddress());
+ assertTrue(ptrie.match(p6).equals(mappings.get(prefixes[8])));
+
+
+ //TODO more extensive tests
+ //fail("Not yet implemented");
}
@Test
diff --git a/src/test/java/net/onrc/onos/ofcontroller/bgproute/PtreeTest.java b/src/test/java/net/onrc/onos/ofcontroller/bgproute/PtreeTest.java
index 6af9d30..5eabcc8 100644
--- a/src/test/java/net/onrc/onos/ofcontroller/bgproute/PtreeTest.java
+++ b/src/test/java/net/onrc/onos/ofcontroller/bgproute/PtreeTest.java
@@ -25,14 +25,14 @@
private Logger log = LoggerFactory.getLogger(PtreeTest.class);
private Ptree ptree;
- private PatriciaTrie ooptrie;
+ private PatriciaTrie<RibEntry> ooptrie;
private Map<String, byte[]> byteAddresses;
@Before
public void setUp() throws Exception {
ptree = new Ptree(32);
- ooptrie = new PatriciaTrie(32);
+ ooptrie = new PatriciaTrie<RibEntry>(32);
String[] strPrefixes = {
"192.168.10.0/24",
@@ -197,10 +197,10 @@
@Test
public void testIteration() {
- Iterator<IPatriciaTrie.Entry> it = ooptrie.iterator();
+ Iterator<IPatriciaTrie.Entry<RibEntry>> it = ooptrie.iterator();
while (it.hasNext()) {
- IPatriciaTrie.Entry entry = it.next();
+ IPatriciaTrie.Entry<RibEntry> entry = it.next();
log.debug("PatriciaTrie prefix {} \t {}", entry.getPrefix(), entry.getPrefix().printAsBits());
}