Bundle restructuring
Change-Id: I5a9efa7f4d03bd78dd17297731c5addea5cf0442
diff --git a/core/store/dist/pom.xml b/core/store/dist/pom.xml
new file mode 100644
index 0000000..900a2ff
--- /dev/null
+++ b/core/store/dist/pom.xml
@@ -0,0 +1,48 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<project xmlns="http://maven.apache.org/POM/4.0.0"
+ xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+ xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
+ <modelVersion>4.0.0</modelVersion>
+
+ <parent>
+ <groupId>org.onlab.onos</groupId>
+ <artifactId>onos-core-store</artifactId>
+ <version>1.0.0-SNAPSHOT</version>
+ <relativePath>../pom.xml</relativePath>
+ </parent>
+
+ <artifactId>onos-core-dist</artifactId>
+ <packaging>bundle</packaging>
+
+ <description>ONOS Gossip based distributed store subsystems</description>
+
+ <dependencies>
+ <dependency>
+ <groupId>org.onlab.onos</groupId>
+ <artifactId>onos-api</artifactId>
+ </dependency>
+ <dependency>
+ <groupId>org.onlab.onos</groupId>
+ <artifactId>onos-core-serializers</artifactId>
+ <version>${project.version}</version>
+ </dependency>
+ <dependency>
+ <groupId>org.apache.felix</groupId>
+ <artifactId>org.apache.felix.scr.annotations</artifactId>
+ </dependency>
+ <dependency>
+ <groupId>de.javakaffee</groupId>
+ <artifactId>kryo-serializers</artifactId>
+ </dependency>
+ </dependencies>
+
+ <build>
+ <plugins>
+ <plugin>
+ <groupId>org.apache.felix</groupId>
+ <artifactId>maven-scr-plugin</artifactId>
+ </plugin>
+ </plugins>
+ </build>
+
+</project>
diff --git a/core/store/dist/src/main/java/org/onlab/onos/store/device/impl/package-info.java b/core/store/dist/src/main/java/org/onlab/onos/store/device/impl/package-info.java
new file mode 100644
index 0000000..b2fc91d
--- /dev/null
+++ b/core/store/dist/src/main/java/org/onlab/onos/store/device/impl/package-info.java
@@ -0,0 +1,4 @@
+/**
+ * Implementation of device store using distributed structures.
+ */
+package org.onlab.onos.store.device.impl;
diff --git a/core/store/dist/src/main/java/org/onlab/onos/store/flow/impl/DistributedFlowRuleStore.java b/core/store/dist/src/main/java/org/onlab/onos/store/flow/impl/DistributedFlowRuleStore.java
new file mode 100644
index 0000000..5a5592a
--- /dev/null
+++ b/core/store/dist/src/main/java/org/onlab/onos/store/flow/impl/DistributedFlowRuleStore.java
@@ -0,0 +1,153 @@
+package org.onlab.onos.store.flow.impl;
+
+import static org.onlab.onos.net.flow.FlowRuleEvent.Type.RULE_ADDED;
+import static org.onlab.onos.net.flow.FlowRuleEvent.Type.RULE_REMOVED;
+import static org.slf4j.LoggerFactory.getLogger;
+
+import java.util.Collection;
+import java.util.Collections;
+
+import org.apache.felix.scr.annotations.Activate;
+import org.apache.felix.scr.annotations.Component;
+import org.apache.felix.scr.annotations.Deactivate;
+import org.apache.felix.scr.annotations.Service;
+import org.onlab.onos.ApplicationId;
+import org.onlab.onos.net.DeviceId;
+import org.onlab.onos.net.flow.DefaultFlowRule;
+import org.onlab.onos.net.flow.FlowRule;
+import org.onlab.onos.net.flow.FlowRule.FlowRuleState;
+import org.onlab.onos.net.flow.FlowRuleEvent;
+import org.onlab.onos.net.flow.FlowRuleEvent.Type;
+import org.onlab.onos.net.flow.FlowRuleStore;
+import org.onlab.onos.net.flow.FlowRuleStoreDelegate;
+import org.onlab.onos.store.AbstractStore;
+import org.slf4j.Logger;
+
+import com.google.common.collect.ArrayListMultimap;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Multimap;
+
+/**
+ * Manages inventory of flow rules using trivial in-memory implementation.
+ */
+//FIXME: I LIE I AM NOT DISTRIBUTED
+@Component(immediate = true)
+@Service
+public class DistributedFlowRuleStore
+extends AbstractStore<FlowRuleEvent, FlowRuleStoreDelegate>
+implements FlowRuleStore {
+
+ private final Logger log = getLogger(getClass());
+
+ // store entries as a pile of rules, no info about device tables
+ private final Multimap<DeviceId, FlowRule> flowEntries =
+ ArrayListMultimap.<DeviceId, FlowRule>create();
+
+ private final Multimap<ApplicationId, FlowRule> flowEntriesById =
+ ArrayListMultimap.<ApplicationId, FlowRule>create();
+
+ @Activate
+ public void activate() {
+ log.info("Started");
+ }
+
+ @Deactivate
+ public void deactivate() {
+ log.info("Stopped");
+ }
+
+
+ @Override
+ public synchronized FlowRule getFlowRule(FlowRule rule) {
+ for (FlowRule f : flowEntries.get(rule.deviceId())) {
+ if (f.equals(rule)) {
+ return f;
+ }
+ }
+ return null;
+ }
+
+ @Override
+ public synchronized Iterable<FlowRule> getFlowEntries(DeviceId deviceId) {
+ Collection<FlowRule> rules = flowEntries.get(deviceId);
+ if (rules == null) {
+ return Collections.emptyList();
+ }
+ return ImmutableSet.copyOf(rules);
+ }
+
+ @Override
+ public synchronized Iterable<FlowRule> getFlowEntriesByAppId(ApplicationId appId) {
+ Collection<FlowRule> rules = flowEntriesById.get(appId);
+ if (rules == null) {
+ return Collections.emptyList();
+ }
+ return ImmutableSet.copyOf(rules);
+ }
+
+ @Override
+ public synchronized void storeFlowRule(FlowRule rule) {
+ FlowRule f = new DefaultFlowRule(rule, FlowRuleState.PENDING_ADD);
+ DeviceId did = f.deviceId();
+ if (!flowEntries.containsEntry(did, f)) {
+ flowEntries.put(did, f);
+ flowEntriesById.put(rule.appId(), f);
+ }
+ }
+
+ @Override
+ public synchronized void deleteFlowRule(FlowRule rule) {
+ FlowRule f = new DefaultFlowRule(rule, FlowRuleState.PENDING_REMOVE);
+ DeviceId did = f.deviceId();
+
+ /*
+ * find the rule and mark it for deletion.
+ * Ultimately a flow removed will come remove it.
+ */
+
+ if (flowEntries.containsEntry(did, f)) {
+ //synchronized (flowEntries) {
+ flowEntries.remove(did, f);
+ flowEntries.put(did, f);
+ flowEntriesById.remove(rule.appId(), rule);
+ //}
+ }
+ }
+
+ @Override
+ public synchronized FlowRuleEvent addOrUpdateFlowRule(FlowRule rule) {
+ DeviceId did = rule.deviceId();
+
+ // check if this new rule is an update to an existing entry
+ if (flowEntries.containsEntry(did, rule)) {
+ //synchronized (flowEntries) {
+ // Multimaps support duplicates so we have to remove our rule
+ // and replace it with the current version.
+ flowEntries.remove(did, rule);
+ flowEntries.put(did, rule);
+ //}
+ return new FlowRuleEvent(Type.RULE_UPDATED, rule);
+ }
+
+ flowEntries.put(did, rule);
+ return new FlowRuleEvent(RULE_ADDED, rule);
+ }
+
+ @Override
+ public synchronized FlowRuleEvent removeFlowRule(FlowRule rule) {
+ //synchronized (this) {
+ if (flowEntries.remove(rule.deviceId(), rule)) {
+ return new FlowRuleEvent(RULE_REMOVED, rule);
+ } else {
+ return null;
+ }
+ //}
+ }
+
+
+
+
+
+
+
+}
diff --git a/core/store/dist/src/main/java/org/onlab/onos/store/host/impl/DistributedHostStore.java b/core/store/dist/src/main/java/org/onlab/onos/store/host/impl/DistributedHostStore.java
new file mode 100644
index 0000000..09820f4
--- /dev/null
+++ b/core/store/dist/src/main/java/org/onlab/onos/store/host/impl/DistributedHostStore.java
@@ -0,0 +1,278 @@
+package org.onlab.onos.store.host.impl;
+
+import static org.onlab.onos.net.host.HostEvent.Type.HOST_ADDED;
+import static org.onlab.onos.net.host.HostEvent.Type.HOST_MOVED;
+import static org.onlab.onos.net.host.HostEvent.Type.HOST_REMOVED;
+import static org.onlab.onos.net.host.HostEvent.Type.HOST_UPDATED;
+import static org.slf4j.LoggerFactory.getLogger;
+
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+import java.util.concurrent.ConcurrentHashMap;
+
+import org.apache.felix.scr.annotations.Activate;
+import org.apache.felix.scr.annotations.Component;
+import org.apache.felix.scr.annotations.Deactivate;
+import org.apache.felix.scr.annotations.Service;
+import org.onlab.onos.net.ConnectPoint;
+import org.onlab.onos.net.DefaultHost;
+import org.onlab.onos.net.DeviceId;
+import org.onlab.onos.net.Host;
+import org.onlab.onos.net.HostId;
+import org.onlab.onos.net.host.HostDescription;
+import org.onlab.onos.net.host.HostEvent;
+import org.onlab.onos.net.host.HostStore;
+import org.onlab.onos.net.host.HostStoreDelegate;
+import org.onlab.onos.net.host.PortAddresses;
+import org.onlab.onos.net.provider.ProviderId;
+import org.onlab.onos.store.AbstractStore;
+import org.onlab.packet.IpPrefix;
+import org.onlab.packet.MacAddress;
+import org.onlab.packet.VlanId;
+import org.slf4j.Logger;
+
+import com.google.common.collect.HashMultimap;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Multimap;
+import com.google.common.collect.Sets;
+
+/**
+ * Manages inventory of end-station hosts using trivial in-memory
+ * implementation.
+ */
+//FIXME: I LIE I AM NOT DISTRIBUTED
+@Component(immediate = true)
+@Service
+public class DistributedHostStore
+extends AbstractStore<HostEvent, HostStoreDelegate>
+implements HostStore {
+
+ private final Logger log = getLogger(getClass());
+
+ // Host inventory
+ private final Map<HostId, Host> hosts = new ConcurrentHashMap<>();
+
+ // Hosts tracked by their location
+ private final Multimap<ConnectPoint, Host> locations = HashMultimap.create();
+
+ private final Map<ConnectPoint, PortAddresses> portAddresses =
+ new ConcurrentHashMap<>();
+
+ @Activate
+ public void activate() {
+ log.info("Started");
+ }
+
+ @Deactivate
+ public void deactivate() {
+ log.info("Stopped");
+ }
+
+ @Override
+ public HostEvent createOrUpdateHost(ProviderId providerId, HostId hostId,
+ HostDescription hostDescription) {
+ Host host = hosts.get(hostId);
+ if (host == null) {
+ return createHost(providerId, hostId, hostDescription);
+ }
+ return updateHost(providerId, host, hostDescription);
+ }
+
+ // creates a new host and sends HOST_ADDED
+ private HostEvent createHost(ProviderId providerId, HostId hostId,
+ HostDescription descr) {
+ DefaultHost newhost = new DefaultHost(providerId, hostId,
+ descr.hwAddress(),
+ descr.vlan(),
+ descr.location(),
+ descr.ipAddresses());
+ synchronized (this) {
+ hosts.put(hostId, newhost);
+ locations.put(descr.location(), newhost);
+ }
+ return new HostEvent(HOST_ADDED, newhost);
+ }
+
+ // checks for type of update to host, sends appropriate event
+ private HostEvent updateHost(ProviderId providerId, Host host,
+ HostDescription descr) {
+ DefaultHost updated;
+ HostEvent event;
+ if (!host.location().equals(descr.location())) {
+ updated = new DefaultHost(providerId, host.id(),
+ host.mac(),
+ host.vlan(),
+ descr.location(),
+ host.ipAddresses());
+ event = new HostEvent(HOST_MOVED, updated);
+
+ } else if (!(host.ipAddresses().equals(descr.ipAddresses()))) {
+ updated = new DefaultHost(providerId, host.id(),
+ host.mac(),
+ host.vlan(),
+ descr.location(),
+ descr.ipAddresses());
+ event = new HostEvent(HOST_UPDATED, updated);
+ } else {
+ return null;
+ }
+ synchronized (this) {
+ hosts.put(host.id(), updated);
+ locations.remove(host.location(), host);
+ locations.put(updated.location(), updated);
+ }
+ return event;
+ }
+
+ @Override
+ public HostEvent removeHost(HostId hostId) {
+ synchronized (this) {
+ Host host = hosts.remove(hostId);
+ if (host != null) {
+ locations.remove((host.location()), host);
+ return new HostEvent(HOST_REMOVED, host);
+ }
+ return null;
+ }
+ }
+
+ @Override
+ public int getHostCount() {
+ return hosts.size();
+ }
+
+ @Override
+ public Iterable<Host> getHosts() {
+ return Collections.unmodifiableSet(new HashSet<>(hosts.values()));
+ }
+
+ @Override
+ public Host getHost(HostId hostId) {
+ return hosts.get(hostId);
+ }
+
+ @Override
+ public Set<Host> getHosts(VlanId vlanId) {
+ Set<Host> vlanset = new HashSet<>();
+ for (Host h : hosts.values()) {
+ if (h.vlan().equals(vlanId)) {
+ vlanset.add(h);
+ }
+ }
+ return vlanset;
+ }
+
+ @Override
+ public Set<Host> getHosts(MacAddress mac) {
+ Set<Host> macset = new HashSet<>();
+ for (Host h : hosts.values()) {
+ if (h.mac().equals(mac)) {
+ macset.add(h);
+ }
+ }
+ return macset;
+ }
+
+ @Override
+ public Set<Host> getHosts(IpPrefix ip) {
+ Set<Host> ipset = new HashSet<>();
+ for (Host h : hosts.values()) {
+ if (h.ipAddresses().contains(ip)) {
+ ipset.add(h);
+ }
+ }
+ return ipset;
+ }
+
+ @Override
+ public Set<Host> getConnectedHosts(ConnectPoint connectPoint) {
+ return ImmutableSet.copyOf(locations.get(connectPoint));
+ }
+
+ @Override
+ public Set<Host> getConnectedHosts(DeviceId deviceId) {
+ Set<Host> hostset = new HashSet<>();
+ for (ConnectPoint p : locations.keySet()) {
+ if (p.deviceId().equals(deviceId)) {
+ hostset.addAll(locations.get(p));
+ }
+ }
+ return hostset;
+ }
+
+ @Override
+ public void updateAddressBindings(PortAddresses addresses) {
+ synchronized (portAddresses) {
+ PortAddresses existing = portAddresses.get(addresses.connectPoint());
+ if (existing == null) {
+ portAddresses.put(addresses.connectPoint(), addresses);
+ } else {
+ Set<IpPrefix> union = Sets.union(existing.ips(), addresses.ips())
+ .immutableCopy();
+
+ MacAddress newMac = (addresses.mac() == null) ? existing.mac()
+ : addresses.mac();
+
+ PortAddresses newAddresses =
+ new PortAddresses(addresses.connectPoint(), union, newMac);
+
+ portAddresses.put(newAddresses.connectPoint(), newAddresses);
+ }
+ }
+ }
+
+ @Override
+ public void removeAddressBindings(PortAddresses addresses) {
+ synchronized (portAddresses) {
+ PortAddresses existing = portAddresses.get(addresses.connectPoint());
+ if (existing != null) {
+ Set<IpPrefix> difference =
+ Sets.difference(existing.ips(), addresses.ips()).immutableCopy();
+
+ // If they removed the existing mac, set the new mac to null.
+ // Otherwise, keep the existing mac.
+ MacAddress newMac = existing.mac();
+ if (addresses.mac() != null && addresses.mac().equals(existing.mac())) {
+ newMac = null;
+ }
+
+ PortAddresses newAddresses =
+ new PortAddresses(addresses.connectPoint(), difference, newMac);
+
+ portAddresses.put(newAddresses.connectPoint(), newAddresses);
+ }
+ }
+ }
+
+ @Override
+ public void clearAddressBindings(ConnectPoint connectPoint) {
+ synchronized (portAddresses) {
+ portAddresses.remove(connectPoint);
+ }
+ }
+
+ @Override
+ public Set<PortAddresses> getAddressBindings() {
+ synchronized (portAddresses) {
+ return new HashSet<>(portAddresses.values());
+ }
+ }
+
+ @Override
+ public PortAddresses getAddressBindingsForPort(ConnectPoint connectPoint) {
+ PortAddresses addresses;
+
+ synchronized (portAddresses) {
+ addresses = portAddresses.get(connectPoint);
+ }
+
+ if (addresses == null) {
+ addresses = new PortAddresses(connectPoint, null, null);
+ }
+
+ return addresses;
+ }
+
+}
diff --git a/core/store/dist/src/main/java/org/onlab/onos/store/impl/OnosTimestamp.java b/core/store/dist/src/main/java/org/onlab/onos/store/impl/OnosTimestamp.java
new file mode 100644
index 0000000..5b68d1a
--- /dev/null
+++ b/core/store/dist/src/main/java/org/onlab/onos/store/impl/OnosTimestamp.java
@@ -0,0 +1,87 @@
+package org.onlab.onos.store.impl;
+
+import static com.google.common.base.Preconditions.checkArgument;
+
+import java.util.Objects;
+
+import org.onlab.onos.store.Timestamp;
+
+import com.google.common.base.MoreObjects;
+import com.google.common.collect.ComparisonChain;
+
+// If it is store specific, implement serializable interfaces?
+/**
+ * Default implementation of Timestamp.
+ * TODO: Better documentation.
+ */
+public final class OnosTimestamp implements Timestamp {
+
+ private final int termNumber;
+ private final int sequenceNumber;
+
+ /**
+ * Default version tuple.
+ *
+ * @param termNumber the mastership termNumber
+ * @param sequenceNumber the sequenceNumber number within the termNumber
+ */
+ public OnosTimestamp(int termNumber, int sequenceNumber) {
+ this.termNumber = termNumber;
+ this.sequenceNumber = sequenceNumber;
+ }
+
+ @Override
+ public int compareTo(Timestamp o) {
+ checkArgument(o instanceof OnosTimestamp, "Must be OnosTimestamp", o);
+ OnosTimestamp that = (OnosTimestamp) o;
+
+ return ComparisonChain.start()
+ .compare(this.termNumber, that.termNumber)
+ .compare(this.sequenceNumber, that.sequenceNumber)
+ .result();
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hash(termNumber, sequenceNumber);
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj) {
+ return true;
+ }
+ if (!(obj instanceof OnosTimestamp)) {
+ return false;
+ }
+ OnosTimestamp that = (OnosTimestamp) obj;
+ return Objects.equals(this.termNumber, that.termNumber) &&
+ Objects.equals(this.sequenceNumber, that.sequenceNumber);
+ }
+
+ @Override
+ public String toString() {
+ return MoreObjects.toStringHelper(getClass())
+ .add("termNumber", termNumber)
+ .add("sequenceNumber", sequenceNumber)
+ .toString();
+ }
+
+ /**
+ * Returns the termNumber.
+ *
+ * @return termNumber
+ */
+ public int termNumber() {
+ return termNumber;
+ }
+
+ /**
+ * Returns the sequenceNumber number.
+ *
+ * @return sequenceNumber
+ */
+ public int sequenceNumber() {
+ return sequenceNumber;
+ }
+}
\ No newline at end of file
diff --git a/core/store/dist/src/main/java/org/onlab/onos/store/serializers/OnosTimestampSerializer.java b/core/store/dist/src/main/java/org/onlab/onos/store/serializers/OnosTimestampSerializer.java
new file mode 100644
index 0000000..192e035
--- /dev/null
+++ b/core/store/dist/src/main/java/org/onlab/onos/store/serializers/OnosTimestampSerializer.java
@@ -0,0 +1,35 @@
+package org.onlab.onos.store.serializers;
+
+import org.onlab.onos.store.impl.OnosTimestamp;
+
+import com.esotericsoftware.kryo.Kryo;
+import com.esotericsoftware.kryo.Serializer;
+import com.esotericsoftware.kryo.io.Input;
+import com.esotericsoftware.kryo.io.Output;
+
+/**
+ * Kryo Serializer for {@link OnosTimestamp}.
+ */
+public class OnosTimestampSerializer extends Serializer<OnosTimestamp> {
+
+ /**
+ * Default constructor.
+ */
+ public OnosTimestampSerializer() {
+ // non-null, immutable
+ super(false, true);
+ }
+
+ @Override
+ public void write(Kryo kryo, Output output, OnosTimestamp object) {
+ output.writeInt(object.termNumber());
+ output.writeInt(object.sequenceNumber());
+ }
+
+ @Override
+ public OnosTimestamp read(Kryo kryo, Input input, Class<OnosTimestamp> type) {
+ final int term = input.readInt();
+ final int sequence = input.readInt();
+ return new OnosTimestamp(term, sequence);
+ }
+}
diff --git a/core/store/dist/src/main/java/org/onlab/onos/store/topology/impl/DefaultTopology.java b/core/store/dist/src/main/java/org/onlab/onos/store/topology/impl/DefaultTopology.java
new file mode 100644
index 0000000..5574d27
--- /dev/null
+++ b/core/store/dist/src/main/java/org/onlab/onos/store/topology/impl/DefaultTopology.java
@@ -0,0 +1,444 @@
+package org.onlab.onos.store.topology.impl;
+
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.ImmutableSetMultimap;
+import org.onlab.graph.DijkstraGraphSearch;
+import org.onlab.graph.GraphPathSearch;
+import org.onlab.graph.TarjanGraphSearch;
+import org.onlab.onos.net.AbstractModel;
+import org.onlab.onos.net.ConnectPoint;
+import org.onlab.onos.net.DefaultPath;
+import org.onlab.onos.net.DeviceId;
+import org.onlab.onos.net.Link;
+import org.onlab.onos.net.Path;
+import org.onlab.onos.net.provider.ProviderId;
+import org.onlab.onos.net.topology.ClusterId;
+import org.onlab.onos.net.topology.DefaultTopologyCluster;
+import org.onlab.onos.net.topology.DefaultTopologyVertex;
+import org.onlab.onos.net.topology.GraphDescription;
+import org.onlab.onos.net.topology.LinkWeight;
+import org.onlab.onos.net.topology.Topology;
+import org.onlab.onos.net.topology.TopologyCluster;
+import org.onlab.onos.net.topology.TopologyEdge;
+import org.onlab.onos.net.topology.TopologyGraph;
+import org.onlab.onos.net.topology.TopologyVertex;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import static com.google.common.base.MoreObjects.toStringHelper;
+import static com.google.common.collect.ImmutableSetMultimap.Builder;
+import static org.onlab.graph.GraphPathSearch.Result;
+import static org.onlab.graph.TarjanGraphSearch.SCCResult;
+import static org.onlab.onos.net.Link.Type.INDIRECT;
+
+/**
+ * Default implementation of the topology descriptor. This carries the
+ * backing topology data.
+ */
+public class DefaultTopology extends AbstractModel implements Topology {
+
+ private static final DijkstraGraphSearch<TopologyVertex, TopologyEdge> DIJKSTRA =
+ new DijkstraGraphSearch<>();
+ private static final TarjanGraphSearch<TopologyVertex, TopologyEdge> TARJAN =
+ new TarjanGraphSearch<>();
+
+ private static final ProviderId PID = new ProviderId("core", "org.onlab.onos.net");
+
+ private final long time;
+ private final TopologyGraph graph;
+
+ private final SCCResult<TopologyVertex, TopologyEdge> clusterResults;
+ private final ImmutableMap<DeviceId, Result<TopologyVertex, TopologyEdge>> results;
+ private final ImmutableSetMultimap<PathKey, Path> paths;
+
+ private final ImmutableMap<ClusterId, TopologyCluster> clusters;
+ private final ImmutableSet<ConnectPoint> infrastructurePoints;
+ private final ImmutableSetMultimap<ClusterId, ConnectPoint> broadcastSets;
+
+ private ImmutableMap<DeviceId, TopologyCluster> clustersByDevice;
+ private ImmutableSetMultimap<TopologyCluster, DeviceId> devicesByCluster;
+ private ImmutableSetMultimap<TopologyCluster, Link> linksByCluster;
+
+
+ /**
+ * Creates a topology descriptor attributed to the specified provider.
+ *
+ * @param providerId identity of the provider
+ * @param description data describing the new topology
+ */
+ DefaultTopology(ProviderId providerId, GraphDescription description) {
+ super(providerId);
+ this.time = description.timestamp();
+
+ // Build the graph
+ this.graph = new DefaultTopologyGraph(description.vertexes(),
+ description.edges());
+
+ this.results = searchForShortestPaths();
+ this.paths = buildPaths();
+
+ this.clusterResults = searchForClusters();
+ this.clusters = buildTopologyClusters();
+
+ buildIndexes();
+
+ this.broadcastSets = buildBroadcastSets();
+ this.infrastructurePoints = findInfrastructurePoints();
+ }
+
+ @Override
+ public long time() {
+ return time;
+ }
+
+ @Override
+ public int clusterCount() {
+ return clusters.size();
+ }
+
+ @Override
+ public int deviceCount() {
+ return graph.getVertexes().size();
+ }
+
+ @Override
+ public int linkCount() {
+ return graph.getEdges().size();
+ }
+
+ @Override
+ public int pathCount() {
+ return paths.size();
+ }
+
+ /**
+ * Returns the backing topology graph.
+ *
+ * @return topology graph
+ */
+ TopologyGraph getGraph() {
+ return graph;
+ }
+
+ /**
+ * Returns the set of topology clusters.
+ *
+ * @return set of clusters
+ */
+ Set<TopologyCluster> getClusters() {
+ return ImmutableSet.copyOf(clusters.values());
+ }
+
+ /**
+ * Returns the specified topology cluster.
+ *
+ * @param clusterId cluster identifier
+ * @return topology cluster
+ */
+ TopologyCluster getCluster(ClusterId clusterId) {
+ return clusters.get(clusterId);
+ }
+
+ /**
+ * Returns the topology cluster that contains the given device.
+ *
+ * @param deviceId device identifier
+ * @return topology cluster
+ */
+ TopologyCluster getCluster(DeviceId deviceId) {
+ return clustersByDevice.get(deviceId);
+ }
+
+ /**
+ * Returns the set of cluster devices.
+ *
+ * @param cluster topology cluster
+ * @return cluster devices
+ */
+ Set<DeviceId> getClusterDevices(TopologyCluster cluster) {
+ return devicesByCluster.get(cluster);
+ }
+
+ /**
+ * Returns the set of cluster links.
+ *
+ * @param cluster topology cluster
+ * @return cluster links
+ */
+ Set<Link> getClusterLinks(TopologyCluster cluster) {
+ return linksByCluster.get(cluster);
+ }
+
+ /**
+ * Indicates whether the given point is an infrastructure link end-point.
+ *
+ * @param connectPoint connection point
+ * @return true if infrastructure
+ */
+ boolean isInfrastructure(ConnectPoint connectPoint) {
+ return infrastructurePoints.contains(connectPoint);
+ }
+
+ /**
+ * Indicates whether the given point is part of a broadcast set.
+ *
+ * @param connectPoint connection point
+ * @return true if in broadcast set
+ */
+ boolean isBroadcastPoint(ConnectPoint connectPoint) {
+ // Any non-infrastructure, i.e. edge points are assumed to be OK.
+ if (!isInfrastructure(connectPoint)) {
+ return true;
+ }
+
+ // Find the cluster to which the device belongs.
+ TopologyCluster cluster = clustersByDevice.get(connectPoint.deviceId());
+ if (cluster == null) {
+ throw new IllegalArgumentException("No cluster found for device " + connectPoint.deviceId());
+ }
+
+ // If the broadcast set is null or empty, or if the point explicitly
+ // belongs to it, return true;
+ Set<ConnectPoint> points = broadcastSets.get(cluster.id());
+ return points == null || points.isEmpty() || points.contains(connectPoint);
+ }
+
+ /**
+ * Returns the size of the cluster broadcast set.
+ *
+ * @param clusterId cluster identifier
+ * @return size of the cluster broadcast set
+ */
+ int broadcastSetSize(ClusterId clusterId) {
+ return broadcastSets.get(clusterId).size();
+ }
+
+ /**
+ * Returns the set of pre-computed shortest paths between source and
+ * destination devices.
+ *
+ * @param src source device
+ * @param dst destination device
+ * @return set of shortest paths
+ */
+ Set<Path> getPaths(DeviceId src, DeviceId dst) {
+ return paths.get(new PathKey(src, dst));
+ }
+
+ /**
+ * Computes on-demand the set of shortest paths between source and
+ * destination devices.
+ *
+ * @param src source device
+ * @param dst destination device
+ * @return set of shortest paths
+ */
+ Set<Path> getPaths(DeviceId src, DeviceId dst, LinkWeight weight) {
+ GraphPathSearch.Result<TopologyVertex, TopologyEdge> result =
+ DIJKSTRA.search(graph, new DefaultTopologyVertex(src),
+ new DefaultTopologyVertex(dst), weight);
+ ImmutableSet.Builder<Path> builder = ImmutableSet.builder();
+ for (org.onlab.graph.Path<TopologyVertex, TopologyEdge> path : result.paths()) {
+ builder.add(networkPath(path));
+ }
+ return builder.build();
+ }
+
+
+ // Searches the graph for all shortest paths and returns the search results.
+ private ImmutableMap<DeviceId, Result<TopologyVertex, TopologyEdge>> searchForShortestPaths() {
+ ImmutableMap.Builder<DeviceId, Result<TopologyVertex, TopologyEdge>> builder = ImmutableMap.builder();
+
+ // Search graph paths for each source to all destinations.
+ LinkWeight weight = new HopCountLinkWeight(graph.getVertexes().size());
+ for (TopologyVertex src : graph.getVertexes()) {
+ builder.put(src.deviceId(), DIJKSTRA.search(graph, src, null, weight));
+ }
+ return builder.build();
+ }
+
+ // Builds network paths from the graph path search results
+ private ImmutableSetMultimap<PathKey, Path> buildPaths() {
+ Builder<PathKey, Path> builder = ImmutableSetMultimap.builder();
+ for (DeviceId deviceId : results.keySet()) {
+ Result<TopologyVertex, TopologyEdge> result = results.get(deviceId);
+ for (org.onlab.graph.Path<TopologyVertex, TopologyEdge> path : result.paths()) {
+ builder.put(new PathKey(path.src().deviceId(), path.dst().deviceId()),
+ networkPath(path));
+ }
+ }
+ return builder.build();
+ }
+
+ // Converts graph path to a network path with the same cost.
+ private Path networkPath(org.onlab.graph.Path<TopologyVertex, TopologyEdge> path) {
+ List<Link> links = new ArrayList<>();
+ for (TopologyEdge edge : path.edges()) {
+ links.add(edge.link());
+ }
+ return new DefaultPath(PID, links, path.cost());
+ }
+
+
+ // Searches for SCC clusters in the network topology graph using Tarjan
+ // algorithm.
+ private SCCResult<TopologyVertex, TopologyEdge> searchForClusters() {
+ return TARJAN.search(graph, new NoIndirectLinksWeight());
+ }
+
+ // Builds the topology clusters and returns the id-cluster bindings.
+ private ImmutableMap<ClusterId, TopologyCluster> buildTopologyClusters() {
+ ImmutableMap.Builder<ClusterId, TopologyCluster> clusterBuilder = ImmutableMap.builder();
+ SCCResult<TopologyVertex, TopologyEdge> result =
+ TARJAN.search(graph, new NoIndirectLinksWeight());
+
+ // Extract both vertexes and edges from the results; the lists form
+ // pairs along the same index.
+ List<Set<TopologyVertex>> clusterVertexes = result.clusterVertexes();
+ List<Set<TopologyEdge>> clusterEdges = result.clusterEdges();
+
+ // Scan over the lists and create a cluster from the results.
+ for (int i = 0, n = result.clusterCount(); i < n; i++) {
+ Set<TopologyVertex> vertexSet = clusterVertexes.get(i);
+ Set<TopologyEdge> edgeSet = clusterEdges.get(i);
+
+ ClusterId cid = ClusterId.clusterId(i);
+ DefaultTopologyCluster cluster =
+ new DefaultTopologyCluster(cid, vertexSet.size(), edgeSet.size(),
+ findRoot(vertexSet).deviceId());
+ clusterBuilder.put(cid, cluster);
+ }
+ return clusterBuilder.build();
+ }
+
+ // Finds the vertex whose device id is the lexicographical minimum in the
+ // specified set.
+ private TopologyVertex findRoot(Set<TopologyVertex> vertexSet) {
+ TopologyVertex minVertex = null;
+ for (TopologyVertex vertex : vertexSet) {
+ if (minVertex == null ||
+ minVertex.deviceId().toString()
+ .compareTo(minVertex.deviceId().toString()) < 0) {
+ minVertex = vertex;
+ }
+ }
+ return minVertex;
+ }
+
+ // Processes a map of broadcast sets for each cluster.
+ private ImmutableSetMultimap<ClusterId, ConnectPoint> buildBroadcastSets() {
+ Builder<ClusterId, ConnectPoint> builder = ImmutableSetMultimap.builder();
+ for (TopologyCluster cluster : clusters.values()) {
+ addClusterBroadcastSet(cluster, builder);
+ }
+ return builder.build();
+ }
+
+ // Finds all broadcast points for the cluster. These are those connection
+ // points which lie along the shortest paths between the cluster root and
+ // all other devices within the cluster.
+ private void addClusterBroadcastSet(TopologyCluster cluster,
+ Builder<ClusterId, ConnectPoint> builder) {
+ // Use the graph root search results to build the broadcast set.
+ Result<TopologyVertex, TopologyEdge> result = results.get(cluster.root());
+ for (Map.Entry<TopologyVertex, Set<TopologyEdge>> entry : result.parents().entrySet()) {
+ TopologyVertex vertex = entry.getKey();
+
+ // Ignore any parents that lead outside the cluster.
+ if (clustersByDevice.get(vertex.deviceId()) != cluster) {
+ continue;
+ }
+
+ // Ignore any back-link sets that are empty.
+ Set<TopologyEdge> parents = entry.getValue();
+ if (parents.isEmpty()) {
+ continue;
+ }
+
+ // Use the first back-link source and destinations to add to the
+ // broadcast set.
+ Link link = parents.iterator().next().link();
+ builder.put(cluster.id(), link.src());
+ builder.put(cluster.id(), link.dst());
+ }
+ }
+
+ // Collects and returns an set of all infrastructure link end-points.
+ private ImmutableSet<ConnectPoint> findInfrastructurePoints() {
+ ImmutableSet.Builder<ConnectPoint> builder = ImmutableSet.builder();
+ for (TopologyEdge edge : graph.getEdges()) {
+ builder.add(edge.link().src());
+ builder.add(edge.link().dst());
+ }
+ return builder.build();
+ }
+
+ // Builds cluster-devices, cluster-links and device-cluster indexes.
+ private void buildIndexes() {
+ // Prepare the index builders
+ ImmutableMap.Builder<DeviceId, TopologyCluster> clusterBuilder = ImmutableMap.builder();
+ ImmutableSetMultimap.Builder<TopologyCluster, DeviceId> devicesBuilder = ImmutableSetMultimap.builder();
+ ImmutableSetMultimap.Builder<TopologyCluster, Link> linksBuilder = ImmutableSetMultimap.builder();
+
+ // Now scan through all the clusters
+ for (TopologyCluster cluster : clusters.values()) {
+ int i = cluster.id().index();
+
+ // Scan through all the cluster vertexes.
+ for (TopologyVertex vertex : clusterResults.clusterVertexes().get(i)) {
+ devicesBuilder.put(cluster, vertex.deviceId());
+ clusterBuilder.put(vertex.deviceId(), cluster);
+ }
+
+ // Scan through all the cluster edges.
+ for (TopologyEdge edge : clusterResults.clusterEdges().get(i)) {
+ linksBuilder.put(cluster, edge.link());
+ }
+ }
+
+ // Finalize all indexes.
+ clustersByDevice = clusterBuilder.build();
+ devicesByCluster = devicesBuilder.build();
+ linksByCluster = linksBuilder.build();
+ }
+
+ // Link weight for measuring link cost as hop count with indirect links
+ // being as expensive as traversing the entire graph to assume the worst.
+ private static class HopCountLinkWeight implements LinkWeight {
+ private final int indirectLinkCost;
+
+ HopCountLinkWeight(int indirectLinkCost) {
+ this.indirectLinkCost = indirectLinkCost;
+ }
+
+ @Override
+ public double weight(TopologyEdge edge) {
+ // To force preference to use direct paths first, make indirect
+ // links as expensive as the linear vertex traversal.
+ return edge.link().type() == INDIRECT ? indirectLinkCost : 1;
+ }
+ }
+
+ // Link weight for preventing traversal over indirect links.
+ private static class NoIndirectLinksWeight implements LinkWeight {
+ @Override
+ public double weight(TopologyEdge edge) {
+ return edge.link().type() == INDIRECT ? -1 : 1;
+ }
+ }
+
+ @Override
+ public String toString() {
+ return toStringHelper(this)
+ .add("time", time)
+ .add("clusters", clusterCount())
+ .add("devices", deviceCount())
+ .add("links", linkCount())
+ .add("pathCount", pathCount())
+ .toString();
+ }
+}
diff --git a/core/store/dist/src/main/java/org/onlab/onos/store/topology/impl/DefaultTopologyGraph.java b/core/store/dist/src/main/java/org/onlab/onos/store/topology/impl/DefaultTopologyGraph.java
new file mode 100644
index 0000000..945ba05
--- /dev/null
+++ b/core/store/dist/src/main/java/org/onlab/onos/store/topology/impl/DefaultTopologyGraph.java
@@ -0,0 +1,28 @@
+package org.onlab.onos.store.topology.impl;
+
+import org.onlab.graph.AdjacencyListsGraph;
+import org.onlab.onos.net.topology.TopologyEdge;
+import org.onlab.onos.net.topology.TopologyGraph;
+import org.onlab.onos.net.topology.TopologyVertex;
+
+import java.util.Set;
+
+/**
+ * Default implementation of an immutable topology graph based on a generic
+ * implementation of adjacency lists graph.
+ */
+public class DefaultTopologyGraph
+ extends AdjacencyListsGraph<TopologyVertex, TopologyEdge>
+ implements TopologyGraph {
+
+ /**
+ * Creates a topology graph comprising of the specified vertexes and edges.
+ *
+ * @param vertexes set of graph vertexes
+ * @param edges set of graph edges
+ */
+ public DefaultTopologyGraph(Set<TopologyVertex> vertexes, Set<TopologyEdge> edges) {
+ super(vertexes, edges);
+ }
+
+}
diff --git a/core/store/dist/src/main/java/org/onlab/onos/store/topology/impl/DistributedTopologyStore.java b/core/store/dist/src/main/java/org/onlab/onos/store/topology/impl/DistributedTopologyStore.java
new file mode 100644
index 0000000..567861e
--- /dev/null
+++ b/core/store/dist/src/main/java/org/onlab/onos/store/topology/impl/DistributedTopologyStore.java
@@ -0,0 +1,141 @@
+package org.onlab.onos.store.topology.impl;
+
+import static org.slf4j.LoggerFactory.getLogger;
+
+import java.util.List;
+import java.util.Set;
+
+import org.apache.felix.scr.annotations.Activate;
+import org.apache.felix.scr.annotations.Component;
+import org.apache.felix.scr.annotations.Deactivate;
+import org.apache.felix.scr.annotations.Service;
+import org.onlab.onos.event.Event;
+import org.onlab.onos.net.ConnectPoint;
+import org.onlab.onos.net.DeviceId;
+import org.onlab.onos.net.Link;
+import org.onlab.onos.net.Path;
+import org.onlab.onos.net.provider.ProviderId;
+import org.onlab.onos.net.topology.ClusterId;
+import org.onlab.onos.net.topology.GraphDescription;
+import org.onlab.onos.net.topology.LinkWeight;
+import org.onlab.onos.net.topology.Topology;
+import org.onlab.onos.net.topology.TopologyCluster;
+import org.onlab.onos.net.topology.TopologyEvent;
+import org.onlab.onos.net.topology.TopologyGraph;
+import org.onlab.onos.net.topology.TopologyStore;
+import org.onlab.onos.net.topology.TopologyStoreDelegate;
+import org.onlab.onos.store.AbstractStore;
+import org.slf4j.Logger;
+
+/**
+ * Manages inventory of topology snapshots using trivial in-memory
+ * structures implementation.
+ */
+//FIXME: I LIE I AM NOT DISTRIBUTED
+@Component(immediate = true)
+@Service
+public class DistributedTopologyStore
+extends AbstractStore<TopologyEvent, TopologyStoreDelegate>
+implements TopologyStore {
+
+ private final Logger log = getLogger(getClass());
+
+ private volatile DefaultTopology current;
+
+ @Activate
+ public void activate() {
+ log.info("Started");
+ }
+
+ @Deactivate
+ public void deactivate() {
+ log.info("Stopped");
+ }
+ @Override
+ public Topology currentTopology() {
+ return current;
+ }
+
+ @Override
+ public boolean isLatest(Topology topology) {
+ // Topology is current only if it is the same as our current topology
+ return topology == current;
+ }
+
+ @Override
+ public TopologyGraph getGraph(Topology topology) {
+ return defaultTopology(topology).getGraph();
+ }
+
+ @Override
+ public Set<TopologyCluster> getClusters(Topology topology) {
+ return defaultTopology(topology).getClusters();
+ }
+
+ @Override
+ public TopologyCluster getCluster(Topology topology, ClusterId clusterId) {
+ return defaultTopology(topology).getCluster(clusterId);
+ }
+
+ @Override
+ public Set<DeviceId> getClusterDevices(Topology topology, TopologyCluster cluster) {
+ return defaultTopology(topology).getClusterDevices(cluster);
+ }
+
+ @Override
+ public Set<Link> getClusterLinks(Topology topology, TopologyCluster cluster) {
+ return defaultTopology(topology).getClusterLinks(cluster);
+ }
+
+ @Override
+ public Set<Path> getPaths(Topology topology, DeviceId src, DeviceId dst) {
+ return defaultTopology(topology).getPaths(src, dst);
+ }
+
+ @Override
+ public Set<Path> getPaths(Topology topology, DeviceId src, DeviceId dst,
+ LinkWeight weight) {
+ return defaultTopology(topology).getPaths(src, dst, weight);
+ }
+
+ @Override
+ public boolean isInfrastructure(Topology topology, ConnectPoint connectPoint) {
+ return defaultTopology(topology).isInfrastructure(connectPoint);
+ }
+
+ @Override
+ public boolean isBroadcastPoint(Topology topology, ConnectPoint connectPoint) {
+ return defaultTopology(topology).isBroadcastPoint(connectPoint);
+ }
+
+ @Override
+ public TopologyEvent updateTopology(ProviderId providerId,
+ GraphDescription graphDescription,
+ List<Event> reasons) {
+ // First off, make sure that what we're given is indeed newer than
+ // what we already have.
+ if (current != null && graphDescription.timestamp() < current.time()) {
+ return null;
+ }
+
+ // Have the default topology construct self from the description data.
+ DefaultTopology newTopology =
+ new DefaultTopology(providerId, graphDescription);
+
+ // Promote the new topology to current and return a ready-to-send event.
+ synchronized (this) {
+ current = newTopology;
+ return new TopologyEvent(TopologyEvent.Type.TOPOLOGY_CHANGED, current);
+ }
+ }
+
+ // Validates the specified topology and returns it as a default
+ private DefaultTopology defaultTopology(Topology topology) {
+ if (topology instanceof DefaultTopology) {
+ return (DefaultTopology) topology;
+ }
+ throw new IllegalArgumentException("Topology class " + topology.getClass() +
+ " not supported");
+ }
+
+}
diff --git a/core/store/dist/src/main/java/org/onlab/onos/store/topology/impl/PathKey.java b/core/store/dist/src/main/java/org/onlab/onos/store/topology/impl/PathKey.java
new file mode 100644
index 0000000..60736b9
--- /dev/null
+++ b/core/store/dist/src/main/java/org/onlab/onos/store/topology/impl/PathKey.java
@@ -0,0 +1,40 @@
+package org.onlab.onos.store.topology.impl;
+
+import org.onlab.onos.net.DeviceId;
+
+import java.util.Objects;
+
+/**
+ * Key for filing pre-computed paths between source and destination devices.
+ */
+class PathKey {
+ private final DeviceId src;
+ private final DeviceId dst;
+
+ /**
+ * Creates a path key from the given source/dest pair.
+ * @param src source device
+ * @param dst destination device
+ */
+ PathKey(DeviceId src, DeviceId dst) {
+ this.src = src;
+ this.dst = dst;
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hash(src, dst);
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj) {
+ return true;
+ }
+ if (obj instanceof PathKey) {
+ final PathKey other = (PathKey) obj;
+ return Objects.equals(this.src, other.src) && Objects.equals(this.dst, other.dst);
+ }
+ return false;
+ }
+}