Renamed bgproute package
net.onrc.onos.ofcontroller.bgproute => net.onrc.onos.apps.bgproute
Change-Id: If4116c84cc0d5f66adcc8f9ef102cb6bc84d6db3
diff --git a/src/main/java/net/onrc/onos/apps/bgproute/BgpPeer.java b/src/main/java/net/onrc/onos/apps/bgproute/BgpPeer.java
new file mode 100644
index 0000000..32ea288
--- /dev/null
+++ b/src/main/java/net/onrc/onos/apps/bgproute/BgpPeer.java
@@ -0,0 +1,26 @@
+package net.onrc.onos.apps.bgproute;
+
+import java.net.InetAddress;
+
+import org.codehaus.jackson.annotate.JsonProperty;
+
+import com.google.common.net.InetAddresses;
+
+public class BgpPeer {
+ private final String interfaceName;
+ private final InetAddress ipAddress;
+
+ public BgpPeer(@JsonProperty("interface") String interfaceName,
+ @JsonProperty("ipAddress") String ipAddress) {
+ this.interfaceName = interfaceName;
+ this.ipAddress = InetAddresses.forString(ipAddress);
+ }
+
+ public String getInterfaceName() {
+ return interfaceName;
+ }
+
+ public InetAddress getIpAddress() {
+ return ipAddress;
+ }
+}
diff --git a/src/main/java/net/onrc/onos/apps/bgproute/BgpRoute.java b/src/main/java/net/onrc/onos/apps/bgproute/BgpRoute.java
new file mode 100644
index 0000000..062558e
--- /dev/null
+++ b/src/main/java/net/onrc/onos/apps/bgproute/BgpRoute.java
@@ -0,0 +1,1390 @@
+package net.onrc.onos.apps.bgproute;
+
+import java.io.File;
+import java.io.IOException;
+import java.net.InetAddress;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.concurrent.BlockingQueue;
+import java.util.concurrent.ExecutorService;
+import java.util.concurrent.Executors;
+import java.util.concurrent.LinkedBlockingQueue;
+import java.util.concurrent.ScheduledExecutorService;
+import java.util.concurrent.TimeUnit;
+
+import net.floodlightcontroller.core.IFloodlightProviderService;
+import net.floodlightcontroller.core.IOFSwitch;
+import net.floodlightcontroller.core.IOFSwitchListener;
+import net.floodlightcontroller.core.module.FloodlightModuleContext;
+import net.floodlightcontroller.core.module.FloodlightModuleException;
+import net.floodlightcontroller.core.module.IFloodlightModule;
+import net.floodlightcontroller.core.module.IFloodlightService;
+import net.floodlightcontroller.core.util.SingletonTask;
+import net.floodlightcontroller.restserver.IRestApiService;
+import net.floodlightcontroller.util.MACAddress;
+import net.onrc.onos.apps.bgproute.RibUpdate.Operation;
+import net.onrc.onos.ofcontroller.core.config.IConfigInfoService;
+import net.onrc.onos.ofcontroller.linkdiscovery.ILinkDiscovery.LDUpdate;
+import net.onrc.onos.ofcontroller.linkdiscovery.ILinkDiscoveryService;
+import net.onrc.onos.ofcontroller.proxyarp.IArpRequester;
+import net.onrc.onos.ofcontroller.proxyarp.IProxyArpService;
+import net.onrc.onos.ofcontroller.util.CallerId;
+import net.onrc.onos.ofcontroller.util.DataPath;
+import net.onrc.onos.ofcontroller.util.Dpid;
+import net.onrc.onos.ofcontroller.util.FlowEntryAction;
+import net.onrc.onos.ofcontroller.util.FlowEntryActions;
+import net.onrc.onos.ofcontroller.util.FlowEntryMatch;
+import net.onrc.onos.ofcontroller.util.FlowId;
+import net.onrc.onos.ofcontroller.util.FlowPath;
+import net.onrc.onos.ofcontroller.util.FlowPathFlags;
+import net.onrc.onos.ofcontroller.util.FlowPathType;
+import net.onrc.onos.ofcontroller.util.FlowPathUserState;
+import net.onrc.onos.ofcontroller.util.IPv4Net;
+import net.onrc.onos.ofcontroller.util.Port;
+import net.onrc.onos.ofcontroller.util.SwitchPort;
+import net.onrc.onos.packet.Ethernet;
+import net.onrc.onos.packet.IPv4;
+import net.sf.json.JSONArray;
+import net.sf.json.JSONObject;
+import net.sf.json.JSONSerializer;
+
+import org.codehaus.jackson.JsonParseException;
+import org.codehaus.jackson.map.JsonMappingException;
+import org.codehaus.jackson.map.ObjectMapper;
+import org.openflow.protocol.OFFlowMod;
+import org.openflow.protocol.OFMatch;
+import org.openflow.protocol.OFPacketOut;
+import org.openflow.protocol.OFPort;
+import org.openflow.protocol.action.OFAction;
+import org.openflow.protocol.action.OFActionOutput;
+import org.openflow.util.HexString;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+import com.google.common.collect.HashMultimap;
+import com.google.common.collect.Multimap;
+import com.google.common.collect.Multimaps;
+import com.google.common.collect.SetMultimap;
+import com.google.common.net.InetAddresses;
+import com.google.common.util.concurrent.ThreadFactoryBuilder;
+
+public class BgpRoute implements IFloodlightModule, IBgpRouteService,
+ IArpRequester,
+ IOFSwitchListener, IConfigInfoService {
+
+ private final static Logger log = LoggerFactory.getLogger(BgpRoute.class);
+
+ private IFloodlightProviderService floodlightProvider;
+ private ILinkDiscoveryService linkDiscoveryService;
+ private IRestApiService restApi;
+ private IProxyArpService proxyArp;
+
+ private IPatriciaTrie<RibEntry> ptree;
+ private IPatriciaTrie<Interface> interfacePtrie;
+ private BlockingQueue<RibUpdate> ribUpdates;
+
+ private String bgpdRestIp;
+ private String routerId;
+ private String configFilename = "config.json";
+
+ //We need to identify our flows somehow. But like it says in LearningSwitch.java,
+ //the controller/OS should hand out cookie IDs to prevent conflicts.
+ private final long APP_COOKIE = 0xa0000000000000L;
+ //Cookie for flows that do L2 forwarding within SDN domain to egress routers
+ private final long L2_FWD_COOKIE = APP_COOKIE + 1;
+ //Cookie for flows in ingress switches that rewrite the MAC address
+ private final long MAC_RW_COOKIE = APP_COOKIE + 2;
+ //Cookie for flows that setup BGP paths
+ private final long BGP_COOKIE = APP_COOKIE + 3;
+ //Forwarding uses priority 0, and the mac rewrite entries in ingress switches
+ //need to be higher priority than this otherwise the rewrite may not get done
+ private final short SDNIP_PRIORITY = 10;
+ private final short ARP_PRIORITY = 20;
+
+ private final short BGP_PORT = 179;
+
+ private final int TOPO_DETECTION_WAIT = 2; //seconds
+
+ //Configuration stuff
+ private List<String> switches;
+ private Map<String, Interface> interfaces;
+ private Map<InetAddress, BgpPeer> bgpPeers;
+ private SwitchPort bgpdAttachmentPoint;
+ private MACAddress bgpdMacAddress;
+ private short vlan;
+
+ //True when all switches have connected
+ private volatile boolean switchesConnected = false;
+ //True when we have a full mesh of shortest paths between gateways
+ private volatile boolean topologyReady = false;
+
+ private ArrayList<LDUpdate> linkUpdates;
+ private SingletonTask topologyChangeDetectorTask;
+
+ private SetMultimap<InetAddress, RibUpdate> prefixesWaitingOnArp;
+
+ private Map<InetAddress, Path> pathsWaitingOnArp;
+
+ private ExecutorService bgpUpdatesExecutor;
+
+ private Map<InetAddress, Path> pushedPaths;
+ private Map<Prefix, Path> prefixToPath;
+// private Multimap<Prefix, PushedFlowMod> pushedFlows;
+ private Multimap<Prefix, FlowId> pushedFlowIds;
+
+ private FlowCache flowCache;
+
+ // TODO: Fix for the new Topology Network Graph
+ // private volatile Topology topology = null;
+
+ private class TopologyChangeDetector implements Runnable {
+ @Override
+ public void run() {
+ log.debug("Running topology change detection task");
+ synchronized (linkUpdates) {
+ //This is the model the REST API uses to retrieve network graph info
+ // TODO: Fix the code below after topoLinkService was removed
+ /*
+ ITopoLinkService topoLinkService = new TopoLinkServiceImpl();
+
+ List<Link> activeLinks = topoLinkService.getActiveLinks();
+
+ Iterator<LDUpdate> it = linkUpdates.iterator();
+ while (it.hasNext()){
+ LDUpdate ldu = it.next();
+ Link l = new Link(ldu.getSrc(), ldu.getSrcPort(),
+ ldu.getDst(), ldu.getDstPort());
+
+ if (activeLinks.contains(l)){
+ it.remove();
+ }
+ }
+ */
+ }
+
+ if (!topologyReady) {
+ if (linkUpdates.isEmpty()){
+ //All updates have been seen in network map.
+ //We can check if topology is ready
+ log.debug("No known changes outstanding. Checking topology now");
+ checkStatus();
+ }
+ else {
+ //We know of some link updates that haven't propagated to the database yet
+ log.debug("Some changes not found in network map - {} links missing", linkUpdates.size());
+ topologyChangeDetectorTask.reschedule(TOPO_DETECTION_WAIT, TimeUnit.SECONDS);
+ }
+ }
+ }
+ }
+
+ private void readConfiguration(String configFilename){
+ File gatewaysFile = new File(configFilename);
+ ObjectMapper mapper = new ObjectMapper();
+
+ try {
+ Configuration config = mapper.readValue(gatewaysFile, Configuration.class);
+
+ switches = config.getSwitches();
+ interfaces = new HashMap<String, Interface>();
+ for (Interface intf : config.getInterfaces()){
+ interfaces.put(intf.getName(), intf);
+ }
+ bgpPeers = new HashMap<InetAddress, BgpPeer>();
+ for (BgpPeer peer : config.getPeers()){
+ bgpPeers.put(peer.getIpAddress(), peer);
+ }
+
+ bgpdAttachmentPoint = new SwitchPort(
+ new Dpid(config.getBgpdAttachmentDpid()),
+ new Port(config.getBgpdAttachmentPort()));
+
+ bgpdMacAddress = config.getBgpdMacAddress();
+ vlan = config.getVlan();
+ } catch (JsonParseException e) {
+ log.error("Error in JSON file", e);
+ System.exit(1);
+ } catch (JsonMappingException e) {
+ log.error("Error in JSON file", e);
+ System.exit(1);
+ } catch (IOException e) {
+ 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);
+ }
+ }
+
+ @Override
+ public Collection<Class<? extends IFloodlightService>> getModuleServices() {
+ Collection<Class<? extends IFloodlightService>> l
+ = new ArrayList<Class<? extends IFloodlightService>>();
+ l.add(IBgpRouteService.class);
+ l.add(IConfigInfoService.class);
+ return l;
+ }
+
+ @Override
+ public Map<Class<? extends IFloodlightService>, IFloodlightService> getServiceImpls() {
+ Map<Class<? extends IFloodlightService>, IFloodlightService> m
+ = new HashMap<Class<? extends IFloodlightService>, IFloodlightService>();
+ m.put(IBgpRouteService.class, this);
+ m.put(IConfigInfoService.class, this);
+ return m;
+ }
+
+ @Override
+ public Collection<Class<? extends IFloodlightService>> getModuleDependencies() {
+ Collection<Class<? extends IFloodlightService>> l
+ = new ArrayList<Class<? extends IFloodlightService>>();
+ l.add(IFloodlightProviderService.class);
+ l.add(IRestApiService.class);
+ return l;
+ }
+
+ @Override
+ public void init(FloodlightModuleContext context)
+ throws FloodlightModuleException {
+
+ ptree = new PatriciaTrie<RibEntry>(32);
+ interfacePtrie = new PatriciaTrie<Interface>(32);
+
+ ribUpdates = new LinkedBlockingQueue<RibUpdate>();
+
+ // Register floodlight provider and REST handler.
+ floodlightProvider = context.getServiceImpl(IFloodlightProviderService.class);
+ linkDiscoveryService = context.getServiceImpl(ILinkDiscoveryService.class);
+ restApi = context.getServiceImpl(IRestApiService.class);
+ proxyArp = context.getServiceImpl(IProxyArpService.class);
+
+ linkUpdates = new ArrayList<LDUpdate>();
+ ScheduledExecutorService executor = Executors.newScheduledThreadPool(1);
+ topologyChangeDetectorTask = new SingletonTask(executor, new TopologyChangeDetector());
+
+ pathsWaitingOnArp = new HashMap<InetAddress, Path>();
+ prefixesWaitingOnArp = Multimaps.synchronizedSetMultimap(
+ HashMultimap.<InetAddress, RibUpdate>create());
+
+ pushedPaths = new HashMap<InetAddress, Path>();
+ prefixToPath = new HashMap<Prefix, Path>();
+// pushedFlows = HashMultimap.<Prefix, PushedFlowMod>create();
+ pushedFlowIds = HashMultimap.<Prefix, FlowId>create();
+
+ flowCache = new FlowCache(floodlightProvider);
+
+ bgpUpdatesExecutor = Executors.newSingleThreadExecutor(
+ new ThreadFactoryBuilder().setNameFormat("bgp-updates-%d").build());
+
+ //Read in config values
+ bgpdRestIp = context.getConfigParams(this).get("BgpdRestIp");
+ if (bgpdRestIp == null){
+ log.error("BgpdRestIp property not found in config file");
+ System.exit(1);
+ }
+ else {
+ log.info("BgpdRestIp set to {}", bgpdRestIp);
+ }
+
+ routerId = context.getConfigParams(this).get("RouterId");
+ if (routerId == null){
+ log.error("RouterId property not found in config file");
+ System.exit(1);
+ }
+ else {
+ log.info("RouterId set to {}", routerId);
+ }
+
+ String configFilenameParameter = context.getConfigParams(this).get("configfile");
+ if (configFilenameParameter != null){
+ configFilename = configFilenameParameter;
+ }
+ log.debug("Config file set to {}", configFilename);
+
+ readConfiguration(configFilename);
+ }
+
+ @Override
+ public void startUp(FloodlightModuleContext context) {
+ restApi.addRestletRoutable(new BgpRouteWebRoutable());
+ floodlightProvider.addOFSwitchListener(this);
+
+ //Retrieve the RIB from BGPd during startup
+ retrieveRib();
+ }
+
+ @Override
+ public IPatriciaTrie<RibEntry> getPtree() {
+ return ptree;
+ }
+
+ @Override
+ public void clearPtree() {
+ ptree = new PatriciaTrie<RibEntry>(32);
+ }
+
+ @Override
+ public String getBGPdRestIp() {
+ return bgpdRestIp;
+ }
+
+ @Override
+ public String getRouterId() {
+ return routerId;
+ }
+
+ private void retrieveRib(){
+ String url = "http://" + bgpdRestIp + "/wm/bgp/" + routerId;
+ String response = RestClient.get(url);
+
+ if (response.equals("")){
+ return;
+ }
+
+ response = response.replaceAll("\"", "'");
+ JSONObject jsonObj = (JSONObject) JSONSerializer.toJSON(response);
+ JSONArray rib_json_array = jsonObj.getJSONArray("rib");
+ String router_id = jsonObj.getString("router-id");
+
+ int size = rib_json_array.size();
+
+ log.info("Retrived RIB of {} entries from BGPd", size);
+
+ for (int j = 0; j < size; j++) {
+ JSONObject second_json_object = rib_json_array.getJSONObject(j);
+ String prefix = second_json_object.getString("prefix");
+ String nexthop = second_json_object.getString("nexthop");
+
+ //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.valueOf(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(router_id, nexthop);
+
+ 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) {
+ try {
+ ribUpdates.put(update);
+ } catch (InterruptedException e) {
+ log.debug("Interrupted while putting on ribUpdates queue", e);
+ Thread.currentThread().interrupt();
+ }
+ }
+
+ public synchronized void processRibAdd(RibUpdate update) {
+ Prefix prefix = update.getPrefix();
+
+ log.debug("Processing prefix add {}", prefix);
+
+ RibEntry rib = ptree.put(prefix, update.getRibEntry());
+
+ 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
+ _processDeletePrefix(prefix, rib);
+ }
+
+ if (update.getRibEntry().getNextHop().equals(
+ InetAddresses.forString("0.0.0.0"))) {
+ //Route originated by SDN domain
+ //We don't handle these at the moment
+ log.debug("Own route {} to {}", prefix,
+ update.getRibEntry().getNextHop().getHostAddress());
+ return;
+ }
+
+ _processRibAdd(update);
+ }
+
+ private void _processRibAdd(RibUpdate update) {
+ Prefix prefix = update.getPrefix();
+ RibEntry rib = update.getRibEntry();
+
+ InetAddress dstIpAddress = rib.getNextHop();
+ MACAddress nextHopMacAddress = null;
+
+ // See if we know the MAC address of the next hop
+ // TODO if we do not treat the next hop as a device in the future, we need to update this
+ // TODO: Fix the code below after deviceStorage was removed
+ /*
+ IDeviceObject nextHopDevice =
+ deviceStorage.getDeviceByIP(InetAddresses.coerceToInteger(dstIpAddress));
+
+ if (nextHopDevice == null){
+ log.debug("NextHopDevice for IP: {} is null", dstIpAddress);
+ prefixesWaitingOnArp.put(dstIpAddress,
+ new RibUpdate(Operation.UPDATE, prefix, rib));
+ proxyArp.sendArpRequest(dstIpAddress, this, true);
+ return;
+
+ }
+ nextHopMacAddress = MACAddress.valueOf(nextHopDevice.getMACAddress());
+ */
+
+ // Find the attachment point (egress interface) of the next hop
+ Interface egressInterface = null;
+ if (bgpPeers.containsKey(dstIpAddress)) {
+ //Route to a peer
+ log.debug("Route to peer {}", dstIpAddress);
+ BgpPeer peer = bgpPeers.get(dstIpAddress);
+ egressInterface = interfaces.get(peer.getInterfaceName());
+ }
+ else {
+ //Route to non-peer
+ log.debug("Route to non-peer {}", dstIpAddress);
+ egressInterface = interfacePtrie.match(
+ new Prefix(dstIpAddress.getAddress(), 32));
+ if (egressInterface == null) {
+ log.warn("No outgoing interface found for {}", dstIpAddress.getHostAddress());
+ return;
+ }
+ }
+
+ if (nextHopMacAddress == null) {
+ prefixesWaitingOnArp.put(dstIpAddress,
+ new RibUpdate(Operation.UPDATE, prefix, rib));
+ proxyArp.sendArpRequest(dstIpAddress, this, true);
+ return;
+ }
+ else {
+ if (!bgpPeers.containsKey(dstIpAddress)) {
+ //If the prefix is for a non-peer we need to ensure there's a path,
+ //and push one if there isn't.
+ Path path = pushedPaths.get(dstIpAddress);
+ if (path == null) {
+ path = new Path(egressInterface, dstIpAddress);
+ calculateAndPushPath(path, nextHopMacAddress);
+ pushedPaths.put(dstIpAddress, path);
+ }
+
+ path.incrementUsers();
+ prefixToPath.put(prefix, path);
+ }
+
+ //For all prefixes we need to add the first-hop mac-rewriting flows
+ addPrefixFlows(prefix, egressInterface, nextHopMacAddress);
+ }
+ }
+
+ /**
+ * Add a flow to match dst-IP prefix and rewrite MAC for one IP prefix
+ * to all other border switches
+ */
+ private void addPrefixFlows(Prefix prefix, Interface egressInterface,
+ MACAddress nextHopMacAddress) {
+ log.debug("Adding flows for prefix {}, next hop mac {}",
+ prefix, nextHopMacAddress);
+
+ FlowPath flowPath = new FlowPath();
+ flowPath.setInstallerId(new CallerId("SDNIP"));
+
+ // Set flowPath FlowPathType and FlowPathUserState
+ flowPath.setFlowPathType(FlowPathType.FP_TYPE_SHORTEST_PATH);
+ flowPath.setFlowPathUserState(FlowPathUserState.FP_USER_ADD);
+
+ // Insert dst-ip prefix based forwarding and MAC rewrite flow entry
+ // only to the first-host switches
+ FlowPathFlags flowPathFlags = new FlowPathFlags();
+ flowPathFlags.setFlags(FlowPathFlags.KEEP_ONLY_FIRST_HOP_ENTRY);
+ flowPath.setFlowPathFlags(flowPathFlags);
+
+ // Create the DataPath object: dstSwitchPort
+ SwitchPort dstPort = new SwitchPort();
+ dstPort.setDpid(new Dpid(egressInterface.getDpid()));
+ dstPort.setPort(new Port(egressInterface.getPort()));
+
+ // We only need one flow mod per switch, so pick one interface on each switch
+ Map<Long, Interface> srcInterfaces = new HashMap<Long, Interface>();
+ for (Interface intf : interfaces.values()) {
+ if (!srcInterfaces.containsKey(intf.getDpid())
+ && !intf.equals(egressInterface)) {
+ srcInterfaces.put(intf.getDpid(), intf);
+ }
+ }
+ for (Interface srcInterface : srcInterfaces.values()) {
+
+ if (egressInterface.equals(srcInterface)){
+ continue;
+ }
+
+ // Create flowPath FlowId
+ flowPath.setFlowId(new FlowId());
+
+ // Create DataPath object: srcSwitchPort
+ SwitchPort srcPort = new SwitchPort();
+ srcPort.setDpid(new Dpid(srcInterface.getDpid()));
+ srcPort.setPort(new Port(srcInterface.getPort()));
+
+ DataPath dataPath = new DataPath();
+ dataPath.setSrcPort(srcPort);
+ dataPath.setDstPort(dstPort);
+ flowPath.setDataPath(dataPath);
+
+ // Create flow path matching condition(s): IPv4 Prefix
+ FlowEntryMatch flowEntryMatch = new FlowEntryMatch();
+ flowEntryMatch.enableEthernetFrameType(Ethernet.TYPE_IPv4);
+ IPv4Net dstIPv4Net= new IPv4Net(prefix.toString());
+ flowEntryMatch.enableDstIPv4Net(dstIPv4Net);
+ flowPath.setFlowEntryMatch(flowEntryMatch);
+
+ /*
+ * Create the Flow Entry Action(s): dst-MAC rewrite action
+ */
+ FlowEntryActions flowEntryActions = new FlowEntryActions();
+ FlowEntryAction flowEntryAction1 = new FlowEntryAction();
+ flowEntryAction1.setActionSetEthernetDstAddr(nextHopMacAddress);
+ // flowEntryAction1.actionSetEthernetDstAddr(nextHopMacAddress);
+ flowEntryActions.addAction(flowEntryAction1);
+ flowPath.setFlowEntryActions(flowEntryActions);
+
+ // Flow Path installation, only to first hop switches
+ // TODO: Add the flow by using the new Path Intent framework
+ /*
+ if (flowManagerService.addFlow(flowPath) == null) {
+ log.error("Failed to install flow path to the first hop for " +
+ "prefix: {}, nextHopMacAddress: {}", prefix.getAddress(),
+ nextHopMacAddress);
+ }
+ else {
+ log.debug("Successfully installed flow path to the first hop " +
+ "for prefix: {}, nextHopMacAddress: {}", prefix.getAddress(),
+ nextHopMacAddress);
+
+ pushedFlowIds.put(prefix, flowPath.flowId());
+ }
+ */
+ }
+ }
+
+ public synchronized void processRibDelete(RibUpdate update) {
+ Prefix prefix = 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
+ */
+ _processDeletePrefix(prefix, update.getRibEntry());
+ }
+ }
+
+ private void _processDeletePrefix(Prefix prefix, RibEntry ribEntry) {
+ deletePrefixFlows(prefix);
+
+ log.debug("Deleting {} to {}", prefix, ribEntry.getNextHop());
+
+ if (!bgpPeers.containsKey(ribEntry.getNextHop())) {
+ log.debug("Getting path for route with non-peer nexthop");
+ Path path = prefixToPath.remove(prefix);
+
+ if (path != null) {
+ //path could be null if we added to the Ptree but didn't push
+ //flows yet because we were waiting to resolve ARP
+
+ path.decrementUsers();
+ if (path.getUsers() <= 0 && !path.isPermanent()) {
+ deletePath(path);
+ pushedPaths.remove(path.getDstIpAddress());
+ }
+ }
+ }
+ }
+
+ // TODO have not tested this module
+ private void deletePrefixFlows(Prefix prefix) {
+ log.debug("Deleting flows for prefix {}", prefix);
+
+ Collection<FlowId> flowIds = pushedFlowIds.removeAll(prefix);
+ for (FlowId flowId : flowIds) {
+ // TODO: Delete the flow by using the new Path Intent framework
+ /*
+ if (log.isTraceEnabled()) {
+ //Trace the flow status by flowPath in the switch before deleting it
+ log.trace("Pushing a DELETE flow mod to flowPath : {}",
+ flowManagerService.getFlow(flowId).toString());
+ }
+
+ if( flowManagerService.deleteFlow(flowId))
+ {
+ log.debug("Successfully deleted FlowId: {}",flowId);
+ }
+ else
+ {
+ log.debug("Failed to delete FlowId: {}",flowId);
+ }
+ */
+ }
+ }
+
+ // TODO need to record the path and then delete here
+ private void deletePath(Path path) {
+ log.debug("Deleting flows for path to {}",
+ path.getDstIpAddress().getHostAddress());
+
+ // TODO need update
+ /*for (PushedFlowMod pfm : path.getFlowMods()) {
+ if (log.isTraceEnabled()) {
+ log.trace("Pushing a DELETE flow mod to {}, dst MAC {}",
+ new Object[] {HexString.toHexString(pfm.getDpid()),
+ HexString.toHexString(pfm.getFlowMod().getMatch().getDataLayerDestination())
+ });
+ }
+
+ sendDeleteFlowMod(pfm.getFlowMod(), pfm.getDpid());
+ }*/
+ }
+
+
+ //TODO test next-hop changes
+ //TODO check delete/add synchronization
+
+ /**
+ * On startup, we need to calculate a full mesh of paths between all gateway
+ * switches
+ */
+ private void setupFullMesh(){
+ //For each border router, calculate and install a path from every other
+ //border switch to said border router. However, don't install the entry
+ //in to the first hop switch, as we need to install an entry to rewrite
+ //for each prefix received. This will be done later when prefixes have
+ //actually been received.
+
+ for (BgpPeer peer : bgpPeers.values()) {
+ Interface peerInterface = interfaces.get(peer.getInterfaceName());
+
+ //We know there's not already a Path here pushed, because this is
+ //called before all other routing
+ Path path = new Path(peerInterface, peer.getIpAddress());
+ path.setPermanent();
+
+ //See if we know the MAC address of the peer. If not we can't
+ //do anything until we learn it
+ // TODO: Fix the code below after deviceStorage was removed
+ MACAddress macAddress = null;
+ /*
+ IDeviceObject nextHopDevice =
+ deviceStorage.getDeviceByIP(InetAddresses.coerceToInteger(peer.getIpAddress()));
+
+ if(nextHopDevice == null){
+ log.debug("There is no DeviceObject for {}", peer.getIpAddress().getHostAddress());
+ //Put in the pending paths list first
+ pathsWaitingOnArp.put(peer.getIpAddress(), path);
+ proxyArp.sendArpRequest(peer.getIpAddress(), this, true);
+ continue;
+ }
+
+ macAddress = MACAddress.valueOf(nextHopDevice.getMACAddress());
+ */
+
+ if (macAddress == null) {
+ log.debug("Don't know MAC for {}", peer.getIpAddress().getHostAddress());
+ //Put in the pending paths list first
+ pathsWaitingOnArp.put(peer.getIpAddress(), path);
+ proxyArp.sendArpRequest(peer.getIpAddress(), this, true);
+ continue;
+ }
+
+ //If we know the MAC, lets go ahead and push the paths to this peer
+ calculateAndPushPath(path, macAddress);
+ }
+ }
+
+ private void calculateAndPushPath(Path path, MACAddress dstMacAddress) {
+ Interface dstInterface = path.getDstInterface();
+
+ log.debug("Setting up path to {}, {}", path.getDstIpAddress().getHostAddress(),
+ dstMacAddress);
+
+ FlowPath flowPath = new FlowPath();
+
+ flowPath.setInstallerId(new CallerId("SDNIP"));
+
+ // Set flowPath FlowPathType and FlowPathUserState
+ flowPath.setFlowPathType(FlowPathType.FP_TYPE_SHORTEST_PATH);
+ flowPath.setFlowPathUserState(FlowPathUserState.FP_USER_ADD);
+
+ // Insert the dest-mac based forwarding flow entry to the non-first-hop switches
+ FlowPathFlags flowPathFlags = new FlowPathFlags();
+ flowPathFlags.setFlags(FlowPathFlags.DISCARD_FIRST_HOP_ENTRY);
+ flowPath.setFlowPathFlags(flowPathFlags);
+
+ // Create the DataPath object: dstSwitchPort
+ SwitchPort dstPort = new SwitchPort();
+ dstPort.setDpid(new Dpid(dstInterface.getDpid()));
+ dstPort.setPort(new Port(dstInterface.getPort()));
+
+ for (Interface srcInterface : interfaces.values()) {
+
+ if (dstInterface.equals(srcInterface)){
+ continue;
+ }
+
+ // Create flowPath FlowId
+ flowPath.setFlowId(new FlowId());
+
+ // Create the DataPath object: srcSwitchPort
+ SwitchPort srcPort = new SwitchPort();
+ srcPort.setDpid(new Dpid(srcInterface.getDpid()));
+ srcPort.setPort(new Port(srcInterface.getPort()));
+
+ DataPath dataPath = new DataPath();
+ dataPath.setSrcPort(srcPort);
+ dataPath.setDstPort(dstPort);
+ flowPath.setDataPath(dataPath);
+
+ // Create the Flow Path Match condition(s)
+ FlowEntryMatch flowEntryMatch = new FlowEntryMatch();
+ flowEntryMatch.enableEthernetFrameType(Ethernet.TYPE_IPv4);
+ flowEntryMatch.enableDstMac(dstMacAddress);
+ flowPath.setFlowEntryMatch(flowEntryMatch);
+
+ // NOTE: No need to add ACTION_OUTPUT. It is implied when creating
+ // Shortest Path Flow, and is always the last action for the Flow Entries
+ log.debug("FlowPath of MAC based forwarding: {}", flowPath.toString());
+ // TODO: Add the flow by using the new Path Intent framework
+ /*
+ if (flowManagerService.addFlow(flowPath) == null) {
+ log.error("Failed to set up MAC based forwarding path to {}, {}",
+ path.getDstIpAddress().getHostAddress(),dstMacAddress);
+ }
+ else {
+ log.debug("Successfully set up MAC based forwarding path to {}, {}",
+ path.getDstIpAddress().getHostAddress(),dstMacAddress);
+ }
+ */
+ }
+ }
+
+ /**
+ * Pre-actively install all BGP traffic paths from BGP host attachment point
+ * in SDN network to all the virtual gateways to BGP peers in other networks
+ */
+ private void setupBgpPaths(){
+
+ for (BgpPeer bgpPeer : bgpPeers.values()){
+
+ FlowPath flowPath = new FlowPath();
+ flowPath.setInstallerId(new CallerId("SDNIP"));
+
+ // Set flowPath FlowPathType and FlowPathUserState
+ flowPath.setFlowPathType(FlowPathType.FP_TYPE_SHORTEST_PATH);
+ flowPath.setFlowPathUserState(FlowPathUserState.FP_USER_ADD);
+
+ // Install flow paths between BGPd and its peers
+ // There is no need to set the FlowPathFlags
+ flowPath.setFlowPathFlags(new FlowPathFlags(0));
+
+ Interface peerInterface = interfaces.get(bgpPeer.getInterfaceName());
+
+ // Create the Flow Path Match condition(s)
+ FlowEntryMatch flowEntryMatch = new FlowEntryMatch();
+ flowEntryMatch.enableEthernetFrameType(Ethernet.TYPE_IPv4);
+
+ // Match both source address and dest address
+ IPv4Net dstIPv4Net= new IPv4Net(bgpPeer.getIpAddress().getHostAddress()+"/32");
+ flowEntryMatch.enableDstIPv4Net(dstIPv4Net);
+
+ IPv4Net srcIPv4Net= new IPv4Net(peerInterface.getIpAddress().getHostAddress()+"/32");
+ flowEntryMatch.enableSrcIPv4Net(srcIPv4Net);
+
+ // Match TCP protocol
+ flowEntryMatch.enableIpProto(IPv4.PROTOCOL_TCP);
+
+ // Match destination TCP port
+ flowEntryMatch.enableDstTcpUdpPort(BGP_PORT);
+ flowPath.setFlowEntryMatch(flowEntryMatch);
+
+ /**
+ * Create the DataPath: BGP -> BGP peer
+ */
+ // Flow path for src-TCP-port
+ DataPath dataPath = new DataPath();
+
+ SwitchPort srcPort = new SwitchPort();
+ srcPort.setDpid(bgpdAttachmentPoint.dpid());
+ srcPort.setPort(bgpdAttachmentPoint.port());
+ dataPath.setSrcPort(srcPort);
+
+ SwitchPort dstPort = new SwitchPort();
+ dstPort.setDpid(new Dpid(peerInterface.getDpid()));
+ dstPort.setPort(new Port(peerInterface.getSwitchPort().port()));
+ dataPath.setDstPort(dstPort);
+
+ flowPath.setDataPath(dataPath);
+
+ // TODO: Add the flow by using the new Path Intent framework
+ /*
+ if (flowManagerService.addFlow(flowPath) == null) {
+ log.error("Failed to set up path BGP -> peer {}"+"; dst-TCP-port:179",
+ bgpPeer.getIpAddress().getHostAddress());
+ }
+ else {
+ log.debug("Successfully set up path BGP -> peer {}"+"; dst-TCP-port:179",
+ bgpPeer.getIpAddress().getHostAddress());
+ }
+ */
+
+ // Disable dst-TCP-port, and set src-TCP-port
+ flowEntryMatch.disableDstTcpUdpPort();
+ flowEntryMatch.enableSrcTcpUdpPort(BGP_PORT);
+ flowPath.setFlowEntryMatch(flowEntryMatch);
+
+ // Create a new FlowId
+ flowPath.setFlowId(new FlowId());
+
+ // TODO: Add the flow by using the new Path Intent framework
+ /*
+ if (flowManagerService.addFlow(flowPath) == null) {
+ log.error("Failed to set up path BGP -> Peer {}" + "; src-TCP-port:179",
+ bgpPeer.getIpAddress().getHostAddress());
+ }
+ else {
+ log.debug("Successfully set up path BGP -> Peer {}" + "; src-TCP-port:179",
+ bgpPeer.getIpAddress().getHostAddress());
+ }
+ */
+
+ /**
+ * Create the DataPath: BGP <-BGP peer
+ */
+ // Reversed BGP flow path for src-TCP-port
+ flowPath.setFlowId(new FlowId());
+
+ DataPath reverse_dataPath = new DataPath();
+
+ SwitchPort reverse_dstPort = new SwitchPort();
+ reverse_dstPort.setDpid(bgpdAttachmentPoint.dpid());
+ reverse_dstPort.setPort(bgpdAttachmentPoint.port());
+ reverse_dataPath.setDstPort(reverse_dstPort);
+
+ SwitchPort reverse_srcPort = new SwitchPort();
+ reverse_srcPort.setDpid(new Dpid(peerInterface.getDpid()));
+ reverse_srcPort.setPort(new Port(peerInterface.getSwitchPort().port()));
+ reverse_dataPath.setSrcPort(reverse_srcPort);
+ flowPath.setDataPath(reverse_dataPath);
+
+ // reverse the dst IP and src IP addresses
+ flowEntryMatch.enableDstIPv4Net(srcIPv4Net);
+ flowEntryMatch.enableSrcIPv4Net(dstIPv4Net);
+ flowPath.setFlowEntryMatch(flowEntryMatch);
+
+ log.debug("Reversed BGP FlowPath: {}", flowPath.toString());
+
+ // TODO: Add the flow by using the new Path Intent framework
+ /*
+ if (flowManagerService.addFlow(flowPath) == null) {
+
+ log.error("Failed to set up path BGP <- Peer {}" + "; src-TCP-port:179",
+ bgpPeer.getIpAddress().getHostAddress());
+ }
+ else {
+ log.debug("Successfully set up path BGP <- Peer {}" + "; src-TCP-port:179",
+ bgpPeer.getIpAddress().getHostAddress());
+ }
+ */
+
+ // Reversed BGP flow path for dst-TCP-port
+ flowPath.setFlowId(new FlowId());
+
+ // Disable src-TCP-port, and set the dst-TCP-port
+ flowEntryMatch.disableSrcTcpUdpPort();
+ flowEntryMatch.enableDstTcpUdpPort(BGP_PORT);
+ flowPath.setFlowEntryMatch(flowEntryMatch);
+
+ log.debug("Reversed BGP FlowPath: {}", flowPath.toString());
+
+ // TODO: Add the flow by using the new Path Intent framework
+ /*
+ if (flowManagerService.addFlow(flowPath) == null) {
+ log.error("Failed to setting up path BGP <- Peer {}" + "; dst-TCP-port:179",
+ bgpPeer.getIpAddress().getHostAddress());
+ }
+ else {
+ log.debug("Successfully setting up path BGP <- Peer {}" + "; dst-TCP-port:179",
+ bgpPeer.getIpAddress().getHostAddress());
+ }
+ */
+
+ /**
+ * ICMP paths between BGPd and its peers
+ */
+ //match ICMP protocol BGP <- Peer
+ flowPath.setFlowId(new FlowId());
+
+ flowEntryMatch.enableIpProto(IPv4.PROTOCOL_ICMP);
+ flowEntryMatch.disableSrcTcpUdpPort();
+ flowEntryMatch.disableDstTcpUdpPort();
+
+ flowPath.setFlowEntryMatch(flowEntryMatch);
+
+ flowPath.setDataPath(reverse_dataPath);
+
+ log.debug("Reversed ICMP FlowPath: {}", flowPath.toString());
+
+ // TODO: Add the flow by using the new Path Intent framework
+ /*
+ if (flowManagerService.addFlow(flowPath) == null) {
+
+ log.error("Failed to set up ICMP path BGP <- Peer {}",
+ bgpPeer.getIpAddress().getHostAddress());
+ }
+ else {
+ log.debug("Successfully set up ICMP path BGP <- Peer {}",
+ bgpPeer.getIpAddress().getHostAddress());
+ }
+ */
+
+ //match ICMP protocol BGP -> Peer
+ flowPath.setFlowId(new FlowId());
+
+ flowEntryMatch.enableDstIPv4Net(dstIPv4Net);
+ flowEntryMatch.enableSrcIPv4Net(srcIPv4Net);
+ flowPath.setFlowEntryMatch(flowEntryMatch);
+
+ flowPath.setDataPath(dataPath);
+
+ log.debug("ICMP flowPath: {}", flowPath.toString());
+
+ // TODO: Add the flow by using the new Path Intent framework
+ /*
+ if (flowManagerService.addFlow(flowPath) == null) {
+
+ log.error("Failed to set up ICMP path BGP -> Peer {}",
+ bgpPeer.getIpAddress().getHostAddress());
+ }
+ else {
+ log.debug("Successfully set up ICMP path BGP -> Peer {}",
+ bgpPeer.getIpAddress().getHostAddress());
+ }
+ */
+ }
+ }
+
+ @Override
+ public void arpResponse(InetAddress ipAddress, MACAddress macAddress) {
+ log.debug("Received ARP response: {} => {}",
+ ipAddress.getHostAddress(), macAddress);
+
+ /*
+ * 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) {
+ Path path = pathsWaitingOnArp.remove(ipAddress);
+
+ if (path != null) {
+ log.debug("Pushing path to {} at {} on {}", new Object[] {
+ path.getDstIpAddress().getHostAddress(), macAddress,
+ path.getDstInterface().getSwitchPort()});
+ //These paths should always be to BGP peers. Paths to non-peers are
+ //handled once the first prefix is ready to push
+ if (pushedPaths.containsKey(path.getDstIpAddress())) {
+ //A path already got pushed to this endpoint while we were waiting
+ //for ARP. We'll copy over the permanent attribute if it is set on this path.
+ if (path.isPermanent()) {
+ pushedPaths.get(path.getDstIpAddress()).setPermanent();
+ }
+ }
+ else {
+ calculateAndPushPath(path, macAddress);
+ pushedPaths.put(path.getDstIpAddress(), path);
+ }
+ }
+
+ Set<RibUpdate> prefixesToPush = prefixesWaitingOnArp.removeAll(ipAddress);
+
+ for (RibUpdate update : prefixesToPush) {
+ //These will always be adds
+
+ 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.
+ _processRibAdd(update);
+ } else {
+ log.debug("Received ARP response, but {},{} is no longer in ptree",
+ update.getPrefix(), update.getRibEntry());
+ }
+ }
+ }
+ }
+
+ //TODO wait the priority module of the flow Manager
+ private void setupArpFlows() {
+ OFMatch match = new OFMatch();
+ match.setDataLayerType(Ethernet.TYPE_ARP);
+ match.setWildcards(match.getWildcards() & ~OFMatch.OFPFW_DL_TYPE);
+
+ OFFlowMod fm = new OFFlowMod();
+ fm.setMatch(match);
+
+ OFActionOutput action = new OFActionOutput();
+ action.setPort(OFPort.OFPP_CONTROLLER.getValue());
+ action.setMaxLength((short)0xffff);
+ List<OFAction> actions = new ArrayList<OFAction>(1);
+ actions.add(action);
+ fm.setActions(actions);
+
+ fm.setIdleTimeout((short)0)
+ .setHardTimeout((short)0)
+ .setBufferId(OFPacketOut.BUFFER_ID_NONE)
+ .setCookie(0)
+ .setCommand(OFFlowMod.OFPFC_ADD)
+ .setPriority(ARP_PRIORITY)
+ .setLengthU(OFFlowMod.MINIMUM_LENGTH + OFActionOutput.MINIMUM_LENGTH);
+
+ for (String strdpid : switches){
+ flowCache.write(HexString.toLong(strdpid), fm);
+ }
+ }
+ //TODO need update, waiting for the priority feature from flow Manager
+ private void setupDefaultDropFlows() {
+ OFFlowMod fm = new OFFlowMod();
+ fm.setMatch(new OFMatch());
+ fm.setActions(new ArrayList<OFAction>()); //No action means drop
+
+ fm.setIdleTimeout((short)0)
+ .setHardTimeout((short)0)
+ .setBufferId(OFPacketOut.BUFFER_ID_NONE)
+ .setCookie(0)
+ .setCommand(OFFlowMod.OFPFC_ADD)
+ .setPriority((short)0)
+ .setLengthU(OFFlowMod.MINIMUM_LENGTH);
+
+ OFFlowMod fmLLDP;
+ OFFlowMod fmBDDP;
+ try {
+ fmLLDP = fm.clone();
+ fmBDDP = fm.clone();
+ } catch (CloneNotSupportedException e1) {
+ log.error("Error cloning flow mod", e1);
+ return;
+ }
+
+ OFMatch matchLLDP = new OFMatch();
+ matchLLDP.setDataLayerType((short)0x88cc);
+ matchLLDP.setWildcards(matchLLDP.getWildcards() & ~ OFMatch.OFPFW_DL_TYPE);
+ fmLLDP.setMatch(matchLLDP);
+
+ OFMatch matchBDDP = new OFMatch();
+ matchBDDP.setDataLayerType((short)0x8942);
+ matchBDDP.setWildcards(matchBDDP.getWildcards() & ~ OFMatch.OFPFW_DL_TYPE);
+ fmBDDP.setMatch(matchBDDP);
+
+ OFActionOutput action = new OFActionOutput();
+ action.setPort(OFPort.OFPP_CONTROLLER.getValue());
+ action.setMaxLength((short)0xffff);
+ List<OFAction> actions = new ArrayList<OFAction>(1);
+ actions.add(action);
+
+ fmLLDP.setActions(actions);
+ fmBDDP.setActions(actions);
+
+ fmLLDP.setPriority(ARP_PRIORITY);
+ fmLLDP.setLengthU(OFFlowMod.MINIMUM_LENGTH + OFActionOutput.MINIMUM_LENGTH);
+ fmBDDP.setPriority(ARP_PRIORITY);
+ fmBDDP.setLengthU(OFFlowMod.MINIMUM_LENGTH + OFActionOutput.MINIMUM_LENGTH);
+
+ List<OFFlowMod> flowModList = new ArrayList<OFFlowMod>(3);
+ flowModList.add(fm);
+ flowModList.add(fmLLDP);
+ flowModList.add(fmBDDP);
+
+ for (String strdpid : switches){
+ flowCache.write(HexString.toLong(strdpid), flowModList);
+ }
+ }
+
+ private void beginRouting(){
+ log.debug("Topology is now ready, beginning routing function");
+ // TODO: Fix for the new Topology Network Graph
+ // topology = topologyNetService.newDatabaseTopology();
+
+ // Wait Pavlin's API. We need the following functions.
+ /*setupArpFlows();
+ setupDefaultDropFlows();*/
+
+ setupBgpPaths();
+ setupFullMesh();
+
+ //Suppress link discovery on external-facing router ports
+ for (Interface intf : interfaces.values()) {
+ linkDiscoveryService.AddToSuppressLLDPs(intf.getDpid(), intf.getPort());
+ }
+
+ bgpUpdatesExecutor.execute(new Runnable() {
+ @Override
+ public void run() {
+ doUpdatesThread();
+ }
+ });
+ }
+
+ // Before inserting the paths for BGP traffic, we should check
+ // whether all the switches in the configure file are discovered by onos.
+ private void checkSwitchesConnected(){
+ for (String dpid : switches){
+ // TODO: Fix the code below after topoSwitchSerice was removed
+ /*
+ Iterator<ISwitchObject> activeSwitches = topoSwitchService.
+ getActiveSwitches().iterator();
+ while(activeSwitches.hasNext())
+ {
+ ISwitchObject switchObject = activeSwitches.next();
+ if (switchObject.getDPID().equals(dpid)) {
+ break;
+ }
+ if(activeSwitches.hasNext() == false) {
+ log.debug("Not all switches are here yet");
+ return;
+ }
+ }
+ */
+ }
+ switchesConnected = true;
+ }
+
+ //Actually we only need to go half way round to verify full mesh connectivity
+ //(n^2)/2
+ private void checkTopologyReady(){
+ for (Interface dstInterface : interfaces.values()) {
+ for (Interface srcInterface : interfaces.values()) {
+ if (dstInterface.equals(srcInterface)) {
+ continue;
+ }
+
+ // TODO: Fix for the new Topology Network Graph
+ /*
+ DataPath shortestPath = topologyNetService.getDatabaseShortestPath(
+ srcInterface.getSwitchPort(), dstInterface.getSwitchPort());
+
+ if (shortestPath == null){
+ log.debug("Shortest path between {} and {} not found",
+ srcInterface.getSwitchPort(), dstInterface.getSwitchPort());
+ return;
+ }
+ */
+ }
+ }
+ topologyReady = true;
+ }
+
+ private void checkStatus(){
+ if (!switchesConnected){
+ checkSwitchesConnected();
+ }
+ boolean oldTopologyReadyStatus = topologyReady;
+ if (switchesConnected && !topologyReady){
+ checkTopologyReady();
+ }
+ if (!oldTopologyReadyStatus && topologyReady){
+ beginRouting();
+ }
+ }
+
+ private void doUpdatesThread() {
+ boolean interrupted = false;
+ try {
+ while (true) {
+ try {
+ RibUpdate update = ribUpdates.take();
+ switch (update.getOperation()){
+ case UPDATE:
+ if (validateUpdate(update)) {
+ processRibAdd(update);
+ }
+ else {
+ log.debug("Rib UPDATE out of order: {} via {}",
+ update.getPrefix(), update.getRibEntry().getNextHop());
+ }
+ break;
+ case DELETE:
+ if (validateUpdate(update)) {
+ processRibDelete(update);
+ }
+ else {
+ log.debug("Rib DELETE out of order: {} via {}",
+ update.getPrefix(), update.getRibEntry().getNextHop());
+ }
+ break;
+ }
+ } catch (InterruptedException e) {
+ log.debug("Interrupted while taking from updates queue", e);
+ interrupted = true;
+ } catch (Exception e) {
+ log.debug("exception", e);
+ }
+ }
+ } finally {
+ if (interrupted) {
+ Thread.currentThread().interrupt();
+ }
+ }
+ }
+
+ private boolean validateUpdate(RibUpdate update) {
+ RibEntry newEntry = update.getRibEntry();
+ RibEntry oldEntry = ptree.lookup(update.getPrefix());
+
+ //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
+ //POST then DELETE reordering.
+ //if (oldEntry == null || !newEntry.getNextHop().equals(oldEntry.getNextHop())) {
+ if (oldEntry == null) {
+ return true;
+ }
+
+ // This handles the case where routes are gathered in the initial
+ // request because they don't have sequence number info
+ if (newEntry.getSysUpTime() == -1 && newEntry.getSequenceNum() == -1) {
+ return true;
+ }
+
+ if (newEntry.getSysUpTime() > oldEntry.getSysUpTime()) {
+ return true;
+ }
+ else if (newEntry.getSysUpTime() == oldEntry.getSysUpTime()) {
+ if (newEntry.getSequenceNum() > oldEntry.getSequenceNum()) {
+ return true;
+ }
+ else {
+ return false;
+ }
+ }
+ else {
+ return false;
+ }
+ }
+
+ // 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...)
+ /*
+ @Override
+ public void topologyChanged() {
+ if (topologyReady) {
+ return;
+ }
+
+ boolean refreshNeeded = false;
+ for (LDUpdate ldu : topologyService.getLastLinkUpdates()){
+ if (!ldu.getOperation().equals(ILinkDiscovery.UpdateOperation.LINK_UPDATED)){
+ //We don't need to recalculate anything for just link updates
+ //They happen very frequently
+ refreshNeeded = true;
+ }
+
+ log.debug("Topo change {}", ldu.getOperation());
+
+ if (ldu.getOperation().equals(ILinkDiscovery.UpdateOperation.LINK_ADDED)){
+ synchronized (linkUpdates) {
+ linkUpdates.add(ldu);
+ }
+ }
+ }
+
+ if (refreshNeeded && !topologyReady){
+ topologyChangeDetectorTask.reschedule(TOPO_DETECTION_WAIT, TimeUnit.SECONDS);
+ }
+ }
+ */
+
+ @Override
+ public void addedSwitch(IOFSwitch sw) {
+ if (!topologyReady) {
+ sw.clearAllFlowMods();
+ }
+
+ flowCache.switchConnected(sw);
+ }
+
+ @Override
+ public void removedSwitch(IOFSwitch sw) {}
+
+ @Override
+ public void switchPortChanged(Long switchId) {}
+
+ @Override
+ public String getName() {
+ return "BgpRoute";
+ }
+
+ /*
+ * IConfigInfoService methods
+ */
+
+ @Override
+ public boolean isInterfaceAddress(InetAddress address) {
+ Interface intf = interfacePtrie.match(new Prefix(address.getAddress(), 32));
+ return (intf != null && intf.getIpAddress().equals(address));
+ }
+
+ @Override
+ public boolean inConnectedNetwork(InetAddress address) {
+ Interface intf = interfacePtrie.match(new Prefix(address.getAddress(), 32));
+ return (intf != null && !intf.getIpAddress().equals(address));
+ }
+
+ @Override
+ public boolean fromExternalNetwork(long inDpid, short inPort) {
+ for (Interface intf : interfaces.values()) {
+ if (intf.getDpid() == inDpid && intf.getPort() == inPort) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ @Override
+ public Interface getOutgoingInterface(InetAddress dstIpAddress) {
+ return interfacePtrie.match(new Prefix(dstIpAddress.getAddress(), 32));
+ }
+
+ @Override
+ public boolean hasLayer3Configuration() {
+ return !interfaces.isEmpty();
+ }
+
+ @Override
+ public MACAddress getRouterMacAddress() {
+ return bgpdMacAddress;
+ }
+
+ @Override
+ public short getVlan() {
+ return vlan;
+ }
+}
diff --git a/src/main/java/net/onrc/onos/apps/bgproute/BgpRouteResource.java b/src/main/java/net/onrc/onos/apps/bgproute/BgpRouteResource.java
new file mode 100644
index 0000000..cbb1634
--- /dev/null
+++ b/src/main/java/net/onrc/onos/apps/bgproute/BgpRouteResource.java
@@ -0,0 +1,176 @@
+package net.onrc.onos.apps.bgproute;
+
+import java.util.Iterator;
+
+import net.onrc.onos.apps.bgproute.RibUpdate.Operation;
+
+import org.restlet.resource.Delete;
+import org.restlet.resource.Get;
+import org.restlet.resource.Post;
+import org.restlet.resource.ServerResource;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+public class BgpRouteResource extends ServerResource {
+
+ protected final static Logger log = LoggerFactory.getLogger(BgpRouteResource.class);
+
+ @Get
+ public String get(String fmJson) {
+ String dest = (String) getRequestAttributes().get("dest");
+ String output = "";
+ IBgpRouteService bgpRoute = (IBgpRouteService)getContext().getAttributes().
+ get(IBgpRouteService.class.getCanonicalName());
+
+ if (dest != null) {
+ //TODO Needs to be changed to use the new RestClient.get().
+
+ // the dest here refers to router-id
+ //bgpdRestIp includes port number, such as 1.1.1.1:8080
+ String BGPdRestIp = bgpRoute.getBGPdRestIp();
+ String url="http://"+BGPdRestIp+"/wm/bgp/"+dest;
+
+ //Doesn't actually do anything with the response
+ RestClient.get(url);
+
+ output="Get rib from bgpd finished!\n";
+ return output;
+ }
+ else {
+ IPatriciaTrie<RibEntry> ptree = bgpRoute.getPtree();
+ output += "{\n \"rib\": [\n";
+ boolean printed = false;
+
+ synchronized(ptree) {
+ Iterator<IPatriciaTrie.Entry<RibEntry>> it = ptree.iterator();
+ while (it.hasNext()) {
+ IPatriciaTrie.Entry<RibEntry> entry = it.next();
+
+ if (printed == true) {
+ output += ",\n";
+ }
+
+ output += " {\"prefix\": \"" + entry.getPrefix() +"\", ";
+ output += "\"nexthop\": \"" + entry.getValue().getNextHop().getHostAddress() +"\"}";
+
+ printed = true;
+ }
+ }
+
+ output += "\n ]\n}\n";
+ }
+
+ return output;
+ }
+
+ @Post
+ public String store(String fmJson) {
+ IBgpRouteService bgpRoute = (IBgpRouteService) getContext().getAttributes().
+ get(IBgpRouteService.class.getCanonicalName());
+
+ String strSysuptime = (String) getRequestAttributes().get("sysuptime");
+ String strSequence = (String) getRequestAttributes().get("sequence");
+ String routerId = (String) getRequestAttributes().get("routerid");
+ String prefix = (String) getRequestAttributes().get("prefix");
+ String mask = (String) getRequestAttributes().get("mask");
+ String nexthop = (String) getRequestAttributes().get("nexthop");
+ String capability = (String) getRequestAttributes().get("capability");
+
+ log.debug("sysuptime: {}", strSysuptime);
+ log.debug("sequence: {}", strSequence);
+
+ String reply = "";
+
+ if (capability == null) {
+ // this is a prefix add
+ Prefix p;
+ long sysUpTime, sequenceNum;
+ try {
+ p = new Prefix(prefix, Integer.valueOf(mask));
+ sysUpTime = Long.parseLong(strSysuptime);
+ sequenceNum = Long.parseLong(strSequence);
+ } catch (NumberFormatException e) {
+ reply = "[POST: mask format is wrong]";
+ log.info(reply);
+ return reply + "\n";
+ } catch (IllegalArgumentException e1) {
+ reply = "[POST: prefix format is wrong]";
+ log.info(reply);
+ return reply + "\n";
+ }
+
+ RibEntry rib = new RibEntry(routerId, nexthop, sysUpTime, sequenceNum);
+
+ bgpRoute.newRibUpdate(new RibUpdate(Operation.UPDATE, p, rib));
+
+ reply = "[POST: " + prefix + "/" + mask + ":" + nexthop + "]";
+ log.info(reply);
+ }
+ else if(capability.equals("1")) {
+ reply = "[POST-capability: " + capability + "]\n";
+ log.info(reply);
+ // to store the number in the top node of the Ptree
+ }
+ else {
+ reply = "[POST-capability: " + capability + "]\n";
+ log.info(reply);
+ // to store the number in the top node of the Ptree
+ }
+
+ return reply + "\n";
+ }
+
+ @Delete
+ public String delete(String fmJson) {
+ IBgpRouteService bgpRoute = (IBgpRouteService)getContext().getAttributes().
+ get(IBgpRouteService.class.getCanonicalName());
+
+ String strSysuptime = (String) getRequestAttributes().get("sysuptime");
+ String strSequence = (String) getRequestAttributes().get("sequence");
+ String routerId = (String) getRequestAttributes().get("routerid");
+ String prefix = (String) getRequestAttributes().get("prefix");
+ String mask = (String) getRequestAttributes().get("mask");
+ String nextHop = (String) getRequestAttributes().get("nexthop");
+ String capability = (String) getRequestAttributes().get("capability");
+
+ log.debug("sysuptime: {}", strSysuptime);
+ log.debug("sequence: {}", strSequence);
+
+ String reply = "";
+
+ if (capability == null) {
+ // this is a prefix delete
+ Prefix p;
+ long sysUpTime, sequenceNum;
+ try {
+ p = new Prefix(prefix, Integer.valueOf(mask));
+ sysUpTime = Long.parseLong(strSysuptime);
+ sequenceNum = Long.parseLong(strSequence);
+ } catch (NumberFormatException e) {
+ reply = "[DELE: mask format is wrong]";
+ log.info(reply);
+ return reply + "\n";
+ } catch (IllegalArgumentException e1) {
+ reply = "[DELE: prefix format is wrong]";
+ log.info(reply);
+ return reply + "\n";
+ }
+
+ RibEntry r = new RibEntry(routerId, nextHop, sysUpTime, sequenceNum);
+
+ bgpRoute.newRibUpdate(new RibUpdate(Operation.DELETE, p, r));
+
+ reply =reply + "[DELE: " + prefix + "/" + mask + ":" + nextHop + "]";
+ }
+ else {
+ // clear the local rib: Ptree
+ bgpRoute.clearPtree();
+ reply = "[DELE-capability: " + capability + "; The local RibEntry is cleared!]\n";
+
+ // to store the number in the top node of the Ptree
+ }
+
+ log.info(reply);
+ return reply + "\n";
+ }
+}
diff --git a/src/main/java/net/onrc/onos/apps/bgproute/BgpRouteResourceSynch.java b/src/main/java/net/onrc/onos/apps/bgproute/BgpRouteResourceSynch.java
new file mode 100644
index 0000000..99ef302
--- /dev/null
+++ b/src/main/java/net/onrc/onos/apps/bgproute/BgpRouteResourceSynch.java
@@ -0,0 +1,71 @@
+package net.onrc.onos.apps.bgproute;
+
+
+import org.restlet.resource.Post;
+import org.restlet.resource.Delete;
+import org.restlet.resource.ServerResource;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+
+public class BgpRouteResourceSynch extends ServerResource {
+
+ protected final static Logger log = LoggerFactory
+ .getLogger(BgpRouteResource.class);
+
+ @Post
+ public String store(String fmJson) {
+
+ IBgpRouteService bgpRoute = (IBgpRouteService)getContext().getAttributes().
+ get(IBgpRouteService.class.getCanonicalName());
+
+ String router_id = (String) getRequestAttributes().get("routerid");
+ String prefix = (String) getRequestAttributes().get("prefix");
+ String mask = (String) getRequestAttributes().get("mask");
+ String nexthop = (String) getRequestAttributes().get("nexthop");
+
+ try{
+
+ String BGPdRestIp = bgpRoute.getBGPdRestIp();
+
+ //bgpdRestIp includes port number, such as 1.1.1.1:8080
+ RestClient.post("http://"+BGPdRestIp+"/wm/bgp/"+router_id+"/"+prefix+"/"+mask+"/"+nexthop);
+ }catch(Exception e)
+ {e.printStackTrace();}
+
+ String reply = "";
+ reply = "[POST: " + prefix + "/" + mask + ":" + nexthop + "/synch]";
+ log.info(reply);
+
+ return reply + "\n";
+
+
+ }
+
+ @Delete
+ public String delete(String fmJson) {
+ IBgpRouteService bgpRoute = (IBgpRouteService)getContext().getAttributes().
+ get(IBgpRouteService.class.getCanonicalName());
+
+ String routerId = (String) getRequestAttributes().get("routerid");
+ String prefix = (String) getRequestAttributes().get("prefix");
+ String mask = (String) getRequestAttributes().get("mask");
+ String nextHop = (String) getRequestAttributes().get("nexthop");
+
+ String reply = "";
+ try{
+ String BGPdRestIp = bgpRoute.getBGPdRestIp();
+
+ RestClient.delete("http://"+BGPdRestIp+"/wm/bgp/"+routerId+"/"+prefix+"/"+mask+"/"+nextHop);
+
+ }catch(Exception e)
+ {e.printStackTrace();}
+
+ reply =reply + "[DELE: " + prefix + "/" + mask + ":" + nextHop + "/synch]";
+
+ log.info(reply);
+
+
+ return reply + "\n";
+ }
+}
diff --git a/src/main/java/net/onrc/onos/apps/bgproute/BgpRouteWebRoutable.java b/src/main/java/net/onrc/onos/apps/bgproute/BgpRouteWebRoutable.java
new file mode 100644
index 0000000..2399c78
--- /dev/null
+++ b/src/main/java/net/onrc/onos/apps/bgproute/BgpRouteWebRoutable.java
@@ -0,0 +1,25 @@
+package net.onrc.onos.apps.bgproute;
+
+import org.restlet.Context;
+import org.restlet.Restlet;
+import org.restlet.routing.Router;
+
+import net.floodlightcontroller.restserver.RestletRoutable;
+
+public class BgpRouteWebRoutable implements RestletRoutable {
+ @Override
+ public Restlet getRestlet(Context context) {
+ Router router = new Router(context);
+ router.attach("/json", BgpRouteResource.class);
+ router.attach("/rib/{dest}", BgpRouteResource.class);
+ router.attach("/{sysuptime}/{sequence}/{routerid}/{prefix}/{mask}/{nexthop}", BgpRouteResource.class);
+ router.attach("/{routerid}/{prefix}/{mask}/{nexthop}/synch", BgpRouteResourceSynch.class);
+ router.attach("/{routerid}/{capability}", BgpRouteResource.class);
+ return router;
+ }
+
+ @Override
+ public String basePath() {
+ return "/wm/bgp";
+ }
+}
diff --git a/src/main/java/net/onrc/onos/apps/bgproute/Configuration.java b/src/main/java/net/onrc/onos/apps/bgproute/Configuration.java
new file mode 100644
index 0000000..6f02fe3
--- /dev/null
+++ b/src/main/java/net/onrc/onos/apps/bgproute/Configuration.java
@@ -0,0 +1,87 @@
+package net.onrc.onos.apps.bgproute;
+
+import java.util.Collections;
+import java.util.List;
+
+import net.floodlightcontroller.util.MACAddress;
+
+import org.codehaus.jackson.annotate.JsonProperty;
+import org.openflow.util.HexString;
+
+public class Configuration {
+ private long bgpdAttachmentDpid;
+ private short bgpdAttachmentPort;
+ private MACAddress bgpdMacAddress;
+ private short vlan;
+ private List<String> switches;
+ private List<Interface> interfaces;
+ private List<BgpPeer> peers;
+
+ public Configuration() {
+ // TODO Auto-generated constructor stub
+ }
+
+ public long getBgpdAttachmentDpid() {
+ return bgpdAttachmentDpid;
+ }
+
+ @JsonProperty("bgpdAttachmentDpid")
+ public void setBgpdAttachmentDpid(String bgpdAttachmentDpid) {
+ this.bgpdAttachmentDpid = HexString.toLong(bgpdAttachmentDpid);
+ }
+
+ public short getBgpdAttachmentPort() {
+ return bgpdAttachmentPort;
+ }
+
+ @JsonProperty("bgpdAttachmentPort")
+ public void setBgpdAttachmentPort(short bgpdAttachmentPort) {
+ this.bgpdAttachmentPort = bgpdAttachmentPort;
+ }
+
+ public MACAddress getBgpdMacAddress() {
+ return bgpdMacAddress;
+ }
+
+ @JsonProperty("bgpdMacAddress")
+ public void setBgpdMacAddress(String strMacAddress) {
+ this.bgpdMacAddress = MACAddress.valueOf(strMacAddress);
+ }
+
+ public List<String> getSwitches() {
+ return Collections.unmodifiableList(switches);
+ }
+
+ @JsonProperty("vlan")
+ public void setVlan(short vlan) {
+ this.vlan = vlan;
+ }
+
+ public short getVlan() {
+ return vlan;
+ }
+
+ @JsonProperty("switches")
+ public void setSwitches(List<String> switches) {
+ this.switches = switches;
+ }
+
+ public List<Interface> getInterfaces() {
+ return Collections.unmodifiableList(interfaces);
+ }
+
+ @JsonProperty("interfaces")
+ public void setInterfaces(List<Interface> interfaces) {
+ this.interfaces = interfaces;
+ }
+
+ public List<BgpPeer> getPeers() {
+ return Collections.unmodifiableList(peers);
+ }
+
+ @JsonProperty("bgpPeers")
+ public void setPeers(List<BgpPeer> peers) {
+ this.peers = peers;
+ }
+
+}
diff --git a/src/main/java/net/onrc/onos/apps/bgproute/FlowCache.java b/src/main/java/net/onrc/onos/apps/bgproute/FlowCache.java
new file mode 100644
index 0000000..31bbc95
--- /dev/null
+++ b/src/main/java/net/onrc/onos/apps/bgproute/FlowCache.java
@@ -0,0 +1,158 @@
+package net.onrc.onos.apps.bgproute;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+import net.floodlightcontroller.core.IFloodlightProviderService;
+import net.floodlightcontroller.core.IOFSwitch;
+
+import org.openflow.protocol.OFFlowMod;
+import org.openflow.protocol.OFMessage;
+import org.openflow.protocol.OFPort;
+import org.openflow.util.HexString;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+public class FlowCache {
+ private final static Logger log = LoggerFactory.getLogger(FlowCache.class);
+
+ private IFloodlightProviderService floodlightProvider;
+
+ private Map<Long, List<OFFlowMod>> flowCache;
+
+ private Comparator<OFFlowMod> cookieComparator = new Comparator<OFFlowMod>() {
+ @Override
+ public int compare(OFFlowMod fm1, OFFlowMod fm2) {
+ long difference = fm2.getCookie() - fm1.getCookie();
+
+ if (difference > 0) {
+ return 1;
+ }
+ else if (difference < 0) {
+ return -1;
+ }
+ else {
+ return 0;
+ }
+ }
+ };
+
+ public FlowCache(IFloodlightProviderService floodlightProvider) {
+ this.floodlightProvider = floodlightProvider;
+
+ flowCache = new HashMap<Long, List<OFFlowMod>>();
+ }
+
+ public synchronized void write(long dpid, OFFlowMod flowMod) {
+ List<OFFlowMod> flowModList = new ArrayList<OFFlowMod>(1);
+ flowModList.add(flowMod);
+ write(dpid, flowModList);
+ }
+
+ public synchronized void write(long dpid, List<OFFlowMod> flowMods) {
+ ensureCacheForSwitch(dpid);
+
+ List<OFFlowMod> clones = new ArrayList<OFFlowMod>(flowMods.size());
+
+ //Somehow the OFFlowMods we get passed in will change later on.
+ //No idea how this happens, but we can just clone to prevent problems
+ try {
+ for (OFFlowMod fm : flowMods) {
+ clones.add(fm.clone());
+ }
+ } catch (CloneNotSupportedException e) {
+ log.debug("Clone exception", e);
+ }
+
+ flowCache.get(dpid).addAll(clones);
+
+ IOFSwitch sw = floodlightProvider.getSwitches().get(dpid);
+
+ if (sw == null) {
+ log.debug("Switch not found when writing flow mods");
+ return;
+ }
+
+ List<OFMessage> msgList = new ArrayList<OFMessage>(clones.size());
+ msgList.addAll(clones);
+
+ try {
+ sw.write(msgList, null);
+ } catch (IOException e) {
+ log.error("Error writing to switch", e);
+ }
+
+
+ }
+
+ public synchronized void delete(long dpid, OFFlowMod flowMod) {
+ List<OFFlowMod> flowModList = new ArrayList<OFFlowMod>(1);
+ flowModList.add(flowMod);
+ delete(dpid, flowModList);
+ }
+
+ public synchronized void delete(long dpid, List<OFFlowMod> flowMods) {
+ ensureCacheForSwitch(dpid);
+
+ //Remove the flow mods from the cache first before we alter them
+ flowCache.get(dpid).removeAll(flowMods);
+
+ //Alter the original flow mods to make them delete flow mods
+ for (OFFlowMod fm : flowMods) {
+ fm.setCommand(OFFlowMod.OFPFC_DELETE_STRICT)
+ .setOutPort(OFPort.OFPP_NONE)
+ .setLengthU(OFFlowMod.MINIMUM_LENGTH);
+
+ fm.getActions().clear();
+ }
+
+ IOFSwitch sw = floodlightProvider.getSwitches().get(dpid);
+ if (sw == null) {
+ log.debug("Switch not found when writing flow mods");
+ return;
+ }
+
+ List<OFMessage> msgList = new ArrayList<OFMessage>(flowMods.size());
+ msgList.addAll(flowMods);
+
+ try {
+ sw.write(msgList, null);
+ } catch (IOException e) {
+ log.error("Error writing to switch", e);
+ }
+ }
+
+ //TODO can the Prontos handle being sent all flow mods in one message?
+ public synchronized void switchConnected(IOFSwitch sw) {
+ log.debug("Switch connected: {}", sw);
+
+ ensureCacheForSwitch(sw.getId());
+
+ List<OFFlowMod> flowMods = flowCache.get(sw.getId());
+
+ Collections.sort(flowMods, cookieComparator);
+
+ sw.clearAllFlowMods();
+
+ List<OFMessage> messages = new ArrayList<OFMessage>(flowMods.size());
+ messages.addAll(flowMods);
+
+ try {
+ sw.write(messages, null);
+ } catch (IOException e) {
+ log.error("Failure writing flow mods to switch {}",
+ HexString.toHexString(sw.getId()));
+ }
+ }
+
+ private void ensureCacheForSwitch(long dpid) {
+ if (!flowCache.containsKey(dpid)) {
+ flowCache.put(dpid, new ArrayList<OFFlowMod>());
+ }
+ }
+}
diff --git a/src/main/java/net/onrc/onos/apps/bgproute/IBgpRouteService.java b/src/main/java/net/onrc/onos/apps/bgproute/IBgpRouteService.java
new file mode 100644
index 0000000..56d5393
--- /dev/null
+++ b/src/main/java/net/onrc/onos/apps/bgproute/IBgpRouteService.java
@@ -0,0 +1,27 @@
+package net.onrc.onos.apps.bgproute;
+
+import net.floodlightcontroller.core.module.IFloodlightService;
+
+public interface IBgpRouteService extends IFloodlightService {
+
+ //public RibEntry lookupRib(byte[] dest);
+
+ //public Ptree getPtree();
+ public IPatriciaTrie<RibEntry> getPtree();
+
+ public String getBGPdRestIp();
+
+ public String getRouterId();
+
+ public void clearPtree();
+
+ /**
+ * Pass a RIB update to the {@link IBgpRouteService}
+ * @param update
+ */
+ public void newRibUpdate(RibUpdate update);
+
+ //TODO This functionality should be provided by some sort of Ptree listener framework
+ //public void prefixAdded(PtreeNode node);
+ //public void prefixDeleted(PtreeNode node);
+}
diff --git a/src/main/java/net/onrc/onos/apps/bgproute/IPatriciaTrie.java b/src/main/java/net/onrc/onos/apps/bgproute/IPatriciaTrie.java
new file mode 100644
index 0000000..854b340
--- /dev/null
+++ b/src/main/java/net/onrc/onos/apps/bgproute/IPatriciaTrie.java
@@ -0,0 +1,20 @@
+package net.onrc.onos.apps.bgproute;
+
+import java.util.Iterator;
+
+public interface IPatriciaTrie<V> {
+ public V put(Prefix prefix, V value);
+
+ public V lookup(Prefix prefix);
+
+ public V match(Prefix prefix);
+
+ public boolean remove(Prefix prefix, V value);
+
+ public Iterator<Entry<V>> iterator();
+
+ interface Entry<V> {
+ public Prefix getPrefix();
+ public V getValue();
+ }
+}
diff --git a/src/main/java/net/onrc/onos/apps/bgproute/Interface.java b/src/main/java/net/onrc/onos/apps/bgproute/Interface.java
new file mode 100644
index 0000000..fa5d568
--- /dev/null
+++ b/src/main/java/net/onrc/onos/apps/bgproute/Interface.java
@@ -0,0 +1,87 @@
+package net.onrc.onos.apps.bgproute;
+
+import java.net.InetAddress;
+
+import net.onrc.onos.ofcontroller.util.Dpid;
+import net.onrc.onos.ofcontroller.util.Port;
+import net.onrc.onos.ofcontroller.util.SwitchPort;
+
+import org.codehaus.jackson.annotate.JsonCreator;
+import org.codehaus.jackson.annotate.JsonProperty;
+import org.openflow.util.HexString;
+
+import com.google.common.net.InetAddresses;
+
+public class Interface {
+ private final String name;
+ private final long dpid;
+ private final short port;
+ private final InetAddress ipAddress;
+ private final int prefixLength;
+
+ @JsonCreator
+ public Interface (@JsonProperty("name") String name,
+ @JsonProperty("dpid") String dpid,
+ @JsonProperty("port") short port,
+ @JsonProperty("ipAddress") String ipAddress,
+ @JsonProperty("prefixLength") int prefixLength) {
+ this.name = name;
+ this.dpid = HexString.toLong(dpid);
+ this.port = port;
+ this.ipAddress = InetAddresses.forString(ipAddress);
+ this.prefixLength = prefixLength;
+ }
+
+ public String getName() {
+ return name;
+ }
+
+ public SwitchPort getSwitchPort() {
+ //TODO SwitchPort, Dpid and Port are mutable, but they could probably
+ //be made immutable which would prevent the need to copy
+ return new SwitchPort(new Dpid(dpid), new Port(port));
+ }
+
+ public long getDpid() {
+ return dpid;
+ }
+
+ public short getPort() {
+ return port;
+ }
+
+ public InetAddress getIpAddress() {
+ return ipAddress;
+ }
+
+ public int getPrefixLength() {
+ return prefixLength;
+ }
+
+ @Override
+ public boolean equals(Object other) {
+ if (other == null || !(other instanceof Interface)) {
+ return false;
+ }
+
+ Interface otherInterface = (Interface)other;
+
+ //Don't check switchPort as it's comprised of dpid and port
+ return (name.equals(otherInterface.name)) &&
+ (dpid == otherInterface.dpid) &&
+ (port == otherInterface.port) &&
+ (ipAddress.equals(otherInterface.ipAddress)) &&
+ (prefixLength == otherInterface.prefixLength);
+ }
+
+ @Override
+ public int hashCode() {
+ int hash = 17;
+ hash = 31 * hash + name.hashCode();
+ hash = 31 * hash + (int)(dpid ^ dpid >>> 32);
+ hash = 31 * hash + (int)port;
+ hash = 31 * hash + ipAddress.hashCode();
+ hash = 31 * hash + prefixLength;
+ return hash;
+ }
+}
diff --git a/src/main/java/net/onrc/onos/apps/bgproute/Path.java b/src/main/java/net/onrc/onos/apps/bgproute/Path.java
new file mode 100644
index 0000000..cd0b1b6
--- /dev/null
+++ b/src/main/java/net/onrc/onos/apps/bgproute/Path.java
@@ -0,0 +1,61 @@
+package net.onrc.onos.apps.bgproute;
+
+import java.net.InetAddress;
+import java.util.Collections;
+import java.util.List;
+
+/*
+ * A path is always assumed to be from all other interfaces (external-facing
+ * switchports) to the destination interface.
+ */
+
+public class Path {
+
+ private Interface dstInterface;
+ private InetAddress dstIpAddress;
+ private int numUsers = 0;
+
+ private List<PushedFlowMod> flowMods = null;
+ private boolean permanent = false;
+
+ public Path(Interface dstInterface, InetAddress dstIpAddress) {
+ this.dstInterface = dstInterface;
+ this.dstIpAddress = dstIpAddress;
+ }
+
+ public Interface getDstInterface() {
+ return dstInterface;
+ }
+
+ public InetAddress getDstIpAddress() {
+ return dstIpAddress;
+ }
+
+ public void incrementUsers() {
+ numUsers++;
+ }
+
+ public void decrementUsers() {
+ numUsers--;
+ }
+
+ public int getUsers() {
+ return numUsers;
+ }
+
+ public List<PushedFlowMod> getFlowMods() {
+ return Collections.unmodifiableList(flowMods);
+ }
+
+ public void setFlowMods(List<PushedFlowMod> flowMods) {
+ this.flowMods = flowMods;
+ }
+
+ public boolean isPermanent() {
+ return permanent;
+ }
+
+ public void setPermanent() {
+ permanent = true;
+ }
+}
diff --git a/src/main/java/net/onrc/onos/apps/bgproute/PatriciaTrie.java b/src/main/java/net/onrc/onos/apps/bgproute/PatriciaTrie.java
new file mode 100644
index 0000000..9badd11
--- /dev/null
+++ b/src/main/java/net/onrc/onos/apps/bgproute/PatriciaTrie.java
@@ -0,0 +1,506 @@
+package net.onrc.onos.apps.bgproute;
+
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+public class PatriciaTrie<V> implements IPatriciaTrie<V> {
+ 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;
+ }
+
+ @Override
+ public synchronized V put(Prefix prefix, V value) {
+ if (prefix == null || value == null) {
+ throw new NullPointerException();
+ }
+
+ if (prefix.getPrefixLength() > maxPrefixLength) {
+ throw new IllegalArgumentException(String.format(
+ "Prefix length %d is greater than max prefix length %d",
+ prefix.getPrefixLength(), maxPrefixLength));
+ }
+
+ 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.prefix.getPrefixLength() == prefix.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.
+ */
+ V oldValue = node.value;
+ node.value = value;
+ return oldValue;
+ }
+
+ match = node;
+
+ if (bit_check(prefix.getAddress(), node.prefix.getPrefixLength()) == true) {
+ node = node.right;
+ } else {
+ node = node.left;
+ }
+ }
+
+ Node add = null;
+
+ if (node == null) {
+ //add = new Node(p, r);
+ add = new Node(prefix);
+ add.value = value;
+
+ if (match != null) {
+ node_link(match, add);
+ } else {
+ top = add;
+ }
+ } else {
+ add = node_common(node, prefix.getAddress(), prefix.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() != prefix.getPrefixLength()) {
+ match = add;
+
+ //add = new Node(p, r);
+ add = new Node(prefix);
+ add.value = value;
+ node_link(match, add);
+ }
+ else {
+ add.value = value;
+ }
+ }
+
+ //If we added a new Node, there was no previous mapping
+ return null;
+ //return addReference(add);
+ }
+
+ /*exact match*/
+ @Override
+ public synchronized V lookup(Prefix prefix) {
+ if (prefix.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(prefix);
+
+ return node == null ? null : node.value;
+ }
+
+ /*closest containing prefix*/
+ @Override
+ public synchronized V match(Prefix prefix) {
+ //TODO
+ if (prefix.getPrefixLength() > maxPrefixLength) {
+ return null;
+ }
+
+ Node closestNode = findClosestNode(prefix);
+
+ return closestNode == null ? null : closestNode.value;
+ }
+
+ @Override
+ public synchronized boolean remove(Prefix prefix, V value) {
+ Node child;
+ Node parent;
+
+ if (prefix == null || value == null) {
+ return false;
+ }
+
+ Node node = findNode(prefix);
+
+ if (node == null || node.isAggregate() || !node.value.equals(value)) {
+ //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.value = 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;
+ }
+
+ @Override
+ public Iterator<Entry<V>> iterator() {
+ return new PatriciaTrieIterator(top);
+ }
+
+ private Node findNode(Prefix prefix) {
+ Node node = top;
+
+ while (node != null
+ && node.prefix.getPrefixLength() <= prefix.getPrefixLength()
+ && key_match(node.prefix.getAddress(), node.prefix.getPrefixLength(), prefix.getAddress(), prefix.getPrefixLength()) == true) {
+ if (node.prefix.getPrefixLength() == prefix.getPrefixLength()) {
+ //return addReference(node);
+ return node;
+ }
+
+ if (bit_check(prefix.getAddress(), node.prefix.getPrefixLength()) == true) {
+ node = node.right;
+ } else {
+ node = node.left;
+ }
+ }
+
+ 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
+ * 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 new Node(new Prefix(newPrefix, common_len));
+ //return add;
+ }
+
+ private class Node {
+ public Node parent = null;
+ public Node left = null;
+ public Node right = null;
+
+ public final Prefix prefix;
+ public V value;
+
+ //public Node(Prefix p, RibEntry r) {
+ // this.prefix = p;
+ // this.rib = r;
+ //}
+ public Node(Prefix p) {
+ this.prefix = p;
+ }
+
+ public boolean isAggregate() {
+ return value == null;
+ }
+
+ public Entry<V> getEntry() {
+ return new PatriciaTrieEntry(prefix, value);
+ }
+ }
+
+ private class PatriciaTrieEntry implements Entry<V> {
+ private Prefix prefix;
+ private V value;
+
+ public PatriciaTrieEntry(Prefix prefix, V value) {
+ this.prefix = prefix;
+ this.value = value;
+ }
+
+ @Override
+ public Prefix getPrefix() {
+ return prefix;
+ }
+
+ @Override
+ public V getValue() {
+ return value;
+ }
+ }
+
+ private class PatriciaTrieIterator implements Iterator<Entry<V>> {
+
+ 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.isAggregate()) {
+ current = findNext(current);
+ }
+ }
+
+ @Override
+ public boolean hasNext() {
+ if (current == null) {
+ return false;
+ }
+
+ if (!started) {
+ return true;
+ }
+
+ return findNext(current) != null;
+ }
+
+ @Override
+ public Entry<V> 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 value, 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.isAggregate()) {
+ return findNext(next);
+ }
+
+ return next;
+ }
+ }
+}
diff --git a/src/main/java/net/onrc/onos/apps/bgproute/Prefix.java b/src/main/java/net/onrc/onos/apps/bgproute/Prefix.java
new file mode 100644
index 0000000..8539759
--- /dev/null
+++ b/src/main/java/net/onrc/onos/apps/bgproute/Prefix.java
@@ -0,0 +1,135 @@
+package net.onrc.onos.apps.bgproute;
+
+import java.net.InetAddress;
+import java.net.UnknownHostException;
+import java.util.Arrays;
+
+import com.google.common.net.InetAddresses;
+
+public class Prefix {
+ 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();
+ }
+
+ address = canonicalizeAddress(addr, prefixLength);
+ this.prefixLength = prefixLength;
+
+ try {
+ inetAddress = InetAddress.getByAddress(address);
+ } catch (UnknownHostException e) {
+ throw new IllegalArgumentException();
+ }
+ }
+
+ public Prefix(String strAddress, int prefixLength) {
+ byte[] addr = null;
+ addr = InetAddresses.forString(strAddress).getAddress();
+
+ 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() {
+ return prefixLength;
+ }
+
+ public byte[] getAddress() {
+ return address;
+ }
+
+ @Override
+ public boolean equals(Object other) {
+ if (other == null || !(other instanceof Prefix)) {
+ return false;
+ }
+
+ Prefix otherPrefix = (Prefix) other;
+
+ return (Arrays.equals(address, otherPrefix.address)) &&
+ (prefixLength == otherPrefix.prefixLength);
+ }
+
+ @Override
+ public int hashCode() {
+ int hash = 17;
+ hash = 31 * hash + prefixLength;
+ hash = 31 * hash + Arrays.hashCode(address);
+ return hash;
+ }
+
+ @Override
+ public String toString() {
+ 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/apps/bgproute/Ptree.java b/src/main/java/net/onrc/onos/apps/bgproute/Ptree.java
new file mode 100644
index 0000000..682066a
--- /dev/null
+++ b/src/main/java/net/onrc/onos/apps/bgproute/Ptree.java
@@ -0,0 +1,322 @@
+package net.onrc.onos.apps.bgproute;
+
+/*
+ * TODO This Ptree needs to be refactored if we're going to use it permenantly.
+ *
+ * The biggest problem is it leaks PTreeNode references - these need to stay within
+ * the Ptree as they contain data fundamental to the structure of the tree.
+ * You should put RIB entries in and get RIB entries out.
+ * Also we need to get rid of the referencing scheme to determine when to delete nodes.
+ * Deletes should be explicit, and there's no need to keep track of references if
+ * we don't leak them out the the Ptree.
+ */
+public class Ptree {
+ private int maxKeyBits;
+ private int maxKeyOctets;
+ //private int refCount;
+ private PtreeNode top;
+ private byte maskBits[] = { (byte)0x00, (byte)0x80, (byte)0xc0, (byte)0xe0, (byte)0xf0, (byte)0xf8, (byte)0xfc, (byte)0xfe, (byte)0xff };
+
+ public Ptree(int max_key_bits) {
+ maxKeyBits = max_key_bits;
+ maxKeyOctets = bit_to_octet(max_key_bits);
+ //refCount = 0;
+ }
+
+ public synchronized PtreeNode acquire(byte [] key) {
+ return acquire(key, maxKeyBits);
+ }
+
+ public synchronized PtreeNode acquire(byte [] key, int key_bits) {
+ if (key_bits > maxKeyBits) {
+ return null;
+ }
+
+ PtreeNode node = top;
+ PtreeNode match = null;
+
+ while (node != null
+ && node.keyBits <= key_bits
+ && key_match(node.key, node.keyBits, key, key_bits) == true) {
+ if (node.keyBits == key_bits) {
+ return addReference(node);
+ }
+
+ match = node;
+
+ if (bit_check(key, node.keyBits) == true) {
+ node = node.right;
+ } else {
+ node = node.left;
+ }
+ }
+
+ PtreeNode add = null;
+
+ if (node == null) {
+ add = new PtreeNode(key, key_bits, maxKeyOctets);
+
+ if (match != null) {
+ node_link(match, add);
+ } else {
+ top = add;
+ }
+ } else {
+ add = node_common(node, key, key_bits);
+ if (add == null) {
+ return null;
+ }
+
+ if (match != null) {
+ node_link(match, add);
+ } else {
+ top = add;
+ }
+ node_link(add, node);
+
+ if (add.keyBits != key_bits) {
+ match = add;
+
+ add = new PtreeNode(key, key_bits, maxKeyOctets);
+ node_link(match, add);
+ }
+ }
+
+ return addReference(add);
+ }
+
+ public synchronized PtreeNode lookup(byte [] key, int key_bits) {
+ if (key_bits > maxKeyBits) {
+ return null;
+ }
+
+ PtreeNode node = top;
+
+ while (node != null
+ && node.keyBits <= key_bits
+ && key_match(node.key, node.keyBits, key, key_bits) == true) {
+ if (node.keyBits == key_bits) {
+ return addReference(node);
+ }
+
+ if (bit_check(key, node.keyBits) == true) {
+ node = node.right;
+ } else {
+ node = node.left;
+ }
+ }
+ return null;
+ }
+
+ public synchronized PtreeNode match(byte [] key, int key_bits) {
+ if (key_bits > maxKeyBits) {
+ return null;
+ }
+ PtreeNode node = top;
+ PtreeNode matched = null;
+
+ if(node!=null)
+
+ while (node != null
+ && node.keyBits <= key_bits
+ && key_match(node.key, node.keyBits, key, key_bits) == true) {
+ matched = node;
+
+ if (bit_check(key, node.keyBits) == true) {
+ node = node.right;
+ } else {
+ node = node.left;
+ }
+ }
+
+ if (matched != null) {
+ return addReference(matched);
+ }
+
+ return null;
+ }
+
+ public synchronized PtreeNode begin() {
+ if (top == null) {
+ return null;
+ }
+ return addReference(top);
+ }
+
+ public synchronized PtreeNode next(PtreeNode node) {
+ PtreeNode next;
+
+ if (node.left != null) {
+ next = node.left;
+ addReference(next);
+ delReference(node);
+ return next;
+ }
+ if (node.right != null) {
+ next = node.right;
+ addReference(next);
+ delReference(node);
+ return next;
+ }
+
+ PtreeNode 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;
+ }
+ node = node.parent;
+ }
+
+ delReference(start);
+
+ return null;
+ }
+
+ static public int bit_to_octet(int key_bits) {
+ return Math.max((key_bits + 7) / 8, 1);
+ }
+
+ private PtreeNode addReference(PtreeNode node) {
+ node.refCount++;
+ return node;
+ }
+
+ public synchronized void delReference(PtreeNode node) {
+ if (node.refCount > 0) {
+ node.refCount--;
+ }
+ if (node.refCount == 0) {
+ node_remove(node);
+ }
+ }
+
+ 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;
+ }
+
+ offset = (Math.min(key1_len, key2_len)) / 8;
+ 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(PtreeNode node, PtreeNode add) {
+ boolean bit = bit_check(add.key, node.keyBits);
+
+ if (bit == true) {
+ node.right = add;
+ } else {
+ node.left = add;
+ }
+ add.parent = node;
+ }
+
+ private PtreeNode node_common(PtreeNode node, byte [] key, int key_bits) {
+ int i;
+ int limit = Math.min(node.keyBits, key_bits) / 8;
+
+ for (i = 0; i < limit; i++) {
+ if (node.key[i] != key[i]) {
+ break;
+ }
+ }
+
+ int common_len = i * 8;
+ int boundary = 0;
+
+ if (common_len != key_bits) {
+ byte diff = (byte)(node.key[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++;
+ }
+ }
+
+ PtreeNode add = new PtreeNode(null, common_len, maxKeyOctets);
+
+ int j;
+ for (j = 0; j < i; j++)
+ add.key[j] = node.key[j];
+
+ if (boundary != 0)
+ add.key[j] = (byte)(node.key[j] & maskBits[add.keyBits % 8]);
+
+ return add;
+ }
+
+ private void node_remove(PtreeNode node) {
+ PtreeNode child;
+ PtreeNode parent;
+
+ if (node.left != null && node.right != null) {
+ return;
+ }
+
+ 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;
+ }
+
+ if (parent != null && parent.refCount == 0) {
+ node_remove(parent);
+ }
+ }
+}
diff --git a/src/main/java/net/onrc/onos/apps/bgproute/PtreeNode.java b/src/main/java/net/onrc/onos/apps/bgproute/PtreeNode.java
new file mode 100644
index 0000000..d20b7c4
--- /dev/null
+++ b/src/main/java/net/onrc/onos/apps/bgproute/PtreeNode.java
@@ -0,0 +1,44 @@
+package net.onrc.onos.apps.bgproute;
+
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+public class PtreeNode {
+ public PtreeNode parent;
+ public PtreeNode left;
+ public PtreeNode right;
+
+ public byte key[];
+ public int keyBits;
+
+ public int refCount;
+
+ public RibEntry rib;
+ protected final static Logger log = LoggerFactory.getLogger(BgpRoute.class);
+
+ PtreeNode(byte [] key, int key_bits, int max_key_octet) {
+ parent = null;
+ left = null;
+ right = null;
+ refCount = 0;
+ rib = null;
+ this.key = new byte[max_key_octet];
+ this.keyBits = key_bits;
+ log.debug("inside Ptreenode constructor key {} bits {}", key, key_bits);
+
+ int octet = Ptree.bit_to_octet(key_bits);
+ for (int i = 0; i < max_key_octet; i++) {
+ if (i < octet) {
+ if (key != null) {
+ log.debug(octet + ": filling key[{}] {}", i, key[i]);
+ this.key[i] = key[i];
+ } else {
+ log.debug("no filling, null key", i);
+ }
+ } else {
+ log.debug("filling key {} as 0", i);
+ this.key[i] = 0;
+ }
+ }
+ }
+}
diff --git a/src/main/java/net/onrc/onos/apps/bgproute/PushedFlowMod.java b/src/main/java/net/onrc/onos/apps/bgproute/PushedFlowMod.java
new file mode 100644
index 0000000..1908050
--- /dev/null
+++ b/src/main/java/net/onrc/onos/apps/bgproute/PushedFlowMod.java
@@ -0,0 +1,32 @@
+package net.onrc.onos.apps.bgproute;
+
+import org.openflow.protocol.OFFlowMod;
+
+/**
+ * Wraps up a DPID and a OFFlowMod so we know how to delete
+ * the flow if we have to.
+ *
+ * TODO This functionality should be handled by ONOS's flow layer in future.
+ *
+ */
+public class PushedFlowMod {
+ private long dpid;
+ private OFFlowMod flowMod;
+
+ public PushedFlowMod(long dpid, OFFlowMod flowMod) {
+ this.dpid = dpid;
+ try {
+ this.flowMod = flowMod.clone();
+ } catch (CloneNotSupportedException e) {
+ this.flowMod = flowMod;
+ }
+ }
+
+ public long getDpid() {
+ return dpid;
+ }
+
+ public OFFlowMod getFlowMod() {
+ return flowMod;
+ }
+}
\ No newline at end of file
diff --git a/src/main/java/net/onrc/onos/apps/bgproute/RestClient.java b/src/main/java/net/onrc/onos/apps/bgproute/RestClient.java
new file mode 100644
index 0000000..d085e6c
--- /dev/null
+++ b/src/main/java/net/onrc/onos/apps/bgproute/RestClient.java
@@ -0,0 +1,104 @@
+package net.onrc.onos.apps.bgproute;
+
+import java.io.BufferedReader;
+import java.io.IOException;
+import java.io.InputStreamReader;
+import java.net.HttpURLConnection;
+import java.net.MalformedURLException;
+import java.net.URL;
+
+import org.apache.commons.httpclient.ConnectTimeoutException;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+
+public class RestClient {
+ protected final static Logger log = LoggerFactory.getLogger(RestClient.class);
+
+ public static String get(String str) {
+ StringBuilder response = new StringBuilder();
+
+ try {
+
+ URL url = new URL(str);
+ HttpURLConnection conn = (HttpURLConnection) url.openConnection();
+ conn.setConnectTimeout(2 * 1000); //2 seconds
+ conn.setRequestMethod("GET");
+ conn.setRequestProperty("Accept", "application/json");
+
+ if (conn.getResponseCode() != 200) {
+ throw new RuntimeException("Failed : HTTP error code : "
+ + conn.getResponseCode());
+ }
+
+ if (!conn.getContentType().equals("application/json")){
+ log.warn("The content received from {} is not json", str);
+ }
+
+ BufferedReader br = new BufferedReader(new InputStreamReader((conn.getInputStream())));
+ String line;
+ while ((line = br.readLine()) != null) {
+ response.append(line);
+ }
+
+ br.close();
+ conn.disconnect();
+
+ } catch (MalformedURLException e) {
+ log.error("Malformed URL for GET request", e);
+ } catch (ConnectTimeoutException e) {
+ log.warn("Couldn't connect remote REST server");
+ } catch (IOException e) {
+ log.warn("Couldn't connect remote REST server");
+ }
+
+ return response.toString();
+ }
+
+ public static void post (String str) {
+
+ try {
+ URL url = new URL(str);
+ HttpURLConnection conn = (HttpURLConnection) url.openConnection();
+ conn.setDoOutput(true);
+ conn.setRequestMethod("POST");
+ conn.setRequestProperty("Content-Type", "application/json");
+
+ if (conn.getResponseCode() != 200) {
+ throw new RuntimeException("Failed : HTTP error code : "
+ + conn.getResponseCode());
+ }
+
+ conn.disconnect();
+
+ } catch (MalformedURLException e) {
+ log.error("Malformed URL for GET request", e);
+ } catch (IOException e) {
+ log.warn("Couldn't connect remote REST server");
+ }
+ }
+
+
+ public static void delete (String str) {
+
+ try {
+ URL url = new URL(str);
+ HttpURLConnection conn = (HttpURLConnection) url.openConnection();
+ conn.setRequestMethod("DELETE");
+ conn.setRequestProperty("Accept", "application/json");
+
+
+ if (conn.getResponseCode() != 200) {
+ throw new RuntimeException("Failed : HTTP error code : "
+ + conn.getResponseCode());
+ }
+
+ conn.disconnect();
+
+ } catch (MalformedURLException e) {
+ log.error("Malformed URL for GET request", e);
+ } catch (IOException e) {
+ log.warn("Couldn't connect remote REST server");
+ }
+ }
+}
diff --git a/src/main/java/net/onrc/onos/apps/bgproute/RibEntry.java b/src/main/java/net/onrc/onos/apps/bgproute/RibEntry.java
new file mode 100644
index 0000000..16f5aff
--- /dev/null
+++ b/src/main/java/net/onrc/onos/apps/bgproute/RibEntry.java
@@ -0,0 +1,80 @@
+package net.onrc.onos.apps.bgproute;
+
+import java.net.InetAddress;
+
+import com.google.common.net.InetAddresses;
+
+public class RibEntry {
+ private final InetAddress routerId;
+ private final InetAddress nextHop;
+
+ /*
+ * Store the sequence number information provided on the update here for
+ * now. I think this *should* really be in the RibUpdate, and we should
+ * store RibUpdates in the Ptrie. But, that's a bigger change to change
+ * what the Ptrie stores.
+ */
+ private final long sysUpTime;
+ private final long sequenceNum;
+
+ /*
+ * Marker for RibEntries where we don't have sequence number info.
+ * The user of this class should make sure they don't check this data
+ * if they don't provide it.
+ */
+ private final static long NULL_TIME = -1;
+
+ public RibEntry(InetAddress routerId, InetAddress nextHop) {
+ this.routerId = routerId;
+ this.nextHop = nextHop;
+ sequenceNum = NULL_TIME;
+ sysUpTime = NULL_TIME;
+ }
+
+ public RibEntry(String routerId, String nextHop) {
+ this.routerId = InetAddresses.forString(routerId);
+ this.nextHop = InetAddresses.forString(nextHop);
+ sequenceNum = NULL_TIME;
+ sysUpTime = NULL_TIME;
+ }
+
+ public RibEntry(String routerId, String nextHop, long sysUpTime
+ , long sequenceNum) {
+ this.routerId = InetAddresses.forString(routerId);
+ this.nextHop = InetAddresses.forString(nextHop);
+ this.sequenceNum = sequenceNum;
+ this.sysUpTime = sysUpTime;
+ }
+
+ public InetAddress getNextHop() {
+ return nextHop;
+ }
+
+ public long getSysUpTime() {
+ return sysUpTime;
+ }
+
+ public long getSequenceNum() {
+ return sequenceNum;
+ }
+
+ @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/apps/bgproute/RibUpdate.java b/src/main/java/net/onrc/onos/apps/bgproute/RibUpdate.java
new file mode 100644
index 0000000..d69a538
--- /dev/null
+++ b/src/main/java/net/onrc/onos/apps/bgproute/RibUpdate.java
@@ -0,0 +1,27 @@
+package net.onrc.onos.apps.bgproute;
+
+public class RibUpdate {
+ public enum Operation {UPDATE, DELETE};
+
+ private final Operation operation;
+ private final Prefix prefix;
+ private final RibEntry ribEntry;
+
+ public RibUpdate(Operation operation, Prefix prefix, RibEntry ribEntry) {
+ this.operation = operation;
+ this.prefix = prefix;
+ this.ribEntry = ribEntry;
+ }
+
+ public Operation getOperation() {
+ return operation;
+ }
+
+ public Prefix getPrefix() {
+ return prefix;
+ }
+
+ public RibEntry getRibEntry() {
+ return ribEntry;
+ }
+}