| package net.onrc.onos.ofcontroller.topology; |
| |
| import java.util.Collections; |
| import java.util.HashMap; |
| import java.util.HashSet; |
| import java.util.LinkedList; |
| import java.util.List; |
| import java.util.Map; |
| import java.util.Queue; |
| import java.util.Set; |
| |
| import net.onrc.onos.graph.DBOperation; |
| import net.onrc.onos.ofcontroller.core.INetMapTopologyObjects.ISwitchObject; |
| import net.onrc.onos.ofcontroller.core.ISwitchStorage.SwitchState; |
| import net.onrc.onos.ofcontroller.util.DataPath; |
| import net.onrc.onos.ofcontroller.util.Dpid; |
| import net.onrc.onos.ofcontroller.util.FlowEntry; |
| import net.onrc.onos.ofcontroller.util.Port; |
| import net.onrc.onos.ofcontroller.util.SwitchPort; |
| |
| import org.openflow.util.HexString; |
| |
| import com.tinkerpop.blueprints.Direction; |
| import com.tinkerpop.blueprints.Vertex; |
| |
| /** |
| * Class to calculate a shortest DataPath between 2 SwitchPorts |
| * based on hops in Network Topology. |
| */ |
| public class ShortestPath { |
| /** |
| * Get the shortest path from a source to a destination by |
| * using the pre-populated local topology state prepared |
| * by method @ref TopologyManager.newDatabaseTopology(). |
| * |
| * For additional documentation and usage, see method |
| * @ref TopologyManager.newDatabaseTopology() |
| * |
| * @param topology the topology handler to use. |
| * @param src the source in the shortest path computation. |
| * @param dest the destination in the shortest path computation. |
| * @return the data path with the computed shortest path if |
| * found, otherwise null. |
| */ |
| public static DataPath getTopologyShortestPath( |
| Topology topology, |
| SwitchPort src, SwitchPort dest) { |
| DataPath result_data_path = new DataPath(); |
| |
| // Initialize the source and destination in the data path to return |
| result_data_path.setSrcPort(src); |
| result_data_path.setDstPort(dest); |
| |
| String dpid_src = src.dpid().toString(); |
| String dpid_dest = dest.dpid().toString(); |
| |
| // Get the source vertex |
| Node v_src = topology.getNode(src.dpid().value()); |
| if (v_src == null) { |
| return null; // Source vertex not found |
| } |
| |
| // Get the destination vertex |
| Node v_dest = topology.getNode(dest.dpid().value()); |
| if (v_dest == null) { |
| return null; // Destination vertex not found |
| } |
| |
| // |
| // Test whether we are computing a path from/to the same DPID. |
| // If "yes", then just add a single flow entry in the return result. |
| // However, if the "in" and "out" ports are same, return null. |
| // |
| if (dpid_src.equals(dpid_dest)) { |
| if (src.port().value() == dest.port().value()) |
| return null; // "In" and "Out" ports are same |
| FlowEntry flowEntry = new FlowEntry(); |
| flowEntry.setDpid(src.dpid()); |
| flowEntry.setInPort(src.port()); |
| flowEntry.setOutPort(dest.port()); |
| result_data_path.flowEntries().add(flowEntry); |
| return result_data_path; |
| } |
| |
| // |
| // Implement the Shortest Path computation by using Breath First Search |
| // |
| Set<Node> visitedSet = new HashSet<Node>(); |
| Queue<Node> processingList = new LinkedList<Node>(); |
| Map<Node, Node.Link> previousVertexMap = new HashMap<Node, Node.Link>(); |
| processingList.add(v_src); |
| visitedSet.add(v_src); |
| Boolean path_found = false; |
| while (! processingList.isEmpty()) { |
| Node nextVertex = processingList.poll(); |
| if (v_dest == nextVertex) { |
| path_found = true; |
| break; |
| } |
| for (Node.Link link : nextVertex.links.values()) { |
| Node child = link.neighbor; |
| if (! visitedSet.contains(child)) { |
| previousVertexMap.put(child, link); |
| visitedSet.add(child); |
| processingList.add(child); |
| } |
| } |
| } |
| if (! path_found) |
| return null; // No path found |
| |
| // Collect the path as a list of links |
| List<Node.Link> resultPath = new LinkedList<Node.Link>(); |
| Node previousVertex = v_dest; |
| while (! v_src.equals(previousVertex)) { |
| Node.Link currentLink = previousVertexMap.get(previousVertex); |
| resultPath.add(currentLink); |
| previousVertex = currentLink.me; |
| } |
| Collections.reverse(resultPath); |
| |
| // |
| // Loop through the result and prepare the return result |
| // as a list of Flow Entries. |
| // |
| Port inPort = new Port(src.port().value()); |
| Port outPort; |
| for (Node.Link link: resultPath) { |
| // Setup the outgoing port, and add the Flow Entry |
| outPort = new Port((short)link.myPort); |
| |
| FlowEntry flowEntry = new FlowEntry(); |
| flowEntry.setDpid(new Dpid(link.me.nodeId)); |
| flowEntry.setInPort(inPort); |
| flowEntry.setOutPort(outPort); |
| result_data_path.flowEntries().add(flowEntry); |
| |
| // Setup the next incoming port |
| inPort = new Port((short)link.neighborPort); |
| } |
| if (resultPath.size() > 0) { |
| // Add the last Flow Entry |
| FlowEntry flowEntry = new FlowEntry(); |
| flowEntry.setDpid(new Dpid(dest.dpid().value())); |
| flowEntry.setInPort(inPort); |
| flowEntry.setOutPort(dest.port()); |
| result_data_path.flowEntries().add(flowEntry); |
| } |
| |
| if (result_data_path.flowEntries().size() > 0) |
| return result_data_path; |
| |
| return null; |
| } |
| |
| /** |
| * Get the shortest path from a source to a destination by using |
| * the underlying Graph Database. |
| * |
| * @param dbHandler the Graph Database handler to use. |
| * @param src the source in the shortest path computation. |
| * @param dest the destination in the shortest path computation. |
| * @return the data path with the computed shortest path if |
| * found, otherwise null. |
| */ |
| public static DataPath getDatabaseShortestPath(DBOperation dbHandler, |
| SwitchPort src, SwitchPort dest) { |
| DataPath result_data_path = new DataPath(); |
| |
| // Initialize the source and destination in the data path to return |
| result_data_path.setSrcPort(src); |
| result_data_path.setDstPort(dest); |
| |
| String dpid_src = src.dpid().toString(); |
| String dpid_dest = dest.dpid().toString(); |
| |
| // Get the source and destination switches |
| ISwitchObject srcSwitch = |
| dbHandler.searchActiveSwitch(dpid_src); |
| ISwitchObject destSwitch = |
| dbHandler.searchActiveSwitch(dpid_dest); |
| if (srcSwitch == null || destSwitch == null) { |
| return null; |
| } |
| |
| // |
| // Test whether we are computing a path from/to the same DPID. |
| // If "yes", then just add a single flow entry in the return result. |
| // |
| if (dpid_src.equals(dpid_dest)) { |
| FlowEntry flowEntry = new FlowEntry(); |
| flowEntry.setDpid(src.dpid()); |
| flowEntry.setInPort(src.port()); |
| flowEntry.setOutPort(dest.port()); |
| result_data_path.flowEntries().add(flowEntry); |
| dbHandler.commit(); |
| return result_data_path; |
| } |
| |
| Vertex v_src = srcSwitch.asVertex(); |
| Vertex v_dest = destSwitch.asVertex(); |
| |
| // |
| // Implement the Shortest Path computation by using Breath First Search |
| // |
| Set<Vertex> visitedSet = new HashSet<Vertex>(); |
| Queue<Vertex> processingList = new LinkedList<Vertex>(); |
| Map<Vertex, Vertex> previousVertexMap = new HashMap<Vertex, Vertex>(); |
| |
| processingList.add(v_src); |
| visitedSet.add(v_src); |
| Boolean path_found = false; |
| while (! processingList.isEmpty()) { |
| Vertex nextVertex = processingList.poll(); |
| if (v_dest.equals(nextVertex)) { |
| path_found = true; |
| break; |
| } |
| for (Vertex parentPort : nextVertex.getVertices(Direction.OUT, "on")) { |
| // Ignore inactive ports |
| if (! parentPort.getProperty("state").toString().equals("ACTIVE")) |
| continue; |
| |
| for (Vertex childPort : parentPort.getVertices(Direction.OUT, "link")) { |
| // Ignore inactive ports |
| if (! childPort.getProperty("state").toString().equals("ACTIVE")) |
| continue; |
| |
| for (Vertex child : childPort.getVertices(Direction.IN, "on")) { |
| // Ignore inactive switches |
| String state = child.getProperty("state").toString(); |
| if (! state.equals(SwitchState.ACTIVE.toString())) |
| continue; |
| |
| if (! visitedSet.contains(child)) { |
| previousVertexMap.put(parentPort, nextVertex); |
| previousVertexMap.put(childPort, parentPort); |
| previousVertexMap.put(child, childPort); |
| visitedSet.add(child); |
| processingList.add(child); |
| } |
| } |
| } |
| } |
| } |
| if (! path_found) |
| return null; // No path found |
| |
| List<Vertex> resultPath = new LinkedList<Vertex>(); |
| Vertex previousVertex = v_dest; |
| resultPath.add(v_dest); |
| while (! v_src.equals(previousVertex)) { |
| Vertex currentVertex = previousVertexMap.get(previousVertex); |
| resultPath.add(currentVertex); |
| previousVertex = currentVertex; |
| } |
| Collections.reverse(resultPath); |
| |
| |
| // |
| // Loop through the result and prepare the return result |
| // as a list of Flow Entries. |
| // |
| long nodeId = 0; |
| short portId = 0; |
| Port inPort = new Port(src.port().value()); |
| Port outPort = new Port(); |
| int idx = 0; |
| for (Vertex v: resultPath) { |
| String type = v.getProperty("type").toString(); |
| // System.out.println("type: " + type); |
| if (type.equals("port")) { |
| //String number = v.getProperty("number").toString(); |
| // System.out.println("number: " + number); |
| |
| Object obj = v.getProperty("number"); |
| // String class_str = obj.getClass().toString(); |
| if (obj instanceof Short) { |
| portId = (Short)obj; |
| } else if (obj instanceof Integer) { |
| Integer int_nodeId = (Integer)obj; |
| portId = int_nodeId.shortValue(); |
| // int int_nodeId = (Integer)obj; |
| // portId = (short)int_nodeId.; |
| } |
| } else if (type.equals("switch")) { |
| String dpid = v.getProperty("dpid").toString(); |
| nodeId = HexString.toLong(dpid); |
| |
| // System.out.println("dpid: " + dpid); |
| } |
| idx++; |
| if (idx == 1) { |
| continue; |
| } |
| int mod = idx % 3; |
| if (mod == 0) { |
| // Setup the incoming port |
| inPort = new Port(portId); |
| continue; |
| } |
| if (mod == 2) { |
| // Setup the outgoing port, and add the Flow Entry |
| outPort = new Port(portId); |
| |
| FlowEntry flowEntry = new FlowEntry(); |
| flowEntry.setDpid(new Dpid(nodeId)); |
| flowEntry.setInPort(inPort); |
| flowEntry.setOutPort(outPort); |
| result_data_path.flowEntries().add(flowEntry); |
| continue; |
| } |
| } |
| if (idx > 0) { |
| // Add the last Flow Entry |
| FlowEntry flowEntry = new FlowEntry(); |
| flowEntry.setDpid(new Dpid(nodeId)); |
| flowEntry.setInPort(inPort); |
| flowEntry.setOutPort(dest.port()); |
| result_data_path.flowEntries().add(flowEntry); |
| } |
| |
| dbHandler.commit(); |
| if (result_data_path.flowEntries().size() > 0) |
| return result_data_path; |
| |
| return null; |
| } |
| } |