| package net.onrc.onos.ofcontroller.topology; |
| |
| import java.util.ArrayList; |
| import java.util.List; |
| import java.util.LinkedList; |
| import java.util.Map; |
| import java.util.TreeMap; |
| |
| import net.onrc.onos.graph.DBOperation; |
| import net.onrc.onos.graph.IDBOperation; |
| import net.onrc.onos.ofcontroller.core.INetMapTopologyObjects.IPortObject; |
| import net.onrc.onos.ofcontroller.core.INetMapTopologyObjects.ISwitchObject; |
| import net.onrc.onos.ofcontroller.core.ISwitchStorage.SwitchState; |
| |
| import org.apache.commons.lang.StringUtils; |
| import org.openflow.util.HexString; |
| import org.slf4j.Logger; |
| import org.slf4j.LoggerFactory; |
| |
| import com.tinkerpop.blueprints.Direction; |
| import com.tinkerpop.blueprints.Vertex; |
| |
| /** |
| * A class for storing Node and Link information for fast computation |
| * of shortest paths. |
| */ |
| class Node { |
| /** |
| * A class for storing Link information for fast computation of shortest |
| * paths. |
| */ |
| class Link { |
| public Node me; // The node this link originates from |
| public Node neighbor; // The neighbor node on the other side |
| public int myPort; // Local port ID for the link |
| public int neighborPort; // Neighbor port ID for the link |
| |
| /** |
| * Link constructor. |
| * |
| * @param me the node this link originates from. |
| * @param the neighbor node on the other side of the link. |
| * @param myPort local port ID for the link. |
| * @param neighborPort neighbor port ID for the link. |
| */ |
| public Link(Node me, Node neighbor, int myPort, int neighborPort) { |
| this.me = me; |
| this.neighbor = neighbor; |
| this.myPort = myPort; |
| this.neighborPort = neighborPort; |
| } |
| }; |
| |
| public long nodeId; // The node ID |
| // TODO Change type of PortNumber to Short |
| public TreeMap<Integer, Link> links; // The links from this node: |
| // (src PortNumber -> Link) |
| private TreeMap<Integer, Link> reverseLinksMap; // The links to this node: |
| // (dst PortNumber -> Link) |
| private TreeMap<Integer, Integer> portsMap; // The ports on this node: |
| // (PortNumber -> PortNumber) |
| // TODO: In the future will be: |
| // (PortNumber -> Port) |
| |
| /** |
| * Node constructor. |
| * |
| * @param nodeId the node ID. |
| */ |
| public Node(long nodeId) { |
| this.nodeId = nodeId; |
| links = new TreeMap<Integer, Link>(); |
| reverseLinksMap = new TreeMap<Integer, Link>(); |
| portsMap = new TreeMap<Integer, Integer>(); |
| } |
| |
| /** |
| * Get all ports. |
| * |
| * @return all ports. |
| */ |
| public Map<Integer, Integer> ports() { |
| return portsMap; |
| } |
| |
| /** |
| * Get the port for a given Port ID. |
| * |
| * Note: For now the port itself is just the Port ID. In the future |
| * it might contain more information. |
| * |
| * @return the port if found, otherwise null. |
| */ |
| public Integer getPort(int portId) { |
| return portsMap.get(portId); |
| } |
| |
| /** |
| * Add a port for a given Port ID. |
| * |
| * Note: For now the port itself is just the Port ID. In the future |
| * it might contain more information. |
| * |
| * @param portId the Port ID of the port to add. |
| * @return the added Port. |
| */ |
| Integer addPort(int portId) { |
| Integer port = new Integer(portId); |
| portsMap.put(portId, port); |
| return port; |
| } |
| |
| /** |
| * Remove a port for a given Port ID. |
| * |
| * NOTE: The outgoing and incoming links using this port are removed as |
| * well. |
| */ |
| void removePort(int portId) { |
| // Remove the outgoing link |
| Link link = getLink(portId); |
| if (link != null) { |
| link.neighbor.removeReverseLink(link); |
| removeLink(portId); |
| } |
| |
| // Remove the incoming link |
| Link reverseLink = reverseLinksMap.get(portId); |
| if (reverseLink != null) { |
| // NOTE: reverseLink.myPort is the neighbor's outgoing port |
| reverseLink.me.removeLink(reverseLink.myPort); |
| removeReverseLink(reverseLink); |
| } |
| |
| portsMap.remove(portId); |
| } |
| |
| /** |
| * Get a link on a port to a neighbor. |
| * |
| * @param myPortId the local port ID for the link to the neighbor. |
| * @return the link if found, otherwise null. |
| */ |
| public Link getLink(int myPortId) { |
| return links.get(myPortId); |
| } |
| |
| /** |
| * Add a link to a neighbor. |
| * |
| * @param myPortId the local port ID for the link to the neighbor. |
| * @param neighbor the neighbor for the link. |
| * @param neighborPortId the neighbor port ID for the link. |
| * @return the added Link. |
| */ |
| public Link addLink(int myPortId, Node neighbor, int neighborPortId) { |
| Link link = new Link(this, neighbor, myPortId, neighborPortId); |
| links.put(myPortId, link); |
| neighbor.addReverseLink(link); |
| return link; |
| } |
| |
| /** |
| * Add a reverse link from a neighbor. |
| * |
| * @param link the reverse link from a neighbor to add. |
| */ |
| private void addReverseLink(Link link) { |
| // NOTE: link.neghborPort is my port |
| reverseLinksMap.put(link.neighborPort, link); |
| } |
| |
| /** |
| * Remove a link to a neighbor. |
| * |
| * @param myPortId the local port ID for the link to the neighbor. |
| */ |
| public void removeLink(int myPortId) { |
| links.remove(myPortId); |
| } |
| |
| /** |
| * Remove a reverse link from a neighbor. |
| * |
| * @param link the reverse link from a neighbor to remove. |
| */ |
| private void removeReverseLink(Link link) { |
| // NOTE: link.neghborPort is my port |
| reverseLinksMap.remove(link.neighborPort); |
| } |
| }; |
| |
| /** |
| * A class for storing topology information. |
| */ |
| public class Topology { |
| private final static Logger log = LoggerFactory.getLogger(Topology.class); |
| |
| private Map<Long, Node> nodesMap; // The dpid->Node mapping |
| |
| /** |
| * Default constructor. |
| */ |
| public Topology() { |
| nodesMap = new TreeMap<Long, Node>(); |
| } |
| |
| /** |
| * Add a topology element to the topology. |
| * |
| * @param topologyElement the topology element to add. |
| * @return true if the topology was modified, otherwise false. |
| */ |
| public boolean addTopologyElement(TopologyElement topologyElement) { |
| boolean isModified = false; |
| |
| switch (topologyElement.getType()) { |
| case ELEMENT_SWITCH: { |
| // Add the switch |
| Node node = getNode(topologyElement.getSwitch()); |
| if (node == null) { |
| node = addNode(topologyElement.getSwitch()); |
| isModified = true; |
| } |
| break; |
| } |
| case ELEMENT_PORT: { |
| // Add the switch |
| Node node = getNode(topologyElement.getSwitch()); |
| if (node == null) { |
| node = addNode(topologyElement.getSwitch()); |
| isModified = true; |
| } |
| // Add the port for the switch |
| Integer port = node.getPort(topologyElement.getSwitchPort()); |
| if (port == null) { |
| node.addPort(topologyElement.getSwitchPort()); |
| isModified = true; |
| } |
| break; |
| } |
| case ELEMENT_LINK: { |
| // Add the "from" switch |
| Node fromNode = getNode(topologyElement.getFromSwitch()); |
| if (fromNode == null) { |
| fromNode = addNode(topologyElement.getFromSwitch()); |
| isModified = true; |
| } |
| // Add the "to" switch |
| Node toNode = getNode(topologyElement.getToSwitch()); |
| if (toNode == null) { |
| toNode = addNode(topologyElement.getToSwitch()); |
| isModified = true; |
| } |
| // Add the "from" port |
| Integer fromPort = fromNode.getPort(topologyElement.getFromPort()); |
| if (fromPort == null) { |
| fromNode.addPort(topologyElement.getFromPort()); |
| isModified = true; |
| } |
| // Add the "to" port |
| Integer toPort = fromNode.getPort(topologyElement.getToPort()); |
| if (toPort == null) { |
| toNode.addPort(topologyElement.getToPort()); |
| isModified = true; |
| } |
| Node.Link link = fromNode.getLink(topologyElement.getFromPort()); |
| if (link == null) { |
| fromNode.addLink(topologyElement.getFromPort(), |
| toNode, |
| topologyElement.getToPort()); |
| isModified = true; |
| } |
| |
| break; |
| } |
| case ELEMENT_UNKNOWN: |
| // TODO: Adding "assert(false);" here can be dangerous |
| break; |
| } |
| |
| return isModified; |
| } |
| |
| /** |
| * Remove a topology element from the topology. |
| * |
| * @param topologyElement the topology element to remove. |
| * @return true if the topology was modified, otherwise false. |
| */ |
| public boolean removeTopologyElement(TopologyElement topologyElement) { |
| boolean isModified = false; |
| |
| switch (topologyElement.getType()) { |
| case ELEMENT_SWITCH: { |
| // Remove the switch |
| Node node = getNode(topologyElement.getSwitch()); |
| if (node != null) { |
| removeNode(node); |
| isModified = true; |
| } |
| break; |
| } |
| case ELEMENT_PORT: { |
| // Find the switch |
| Node node = getNode(topologyElement.getSwitch()); |
| if (node == null) |
| break; |
| // Remove the port for the switch |
| Integer port = node.getPort(topologyElement.getSwitchPort()); |
| if (port != null) { |
| node.removePort(topologyElement.getSwitchPort()); |
| isModified = true; |
| } |
| break; |
| } |
| case ELEMENT_LINK: { |
| // Find the "from" switch |
| Node fromNode = getNode(topologyElement.getFromSwitch()); |
| if (fromNode == null) |
| break; |
| // Remove the link originating from the "from" port |
| Node.Link link = fromNode.getLink(topologyElement.getFromPort()); |
| if (link != null) { |
| fromNode.removeLink(topologyElement.getFromPort()); |
| isModified = true; |
| } |
| break; |
| } |
| case ELEMENT_UNKNOWN: |
| // TODO: Adding "assert(false);" here can be dangerous |
| break; |
| } |
| |
| return isModified; |
| } |
| |
| /** |
| * Get a node for a given Node ID. |
| * |
| * @param nodeId the Node ID to use. |
| * @return the corresponding Node if found, otherwise null. |
| */ |
| Node getNode(long nodeId) { |
| return nodesMap.get(nodeId); |
| } |
| |
| /** |
| * Add a node for a given Node ID. |
| * |
| * @param nodeId the Node ID to use. |
| * @return the added Node. |
| */ |
| Node addNode(long nodeId) { |
| Node node = new Node(nodeId); |
| nodesMap.put(nodeId, node); |
| return node; |
| } |
| |
| /** |
| * Remove an existing node. |
| * |
| * @param node the Node to remove. |
| */ |
| void removeNode(Node node) { |
| // |
| // Remove all ports one-by-one. This operation will also remove the |
| // incoming links originating from the neighbors. |
| // |
| // NOTE: We have to extract all Port IDs in advance, otherwise we |
| // cannot loop over the Ports collection and remove entries at the |
| // same time. |
| // TODO: If there is a large number of ports, the implementation |
| // below can be sub-optimal. It should be refactored as follows: |
| // 1. Modify removePort() to perform all the cleanup, except |
| // removing the Port entry from the portsMap |
| // 2. Call portsMap.clear() at the end of this method |
| // 3. In all other methods: if removePort() is called somewhere else, |
| // add an explicit removal of the Port entry from the portsMap. |
| // |
| List<Integer> allPortIdKeys = new LinkedList<Integer>(); |
| allPortIdKeys.addAll(node.ports().keySet()); |
| for (Integer portId : allPortIdKeys) |
| node.removePort(portId); |
| |
| nodesMap.remove(node.nodeId); |
| } |
| |
| /** |
| * Read topology state from the database. |
| * |
| * @param dbHandler the Graph Database handler to use. |
| */ |
| public void readFromDatabase(DBOperation dbHandler) { |
| // |
| // Fetch the relevant info from the Switch and Port vertices |
| // from the Titan Graph. |
| // |
| nodesMap.clear(); |
| |
| // Load all switches into Map |
| Iterable<ISwitchObject> switches = dbHandler.getAllSwitches(); |
| for (ISwitchObject switchObj : switches) { |
| // Ignore inactive ports |
| if (!switchObj.getState().equals(SwitchState.ACTIVE.toString())) { |
| continue; |
| } |
| Vertex nodeVertex = switchObj.asVertex(); |
| // |
| // The Switch info |
| // |
| String nodeDpid = nodeVertex.getProperty("dpid").toString(); |
| long nodeId = HexString.toLong(nodeDpid); |
| addNode(nodeId); |
| } |
| |
| // |
| // Get All Ports |
| // |
| Iterable<IPortObject> ports = dbHandler.getAllPorts(); //TODO: Add to DB operations |
| for (IPortObject myPortObj : ports) { |
| Vertex myPortVertex = myPortObj.asVertex(); |
| |
| // Ignore inactive ports |
| if (! myPortVertex.getProperty("state").toString().equals("ACTIVE")) { |
| continue; |
| } |
| |
| short myPort = 0; |
| String idStr = myPortObj.getPortId(); |
| String[] splitter = idStr.split(IDBOperation.PORT_ID_DELIM); |
| if (splitter.length != 2) { |
| log.error("Invalid port_id : {}", idStr); |
| continue; |
| } |
| String myDpid = splitter[0]; |
| myPort = Short.parseShort(splitter[1]); |
| long myId = HexString.toLong(myDpid); |
| Node me = nodesMap.get(myId); |
| |
| if (me == null) { |
| // cannot proceed ports and switches are out of sync |
| //TODO: Restart the whole read |
| continue; |
| } |
| |
| if (me.getPort(myPort) == null) { |
| me.addPort(myPort); |
| } else if (me.getLink(myPort) != null) { |
| // Link already added..probably by neighbor |
| continue; |
| } |
| |
| // |
| // The neighbor Port info |
| // |
| for (Vertex neighborPortVertex : myPortVertex.getVertices(Direction.OUT, "link")) { |
| // log.debug("state : {}", neighborPortVertex.getProperty("state")); |
| // log.debug("port id : {}", neighborPortVertex.getProperty("port_id")); |
| // Ignore inactive ports |
| if (! neighborPortVertex.getProperty("state").toString().equals("ACTIVE")) { |
| continue; |
| } |
| int neighborPort = 0; |
| idStr = neighborPortVertex.getProperty("port_id").toString(); |
| splitter = idStr.split(IDBOperation.PORT_ID_DELIM); |
| if (splitter.length != 2) { |
| log.error("Invalid port_id : {}", idStr); |
| continue; |
| } |
| String neighborDpid = splitter[0]; |
| neighborPort = Short.parseShort(splitter[1]); |
| long neighborId = HexString.toLong(neighborDpid); |
| Node neighbor = nodesMap.get(neighborId); |
| // log.debug("dpid {},{} port {}", neighborDpid, neighborId, neighborPort); |
| if (neighbor == null) { |
| continue; |
| } |
| me.addLink(myPort, neighbor, neighborPort); |
| } |
| } |
| dbHandler.commit(); |
| } |
| |
| |
| // Only for debug use |
| List<Long> logGetSw = new ArrayList<Long>(100); |
| List<Long> logGetPt = new ArrayList<Long>(100); |
| List<Long> logAddSw = new ArrayList<Long>(100); |
| List<Long> logAddPt = new ArrayList<Long>(100); |
| List<Long> logAddLk = new ArrayList<Long>(100); |
| List<Long> logCommit = new ArrayList<Long>(100); |
| List<Integer> logGetVertices = new ArrayList<Integer>(100); |
| List<Integer> logGetProperty = new ArrayList<Integer>(100); |
| public void readFromDatabaseBreakdown(DBOperation dbHandler) { |
| int getVerticesCount = 0; |
| int getPropertyCount = 0; |
| int getVCount_sw = 0; |
| int getVCount_pt = 0; |
| int getVCount_lk = 0; |
| int getPCount_sw = 0; |
| int getPCount_pt = 0; |
| int getPCount_lk = 0; |
| |
| // |
| // Fetch the relevant info from the Switch and Port vertices |
| // from the Titan Graph. |
| // |
| |
| nodesMap.clear(); |
| long t1 = System.nanoTime(); |
| |
| // Load all switches into Map |
| Iterable<ISwitchObject> switches = dbHandler.getAllSwitches(); |
| |
| long t2 = System.nanoTime(); |
| |
| long t_addSw = 0; |
| for (ISwitchObject switchObj : switches) { |
| long t3 = System.nanoTime(); |
| long t4; |
| |
| // Ignore inactive ports |
| ++getPropertyCount; |
| ++getPCount_sw; |
| if (!switchObj.getState().equals(SwitchState.ACTIVE.toString())) { |
| t4 = System.nanoTime(); |
| t_addSw += t4 - t3; |
| continue; |
| } |
| Vertex nodeVertex = switchObj.asVertex(); |
| // |
| // The Switch info |
| // |
| ++getPropertyCount; |
| ++getPCount_sw; |
| String nodeDpid = nodeVertex.getProperty("dpid").toString(); |
| long nodeId = HexString.toLong(nodeDpid); |
| addNode(nodeId); |
| t4 = System.nanoTime(); |
| t_addSw += t4 - t3; |
| } |
| |
| long t5 = System.nanoTime(); |
| // |
| // Get All Ports |
| // |
| Iterable<IPortObject> ports = dbHandler.getAllPorts(); //TODO: Add to DB operations |
| |
| long t6 = System.nanoTime(); |
| long t_addPort = 0; |
| long t_addLink = 0; |
| |
| for (IPortObject myPortObj : ports) { |
| long t7 = System.nanoTime(); |
| long t8; |
| Vertex myPortVertex = myPortObj.asVertex(); |
| |
| // Ignore inactive ports |
| ++getPropertyCount; |
| ++getPCount_pt; |
| if (! myPortVertex.getProperty("state").toString().equals("ACTIVE")) { |
| t8 = System.nanoTime(); |
| t_addPort += t8 - t7; |
| continue; |
| } |
| |
| short myPort = 0; |
| ++getPropertyCount; |
| ++getPCount_pt; |
| String idStr = myPortObj.getPortId(); |
| String[] splitter = idStr.split(IDBOperation.PORT_ID_DELIM); |
| if (splitter.length != 2) { |
| log.error("Invalid port_id : {}", idStr); |
| t8 = System.nanoTime(); |
| t_addPort += t8 - t7; |
| continue; |
| } |
| String myDpid = splitter[0]; |
| myPort = Short.parseShort(splitter[1]); |
| long myId = HexString.toLong(myDpid); |
| Node me = nodesMap.get(myId); |
| |
| if (me == null) { |
| // cannot proceed ports and switches are out of sync |
| //TODO: Restart the whole read |
| t8 = System.nanoTime(); |
| t_addPort += t8 - t7; |
| continue; |
| } |
| |
| if (me.getPort(myPort) == null) { |
| me.addPort(myPort); |
| } else if (me.getLink(myPort) != null) { |
| // Link already added..probably by neighbor |
| t8 = System.nanoTime(); |
| t_addPort += t8 - t7; |
| continue; |
| } |
| t8 = System.nanoTime(); |
| t_addPort += t8 - t7; |
| |
| // |
| // The neighbor Port info |
| // |
| ++getVerticesCount; |
| ++getVCount_pt; |
| for (Vertex neighborPortVertex : myPortVertex.getVertices(Direction.OUT, "link")) { |
| // log.debug("state : {}", neighborPortVertex.getProperty("state")); |
| // log.debug("port id : {}", neighborPortVertex.getProperty("port_id")); |
| |
| long t9 = System.nanoTime(); |
| long t10; |
| |
| // Ignore inactive ports |
| ++getPropertyCount; |
| ++getPCount_lk; |
| if (! neighborPortVertex.getProperty("state").toString().equals("ACTIVE")) { |
| t10 = System.nanoTime(); |
| t_addLink += t10 - t9; |
| continue; |
| } |
| int neighborPort = 0; |
| ++getPropertyCount; |
| ++getPCount_lk; |
| idStr = neighborPortVertex.getProperty("port_id").toString(); |
| splitter = idStr.split(IDBOperation.PORT_ID_DELIM); |
| if (splitter.length != 2) { |
| log.error("Invalid port_id : {}", idStr); |
| t10 = System.nanoTime(); |
| t_addLink += t10 - t9; |
| continue; |
| } |
| String neighborDpid = splitter[0]; |
| neighborPort = Short.parseShort(splitter[1]); |
| long neighborId = HexString.toLong(neighborDpid); |
| Node neighbor = nodesMap.get(neighborId); |
| // log.debug("dpid {},{} port {}", neighborDpid, neighborId, neighborPort); |
| if (neighbor == null) { |
| t10 = System.nanoTime(); |
| t_addLink += t10 - t9; |
| continue; |
| } |
| me.addLink(myPort, neighbor, neighborPort); |
| |
| t10 = System.nanoTime(); |
| t_addLink += t10 - t9; |
| } |
| } |
| long t11 = System.nanoTime(); |
| dbHandler.commit(); |
| long t12 = System.nanoTime(); |
| |
| logGetSw.add((t2-t1)/1000); |
| logGetPt.add((t6-t5)/1000); |
| logAddSw.add(t_addSw/1000); |
| logAddPt.add(t_addPort/1000); |
| logAddLk.add(t_addLink/1000); |
| logCommit.add((t12-t11)/1000); |
| logGetVertices.add(getVerticesCount); |
| logGetProperty.add(getPropertyCount); |
| log.debug("getVertices[N({}),P({}),L({})] getProperty[N({}),P({}),L({})]", |
| new Object[]{getVCount_sw,getVCount_pt,getVCount_lk, |
| getPCount_sw,getPCount_pt,getPCount_lk}); |
| } |
| |
| public void printMeasuredLog() { |
| log.debug("getsw: {}", StringUtils.join(logGetSw, ",")); |
| log.debug("getpt: {}", StringUtils.join(logGetPt, ",")); |
| log.debug("addsw: {}", StringUtils.join(logAddSw, ",")); |
| log.debug("addpt: {}", StringUtils.join(logAddPt, ",")); |
| log.debug("addlk: {}", StringUtils.join(logAddLk, ",")); |
| log.debug("commit: {}", StringUtils.join(logCommit, ",")); |
| log.debug("getvertices: {}", StringUtils.join(logGetVertices, ",")); |
| log.debug("getproperty: {}", StringUtils.join(logGetProperty, ",")); |
| } |
| |
| // Only for debug use |
| @Override |
| public String toString() { |
| long numNodes = nodesMap.size(); |
| long numLinks = 0; |
| for (Map.Entry<Long, Node> entry : nodesMap.entrySet()) { |
| Node n = entry.getValue(); |
| for (Map.Entry<Integer, Node.Link> linkEntry : n.links.entrySet()) { |
| if (n.nodeId > linkEntry.getValue().neighbor.nodeId) { |
| ++numLinks; |
| } |
| } |
| } |
| return "Topology has " + numNodes + " Nodes and " + numLinks + " Links."; |
| } |
| } |