Merge pull request #420 from pberde/master
Move GraphPublisher to up in the order of listeners
diff --git a/README.md b/README.md
index 70683fb..08878d4 100644
--- a/README.md
+++ b/README.md
@@ -1,9 +1,11 @@
ONOS (Open Networking Operating System)
=======================================
-ONOS (Open Networking Operating System) is an experimental distributed SDN OS. ONOS is under development. ONOS was announced and demonstrated at ONS'13.
+ONOS (Open Networking Operating System) is an experimental distributed
+SDN OS. Currently, it is under active development. ONOS was announced
+and demonstrated at ONS'13.
-Steps to download and setup development VM
+Steps to download and setup a development Virtual Machine
==========================================
http://wiki.onlab.us/display/Eng/ONOS+Development+VM
@@ -11,84 +13,105 @@
Building ONOS
-------------
-0. Install custom jars and dependencies (Only need to be run only once)
+0. Install custom jars and dependencies (needs to be run only once)
$ ./setup-local-maven.sh
-1. Cleanly Build ONOS
+1. Cleanly build ONOS
$ mvn clean
$ mvn compile
- NOTE: installing maven for the first time may switch java version from 1.7 to 1.6 causing cassandra to not run
+ NOTE: installing maven for the first time may switch java version
+ from 1.7 to 1.6. This might prevent Cassandra to run.
Dependencies
------------
1. Zookeeper
- Download and install apache-zookeeper-3.4.5: http://zookeeper.apache.org/releases.html
+ Download and install apache-zookeeper-3.4.5:
+ http://zookeeper.apache.org/releases.html
+
+ Edit file (ONOS-INSTALL-DIR)/start-zk.sh and set variable "ZK_DIR"
+ to point to the Zookeeper directory.
+
2. Cassandra
- Download and install apache-cassandra-1.2.2: http://cassandra.apache.org/download/
+ Download and install apache-cassandra-1.2.4:
+ http://cassandra.apache.org/download/
+
+ Edit file (ONOS-INSTALL-DIR)/start-cassandra.sh and set variable
+ "CASSANDRA_DIR" to point to the Cassandra directory.
Running ONOS
------------
-1. Start zookeeper
+1. Start Zookeeper
$ cd (ONOS-INSTALL-DIR)/
+ $ ./start-zk.sh start
- $ ./start-zk.sh
+ ## Confirm Zookeeper is running:
+ $ ./start.zk.sh status
-2. Start cassandra
+2. Start Cassandra
$ cd (ONOS-INSTALL-DIR)/
-
$ ./start-cassandra.sh start
- 1. Confirm cassandra is running
-
- $ ./start-cassandra.sh status
+ ## Confirm Cassandra is running:
+ $ ./start-cassandra.sh status
-3. Start ONOS instance
+3. Start ONOS
$ cd (ONOS-INSTALL-DIR)/
-
$ ./start-onos.sh start
-
-4. Start ONOS rest apis
+ ## Confirm ONOS is running:
+ $ ./start-onos.sh status
+
+4. Start ONOS REST API server
+
+ $ cd (ONOS-INSTALL-DIR)/
$ ./start-rest.sh start
+ ## Confirm the REST API server is running:
+ $ ./start-rest.sh status
+
Running ONOS with Cassandra embedded (Optional)
-----------------------------------------------
1. Start Zookeeper
$ cd (ONOS-INSTALL-DIR)/
+ $ ./start-zk.sh start
- $ ./zkServer.sh start
+ ## Confirm Zookeeper is running:
+ $ ./start.zk.sh status
2. Start ONOS and Cassandra embedded
$ cd (ONOS-INSTALL_DIR)/
-
$ ./start-onos-embedded.sh start
-
-3. Start ONOS rest apis
+ ## Confirm ONOS is running:
+ $ ./start-onos-embedded.sh status
+
+3. Start ONOS REST API server
+
+ $ cd (ONOS-INSTALL-DIR)/
$ ./start-rest.sh start
+ ## Confirm the REST API server is running:
+ $ ./start-rest.sh status
+
Running in offline mode (Optional)
----------------------------------
-Maven is used to build and run ONOS.
-By default, maven tries to reach the repositories.
-To suppress this behavior '-o' option should be given to `mvn` command.
-
-To give additional option to `mvn` commands used in ONOS,
-use the MVN environment variable.
+Maven is used to build and run ONOS. By default, maven tries to reach
+the repositories. The '-o' option can be given to the 'mvn' command to
+suppress this behavior. The MVN environmental variable can be used to
+set additional options to the 'mvn' command used in ONOS.
* Example: Running in offline mode
$ env MVN="mvn -o" ./start-onos.sh start
-
diff --git a/pom.xml b/pom.xml
index 4899f34..133e294 100644
--- a/pom.xml
+++ b/pom.xml
@@ -80,8 +80,6 @@
<exclude>**/*TestCase.java</exclude>
-->
</excludes>
- <argLine>-XX:MaxPermSize=512m</argLine>
- <reuseFork>false</reuseFork>
</configuration>
</plugin>
<!-- exec:java -->
@@ -186,11 +184,6 @@
<locale>en</locale>
</configuration>
</plugin>
- <plugin>
- <groupId>org.codehaus.mojo</groupId>
- <artifactId>cobertura-maven-plugin</artifactId>
- <version>2.5.2</version>
- </plugin>
</plugins>
</reporting>
<dependencies>
@@ -386,4 +379,4 @@
</dependency>
-->
</dependencies>
-</project>
+</project>
\ No newline at end of file
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 9936cb7..c36d4a5 100644
--- a/src/main/java/net/onrc/onos/ofcontroller/bgproute/BgpRoute.java
+++ b/src/main/java/net/onrc/onos/ofcontroller/bgproute/BgpRoute.java
@@ -3,7 +3,6 @@
import java.io.File;
import java.io.IOException;
import java.net.InetAddress;
-import java.net.UnknownHostException;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
@@ -88,7 +87,8 @@
protected ProxyArpManager proxyArp;
- protected static Ptree ptree;
+ //protected static Ptree ptree;
+ protected IPatriciaTrie ptree;
protected BlockingQueue<RibUpdate> ribUpdates;
protected String bgpdRestIp;
@@ -129,6 +129,8 @@
protected SetMultimap<InetAddress, RibUpdate> prefixesWaitingOnArp;
protected SetMultimap<InetAddress, PathUpdate> pathsWaitingOnArp;
+ protected ExecutorService bgpUpdatesExecutor;
+
protected Multimap<Prefix, PushedFlowMod> pushedFlows;
private class PushedFlowMod {
@@ -250,7 +252,8 @@
public void init(FloodlightModuleContext context)
throws FloodlightModuleException {
- ptree = new Ptree(32);
+ //ptree = new Ptree(32);
+ ptree = new PatriciaTrie(32);
ribUpdates = new LinkedBlockingQueue<RibUpdate>();
@@ -277,6 +280,9 @@
pushedFlows = HashMultimap.<Prefix, PushedFlowMod>create();
+ bgpUpdatesExecutor = Executors.newSingleThreadExecutor(
+ new ThreadFactoryBuilder().setNameFormat("bgp-updates-%d").build());
+
//Read in config values
bgpdRestIp = context.getConfigParams(this).get("BgpdRestIp");
if (bgpdRestIp == null){
@@ -307,13 +313,15 @@
//test();
}
- public Ptree getPtree() {
+ //public Ptree getPtree() {
+ public IPatriciaTrie getPtree() {
return ptree;
}
public void clearPtree() {
//ptree = null;
- ptree = new Ptree(32);
+ //ptree = new Ptree(32);
+ ptree = new PatriciaTrie(32);
}
public String getBGPdRestIp() {
@@ -325,7 +333,8 @@
}
// Return nexthop address as byte array.
- public Rib lookupRib(byte[] dest) {
+ /*
+ public RibEntry lookupRib(byte[] dest) {
if (ptree == null) {
log.debug("lookupRib: ptree null");
return null;
@@ -346,7 +355,9 @@
return node.rib;
}
+ */
+ /*
//TODO looks like this should be a unit test
@SuppressWarnings("unused")
private void test() throws UnknownHostException {
@@ -403,8 +414,10 @@
}
}
+ */
//TODO once the Ptree is object oriented this can go
+ /*
private String getPrefixFromPtree(PtreeNode node){
InetAddress address = null;
try {
@@ -416,6 +429,7 @@
}
return address.toString() + "/" + node.rib.masklen;
}
+ */
private void retrieveRib(){
String url = "http://" + bgpdRestIp + "/wm/bgp/" + routerId;
@@ -450,56 +464,74 @@
} catch (NumberFormatException e) {
log.warn("Wrong mask format in RIB JSON: {}", mask1);
continue;
- } catch (UnknownHostException e1) {
+ } catch (IllegalArgumentException e1) {
log.warn("Wrong prefix format in RIB JSON: {}", prefix1);
continue;
}
- PtreeNode node = ptree.acquire(p.getAddress(), p.getPrefixLength());
- Rib rib = new Rib(router_id, nexthop, p.getPrefixLength());
+ //PtreeNode node = ptree.acquire(p.getAddress(), p.getPrefixLength());
+ RibEntry rib = new RibEntry(router_id, nexthop);
+ /*
if (node.rib != null) {
node.rib = null;
ptree.delReference(node);
}
node.rib = rib;
+ */
- addPrefixFlows(p, rib);
+ //ptree.put(p, rib);
+
+ //addPrefixFlows(p, rib);
+ try {
+ ribUpdates.put(new RibUpdate(Operation.UPDATE, p, rib));
+ } catch (InterruptedException e) {
+ log.debug("Interrupted while pushing onto update queue");
+ }
}
}
@Override
public void newRibUpdate(RibUpdate update) {
- ribUpdates.add(update);
+ try {
+ ribUpdates.put(update);
+ } catch (InterruptedException e) {
+ // TODO Auto-generated catch block
+ log.debug(" ", e);
+ }
}
- public void processRibAdd(RibUpdate update) {
+ public synchronized void processRibAdd(RibUpdate update) {
Prefix prefix = update.getPrefix();
- PtreeNode node = ptree.acquire(prefix.getAddress(), prefix.getPrefixLength());
+ log.debug("Processing prefix add {}", prefix);
- if (node.rib != null) {
+ //PtreeNode node = ptree.acquire(prefix.getAddress(), prefix.getPrefixLength());
+ RibEntry rib = ptree.put(prefix, update.getRibEntry());
+
+ //if (node.rib != null) {
+ if (rib != null && !rib.equals(update.getRibEntry())) {
//There was an existing nexthop for this prefix. This update supersedes that,
//so we need to remove the old flows for this prefix from the switches
deletePrefixFlows(prefix);
//Then remove the old nexthop from the Ptree
- node.rib = null;
- ptree.delReference(node);
+ //node.rib = null;
+ //ptree.delReference(node);
}
//Put the new nexthop in the Ptree
- node.rib = update.getRibEntry();
+ //node.rib = update.getRibEntry();
//Push flows for the new <prefix, nexthop>
addPrefixFlows(prefix, update.getRibEntry());
}
- public void processRibDelete(RibUpdate update) {
+ public synchronized void processRibDelete(RibUpdate update) {
Prefix prefix = update.getPrefix();
- PtreeNode node = ptree.lookup(prefix.getAddress(), prefix.getPrefixLength());
+ //PtreeNode node = ptree.lookup(prefix.getAddress(), prefix.getPrefixLength());
/*
* Remove the flows from the switches before the rib is lost
@@ -510,6 +542,7 @@
* rib is an actual prefix in the Ptree.
*/
+ /*
if (node != null && node.rib != null) {
if (update.getRibEntry().equals(node.rib)) {
node.rib = null;
@@ -518,21 +551,31 @@
deletePrefixFlows(update.getPrefix());
}
}
+ */
+
+ if (ptree.remove(prefix, update.getRibEntry())) {
+ /*
+ * Only delete flows if an entry was actually removed from the trie.
+ * If no entry was removed, the <prefix, nexthop> wasn't there so
+ * it's probably already been removed and we don't need to do anything
+ */
+ deletePrefixFlows(prefix);
+ }
}
//TODO compatibility layer, used by beginRouting()
- public void prefixAdded(PtreeNode node) {
+ /*public void prefixAdded(PtreeNode node) {
Prefix prefix = null;
try {
prefix = new Prefix(node.key, node.rib.masklen);
- } catch (UnknownHostException e) {
+ } catch (IllegalArgumentException e) {
log.error(" ", e);
}
addPrefixFlows(prefix, node.rib);
- }
+ }*/
- private void addPrefixFlows(Prefix prefix, Rib rib) {
+ private void addPrefixFlows(Prefix prefix, RibEntry rib) {
if (!topologyReady){
return;
}
@@ -542,16 +585,15 @@
//I think we'll have to make prefixAdded and prefixDelete atomic as well
//to protect against the prefix getting deleted while where trying to add it
- log.debug("New prefix {} added, next hop {}, routerId {}",
- new Object[] {prefix, rib.nextHop.getHostAddress(),
- rib.routerId.getHostAddress()});
+ log.debug("New prefix {} added, next hop {}",
+ prefix, rib.getNextHop().getHostAddress());
//TODO this is wrong, we shouldn't be dealing with BGP peers here.
//We need to figure out where the device is attached and what its
//mac address is by learning.
//The next hop is not necessarily the peer, and the peer's attachment
//point is not necessarily the next hop's attachment point.
- BgpPeer peer = bgpPeers.get(rib.nextHop);
+ BgpPeer peer = bgpPeers.get(rib.getNextHop());
if (peer == null){
//TODO local router isn't in peers list so this will get thrown
@@ -560,7 +602,7 @@
//The other scenario is this is a route server route. In that
//case the next hop is not in our configuration
log.error("Couldn't find next hop router in router {} in config",
- rib.nextHop.getHostAddress());
+ rib.getNextHop().getHostAddress());
return; //just quit out here? This is probably a configuration error
}
@@ -614,6 +656,7 @@
match.setDataLayerType(Ethernet.TYPE_IPv4);
match.setWildcards(match.getWildcards() & ~OFMatch.OFPFW_DL_TYPE);
+ /*
InetAddress address = null;
try {
address = InetAddress.getByAddress(prefix.getAddress());
@@ -621,10 +664,11 @@
//Should never happen is the reverse conversion has already been done
log.error("Malformed IP address");
return;
- }
+ }*/
- match.setFromCIDR(address.getHostAddress() + "/" +
- prefix.getPrefixLength(), OFMatch.STR_NW_DST);
+ //match.setFromCIDR(address.getHostAddress() + "/" +
+ // prefix.getPrefixLength(), OFMatch.STR_NW_DST);
+ match.setFromCIDR(prefix.toString(), OFMatch.STR_NW_DST);
fm.setMatch(match);
//Set up MAC rewrite action
@@ -857,12 +901,11 @@
//Forward = gateway -> bgpd, reverse = bgpd -> gateway
OFMatch forwardMatchSrc = new OFMatch();
-
String interfaceCidrAddress = peerInterface.getIpAddress().getHostAddress()
+ "/32";
String peerCidrAddress = bgpPeer.getIpAddress().getHostAddress()
+ "/32";
-
+
//Common match fields
forwardMatchSrc.setDataLayerType(Ethernet.TYPE_IPv4);
//forwardMatch.setWildcards(forwardMatch.getWildcards() & ~OFMatch.OFPFW_DL_TYPE);
@@ -896,14 +939,27 @@
fm.setMatch(forwardMatchSrc);
+ OFMatch forwardIcmpMatch = new OFMatch();
+ forwardIcmpMatch.setDataLayerType(Ethernet.TYPE_IPv4);
+ forwardIcmpMatch.setNetworkProtocol(IPv4.PROTOCOL_ICMP);
+ forwardIcmpMatch.setWildcards(forwardIcmpMatch.getWildcards() &
+ ~OFMatch.OFPFW_DL_TYPE & ~OFMatch.OFPFW_NW_PROTO);
+
+ OFMatch reverseIcmpMatch = forwardIcmpMatch.clone();
+ forwardIcmpMatch.setFromCIDR(interfaceCidrAddress, OFMatch.STR_NW_DST);
+ reverseIcmpMatch.setFromCIDR(interfaceCidrAddress, OFMatch.STR_NW_SRC);
+
for (FlowEntry flowEntry : path.flowEntries()){
OFFlowMod forwardFlowModSrc, forwardFlowModDst;
OFFlowMod reverseFlowModSrc, reverseFlowModDst;
+ OFFlowMod forwardIcmp, reverseIcmp;
try {
forwardFlowModSrc = fm.clone();
forwardFlowModDst = fm.clone();
reverseFlowModSrc = fm.clone();
reverseFlowModDst = fm.clone();
+ forwardIcmp = fm.clone();
+ reverseIcmp = fm.clone();
} catch (CloneNotSupportedException e) {
log.warn("Clone failed", e);
continue;
@@ -929,14 +985,29 @@
((OFActionOutput)reverseFlowModDst.getActions().get(0))
.setPort(flowEntry.inPort().value());
+ ((OFActionOutput)forwardIcmp.getActions().get(0))
+ .setPort(flowEntry.outPort().value());
+ forwardIcmp.setMatch(forwardIcmpMatch);
+
+ ((OFActionOutput)reverseIcmp.getActions().get(0))
+ .setPort(flowEntry.inPort().value());
+ reverseIcmp.setMatch(reverseIcmpMatch);
+
+
IOFSwitch sw = floodlightProvider.getSwitches().get(flowEntry.dpid().value());
- //Hopefully the switch is there
+ if (sw == null) {
+ log.warn("Switch not found when pushing BGP paths");
+ return;
+ }
+
List<OFMessage> msgList = new ArrayList<OFMessage>(2);
msgList.add(forwardFlowModSrc);
msgList.add(forwardFlowModDst);
msgList.add(reverseFlowModSrc);
msgList.add(reverseFlowModDst);
+ msgList.add(forwardIcmp);
+ msgList.add(reverseIcmp);
try {
sw.write(msgList, null);
@@ -966,11 +1037,31 @@
Set<RibUpdate> prefixesToPush = prefixesWaitingOnArp.removeAll(ipAddress);
- for (RibUpdate update : prefixesToPush) {
- //These will always be adds
- log.debug("Pushing prefix {} next hop {}", update.getPrefix(),
- update.getRibEntry().nextHop.getHostAddress());
- addPrefixFlows(update.getPrefix(), update.getRibEntry());
+ /*
+ * We synchronize on this to prevent changes to the ptree while we're pushing
+ * flows to the switches. If the ptree changes, the ptree and switches
+ * could get out of sync.
+ */
+ synchronized (this) {
+ for (RibUpdate update : prefixesToPush) {
+ //These will always be adds
+
+ //addPrefixFlows(update.getPrefix(), update.getRibEntry());
+ //processRibAdd(update);
+ RibEntry rib = ptree.lookup(update.getPrefix());
+ if (rib != null && rib.equals(update.getRibEntry())) {
+ log.debug("Pushing prefix {} next hop {}", update.getPrefix(),
+ rib.getNextHop().getHostAddress());
+ //We only push prefix flows if the prefix is still in the ptree
+ //and the next hop is the same as our update. The prefix could
+ //have been removed while we were waiting for the ARP, or the
+ //next hop could have changed.
+ addPrefixFlows(update.getPrefix(), rib);
+ } else {
+ log.debug("Received ARP response, but {},{} is no longer in ptree",
+ update.getPrefix(), update.getRibEntry());
+ }
+ }
}
}
@@ -980,11 +1071,31 @@
setupFullMesh();
//Traverse ptree and create flows for all routes
+ /*
for (PtreeNode node = ptree.begin(); node != null; node = ptree.next(node)){
if (node.rib != null){
prefixAdded(node);
}
}
+ */
+
+ /*
+ synchronized (ptree) {
+ Iterator<IPatriciaTrie.Entry> it = ptree.iterator();
+ while (it.hasNext()) {
+ IPatriciaTrie.Entry entry = it.next();
+ addPrefixFlows(entry.getPrefix(), entry.getRib());
+ }
+ }
+ */
+
+ bgpUpdatesExecutor.execute(new Runnable() {
+ @Override
+ public void run() {
+ doUpdatesThread();
+ }
+ });
+
}
private void checkSwitchesConnected(){
@@ -1042,17 +1153,6 @@
floodlightProvider.addOFMessageListener(OFType.PACKET_IN, proxyArp);
- ExecutorService e = Executors.newSingleThreadExecutor(
- new ThreadFactoryBuilder().setNameFormat("bgp-updates-%d").build());
-
-
- e.execute(new Runnable() {
- @Override
- public void run() {
- doUpdatesThread();
- }
- });
-
//Retrieve the RIB from BGPd during startup
retrieveRib();
}
@@ -1072,6 +1172,7 @@
break;
}
} catch (InterruptedException e) {
+ log.debug("interrupted", e);
interrupted = true;
}
}
@@ -1084,14 +1185,11 @@
@Override
public void topologyChanged() {
- //There seems to be more topology events than there should be. Lots of link
- //updated, port up and switch updated on what should be a fairly static topology
-
boolean refreshNeeded = false;
for (LDUpdate ldu : topology.getLastLinkUpdates()){
if (!ldu.getOperation().equals(ILinkDiscovery.UpdateOperation.LINK_UPDATED)){
//We don't need to recalculate anything for just link updates
- //They happen way too frequently (may be a bug in our link discovery)
+ //They happen very frequently
refreshNeeded = true;
}
diff --git a/src/main/java/net/onrc/onos/ofcontroller/bgproute/BgpRouteResource.java b/src/main/java/net/onrc/onos/ofcontroller/bgproute/BgpRouteResource.java
index 19b44c8..c9b3265 100644
--- a/src/main/java/net/onrc/onos/ofcontroller/bgproute/BgpRouteResource.java
+++ b/src/main/java/net/onrc/onos/ofcontroller/bgproute/BgpRouteResource.java
@@ -1,6 +1,6 @@
package net.onrc.onos.ofcontroller.bgproute;
-import java.net.UnknownHostException;
+import java.util.Iterator;
import net.onrc.onos.ofcontroller.bgproute.RibUpdate.Operation;
@@ -59,11 +59,13 @@
return output;
}
else {
- Ptree ptree = bgpRoute.getPtree();
+ //Ptree ptree = bgpRoute.getPtree();
+ IPatriciaTrie ptree = bgpRoute.getPtree();
output += "{\n \"rib\": [\n";
boolean printed = false;
- for (PtreeNode node = ptree.begin(); node != null; node = ptree.next(node)) {
+ /*
+ for (PtreeNode node = ptree.begin(); node!= null; node = ptree.next(node)) {
if (node.rib == null) {
continue;
}
@@ -73,7 +75,25 @@
output += " {\"prefix\": \"" + addrToString(node.key) + "/" + node.keyBits +"\", ";
output += "\"nexthop\": \"" + addrToString(node.rib.nextHop.getAddress()) +"\"}";
printed = true;
+ }*/
+
+ synchronized(ptree) {
+ Iterator<IPatriciaTrie.Entry> it = ptree.iterator();
+ while (it.hasNext()) {
+ IPatriciaTrie.Entry entry = it.next();
+
+ if (printed == true) {
+ output += ",\n";
+ }
+
+ output += " {\"prefix\": \"" + entry.getPrefix() +"\", ";
+ output += "\"nexthop\": \"" + entry.getRib().getNextHop().getHostAddress() +"\"}";
+ //output += ",\n";
+
+ printed = true;
+ }
}
+
//output += "{\"router_id\": \"" + addrToString(node.rib.routerId.getAddress()) +"\"}\n";
output += "\n ]\n}\n";
}
@@ -121,13 +141,13 @@
reply = "[POST: mask format is wrong]";
log.info(reply);
return reply + "\n";
- } catch (UnknownHostException e1) {
+ } catch (IllegalArgumentException e1) {
reply = "[POST: prefix format is wrong]";
log.info(reply);
return reply + "\n";
}
- Rib rib = new Rib(routerId, nexthop, p.getPrefixLength());
+ RibEntry rib = new RibEntry(routerId, nexthop);
bgpRoute.newRibUpdate(new RibUpdate(Operation.UPDATE, p, rib));
@@ -184,13 +204,13 @@
reply = "[DELE: mask format is wrong]";
log.info(reply);
return reply + "\n";
- } catch (UnknownHostException e1) {
+ } catch (IllegalArgumentException e1) {
reply = "[DELE: prefix format is wrong]";
log.info(reply);
return reply + "\n";
}
- Rib r = new Rib(routerId, nextHop, p.getPrefixLength());
+ RibEntry r = new RibEntry(routerId, nextHop);
bgpRoute.newRibUpdate(new RibUpdate(Operation.DELETE, p, r));
@@ -222,7 +242,7 @@
else {
// clear the local rib: Ptree
bgpRoute.clearPtree();
- reply = "[DELE-capability: " + capability + "; The local Rib is cleared!]\n";
+ reply = "[DELE-capability: " + capability + "; The local RibEntry is cleared!]\n";
// to store the number in the top node of the Ptree
}
diff --git a/src/main/java/net/onrc/onos/ofcontroller/bgproute/IBgpRouteService.java b/src/main/java/net/onrc/onos/ofcontroller/bgproute/IBgpRouteService.java
index d865e6e..ba912ce 100644
--- a/src/main/java/net/onrc/onos/ofcontroller/bgproute/IBgpRouteService.java
+++ b/src/main/java/net/onrc/onos/ofcontroller/bgproute/IBgpRouteService.java
@@ -4,9 +4,10 @@
public interface IBgpRouteService extends IFloodlightService {
- public Rib lookupRib(byte[] dest);
+ //public RibEntry lookupRib(byte[] dest);
- public Ptree getPtree();
+ //public Ptree getPtree();
+ public IPatriciaTrie getPtree();
public String getBGPdRestIp();
diff --git a/src/main/java/net/onrc/onos/ofcontroller/bgproute/IPatriciaTrie.java b/src/main/java/net/onrc/onos/ofcontroller/bgproute/IPatriciaTrie.java
new file mode 100644
index 0000000..7fd7382
--- /dev/null
+++ b/src/main/java/net/onrc/onos/ofcontroller/bgproute/IPatriciaTrie.java
@@ -0,0 +1,20 @@
+package net.onrc.onos.ofcontroller.bgproute;
+
+import java.util.Iterator;
+
+public interface IPatriciaTrie {
+ public RibEntry put(Prefix p, RibEntry r);
+
+ public RibEntry lookup(Prefix p);
+
+ public RibEntry match(Prefix p);
+
+ public boolean remove(Prefix p, RibEntry r);
+
+ public Iterator<Entry> iterator();
+
+ interface Entry {
+ public Prefix getPrefix();
+ public RibEntry getRib();
+ }
+}
diff --git a/src/main/java/net/onrc/onos/ofcontroller/bgproute/PatriciaTrie.java b/src/main/java/net/onrc/onos/ofcontroller/bgproute/PatriciaTrie.java
new file mode 100644
index 0000000..86bc8cf
--- /dev/null
+++ b/src/main/java/net/onrc/onos/ofcontroller/bgproute/PatriciaTrie.java
@@ -0,0 +1,464 @@
+package net.onrc.onos.ofcontroller.bgproute;
+
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+public class PatriciaTrie implements IPatriciaTrie{
+ private final byte maskBits[] = {(byte)0x00, (byte)0x80, (byte)0xc0, (byte)0xe0, (byte)0xf0,
+ (byte)0xf8, (byte)0xfc, (byte)0xfe, (byte)0xff};
+
+ private int maxPrefixLength;
+
+ private Node top;
+
+ public PatriciaTrie(int maxPrefixLength) {
+ this.maxPrefixLength = maxPrefixLength;
+ }
+
+ public synchronized RibEntry put(Prefix p, RibEntry r) {
+ if (p.getPrefixLength() > maxPrefixLength) {
+ throw new IllegalArgumentException(String.format(
+ "Prefix length %d is greater than max prefix length %d",
+ p.getPrefixLength(), maxPrefixLength));
+ }
+
+ if (p == null || r == null) {
+ throw new NullPointerException();
+ }
+
+ Node node = top;
+ Node match = null;
+
+ while (node != null
+ && node.prefix.getPrefixLength() <= p.getPrefixLength()
+ && key_match(node.prefix.getAddress(), node.prefix.getPrefixLength(), p.getAddress(), p.getPrefixLength()) == true) {
+ if (node.prefix.getPrefixLength() == p.getPrefixLength()) {
+ /*
+ * Prefix is already in tree. This may be an aggregate node, in which case
+ * we are inserting a new prefix, or it could be an actual node, in which
+ * case we are inserting a new nexthop for the prefix and should return
+ * the old nexthop.
+ */
+ RibEntry oldRib = node.rib;
+ node.rib = r;
+ return oldRib;
+ }
+
+ match = node;
+
+ if (bit_check(p.getAddress(), node.prefix.getPrefixLength()) == true) {
+ node = node.right;
+ } else {
+ node = node.left;
+ }
+ }
+
+ Node add = null;
+
+ if (node == null) {
+ add = new Node(p, r);
+
+ if (match != null) {
+ node_link(match, add);
+ } else {
+ top = add;
+ }
+ } else {
+ add = node_common(node, p.getAddress(), p.getPrefixLength());
+ if (add == null) {
+ //I think this is -ENOMEM?
+ //return null;
+ }
+
+ if (match != null) {
+ node_link(match, add);
+ } else {
+ top = add;
+ }
+ node_link(add, node);
+
+ if (add.prefix.getPrefixLength() != p.getPrefixLength()) {
+ match = add;
+
+ add = new Node(p, r);
+ node_link(match, add);
+ }
+ else {
+ add.rib = r;
+ }
+ }
+
+ //If we added a new Node, there was no previous mapping
+ return null;
+ //return addReference(add);
+ }
+
+ /*exact match*/
+ public synchronized RibEntry lookup(Prefix p) {
+ //TODO
+
+ if (p.getPrefixLength() > maxPrefixLength) {
+ return null;
+ }
+
+ /*
+ Node node = top;
+
+ while (node != null
+ && node.prefix.getPrefixLength() <= p.getPrefixLength()
+ && key_match(node.prefix.getAddress(), node.prefix.getPrefixLength(), p.getAddress(), p.getPrefixLength()) == true) {
+ if (node.prefix.getPrefixLength() == p.getPrefixLength()) {
+ //return addReference(node);
+ return node.rib;
+ }
+
+ if (bit_check(p.getAddress(), node.prefix.getPrefixLength()) == true) {
+ node = node.right;
+ } else {
+ node = node.left;
+ }
+ }
+ */
+
+ Node node = findNode(p);
+
+ return node == null ? null : node.rib;
+ }
+
+ /*closest containing prefix*/
+ public synchronized RibEntry match(Prefix p) {
+ //TODO
+ return null;
+ }
+
+ public synchronized boolean remove(Prefix p, RibEntry r) {
+ Node child;
+ Node parent;
+
+ if (p == null || r == null) {
+ return false;
+ }
+
+ Node node = findNode(p);
+
+ if (node == null || node.rib == null || !node.rib.equals(r)) {
+ //Given <prefix, nexthop> mapping is not in the tree
+ return false;
+ }
+
+ if (node.left != null && node.right != null) {
+ //Remove the RibEntry entry and leave this node as an aggregate node
+ //In the future, maybe we should re-evaluate what the aggregate prefix should be?
+ //It shouldn't necessarily stay the same.
+ //More complicated if the above prefix is also aggregate.
+ node.rib = null;
+ return true;
+ }
+
+ if (node.left != null) {
+ child = node.left;
+ } else {
+ child = node.right;
+ }
+
+ parent = node.parent;
+
+ if (child != null) {
+ child.parent = parent;
+ }
+
+ if (parent != null) {
+ if (parent.left == node) {
+ parent.left = child;
+ } else {
+ parent.right = child;
+ }
+ } else {
+ top = child;
+ }
+
+ /*
+ * TODO not sure what to do here. I think this is lazily deleting aggregate nodes,
+ * notice that it used to do nothing if it detected both children were not null earlier.
+ * But here, what we really should do is reevaluate the aggregate prefix of the parent
+ * node (if it is indeed an aggregate). Because at the moment, no aggregate node will ever
+ * be removed. BUT, I don't actually think this presents a correctness problem, at
+ * least from an external point of view.
+ */
+ //if (parent != null && parent.refCount == 0) {
+ //node_remove(parent);
+ //}
+
+ return true;
+ }
+
+ public Iterator<Entry> iterator() {
+ return new PatriciaTrieIterator(top);
+ }
+
+ private Node findNode(Prefix p) {
+ Node node = top;
+
+ while (node != null
+ && node.prefix.getPrefixLength() <= p.getPrefixLength()
+ && key_match(node.prefix.getAddress(), node.prefix.getPrefixLength(), p.getAddress(), p.getPrefixLength()) == true) {
+ if (node.prefix.getPrefixLength() == p.getPrefixLength()) {
+ //return addReference(node);
+ return node;
+ }
+
+ if (bit_check(p.getAddress(), node.prefix.getPrefixLength()) == true) {
+ node = node.right;
+ } else {
+ node = node.left;
+ }
+ }
+
+ return null;
+ }
+
+ /*
+ * Receives a 1-based bit index
+ * Returns a 1-based byte index
+ * eg. (0 => 1), 1 => 1, 8 => 1, 9 => 2, 17 => 3
+ */
+ private int getByteContainingBit(int bitNumber) {
+ return Math.max((bitNumber + 7) / 8, 1);
+ }
+
+ private boolean key_match(byte [] key1, int key1_len, byte [] key2, int key2_len) {
+ //int offset;
+ //int shift;
+
+ if (key1_len > key2_len) {
+ return false;
+ }
+
+ int offset = (Math.min(key1_len, key2_len)) / 8;
+ int shift = (Math.min(key1_len, key2_len)) % 8;
+
+ if (shift != 0) {
+ if ((maskBits[shift] & (key1[offset] ^ key2[offset])) != 0) {
+ return false;
+ }
+ }
+
+ while (offset != 0) {
+ offset--;
+ if (key1[offset] != key2[offset]) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ private boolean bit_check(byte [] key, int key_bits) {
+ int offset = key_bits / 8;
+ int shift = 7 - (key_bits % 8);
+ int bit = key[offset] & 0xff;
+
+ bit >>= shift;
+
+ if ((bit & 1) == 1) {
+ return true;
+ } else {
+ return false;
+ }
+ }
+
+ private void node_link(Node node, Node add) {
+ boolean bit = bit_check(add.prefix.getAddress(), node.prefix.getPrefixLength());
+
+ if (bit == true) {
+ node.right = add;
+ } else {
+ node.left = add;
+ }
+ add.parent = node;
+ }
+
+ private Node node_common(Node node, byte [] key, int key_bits) {
+ int i;
+ int limit = Math.min(node.prefix.getPrefixLength(), key_bits) / 8;
+
+ for (i = 0; i < limit; i++) {
+ if (node.prefix.getAddress()[i] != key[i]) {
+ break;
+ }
+ }
+
+ int common_len = i * 8;
+ int boundary = 0;
+
+ if (common_len != key_bits) {
+ byte diff = (byte)(node.prefix.getAddress()[i] ^ key[i]);
+ byte mask = (byte)0x80;
+ int shift_mask = 0;
+
+ while (common_len < key_bits && ((mask & diff) == 0)) {
+ boundary = 1;
+
+ shift_mask = (mask & 0xff);
+ shift_mask >>= 1;
+ mask = (byte)shift_mask;
+
+ common_len++;
+ }
+ }
+
+ //Node add = new Node(null, common_len, maxKeyOctets);
+ //if (add == null)
+ //Another -ENOMEM;
+ //return null;
+
+ //Creating a new Prefix with a prefix length of common_len
+ //Bits are copied from node's up until the common_len'th bit
+ //RibEntry is null, because this is an aggregate prefix - it's not
+ //actually been added to the trie.
+
+ byte[] newPrefix = new byte[getByteContainingBit(maxPrefixLength)];
+
+ int j;
+ for (j = 0; j < i; j++)
+ newPrefix[j] = node.prefix.getAddress()[j];
+
+ if (boundary != 0)
+ newPrefix[j] = (byte)(node.prefix.getAddress()[j] & maskBits[common_len % 8]);
+
+ return new Node(new Prefix(newPrefix, common_len), null);
+ //return add;
+ }
+
+ private class Node {
+ public Node parent = null;
+ public Node left = null;
+ public Node right = null;
+
+ public Prefix prefix;
+ public RibEntry rib;
+
+ public Node(Prefix p, RibEntry r) {
+ this.prefix = p;
+ this.rib = r;
+ }
+
+ public Entry getEntry() {
+ return new PatriciaTrieEntry(prefix, rib);
+ }
+ }
+
+ private class PatriciaTrieEntry implements Entry {
+ private Prefix prefix;
+ private RibEntry rib;
+
+ public PatriciaTrieEntry(Prefix prefix, RibEntry rib) {
+ this.prefix = prefix;
+ this.rib = rib;
+ }
+
+ @Override
+ public Prefix getPrefix() {
+ return prefix;
+ }
+
+ @Override
+ public RibEntry getRib() {
+ return rib;
+ }
+ }
+
+ private class PatriciaTrieIterator implements Iterator<Entry> {
+
+ private Node current;
+ private boolean started = false;
+
+ public PatriciaTrieIterator(Node start) {
+ current = start;
+
+ //If the start is an aggregate node fast forward to find the next valid node
+ if (current != null && current.rib == null) {
+ current = findNext(current);
+ }
+ }
+
+ @Override
+ public boolean hasNext() {
+ if (current == null) {
+ return false;
+ }
+
+ if (!started) {
+ return true;
+ }
+
+ return findNext(current) != null;
+ }
+
+ @Override
+ public Entry next() {
+ if (current == null) {
+ throw new NoSuchElementException();
+ }
+
+ if (!started) {
+ started = true;
+ return current.getEntry();
+ }
+
+ current = findNext(current);
+ if (current == null) {
+ throw new NoSuchElementException();
+ }
+
+ return current.getEntry();
+ }
+
+ @Override
+ public void remove() {
+ // TODO This could be implemented, if it were needed
+ throw new NoSuchElementException();
+ }
+
+ private Node findNext(Node node) {
+ Node next = null;
+
+ if (node.left != null) {
+ next = node.left;
+ //addReference(next);
+ //delReference(node);
+ //return next;
+ }
+ else if (node.right != null) {
+ next = node.right;
+ //addReference(next);
+ //delReference(node);
+ //return next;
+ }
+ else {
+ //Node start = node;
+ while (node.parent != null) {
+ if (node.parent.left == node && node.parent.right != null) {
+ next = node.parent.right;
+ //addReference(next);
+ //delReference(start);
+ //return next;
+ break;
+ }
+ node = node.parent;
+ }
+ }
+
+ if (next == null) {
+ return null;
+ }
+
+ //If the node doesn't have a rib, it's not an actual node, it's an artifically
+ //inserted aggregate node. We don't want to return these to the user.
+ if (next.rib == null) {
+ return findNext(next);
+ }
+
+ return next;
+ }
+ }
+}
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 54775df..21dd45c 100644
--- a/src/main/java/net/onrc/onos/ofcontroller/bgproute/Prefix.java
+++ b/src/main/java/net/onrc/onos/ofcontroller/bgproute/Prefix.java
@@ -2,30 +2,88 @@
import java.net.InetAddress;
import java.net.UnknownHostException;
+import java.util.Arrays;
public class Prefix {
- private int prefixLength;
- private InetAddress address;
+ private final int MAX_BYTES = 4;
+
+ private final int prefixLength;
+ private final byte[] address;
+
+ //For verifying the arguments and pretty printing
+ private final InetAddress inetAddress;
+
+ public Prefix(byte[] addr, int prefixLength) {
+ if (addr == null || addr.length != MAX_BYTES ||
+ prefixLength < 0 || prefixLength > MAX_BYTES * Byte.SIZE) {
+ throw new IllegalArgumentException();
+ }
- public Prefix(byte[] addr, int prefixLength) throws UnknownHostException {
- //try {
- address = InetAddress.getByAddress(addr);
- //} catch (UnknownHostException e) {
- // System.out.println("InetAddress exception");
- // return;
- //}
+ address = canonicalizeAddress(addr, prefixLength);
this.prefixLength = prefixLength;
- //System.out.println(address.toString() + "/" + prefixLength);
+
+ try {
+ inetAddress = InetAddress.getByAddress(address);
+ } catch (UnknownHostException e) {
+ throw new IllegalArgumentException();
+ }
}
- public Prefix(String str, int prefixLength) throws UnknownHostException {
- //try {
- address = InetAddress.getByName(str);
- //} catch (UnknownHostException e) {
- // System.out.println("InetAddress exception");
- // return;
- //}
+ 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");
+ }
+
+ if (addr == null || addr.length != MAX_BYTES ||
+ prefixLength < 0 || prefixLength > MAX_BYTES * Byte.SIZE) {
+ throw new IllegalArgumentException();
+ }
+
+ address = canonicalizeAddress(addr, prefixLength);
this.prefixLength = prefixLength;
+
+ try {
+ inetAddress = InetAddress.getByAddress(address);
+ } catch (UnknownHostException e) {
+ throw new IllegalArgumentException();
+ }
+ }
+
+ private byte[] canonicalizeAddress(byte[] address, int prefixLength) {
+ byte[] result = new byte[address.length];
+
+ if (prefixLength == 0) {
+ for (int i = 0; i < MAX_BYTES; i++) {
+ result[i] = 0;
+ }
+
+ return result;
+ }
+
+ result = Arrays.copyOf(address, address.length);
+
+ //Set all bytes after the end of the prefix to 0
+ int lastByteIndex = (prefixLength - 1) / Byte.SIZE;
+ for (int i = lastByteIndex; i < MAX_BYTES; i++) {
+ result[i] = 0;
+ }
+
+ byte lastByte = address[lastByteIndex];
+ byte mask = 0;
+ byte msb = (byte) 0x80;
+ int lastBit = (prefixLength - 1) % Byte.SIZE;
+ for (int i = 0; i < Byte.SIZE; i++) {
+ if (i <= lastBit) {
+ mask |= (msb >> i);
+ }
+ }
+
+ result[lastByteIndex] = (byte) (lastByte & mask);
+
+ return result;
}
public int getPrefixLength() {
@@ -33,7 +91,7 @@
}
public byte[] getAddress() {
- return address.getAddress();
+ return address;
}
@Override
@@ -44,7 +102,7 @@
Prefix otherPrefix = (Prefix) other;
- return (address.equals(otherPrefix.address)) &&
+ return (Arrays.equals(address, otherPrefix.address)) &&
(prefixLength == otherPrefix.prefixLength);
}
@@ -52,12 +110,28 @@
public int hashCode() {
int hash = 17;
hash = 31 * hash + prefixLength;
- hash = 31 * hash + (address == null ? 0 : address.hashCode());
+ hash = 31 * hash + Arrays.hashCode(address);
return hash;
}
@Override
public String toString() {
- return address.getHostAddress() + "/" + prefixLength;
+ return inetAddress.getHostAddress() + "/" + prefixLength;
+ }
+
+ public String printAsBits() {
+ String result = "";
+ 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 += ((b & mask) == 0)? "0" : "1";
+ if (i*Byte.SIZE+j == prefixLength-1) {
+ return result;
+ }
+ }
+ result += " ";
+ }
+ return result.substring(0, result.length() - 1);
}
}
diff --git a/src/main/java/net/onrc/onos/ofcontroller/bgproute/PtreeNode.java b/src/main/java/net/onrc/onos/ofcontroller/bgproute/PtreeNode.java
index a4d6996..50b7c7d 100644
--- a/src/main/java/net/onrc/onos/ofcontroller/bgproute/PtreeNode.java
+++ b/src/main/java/net/onrc/onos/ofcontroller/bgproute/PtreeNode.java
@@ -13,7 +13,7 @@
public int refCount;
- public Rib rib;
+ public RibEntry rib;
protected static Logger log = LoggerFactory.getLogger(BgpRoute.class);
PtreeNode(byte [] key, int key_bits, int max_key_octet) {
diff --git a/src/main/java/net/onrc/onos/ofcontroller/bgproute/Rib.java b/src/main/java/net/onrc/onos/ofcontroller/bgproute/Rib.java
deleted file mode 100644
index dc5f71d..0000000
--- a/src/main/java/net/onrc/onos/ofcontroller/bgproute/Rib.java
+++ /dev/null
@@ -1,46 +0,0 @@
-package net.onrc.onos.ofcontroller.bgproute;
-
-import java.net.InetAddress;
-import java.net.UnknownHostException;
-
-public class Rib {
- protected InetAddress routerId;
- protected InetAddress nextHop;
- protected int masklen;
-// protected int distance;
-
- Rib(InetAddress router_id, InetAddress nexthop, int masklen) {
- this.routerId = router_id;
- this.nextHop = nexthop;
- this.masklen = masklen;
-// this.distance = distance;
- }
-
- Rib(String router_id, String nexthop, int masklen) {
- try {
- this.routerId = InetAddress.getByName(router_id);
- } catch (UnknownHostException e) {
- System.out.println("InetAddress exception");
- }
- try {
- this.nextHop = InetAddress.getByName(nexthop);
- } catch (UnknownHostException e) {
- System.out.println("InetAddress exception");
- }
- this.masklen = masklen;
- }
-
- public InetAddress getNextHop() {
- return nextHop;
- }
-
- public int getMasklen(){
- return masklen;
- }
-
- public boolean equals(Rib r) {
-
- return this.routerId.equals(r.routerId) && this.nextHop.equals(r.nextHop) && this.masklen == r.masklen;
-
- }
-}
diff --git a/src/main/java/net/onrc/onos/ofcontroller/bgproute/RibEntry.java b/src/main/java/net/onrc/onos/ofcontroller/bgproute/RibEntry.java
new file mode 100644
index 0000000..c27f962
--- /dev/null
+++ b/src/main/java/net/onrc/onos/ofcontroller/bgproute/RibEntry.java
@@ -0,0 +1,47 @@
+package net.onrc.onos.ofcontroller.bgproute;
+
+import java.net.InetAddress;
+import java.net.UnknownHostException;
+
+public class RibEntry {
+ private InetAddress routerId;
+ private InetAddress nextHop;
+
+ public RibEntry(InetAddress routerId, InetAddress nextHop) {
+ this.routerId = routerId;
+ this.nextHop = nextHop;
+ }
+
+ 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");
+ }
+ }
+
+ public InetAddress getNextHop() {
+ return nextHop;
+ }
+
+ @Override
+ public boolean equals(Object other) {
+ if (other == null || !(other instanceof RibEntry)) {
+ return false;
+ }
+
+ RibEntry otherRibEntry = (RibEntry) other;
+
+ return this.routerId.equals(otherRibEntry.routerId)
+ && this.nextHop.equals(otherRibEntry.nextHop);
+ }
+
+ @Override
+ public int hashCode() {
+ int hash = 17;
+ hash = 31 * hash + routerId.hashCode();
+ hash = 31 * hash + nextHop.hashCode();
+ return hash;
+ }
+}
diff --git a/src/main/java/net/onrc/onos/ofcontroller/bgproute/RibUpdate.java b/src/main/java/net/onrc/onos/ofcontroller/bgproute/RibUpdate.java
index c7272bd..7d4d7a5 100644
--- a/src/main/java/net/onrc/onos/ofcontroller/bgproute/RibUpdate.java
+++ b/src/main/java/net/onrc/onos/ofcontroller/bgproute/RibUpdate.java
@@ -5,9 +5,9 @@
private Operation operation;
private Prefix prefix;
- private Rib ribEntry;
+ private RibEntry ribEntry;
- public RibUpdate(Operation operation, Prefix prefix, Rib ribEntry) {
+ public RibUpdate(Operation operation, Prefix prefix, RibEntry ribEntry) {
this.operation = operation;
this.prefix = prefix;
this.ribEntry = ribEntry;
@@ -21,7 +21,7 @@
return prefix;
}
- public Rib getRibEntry() {
+ public RibEntry getRibEntry() {
return ribEntry;
}
}
diff --git a/src/main/java/net/onrc/onos/ofcontroller/proxyarp/ProxyArpManager.java b/src/main/java/net/onrc/onos/ofcontroller/proxyarp/ProxyArpManager.java
index f56934d..521ba0f 100644
--- a/src/main/java/net/onrc/onos/ofcontroller/proxyarp/ProxyArpManager.java
+++ b/src/main/java/net/onrc/onos/ofcontroller/proxyarp/ProxyArpManager.java
@@ -38,6 +38,7 @@
import com.google.common.collect.Multimaps;
import com.google.common.collect.SetMultimap;
+//TODO have L2 and also L3 mode, where it takes into account interface addresses
public class ProxyArpManager implements IProxyArpService, IOFMessageListener {
private static Logger log = LoggerFactory.getLogger(ProxyArpManager.class);
@@ -79,7 +80,7 @@
return retry;
}
- public synchronized void dispatchReply(InetAddress ipAddress, byte[] replyMacAddress) {
+ public void dispatchReply(InetAddress ipAddress, byte[] replyMacAddress) {
log.debug("Dispatching reply for {} to {}", ipAddress.getHostAddress(),
requester);
requester.arpResponse(ipAddress, replyMacAddress);
@@ -222,19 +223,13 @@
return;
}
- boolean shouldBroadcastRequest = false;
- synchronized (arpRequests) {
- if (!arpRequests.containsKey(target)) {
- shouldBroadcastRequest = true;
- }
- arpRequests.put(target, new ArpRequest(
- new HostArpRequester(this, arp, sw.getId(), pi.getInPort()), false));
- }
+ //Should we just broadcast all received requests here? Or rate limit
+ //if we know we just sent an request?
+ arpRequests.put(target, new ArpRequest(
+ new HostArpRequester(this, arp, sw.getId(), pi.getInPort()), false));
//Flood the request out edge ports
- if (shouldBroadcastRequest) {
- broadcastArpRequestOutEdge(pi.getPacketData(), sw.getId(), pi.getInPort());
- }
+ broadcastArpRequestOutEdge(pi.getPacketData(), sw.getId(), pi.getInPort());
}
else {
//We know the address, so send a reply
diff --git a/src/test/java/net/onrc/onos/ofcontroller/bgproute/PatriciaTrieTest.java b/src/test/java/net/onrc/onos/ofcontroller/bgproute/PatriciaTrieTest.java
new file mode 100644
index 0000000..1af0416
--- /dev/null
+++ b/src/test/java/net/onrc/onos/ofcontroller/bgproute/PatriciaTrieTest.java
@@ -0,0 +1,189 @@
+package net.onrc.onos.ofcontroller.bgproute;
+
+import static org.junit.Assert.assertFalse;
+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;
+import java.util.Map;
+
+import org.junit.After;
+import org.junit.Before;
+import org.junit.Ignore;
+import org.junit.Test;
+
+public class PatriciaTrieTest {
+
+ IPatriciaTrie ptrie;
+ Prefix[] prefixes;
+ Map<Prefix, RibEntry> mappings;
+
+ @Before
+ public void setUp() throws Exception {
+ ptrie = new PatriciaTrie(32);
+ mappings = new HashMap<Prefix, RibEntry>();
+
+ prefixes = new Prefix[] {
+ new Prefix("192.168.10.0", 24),
+ new Prefix("192.168.8.0", 23),
+ new Prefix("192.168.8.0", 22),
+ new Prefix("192.0.0.0", 7),
+ new Prefix("192.168.11.0", 24),
+ new Prefix("10.0.23.128", 25),
+ new Prefix("206.17.144.0", 20),
+ new Prefix("9.17.0.0", 12),
+ new Prefix("192.168.0.0", 16)
+ };
+
+ for (int i = 0; i < prefixes.length; i++) {
+ mappings.put(prefixes[i], new RibEntry("192.168.10.101", "192.168.20." + i));
+ ptrie.put(prefixes[i], new RibEntry("192.168.10.101", "192.168.20." + i));
+ }
+ }
+
+ @After
+ public void tearDown() throws Exception {
+ }
+
+ @Test
+ public void testPut() {
+ IPatriciaTrie ptrie = new PatriciaTrie(32);
+
+ Prefix p1 = new Prefix("192.168.240.0", 20);
+ RibEntry r1 = new RibEntry("192.168.10.101", "192.168.60.2");
+ RibEntry retval = ptrie.put(p1, r1);
+ assertNull(retval);
+ retval = ptrie.lookup(p1);
+ assertTrue(r1 == retval); //should be the same object
+
+ Prefix p2 = new Prefix("192.160.0.0", 12);
+ RibEntry r2 = new RibEntry("192.168.10.101", "192.168.20.1");
+ retval = ptrie.put(p2, r2);
+ assertNull(retval);
+
+ Prefix p3 = new Prefix("192.168.208.0", 20);
+ RibEntry r3 = new RibEntry("192.168.10.101", "192.168.30.1");
+ retval = ptrie.put(p3, r3);
+ assertNull(retval);
+
+ //Insert a new RibEntry entry over a previous one
+ RibEntry r3new = new RibEntry("192.168.10.101", "192.168.60.2");
+ retval = ptrie.put(p3, r3new);
+ assertNotNull(retval);
+ assertTrue(retval.equals(r3));
+ assertTrue(retval == r3); //should be the same object
+
+ //Now we have an aggregate node with prefix 192.168.192.0/18.
+ //We will insert a RibEntry at this prefix
+ Prefix p4 = new Prefix("192.168.192.0", 18);
+ RibEntry r4 = new RibEntry("192.168.10.101", "192.168.40.1");
+ retval = ptrie.put(p4, r4);
+ assertNull(retval);
+ retval = ptrie.lookup(p4);
+ assertTrue(retval == r4); //should be the same object
+ }
+
+ @Test
+ public void testLookup() {
+ for (Map.Entry<Prefix, RibEntry> entry : mappings.entrySet()) {
+ RibEntry r = ptrie.lookup(entry.getKey());
+ assertTrue(entry.getValue().equals(r));
+ }
+
+ //These are aggregate nodes in the tree. Shouldn't be returned by lookup
+ Prefix p1 = new Prefix("0.0.0.0", 0);
+ RibEntry retval = ptrie.lookup(p1);
+ assertNull(retval);
+
+ //We'll put a RibEntry at an aggregate node and check if lookup returns correctly
+ Prefix p2 = new Prefix("192.0.0.0", 4);
+ RibEntry r2 = new RibEntry("192.168.10.101", "192.168.60.1");
+ retval = ptrie.put(p2, r2);
+ assertNull(retval);
+ retval = ptrie.lookup(p2);
+ assertTrue(retval.equals(r2));
+ }
+
+ @Ignore
+ @Test
+ public void testMatch() {
+ fail("Not yet implemented");
+ }
+
+ @Test
+ public void testRemove() {
+ Prefix p1 = new Prefix("192.168.8.0", 23);
+ RibEntry retval = ptrie.lookup(p1);
+ assertNotNull(retval);
+ boolean success = ptrie.remove(p1, retval);
+ assertTrue(success);
+
+ Prefix p2 = new Prefix("192.168.8.0", 22);
+ Prefix p3 = new Prefix("192.168.10.0", 24);
+
+ //Test it does the right thing with null arguments
+ success = ptrie.remove(null, null);
+ assertFalse(success);
+ success = ptrie.remove(p2, null);
+ assertFalse(success);
+
+ //Check other prefixes are still there
+ retval = ptrie.lookup(p2);
+ assertNotNull(retval);
+ retval = ptrie.lookup(p3);
+ assertNotNull(retval);
+
+ Prefix p4 = new Prefix("9.17.0.0", 12);
+ retval = ptrie.lookup(p4);
+ assertNotNull(retval);
+ success = ptrie.remove(p4, retval);
+ assertTrue(success);
+ success = ptrie.remove(p4, retval);
+ assertFalse(success);
+
+ //Check other prefixes are still there
+ retval = ptrie.lookup(p2);
+ assertNotNull(retval);
+ retval = ptrie.lookup(p3);
+ assertNotNull(retval);
+
+ Prefix p5 = new Prefix("192.0.0.0", 7);
+ retval = ptrie.lookup(p5);
+ assertNotNull(retval);
+ success = ptrie.remove(p5, retval);
+ assertTrue(success);
+
+ //Check other prefixes are still there
+ retval = ptrie.lookup(p2);
+ assertNotNull(retval);
+ retval = ptrie.lookup(p3);
+ assertNotNull(retval);
+
+
+ }
+
+ @Test(expected=java.util.NoSuchElementException.class)
+ public void testIterator() {
+ int[] order = new int[] {7, 5, 3, 8, 2, 1, 0, 4, 6};
+
+ Iterator<IPatriciaTrie.Entry> it = ptrie.iterator();
+ int i = 0;
+ assertTrue(it.hasNext());
+ while (it.hasNext()) {
+ IPatriciaTrie.Entry entry = it.next();
+ assertTrue(entry.getPrefix().equals(prefixes[order[i]]));
+ i++;
+ }
+ assertFalse(it.hasNext());
+ assertTrue(i == order.length);
+
+ IPatriciaTrie pt = new PatriciaTrie(32);
+ Iterator<IPatriciaTrie.Entry> it2 = pt.iterator();
+ assertFalse(it2.hasNext());
+ it.next(); //throws NoSuchElementException
+ }
+
+}
diff --git a/src/test/java/net/onrc/onos/ofcontroller/bgproute/PrefixTest.java b/src/test/java/net/onrc/onos/ofcontroller/bgproute/PrefixTest.java
new file mode 100644
index 0000000..6ebaf0f
--- /dev/null
+++ b/src/test/java/net/onrc/onos/ofcontroller/bgproute/PrefixTest.java
@@ -0,0 +1,101 @@
+package net.onrc.onos.ofcontroller.bgproute;
+
+import static org.junit.Assert.*;
+
+import java.util.Arrays;
+
+import org.junit.After;
+import org.junit.Before;
+import org.junit.Test;
+
+public class PrefixTest {
+
+ @Before
+ public void setUp() throws Exception {
+ }
+
+ @After
+ public void tearDown() throws Exception {
+ }
+
+ @Test
+ public void testPrefixByteArray() {
+ byte[] b1 = new byte[] {(byte)0x8f, (byte)0xa0, (byte)0x00, (byte)0x00};
+ byte[] b2 = new byte[] {(byte)0x8f, (byte)0xa0, (byte)0xff, (byte)0xff};
+ byte[] b3 = new byte[] {(byte)0x8f, (byte)0xac, (byte)0x00, (byte)0x00};
+ byte[] b4 = new byte[] {(byte)0x8f, (byte)0xa0, (byte)0x00, (byte)0x00};
+
+ Prefix p1 = new Prefix(b1, 12);
+ Prefix p2 = new Prefix(b2, 12);
+ Prefix p3 = new Prefix(b3, 12);
+ Prefix p4 = new Prefix(b4, 11);
+
+ //Have different byte arrays, but should be equal after construction
+ assertTrue(p1.equals(p2));
+ assertTrue(p2.equals(p3));
+
+ //Same byte array, but should be false
+ assertFalse(p1.equals(p4));
+
+ assertTrue(Arrays.equals(p1.getAddress(), p3.getAddress()));
+ assertTrue(p1.toString().equals(p2.toString()));
+ assertTrue(Arrays.equals(p1.getAddress(), p4.getAddress()));
+ assertFalse(p1.toString().equals(p4.toString()));
+ }
+
+ @Test
+ public void testPrefixString() {
+ Prefix p1 = new Prefix("192.168.166.0", 24);
+ Prefix p2 = new Prefix("192.168.166.0", 23);
+ Prefix p3 = new Prefix("192.168.166.128", 24);
+ Prefix p4 = new Prefix("192.168.166.128", 25);
+
+ assertFalse(p1.equals(p2));
+ assertTrue(Arrays.equals(p1.getAddress(), p2.getAddress()));
+
+ assertTrue(p1.equals(p3));
+ assertTrue(Arrays.equals(p1.getAddress(), p2.getAddress()));
+
+ assertFalse(p3.equals(p4));
+ assertFalse(Arrays.equals(p3.getAddress(), p4.getAddress()));
+
+ assertTrue(p1.toString().equals(p3.toString()));
+ assertEquals(p1.hashCode(), p3.hashCode());
+ }
+
+ @Test
+ public void testPrefixReturnsSame() {
+ //Create a prefix of all 1s for each prefix length.
+ //Check that Prefix doesn't mangle it
+ int MAX_PREFIX_LENGTH = 32;
+ for (int prefixLength = 1; prefixLength <= MAX_PREFIX_LENGTH; prefixLength++) {
+ byte address[] = new byte[MAX_PREFIX_LENGTH/Byte.SIZE];
+
+ int lastByte = (prefixLength - 1) / Byte.SIZE;
+ int lastBit = (prefixLength - 1) % Byte.SIZE;
+
+ for (int j = 0; j < address.length; j++) {
+ if (j < lastByte) {
+ address[j] = (byte)0xff;
+ }
+ else if (j == lastByte) {
+ byte b = 0;
+ byte msb = (byte) 0x80;
+ for (int k = 0; k < Byte.SIZE; k++) {
+ if (k <= lastBit) {
+ b |= (msb >> k);
+ }
+ }
+ address[j] = b;
+ }
+ else {
+ address[j] = 0;
+ }
+ }
+
+ Prefix p = new Prefix(address, prefixLength);
+ System.out.println(p.printAsBits());
+ assertTrue(Arrays.equals(address, p.getAddress()));
+ }
+ }
+}
diff --git a/src/test/java/net/onrc/onos/ofcontroller/bgproute/PtreeTest.java b/src/test/java/net/onrc/onos/ofcontroller/bgproute/PtreeTest.java
new file mode 100644
index 0000000..6af9d30
--- /dev/null
+++ b/src/test/java/net/onrc/onos/ofcontroller/bgproute/PtreeTest.java
@@ -0,0 +1,227 @@
+package net.onrc.onos.ofcontroller.bgproute;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import java.net.InetAddress;
+import java.net.UnknownHostException;
+import java.util.Arrays;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.Map;
+
+import org.junit.After;
+import org.junit.Before;
+import org.junit.Ignore;
+import org.junit.Test;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+import com.google.common.net.InetAddresses;
+
+public class PtreeTest {
+
+ private Logger log = LoggerFactory.getLogger(PtreeTest.class);
+
+ private Ptree ptree;
+ private PatriciaTrie ooptrie;
+
+ private Map<String, byte[]> byteAddresses;
+
+ @Before
+ public void setUp() throws Exception {
+ ptree = new Ptree(32);
+ ooptrie = new PatriciaTrie(32);
+
+ String[] strPrefixes = {
+ "192.168.10.0/24",
+ "192.168.10.0/23",
+ "192.168.10.0/22",
+ "192.0.0.0/7",
+ "192.168.11.0/24",
+ "10.0.23.128/25",
+ "206.17.144.0/20",
+ "9.17.0.0/12",
+ "192.168.0.0/16"
+ };
+
+ byteAddresses = new HashMap<String, byte[]>(strPrefixes.length+10);
+ for (String prefix : strPrefixes) {
+ String address = prefix.split("/")[0];
+ int prefixLength = Integer.parseInt(prefix.split("/")[1]);
+ byteAddresses.put(prefix, InetAddresses.forString(address).getAddress());
+
+ PtreeNode node = ptree.acquire(byteAddresses.get(prefix), prefixLength);
+ node.rib = new RibEntry("192.168.10.101", "192.168.60.1");
+ ooptrie.put(new Prefix(byteAddresses.get(prefix), prefixLength),
+ new RibEntry("192.168.10.101", "192.168.60.1"));
+ }
+ }
+
+ @After
+ public void tearDown() throws Exception {
+ }
+
+ @Ignore
+ @Test
+ public void testAcquireByteArray() {
+ fail("Not yet implemented");
+ }
+
+ @Ignore
+ @Test
+ public void testAcquireByteArrayInt() {
+ //First let's test an empty Ptree
+ Ptree localPtree = new Ptree(32);
+ PtreeNode node = localPtree.acquire(new byte[] {0x00, 0x00, 0x00, 0x00});
+ assertTrue(node != null && node.rib == null);
+
+ //Now let's look at the prepopulated tree
+ String testPrefix = "206.17.144.0/20";
+ PtreeNode existingNode = ptree.acquire(byteAddresses.get(testPrefix), 20);
+ printByteArray(existingNode.key);
+ printByteArray(byteAddresses.get(testPrefix));
+ assertTrue(existingNode != null && existingNode.rib == null);
+
+ assertTrue(Arrays.equals(existingNode.key, byteAddresses.get(testPrefix)));
+ }
+
+ @Test
+ public void testLookup() {
+ String prefix1 = "192.168.10.12";
+ int length1 = 29;
+ PtreeNode node1 = ptree.lookup(InetAddresses.forString(prefix1).getAddress(), length1);
+
+ //There should be no direct match
+ assertTrue(node1 == null);
+
+ log.debug("{} null: {}", "node1", node1 == null ? "true" : "false");
+
+ String prefix2 = "206.17.144.0";
+ int length2 = 20;
+ PtreeNode node2 = ptree.lookup(InetAddresses.forString(prefix2).getAddress(), length2);
+
+ assertTrue(node2 != null);
+ assertTrue(Arrays.equals(node2.key, byteAddresses.get(prefix2 + "/" + length2)));
+
+ log.debug("{} null: {}", "node2", node2 == null ? "true" : "false");
+ if (node2 != null) {
+ log.debug("{} key: {}, keybits: {}", new Object[] {"node2", node2.key, node2.keyBits});
+ }
+
+ String prefix3 = "192.0.0.0";
+ int length3 = 7;
+ PtreeNode node3 = ptree.lookup(InetAddresses.forString(prefix3).getAddress(), length3);
+ assertTrue(node3 != null);
+ }
+
+ @Test
+ public void testMatch() {
+ String prefix1 = "192.168.10.12";
+ int length1 = 29;
+ PtreeNode node1 = ptree.match(InetAddresses.forString(prefix1).getAddress(), length1);
+
+ //There should be no direct match, but we should get the covering prefix
+ assertTrue(node1 != null);
+ assertTrue(Arrays.equals(node1.key, byteAddresses.get("192.168.10.0/24")));
+
+ log.debug("{} null: {}", "node1", node1 == null ? "true" : "false");
+ if (node1 != null) {
+ log.debug("{} key: {}, keybits: {}", new Object[] {"node1", node1.key, node1.keyBits});
+ }
+ }
+
+ @Ignore
+ @Test
+ public void testTraverse() {
+
+ String expected = "[0, 0, 0, 0]/0\n";
+ expected += "[8, 0, 0, 0]/6\n";
+ expected += "[9, 17, 0, 0]/12\n";
+ expected += "[10, 0, 23, -128]/25\n";
+ expected += "[-64, 0, 0, 0]/4\n";
+ expected += "[-64, -88, 0, 0]/16\n";
+ expected += "[-64, -88, 8, 0]/22\n";
+ expected += "[-64, -88, 10, 0]/23\n";
+ expected += "[-64, -88, 10, 0]/24\n";
+ expected += "[-64, -88, 11, 0]/24\n";
+ expected += "[-50, 17, -112, 0]/20\n";
+
+ PtreeNode node;
+ String result = "";
+
+ for (node = ptree.begin(); node != null; node = ptree.next(node)) {
+ result += printByteArray(node.key) + "/" + node.keyBits + "\n";
+ }
+
+ assertEquals(expected, result);
+ }
+
+ @Ignore
+ @Test
+ public void testBegin() {
+ fail("Not yet implemented");
+ }
+
+ @Ignore
+ @Test
+ public void testNext() {
+ fail("Not yet implemented");
+ }
+
+ @Ignore
+ @Test
+ public void testDelReference() {
+ fail("Not yet implemented");
+ }
+
+ @Test
+ public void testMisc() {
+ int bitIndex = -1;
+ int index = (int)(bitIndex / Byte.SIZE);
+ int bit = (int)(bitIndex % Byte.SIZE);
+
+ log.debug("index {} bit {}", index, bit);
+ log.debug("percent {}", 1%8);
+
+ //PtreeNode node1 = new PtreeNode(new byte[] {0x0, 0x0, 0x0, 0x0}, 0, 4);
+ PtreeNode node1 = new PtreeNode(null, 0, 4);
+ log.debug("node1: key {}, keybits {}", printByteArray(node1.key), node1.keyBits);
+
+ //PtreeNode node2 = new PtreeNode(new byte[] {(byte)0xff, (byte)0xff, (byte)0xff, (byte)0xff},
+ PtreeNode node2 = new PtreeNode(null,
+ 32, 4);
+ log.debug("node2: key {}, keybits {}", printByteArray(node2.key), node2.keyBits);
+ }
+
+ @Test
+ public void testIteration() {
+ Iterator<IPatriciaTrie.Entry> it = ooptrie.iterator();
+
+ while (it.hasNext()) {
+ IPatriciaTrie.Entry entry = it.next();
+ log.debug("PatriciaTrie prefix {} \t {}", entry.getPrefix(), entry.getPrefix().printAsBits());
+ }
+
+ try {
+ PtreeNode node;
+ for (node = ptree.begin(); node != null; node = ptree.next(node)) {
+ log.debug("Ptree prefix {}/{}", InetAddress.getByAddress(node.key).getHostAddress(), node.keyBits);
+ }
+ } catch (UnknownHostException e) {
+
+ }
+ }
+
+ private String printByteArray(byte[] array) {
+ String result = "[";
+ for (byte b : array) {
+ result += b + ", ";
+ }
+ result = result.substring(0, result.length() - 2);
+ result += "]";
+ return result;
+ }
+
+}