[ONOS-4051] Path computation algorithm implementation (Coding & UT).
Change-Id: If94be2ba2a010a203003b7ce38289b516ab20f59
diff --git a/apps/pce/app/src/main/java/org/onosproject/pce/pceservice/PceManager.java b/apps/pce/app/src/main/java/org/onosproject/pce/pceservice/PceManager.java
index 2ff3a49..7ea9934 100644
--- a/apps/pce/app/src/main/java/org/onosproject/pce/pceservice/PceManager.java
+++ b/apps/pce/app/src/main/java/org/onosproject/pce/pceservice/PceManager.java
@@ -18,8 +18,10 @@
import static com.google.common.base.Preconditions.checkNotNull;
import static org.onosproject.incubator.net.tunnel.Tunnel.Type.MPLS;
+import java.util.Collections;
import java.util.Iterator;
import java.util.List;
+import java.util.Set;
import org.apache.felix.scr.annotations.Activate;
import org.apache.felix.scr.annotations.Component;
@@ -34,8 +36,15 @@
import org.onosproject.incubator.net.tunnel.TunnelId;
import org.onosproject.incubator.net.tunnel.TunnelService;
import org.onosproject.net.DeviceId;
+import org.onosproject.net.Path;
import org.onosproject.net.intent.Constraint;
+import org.onosproject.net.device.DeviceService;
+import org.onosproject.net.resource.ResourceService;
+import org.onosproject.net.topology.LinkWeight;
+import org.onosproject.net.topology.PathService;
+import org.onosproject.net.topology.TopologyEdge;
import org.onosproject.pce.pceservice.api.PceService;
+import org.onosproject.pce.pceservice.constraint.CapabilityConstraint;
import org.onosproject.store.serializers.KryoNamespaces;
import org.onosproject.store.service.DistributedSet;
import org.onosproject.store.service.Serializer;
@@ -43,6 +52,8 @@
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
+import com.google.common.collect.ImmutableList;
+
/**
* Implementation of PCE service.
*/
@@ -66,6 +77,15 @@
@Reference(cardinality = ReferenceCardinality.MANDATORY_UNARY)
protected StorageService storageService;
+ @Reference(cardinality = ReferenceCardinality.MANDATORY_UNARY)
+ protected PathService pathService;
+
+ @Reference(cardinality = ReferenceCardinality.MANDATORY_UNARY)
+ protected ResourceService resourceService;
+
+ @Reference(cardinality = ReferenceCardinality.MANDATORY_UNARY)
+ protected DeviceService deviceService;
+
private ApplicationId appId;
/**
@@ -92,6 +112,36 @@
log.info("Stopped");
}
+ /**
+ * Returns an edge-weight capable of evaluating links on the basis of the
+ * specified constraints.
+ *
+ * @param constraints path constraints
+ * @return edge-weight function
+ */
+ private LinkWeight weight(List<Constraint> constraints) {
+ return new TeConstraintBasedLinkWeight(constraints);
+ }
+
+ /**
+ * Computes a path between two devices.
+ *
+ * @param src ingress device
+ * @param dst egress device
+ * @param constraints path constraints
+ * @return computed path based on constraints
+ */
+ protected Set<Path> computePath(DeviceId src, DeviceId dst, List<Constraint> constraints) {
+ if (pathService == null) {
+ return null;
+ }
+ Set<Path> paths = pathService.getPaths(src, dst, weight(constraints));
+ if (!paths.isEmpty()) {
+ return paths;
+ }
+ return null;
+ }
+
//[TODO:] handle requests in queue
@Override
public boolean setupPath(DeviceId src, DeviceId dst, String tunnelName, List<Constraint> constraints,
@@ -103,8 +153,8 @@
checkNotNull(lspType);
// TODO: compute and setup path.
-
- return true;
+ //TODO: gets the path based on constraints and creates a tunnel in network via tunnel manager
+ return computePath(src, dst, constraints) != null ? true : false;
}
@@ -159,4 +209,44 @@
return value;
}
+ protected class TeConstraintBasedLinkWeight implements LinkWeight {
+
+ private final List<Constraint> constraints;
+
+ /**
+ * Creates a new edge-weight function capable of evaluating links
+ * on the basis of the specified constraints.
+ *
+ * @param constraints path constraints
+ */
+ public TeConstraintBasedLinkWeight(List<Constraint> constraints) {
+ if (constraints == null) {
+ this.constraints = Collections.emptyList();
+ } else {
+ this.constraints = ImmutableList.copyOf(constraints);
+ }
+ }
+
+ @Override
+ public double weight(TopologyEdge edge) {
+ if (!constraints.iterator().hasNext()) {
+ //Takes default cost/hopcount as 1 if no constraints specified
+ return 1.0;
+ }
+
+ Iterator<Constraint> it = constraints.iterator();
+ double cost = 1;
+
+ //If any constraint fails return -1 also value of cost returned from cost constraint can't be negative
+ while (it.hasNext() && cost > 0) {
+ Constraint constraint = it.next();
+ if (constraint instanceof CapabilityConstraint) {
+ cost = ((CapabilityConstraint) constraint).isValidLink(edge.link(), deviceService) ? 1 : -1;
+ } else {
+ cost = constraint.cost(edge.link(), resourceService::isAvailable);
+ }
+ }
+ return cost;
+ }
+ }
}
\ No newline at end of file
diff --git a/apps/pce/app/src/main/java/org/onosproject/pce/pceservice/constraint/CapabilityConstraint.java b/apps/pce/app/src/main/java/org/onosproject/pce/pceservice/constraint/CapabilityConstraint.java
new file mode 100644
index 0000000..a479c38
--- /dev/null
+++ b/apps/pce/app/src/main/java/org/onosproject/pce/pceservice/constraint/CapabilityConstraint.java
@@ -0,0 +1,219 @@
+/*
+ * Copyright 2016-present Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.onosproject.pce.pceservice.constraint;
+
+import org.onosproject.net.AnnotationKeys;
+import org.onosproject.net.Device;
+import org.onosproject.net.Link;
+import org.onosproject.net.device.DeviceService;
+import org.onosproject.net.intent.ResourceContext;
+import org.onosproject.net.intent.constraint.BooleanConstraint;
+
+import java.util.Objects;
+
+import static com.google.common.base.MoreObjects.toStringHelper;
+
+/**
+ * Constraint that evaluates whether devices satisfies capability.
+ */
+public final class CapabilityConstraint extends BooleanConstraint {
+
+ private final CapabilityType capabilityType;
+ public static final String PCECC_CAPABILITY = "pceccCapability";
+ public static final String SR_CAPABILITY = "srCapability";
+ public static final String LABEL_STACK_CAPABILITY = "labelStackCapability";
+ public static final String LSRID = "lsrId";
+ public static final String L3 = "L3";
+ public static final String TRUE = "true";
+
+ /**
+ * Represents about capability type.
+ */
+ public enum CapabilityType {
+ /**
+ * Signifies that path is created via signaling mode.
+ */
+ WITH_SIGNALLING(0),
+
+ /**
+ * Signifies that path is created via SR mode.
+ */
+ SR_WITHOUT_SIGNALLING(1),
+
+ /**
+ * Signifies that path is created via without signaling and without SR mode.
+ */
+ WITHOUT_SIGNALLING_AND_WITHOUT_SR(2);
+
+ int value;
+
+ /**
+ * Assign val with the value as the capability type.
+ *
+ * @param val capability type
+ */
+ CapabilityType(int val) {
+ value = val;
+ }
+
+ /**
+ * Returns value of capability type.
+ *
+ * @return capability type
+ */
+ public byte type() {
+ return (byte) value;
+ }
+ }
+
+ // Constructor for serialization
+ private CapabilityConstraint() {
+ capabilityType = null;
+ }
+
+ /**
+ * Creates a new capability constraint.
+ *
+ * @param capabilityType type of capability device supports
+ */
+ public CapabilityConstraint(CapabilityType capabilityType) {
+ this.capabilityType = capabilityType;
+ }
+
+ /**
+ * Creates a new capability constraint.
+ *
+ * @param capabilityType type of capability device supports
+ * @return instance of CapabilityConstraint for specified capability type
+ */
+ public static CapabilityConstraint of(CapabilityType capabilityType) {
+ return new CapabilityConstraint(capabilityType);
+ }
+
+ /**
+ * Obtains type of capability.
+ *
+ * @return type of capability
+ */
+ public CapabilityType capabilityType() {
+ return capabilityType;
+ }
+
+ /**
+ * Validates the link based on capability constraint.
+ *
+ * @param link to validate source and destination based on capability constraint
+ * @param deviceService instance of DeviceService
+ * @return true if link satisfies capability constraint otherwise false
+ */
+ public boolean isValidLink(Link link, DeviceService deviceService) {
+ if (deviceService == null) {
+ return false;
+ }
+
+ Device srcDevice = deviceService.getDevice(link.src().deviceId());
+ Device dstDevice = deviceService.getDevice(link.dst().deviceId());
+
+ //TODO: Usage of annotations are for transient solution. In future will be replaces with the
+ // network config service / Projection model.
+ // L3 device
+ if (srcDevice == null
+ || dstDevice == null
+ || srcDevice.annotations().value(AnnotationKeys.TYPE) == null
+ || dstDevice.annotations().value(AnnotationKeys.TYPE) == null
+ || !srcDevice.annotations().value(AnnotationKeys.TYPE).equals(L3)
+ || !dstDevice.annotations().value(AnnotationKeys.TYPE).equals(L3)) {
+ return false;
+ }
+
+ String scrLsrId = srcDevice.annotations().value(LSRID);
+ String dstLsrId = dstDevice.annotations().value(LSRID);
+
+ Device srcCapDevice = null;
+ Device dstCapDevice = null;
+
+ // Get Capability device
+ Iterable<Device> devices = deviceService.getAvailableDevices();
+ for (Device dev : devices) {
+ if (dev.annotations().value(LSRID).equals(scrLsrId)) {
+ srcCapDevice = dev;
+ } else if (dev.annotations().value(LSRID).equals(dstLsrId)) {
+ dstCapDevice = dev;
+ }
+ }
+
+ if (srcCapDevice == null || dstCapDevice == null) {
+ return false;
+ }
+
+ switch (capabilityType) {
+ case WITH_SIGNALLING:
+ return true;
+ case WITHOUT_SIGNALLING_AND_WITHOUT_SR:
+ if (srcCapDevice.annotations().value(PCECC_CAPABILITY) != null
+ && dstCapDevice.annotations().value(PCECC_CAPABILITY) != null) {
+ return srcCapDevice.annotations().value(PCECC_CAPABILITY).equals(TRUE)
+ && dstCapDevice.annotations().value(PCECC_CAPABILITY).equals(TRUE);
+ }
+ return false;
+ case SR_WITHOUT_SIGNALLING:
+ if (srcCapDevice.annotations().value(LABEL_STACK_CAPABILITY) != null
+ && dstCapDevice.annotations().value(LABEL_STACK_CAPABILITY) != null
+ && srcCapDevice.annotations().value(SR_CAPABILITY) != null
+ && dstCapDevice.annotations().value(SR_CAPABILITY) != null) {
+ return srcCapDevice.annotations().value(LABEL_STACK_CAPABILITY).equals(TRUE)
+ && dstCapDevice.annotations().value(LABEL_STACK_CAPABILITY).equals(TRUE)
+ && srcCapDevice.annotations().value(SR_CAPABILITY).equals(TRUE)
+ && dstCapDevice.annotations().value(SR_CAPABILITY).equals(TRUE);
+ }
+ return false;
+ default:
+ return false;
+ }
+ }
+
+ @Override
+ public boolean isValid(Link link, ResourceContext context) {
+ return false;
+ //Do nothing instead using isValidLink needs device service to validate link
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hash(capabilityType);
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj) {
+ return true;
+ }
+
+ if (obj instanceof CapabilityConstraint) {
+ CapabilityConstraint other = (CapabilityConstraint) obj;
+ return Objects.equals(this.capabilityType, other.capabilityType);
+ }
+
+ return false;
+ }
+
+ @Override
+ public String toString() {
+ return toStringHelper(this)
+ .add("capabilityType", capabilityType)
+ .toString();
+ }
+}
\ No newline at end of file
diff --git a/apps/pce/app/src/main/java/org/onosproject/pce/pceservice/constraint/CostConstraint.java b/apps/pce/app/src/main/java/org/onosproject/pce/pceservice/constraint/CostConstraint.java
new file mode 100644
index 0000000..229644d
--- /dev/null
+++ b/apps/pce/app/src/main/java/org/onosproject/pce/pceservice/constraint/CostConstraint.java
@@ -0,0 +1,160 @@
+/*
+ * Copyright 2016-present Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.onosproject.pce.pceservice.constraint;
+
+import org.onosproject.net.Link;
+import org.onosproject.net.Path;
+import org.onosproject.net.intent.ResourceContext;
+import org.onosproject.net.intent.Constraint;
+
+import java.util.Objects;
+
+import static com.google.common.base.MoreObjects.toStringHelper;
+import static com.google.common.base.Preconditions.checkNotNull;
+
+/**
+ * Constraint that evaluates whether cost for a link is available, if yes return cost for that link.
+ */
+public final class CostConstraint implements Constraint {
+
+ /**
+ * Represents about cost types.
+ */
+ public enum Type {
+ /**
+ * Signifies that cost is IGP cost.
+ */
+ COST(1),
+
+ /**
+ * Signifies that cost is TE cost.
+ */
+ TE_COST(2);
+
+ int value;
+
+ /**
+ * Assign val with the value as the Cost type.
+ *
+ * @param val Cost type
+ */
+ Type(int val) {
+ value = val;
+ }
+
+ /**
+ * Returns value of Cost type.
+ *
+ * @return Cost type
+ */
+ public byte type() {
+ return (byte) value;
+ }
+ }
+
+ private final Type type;
+ public static final String TE_COST = "teCost";
+ public static final String COST = "cost";
+
+ // Constructor for serialization
+ private CostConstraint() {
+ this.type = null;
+ }
+
+ /**
+ * Creates a new cost constraint.
+ *
+ * @param type of a link
+ */
+ public CostConstraint(Type type) {
+ this.type = checkNotNull(type, "Type cannot be null");
+ }
+
+ /**
+ * Creates new CostConstraint with specified cost type.
+ *
+ * @param type of cost
+ * @return instance of CostConstraint
+ */
+ public static CostConstraint of(Type type) {
+ return new CostConstraint(type);
+ }
+
+ /**
+ * Returns the type of a cost specified in a constraint.
+ *
+ * @return required cost type
+ */
+ public Type type() {
+ return type;
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hash(type);
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj) {
+ return true;
+ }
+
+ if (obj instanceof CostConstraint) {
+ CostConstraint other = (CostConstraint) obj;
+ return Objects.equals(this.type, other.type);
+ }
+
+ return false;
+ }
+
+ @Override
+ public String toString() {
+ return toStringHelper(this)
+ .add("type", type)
+ .toString();
+ }
+
+ @Override
+ public double cost(Link link, ResourceContext context) {
+ //TODO: Usage of annotations are for transient solution. In future will be replaces with the
+ // network config service / Projection model.
+ switch (type) {
+ case COST:
+ if (link.annotations().value(COST) != null) {
+ return Double.parseDouble(link.annotations().value(COST));
+ }
+
+ //If cost annotations absent return -1[It is not L3 device]
+ return -1;
+ case TE_COST:
+ if (link.annotations().value(TE_COST) != null) {
+ return Double.parseDouble(link.annotations().value(TE_COST));
+ }
+
+ //If TE cost annotations absent return -1[It is not L3 device]
+ return -1;
+ default:
+ return -1;
+ }
+ }
+
+ @Override
+ public boolean validate(Path path, ResourceContext context) {
+ // TODO Auto-generated method stub
+ return false;
+ }
+}
\ No newline at end of file
diff --git a/apps/pce/app/src/main/java/org/onosproject/pce/pceservice/constraint/SharedBandwidthConstraint.java b/apps/pce/app/src/main/java/org/onosproject/pce/pceservice/constraint/SharedBandwidthConstraint.java
new file mode 100644
index 0000000..2985f24
--- /dev/null
+++ b/apps/pce/app/src/main/java/org/onosproject/pce/pceservice/constraint/SharedBandwidthConstraint.java
@@ -0,0 +1,143 @@
+/*
+ * Copyright 2016-present Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.onosproject.pce.pceservice.constraint;
+
+import org.onlab.util.Bandwidth;
+import org.onosproject.net.Link;
+import org.onosproject.net.intent.ResourceContext;
+import org.onosproject.net.intent.constraint.BooleanConstraint;
+import org.onosproject.net.resource.Resources;
+
+import java.util.List;
+import java.util.Objects;
+import java.util.stream.Stream;
+
+import static com.google.common.base.MoreObjects.toStringHelper;
+
+/**
+ * Constraint that evaluates whether links satisfies sharedbandwidth request.
+ */
+public final class SharedBandwidthConstraint extends BooleanConstraint {
+
+ private final List<Link> links;
+ private final Bandwidth sharedBwValue;
+ private final Bandwidth requestBwValue;
+ //temporary variable declared to hold changed bandwidth value
+ private Bandwidth changedBwValue;
+
+ // Constructor for serialization
+ private SharedBandwidthConstraint() {
+ links = null;
+ sharedBwValue = null;
+ requestBwValue = null;
+ }
+
+ /**
+ * Creates a new SharedBandwidth constraint.
+ *
+ * @param links shared links
+ * @param sharedBwValue shared bandwidth of the links
+ * @param requestBwValue requested bandwidth value
+ */
+ public SharedBandwidthConstraint(List<Link> links, Bandwidth sharedBwValue, Bandwidth requestBwValue) {
+ this.links = links;
+ this.sharedBwValue = sharedBwValue;
+ this.requestBwValue = requestBwValue;
+ }
+
+ /**
+ * Creates a new SharedBandwidth constraint.
+ *
+ * @param links shared links
+ * @param sharedBwValue shared bandwidth of the links
+ * @param requestBwValue requested bandwidth value
+ * @return SharedBandwidth instance
+ */
+ public static SharedBandwidthConstraint of(List<Link> links, Bandwidth sharedBwValue, Bandwidth requestBwValue) {
+ return new SharedBandwidthConstraint(links, sharedBwValue, requestBwValue);
+ }
+
+ /**
+ * Obtains shared links.
+ *
+ * @return shared links
+ */
+ public List<Link> links() {
+ return links;
+ }
+
+ /**
+ * Obtains shared bandwidth of the links.
+ *
+ * @return shared bandwidth
+ */
+ public Bandwidth sharedBwValue() {
+ return sharedBwValue;
+ }
+
+ /**
+ * Obtains requested bandwidth value.
+ *
+ * @return requested bandwidth value
+ */
+ public Bandwidth requestBwValue() {
+ return requestBwValue;
+ }
+
+ @Override
+ public boolean isValid(Link link, ResourceContext context) {
+ changedBwValue = requestBwValue;
+ if (links.contains(link)) {
+ changedBwValue = requestBwValue.isGreaterThan(sharedBwValue) ? requestBwValue.subtract(sharedBwValue)
+ : Bandwidth.bps(0);
+ }
+
+ return Stream
+ .of(link.src(), link.dst())
+ .map(cp -> Resources.continuous(cp.deviceId(), cp.port(), Bandwidth.class).resource(
+ changedBwValue.bps())).allMatch(context::isAvailable);
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hash(requestBwValue, sharedBwValue, links);
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj) {
+ return true;
+ }
+
+ if (obj instanceof SharedBandwidthConstraint) {
+ SharedBandwidthConstraint other = (SharedBandwidthConstraint) obj;
+ return Objects.equals(this.requestBwValue, other.requestBwValue)
+ && Objects.equals(this.sharedBwValue, other.sharedBwValue)
+ && Objects.equals(this.links, other.links);
+ }
+
+ return false;
+ }
+
+ @Override
+ public String toString() {
+ return toStringHelper(this)
+ .add("requestBwValue", requestBwValue)
+ .add("sharedBwValue", sharedBwValue)
+ .add("links", links)
+ .toString();
+ }
+}
\ No newline at end of file
diff --git a/apps/pce/app/src/main/java/org/onosproject/pce/pceservice/constraint/package-info.java b/apps/pce/app/src/main/java/org/onosproject/pce/pceservice/constraint/package-info.java
new file mode 100644
index 0000000..a788a42
--- /dev/null
+++ b/apps/pce/app/src/main/java/org/onosproject/pce/pceservice/constraint/package-info.java
@@ -0,0 +1,20 @@
+/*
+ * Copyright 2016-present Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/**
+ * Constraints for path computation for PCE service.
+ */
+package org.onosproject.pce.pceservice.constraint;