tom | 8bf2e6b | 2014-09-10 20:53:54 -0700 | [diff] [blame] | 1 | package org.onlab.onos.net.trivial.topology.provider.impl; |
tom | cfde062 | 2014-09-09 11:02:42 -0700 | [diff] [blame] | 2 | |
tom | e52ce70 | 2014-09-11 00:12:54 -0700 | [diff] [blame^] | 3 | import com.google.common.collect.ImmutableMap; |
tom | cfde062 | 2014-09-09 11:02:42 -0700 | [diff] [blame] | 4 | import com.google.common.collect.ImmutableSet; |
tom | 2d33141 | 2014-09-10 21:31:20 -0700 | [diff] [blame] | 5 | import com.google.common.collect.ImmutableSetMultimap; |
tom | cbff939 | 2014-09-10 00:45:23 -0700 | [diff] [blame] | 6 | import com.google.common.collect.Maps; |
| 7 | import com.google.common.collect.Sets; |
| 8 | import org.onlab.graph.AdjacencyListsGraph; |
| 9 | import org.onlab.graph.DijkstraGraphSearch; |
tom | cfde062 | 2014-09-09 11:02:42 -0700 | [diff] [blame] | 10 | import org.onlab.graph.Graph; |
| 11 | import org.onlab.graph.GraphPathSearch; |
tom | 8bf2e6b | 2014-09-10 20:53:54 -0700 | [diff] [blame] | 12 | import org.onlab.graph.TarjanGraphSearch; |
tom | cbff939 | 2014-09-10 00:45:23 -0700 | [diff] [blame] | 13 | import org.onlab.onos.net.ConnectPoint; |
| 14 | import org.onlab.onos.net.Device; |
tom | cfde062 | 2014-09-09 11:02:42 -0700 | [diff] [blame] | 15 | import org.onlab.onos.net.DeviceId; |
| 16 | import org.onlab.onos.net.Link; |
| 17 | import org.onlab.onos.net.topology.ClusterId; |
tom | 8bf2e6b | 2014-09-10 20:53:54 -0700 | [diff] [blame] | 18 | import org.onlab.onos.net.topology.DefaultTopologyCluster; |
tom | cbff939 | 2014-09-10 00:45:23 -0700 | [diff] [blame] | 19 | import org.onlab.onos.net.topology.LinkWeight; |
tom | cfde062 | 2014-09-09 11:02:42 -0700 | [diff] [blame] | 20 | import org.onlab.onos.net.topology.TopoEdge; |
| 21 | import org.onlab.onos.net.topology.TopoVertex; |
| 22 | import org.onlab.onos.net.topology.TopologyCluster; |
| 23 | import org.onlab.onos.net.topology.TopologyDescription; |
| 24 | |
tom | 8bf2e6b | 2014-09-10 20:53:54 -0700 | [diff] [blame] | 25 | import java.util.List; |
tom | cfde062 | 2014-09-09 11:02:42 -0700 | [diff] [blame] | 26 | import java.util.Map; |
| 27 | import java.util.Set; |
| 28 | |
tom | 2d33141 | 2014-09-10 21:31:20 -0700 | [diff] [blame] | 29 | import static com.google.common.collect.ImmutableSetMultimap.Builder; |
tom | e52ce70 | 2014-09-11 00:12:54 -0700 | [diff] [blame^] | 30 | import static com.google.common.collect.ImmutableSetMultimap.builder; |
tom | cbff939 | 2014-09-10 00:45:23 -0700 | [diff] [blame] | 31 | import static org.onlab.graph.GraphPathSearch.Result; |
tom | 8bf2e6b | 2014-09-10 20:53:54 -0700 | [diff] [blame] | 32 | import static org.onlab.graph.TarjanGraphSearch.SCCResult; |
tom | cbff939 | 2014-09-10 00:45:23 -0700 | [diff] [blame] | 33 | import static org.onlab.onos.net.Link.Type.INDIRECT; |
| 34 | |
tom | cfde062 | 2014-09-09 11:02:42 -0700 | [diff] [blame] | 35 | /** |
| 36 | * Default implementation of an immutable topology data carrier. |
| 37 | */ |
tom | cbff939 | 2014-09-10 00:45:23 -0700 | [diff] [blame] | 38 | class DefaultTopologyDescription implements TopologyDescription { |
| 39 | |
| 40 | private static final GraphPathSearch<TopoVertex, TopoEdge> DIJKSTRA = |
| 41 | new DijkstraGraphSearch<>(); |
tom | 8bf2e6b | 2014-09-10 20:53:54 -0700 | [diff] [blame] | 42 | private static final TarjanGraphSearch<TopoVertex, TopoEdge> TARJAN = |
| 43 | new TarjanGraphSearch<>(); |
tom | cfde062 | 2014-09-09 11:02:42 -0700 | [diff] [blame] | 44 | |
| 45 | private final long nanos; |
tom | cbff939 | 2014-09-10 00:45:23 -0700 | [diff] [blame] | 46 | private final Map<DeviceId, TopoVertex> vertexesById = Maps.newHashMap(); |
tom | cfde062 | 2014-09-09 11:02:42 -0700 | [diff] [blame] | 47 | private final Graph<TopoVertex, TopoEdge> graph; |
tom | e52ce70 | 2014-09-11 00:12:54 -0700 | [diff] [blame^] | 48 | private final ImmutableMap<DeviceId, Result<TopoVertex, TopoEdge>> results; |
tom | cfde062 | 2014-09-09 11:02:42 -0700 | [diff] [blame] | 49 | |
tom | e52ce70 | 2014-09-11 00:12:54 -0700 | [diff] [blame^] | 50 | // Cluster-related structures |
| 51 | private final ImmutableSet<TopologyCluster> clusters; |
| 52 | private ImmutableSetMultimap<TopologyCluster, DeviceId> devicesByCluster; |
| 53 | private ImmutableSetMultimap<TopologyCluster, Link> linksByCluster; |
tom | cbff939 | 2014-09-10 00:45:23 -0700 | [diff] [blame] | 54 | |
tom | 8bf2e6b | 2014-09-10 20:53:54 -0700 | [diff] [blame] | 55 | /** |
| 56 | * Creates a topology description to carry topology vitals to the core. |
| 57 | * |
| 58 | * @param nanos time in nanos of when the topology description was created |
tom | 2d33141 | 2014-09-10 21:31:20 -0700 | [diff] [blame] | 59 | * @param devices collection of infrastructure devices |
| 60 | * @param links collection of infrastructure links |
tom | 8bf2e6b | 2014-09-10 20:53:54 -0700 | [diff] [blame] | 61 | */ |
tom | cbff939 | 2014-09-10 00:45:23 -0700 | [diff] [blame] | 62 | DefaultTopologyDescription(long nanos, Iterable<Device> devices, Iterable<Link> links) { |
tom | cfde062 | 2014-09-09 11:02:42 -0700 | [diff] [blame] | 63 | this.nanos = nanos; |
tom | cbff939 | 2014-09-10 00:45:23 -0700 | [diff] [blame] | 64 | this.graph = buildGraph(devices, links); |
| 65 | this.results = computeDefaultPaths(); |
| 66 | this.clusters = computeClusters(); |
tom | cbff939 | 2014-09-10 00:45:23 -0700 | [diff] [blame] | 67 | } |
| 68 | |
tom | 2d33141 | 2014-09-10 21:31:20 -0700 | [diff] [blame] | 69 | @Override |
| 70 | public long timestamp() { |
| 71 | return nanos; |
| 72 | } |
| 73 | |
| 74 | @Override |
| 75 | public Graph<TopoVertex, TopoEdge> graph() { |
| 76 | return graph; |
| 77 | } |
| 78 | |
| 79 | @Override |
tom | e52ce70 | 2014-09-11 00:12:54 -0700 | [diff] [blame^] | 80 | public ImmutableMap<DeviceId, Result<TopoVertex, TopoEdge>> pathsBySource() { |
| 81 | return results; |
tom | 2d33141 | 2014-09-10 21:31:20 -0700 | [diff] [blame] | 82 | } |
| 83 | |
| 84 | @Override |
tom | e52ce70 | 2014-09-11 00:12:54 -0700 | [diff] [blame^] | 85 | public ImmutableSet<TopologyCluster> clusters() { |
| 86 | return clusters; |
tom | 2d33141 | 2014-09-10 21:31:20 -0700 | [diff] [blame] | 87 | } |
| 88 | |
| 89 | @Override |
tom | e52ce70 | 2014-09-11 00:12:54 -0700 | [diff] [blame^] | 90 | public ImmutableSetMultimap<TopologyCluster, DeviceId> devicesByCluster() { |
| 91 | return devicesByCluster; |
tom | 2d33141 | 2014-09-10 21:31:20 -0700 | [diff] [blame] | 92 | } |
| 93 | |
| 94 | @Override |
tom | e52ce70 | 2014-09-11 00:12:54 -0700 | [diff] [blame^] | 95 | public ImmutableSetMultimap<TopologyCluster, Link> linksByCluster() { |
| 96 | return linksByCluster; |
tom | 2d33141 | 2014-09-10 21:31:20 -0700 | [diff] [blame] | 97 | } |
| 98 | |
tom | 2d33141 | 2014-09-10 21:31:20 -0700 | [diff] [blame] | 99 | // Link weight for measuring link cost as hop count with indirect links |
| 100 | // being as expensive as traversing the entire graph to assume the worst. |
| 101 | private static class HopCountLinkWeight implements LinkWeight { |
| 102 | private final int indirectLinkCost; |
| 103 | |
| 104 | HopCountLinkWeight(int indirectLinkCost) { |
| 105 | this.indirectLinkCost = indirectLinkCost; |
| 106 | } |
| 107 | |
| 108 | @Override |
| 109 | public double weight(TopoEdge edge) { |
| 110 | // To force preference to use direct paths first, make indirect |
| 111 | // links as expensive as the linear vertex traversal. |
| 112 | return edge.link().type() == INDIRECT ? indirectLinkCost : 1; |
| 113 | } |
| 114 | } |
| 115 | |
| 116 | // Link weight for preventing traversal over indirect links. |
| 117 | private static class NoIndirectLinksWeight implements LinkWeight { |
| 118 | @Override |
| 119 | public double weight(TopoEdge edge) { |
| 120 | return edge.link().type() == INDIRECT ? -1 : 1; |
| 121 | } |
| 122 | } |
| 123 | |
tom | cbff939 | 2014-09-10 00:45:23 -0700 | [diff] [blame] | 124 | // Constructs the topology graph using the supplied devices and links. |
| 125 | private Graph<TopoVertex, TopoEdge> buildGraph(Iterable<Device> devices, |
| 126 | Iterable<Link> links) { |
tom | 2d33141 | 2014-09-10 21:31:20 -0700 | [diff] [blame] | 127 | return new AdjacencyListsGraph<>(buildVertexes(devices), |
| 128 | buildEdges(links)); |
tom | cbff939 | 2014-09-10 00:45:23 -0700 | [diff] [blame] | 129 | } |
| 130 | |
| 131 | // Builds a set of topology vertexes from the specified list of devices |
| 132 | private Set<TopoVertex> buildVertexes(Iterable<Device> devices) { |
| 133 | Set<TopoVertex> vertexes = Sets.newHashSet(); |
| 134 | for (Device device : devices) { |
tom | 2d33141 | 2014-09-10 21:31:20 -0700 | [diff] [blame] | 135 | TopoVertex vertex = new DefaultTopoVertex(device.id()); |
tom | cbff939 | 2014-09-10 00:45:23 -0700 | [diff] [blame] | 136 | vertexes.add(vertex); |
tom | 2d33141 | 2014-09-10 21:31:20 -0700 | [diff] [blame] | 137 | vertexesById.put(vertex.deviceId(), vertex); |
tom | cbff939 | 2014-09-10 00:45:23 -0700 | [diff] [blame] | 138 | } |
| 139 | return vertexes; |
| 140 | } |
| 141 | |
| 142 | // Builds a set of topology vertexes from the specified list of links |
| 143 | private Set<TopoEdge> buildEdges(Iterable<Link> links) { |
| 144 | Set<TopoEdge> edges = Sets.newHashSet(); |
| 145 | for (Link link : links) { |
tom | 2d33141 | 2014-09-10 21:31:20 -0700 | [diff] [blame] | 146 | edges.add(new DefaultTopoEdge(vertexOf(link.src()), |
| 147 | vertexOf(link.dst()), link)); |
tom | cbff939 | 2014-09-10 00:45:23 -0700 | [diff] [blame] | 148 | } |
| 149 | return edges; |
| 150 | } |
| 151 | |
| 152 | // Computes the default shortest paths for all source/dest pairs using |
| 153 | // the multi-path Dijkstra and hop-count as path cost. |
tom | e52ce70 | 2014-09-11 00:12:54 -0700 | [diff] [blame^] | 154 | private ImmutableMap<DeviceId, Result<TopoVertex, TopoEdge>> computeDefaultPaths() { |
tom | cbff939 | 2014-09-10 00:45:23 -0700 | [diff] [blame] | 155 | LinkWeight weight = new HopCountLinkWeight(graph.getVertexes().size()); |
tom | e52ce70 | 2014-09-11 00:12:54 -0700 | [diff] [blame^] | 156 | ImmutableMap.Builder<DeviceId, Result<TopoVertex, TopoEdge>> results = |
| 157 | ImmutableMap.builder(); |
tom | cbff939 | 2014-09-10 00:45:23 -0700 | [diff] [blame] | 158 | |
| 159 | // Search graph paths for each source to all destinations. |
| 160 | for (TopoVertex src : vertexesById.values()) { |
| 161 | results.put(src.deviceId(), DIJKSTRA.search(graph, src, null, weight)); |
| 162 | } |
tom | e52ce70 | 2014-09-11 00:12:54 -0700 | [diff] [blame^] | 163 | return results.build(); |
tom | cbff939 | 2014-09-10 00:45:23 -0700 | [diff] [blame] | 164 | } |
| 165 | |
| 166 | // Computes topology SCC clusters using Tarjan algorithm. |
tom | e52ce70 | 2014-09-11 00:12:54 -0700 | [diff] [blame^] | 167 | private ImmutableSet<TopologyCluster> computeClusters() { |
| 168 | ImmutableSet.Builder<TopologyCluster> clusterBuilder = ImmutableSet.builder(); |
| 169 | SCCResult<TopoVertex, TopoEdge> result = |
| 170 | TARJAN.search(graph, new NoIndirectLinksWeight()); |
tom | 8bf2e6b | 2014-09-10 20:53:54 -0700 | [diff] [blame] | 171 | |
| 172 | // Extract both vertexes and edges from the results; the lists form |
| 173 | // pairs along the same index. |
| 174 | List<Set<TopoVertex>> clusterVertexes = result.clusterVertexes(); |
| 175 | List<Set<TopoEdge>> clusterEdges = result.clusterEdges(); |
| 176 | |
tom | e52ce70 | 2014-09-11 00:12:54 -0700 | [diff] [blame^] | 177 | Builder<TopologyCluster, DeviceId> devicesBuilder = ImmutableSetMultimap.builder(); |
| 178 | Builder<TopologyCluster, Link> linksBuilder = ImmutableSetMultimap.builder(); |
tom | 2d33141 | 2014-09-10 21:31:20 -0700 | [diff] [blame] | 179 | |
tom | 8bf2e6b | 2014-09-10 20:53:54 -0700 | [diff] [blame] | 180 | // Scan over the lists and create a cluster from the results. |
| 181 | for (int i = 0, n = result.clusterCount(); i < n; i++) { |
| 182 | Set<TopoVertex> vertexSet = clusterVertexes.get(i); |
| 183 | Set<TopoEdge> edgeSet = clusterEdges.get(i); |
| 184 | |
| 185 | DefaultTopologyCluster cluster = |
| 186 | new DefaultTopologyCluster(ClusterId.clusterId(i), |
| 187 | vertexSet.size(), edgeSet.size(), |
| 188 | findRoot(vertexSet).deviceId()); |
tom | e52ce70 | 2014-09-11 00:12:54 -0700 | [diff] [blame^] | 189 | clusterBuilder.add(cluster); |
tom | 2d33141 | 2014-09-10 21:31:20 -0700 | [diff] [blame] | 190 | findClusterDevices(vertexSet, cluster, devicesBuilder); |
| 191 | findClusterLinks(edgeSet, cluster, linksBuilder); |
tom | 8bf2e6b | 2014-09-10 20:53:54 -0700 | [diff] [blame] | 192 | } |
tom | e52ce70 | 2014-09-11 00:12:54 -0700 | [diff] [blame^] | 193 | return clusterBuilder.build(); |
tom | cbff939 | 2014-09-10 00:45:23 -0700 | [diff] [blame] | 194 | } |
| 195 | |
tom | 2d33141 | 2014-09-10 21:31:20 -0700 | [diff] [blame] | 196 | // Scans through the set of cluster vertexes and puts their devices in a |
| 197 | // multi-map associated with the cluster. It also binds the devices to |
| 198 | // the cluster. |
tom | 8bf2e6b | 2014-09-10 20:53:54 -0700 | [diff] [blame] | 199 | private void findClusterDevices(Set<TopoVertex> vertexSet, |
tom | 2d33141 | 2014-09-10 21:31:20 -0700 | [diff] [blame] | 200 | DefaultTopologyCluster cluster, |
tom | e52ce70 | 2014-09-11 00:12:54 -0700 | [diff] [blame^] | 201 | Builder<TopologyCluster, DeviceId> builder) { |
tom | 2d33141 | 2014-09-10 21:31:20 -0700 | [diff] [blame] | 202 | for (TopoVertex vertex : vertexSet) { |
| 203 | DeviceId deviceId = vertex.deviceId(); |
tom | e52ce70 | 2014-09-11 00:12:54 -0700 | [diff] [blame^] | 204 | builder.put(cluster, deviceId); |
tom | 8bf2e6b | 2014-09-10 20:53:54 -0700 | [diff] [blame] | 205 | } |
| 206 | } |
| 207 | |
tom | 2d33141 | 2014-09-10 21:31:20 -0700 | [diff] [blame] | 208 | // Scans through the set of cluster edges and puts their links in a |
| 209 | // multi-map associated with the cluster. |
tom | 8bf2e6b | 2014-09-10 20:53:54 -0700 | [diff] [blame] | 210 | private void findClusterLinks(Set<TopoEdge> edgeSet, |
tom | 2d33141 | 2014-09-10 21:31:20 -0700 | [diff] [blame] | 211 | DefaultTopologyCluster cluster, |
tom | e52ce70 | 2014-09-11 00:12:54 -0700 | [diff] [blame^] | 212 | Builder<TopologyCluster, Link> builder) { |
tom | 2d33141 | 2014-09-10 21:31:20 -0700 | [diff] [blame] | 213 | for (TopoEdge edge : edgeSet) { |
tom | e52ce70 | 2014-09-11 00:12:54 -0700 | [diff] [blame^] | 214 | builder.put(cluster, edge.link()); |
tom | 8bf2e6b | 2014-09-10 20:53:54 -0700 | [diff] [blame] | 215 | } |
| 216 | } |
| 217 | |
| 218 | // Finds the vertex whose device id is the lexicographical minimum in the |
| 219 | // specified set. |
| 220 | private TopoVertex findRoot(Set<TopoVertex> vertexSet) { |
| 221 | TopoVertex minVertex = null; |
| 222 | for (TopoVertex vertex : vertexSet) { |
| 223 | if (minVertex == null || |
| 224 | minVertex.deviceId().toString() |
| 225 | .compareTo(minVertex.deviceId().toString()) < 0) { |
| 226 | minVertex = vertex; |
| 227 | } |
| 228 | } |
| 229 | return minVertex; |
| 230 | } |
| 231 | |
tom | cbff939 | 2014-09-10 00:45:23 -0700 | [diff] [blame] | 232 | // Fetches a vertex corresponding to the given connection point device. |
| 233 | private TopoVertex vertexOf(ConnectPoint connectPoint) { |
| 234 | DeviceId id = connectPoint.deviceId(); |
| 235 | TopoVertex vertex = vertexesById.get(id); |
| 236 | if (vertex == null) { |
| 237 | // If vertex does not exist, create one and register it. |
tom | 2d33141 | 2014-09-10 21:31:20 -0700 | [diff] [blame] | 238 | vertex = new DefaultTopoVertex(id); |
tom | cbff939 | 2014-09-10 00:45:23 -0700 | [diff] [blame] | 239 | vertexesById.put(id, vertex); |
| 240 | } |
| 241 | return vertex; |
tom | cfde062 | 2014-09-09 11:02:42 -0700 | [diff] [blame] | 242 | } |
| 243 | |
tom | cfde062 | 2014-09-09 11:02:42 -0700 | [diff] [blame] | 244 | } |