diff options
Diffstat (limited to 'opendc-simulator/opendc-simulator-flow/src/main/java/org')
8 files changed, 319 insertions, 54 deletions
diff --git a/opendc-simulator/opendc-simulator-flow/src/main/java/org/opendc/simulator/engine/graph/FlowConsumer.java b/opendc-simulator/opendc-simulator-flow/src/main/java/org/opendc/simulator/engine/graph/FlowConsumer.java index a9da6f5d..ac6ba8da 100644 --- a/opendc-simulator/opendc-simulator-flow/src/main/java/org/opendc/simulator/engine/graph/FlowConsumer.java +++ b/opendc-simulator/opendc-simulator-flow/src/main/java/org/opendc/simulator/engine/graph/FlowConsumer.java @@ -22,13 +22,28 @@ package org.opendc.simulator.engine.graph; +import org.opendc.common.ResourceType; + public interface FlowConsumer { void handleIncomingSupply(FlowEdge supplierEdge, double newSupply); + default void handleIncomingSupply(FlowEdge supplierEdge, double newSupply, ResourceType resourceType) { + handleIncomingSupply(supplierEdge, newSupply); + } + void pushOutgoingDemand(FlowEdge supplierEdge, double newDemand); + default void pushOutgoingDemand(FlowEdge supplierEdge, double newDemand, ResourceType resourceType) { + pushOutgoingDemand(supplierEdge, newDemand); + } + void addSupplierEdge(FlowEdge supplierEdge); void removeSupplierEdge(FlowEdge supplierEdge); + + // needed for flow nodes with multiple edges to same other flow node (PSU, VM) + default ResourceType getConsumerResourceType() { + return ResourceType.AUXILIARY; + } } diff --git a/opendc-simulator/opendc-simulator-flow/src/main/java/org/opendc/simulator/engine/graph/FlowDistributor.java b/opendc-simulator/opendc-simulator-flow/src/main/java/org/opendc/simulator/engine/graph/FlowDistributor.java index 09cd73f6..674db8ca 100644 --- a/opendc-simulator/opendc-simulator-flow/src/main/java/org/opendc/simulator/engine/graph/FlowDistributor.java +++ b/opendc-simulator/opendc-simulator-flow/src/main/java/org/opendc/simulator/engine/graph/FlowDistributor.java @@ -23,13 +23,15 @@ package org.opendc.simulator.engine.graph; import java.util.ArrayList; -import java.util.Arrays; import java.util.HashSet; import java.util.List; import java.util.Map; import java.util.Objects; import java.util.Set; +import org.opendc.common.ResourceType; import org.opendc.simulator.engine.engine.FlowEngine; +import org.opendc.simulator.engine.graph.distributionPolicies.DistributionPolicy; +import org.opendc.simulator.engine.graph.distributionPolicies.MaxMinFairnessPolicy; public class FlowDistributor extends FlowNode implements FlowSupplier, FlowConsumer { private final ArrayList<FlowEdge> consumerEdges = new ArrayList<>(); @@ -47,9 +49,16 @@ public class FlowDistributor extends FlowNode implements FlowSupplier, FlowConsu private boolean overloaded = false; private double capacity; // What is the max capacity. Can probably be removed + private DistributionPolicy distributionPolicy; public FlowDistributor(FlowEngine engine) { super(engine); + this.distributionPolicy = new MaxMinFairnessPolicy(); + } + + public FlowDistributor(FlowEngine engine, DistributionPolicy distributionPolicy) { + super(engine); + this.distributionPolicy = distributionPolicy; } public double getTotalIncomingDemand() { @@ -88,6 +97,7 @@ public class FlowDistributor extends FlowNode implements FlowSupplier, FlowConsu this.invalidate(); } + // TODO: This should probably be moved to the distribution strategy private void updateOutgoingSupplies() { // If the demand is higher than the current supply, the system is overloaded. @@ -95,10 +105,11 @@ public class FlowDistributor extends FlowNode implements FlowSupplier, FlowConsu if (this.totalIncomingDemand > this.currentIncomingSupply) { this.overloaded = true; - double[] supplies = distributeSupply(this.incomingDemands, this.currentIncomingSupply); + double[] supplies = + this.distributionPolicy.distributeSupply(this.incomingDemands, this.currentIncomingSupply); for (int idx = 0; idx < this.consumerEdges.size(); idx++) { - this.pushOutgoingSupply(this.consumerEdges.get(idx), supplies[idx]); + this.pushOutgoingSupply(this.consumerEdges.get(idx), supplies[idx], this.getConsumerResourceType()); } } else { @@ -108,7 +119,10 @@ public class FlowDistributor extends FlowNode implements FlowSupplier, FlowConsu if (this.overloaded) { for (int idx = 0; idx < this.consumerEdges.size(); idx++) { if (!Objects.equals(this.outgoingSupplies.get(idx), this.incomingDemands.get(idx))) { - this.pushOutgoingSupply(this.consumerEdges.get(idx), this.incomingDemands.get(idx)); + this.pushOutgoingSupply( + this.consumerEdges.get(idx), + this.incomingDemands.get(idx), + this.getConsumerResourceType()); } } this.overloaded = false; @@ -117,7 +131,8 @@ public class FlowDistributor extends FlowNode implements FlowSupplier, FlowConsu // Update the supplies of the consumers that changed their demand in the current cycle else { for (int idx : this.updatedDemands) { - this.pushOutgoingSupply(this.consumerEdges.get(idx), this.incomingDemands.get(idx)); + this.pushOutgoingSupply( + this.consumerEdges.get(idx), this.incomingDemands.get(idx), this.getConsumerResourceType()); } } } @@ -125,48 +140,6 @@ public class FlowDistributor extends FlowNode implements FlowSupplier, FlowConsu this.updatedDemands.clear(); } - private record Demand(int idx, double value) {} - - /** - * Distributed the available supply over the different demands. - * The supply is distributed using MaxMin Fairness. - */ - private static double[] distributeSupply(ArrayList<Double> demands, double currentSupply) { - int inputSize = demands.size(); - - final double[] supplies = new double[inputSize]; - final Demand[] tempDemands = new Demand[inputSize]; - - for (int i = 0; i < inputSize; i++) { - tempDemands[i] = new Demand(i, demands.get(i)); - } - - Arrays.sort(tempDemands, (o1, o2) -> { - Double i1 = o1.value; - Double i2 = o2.value; - return i1.compareTo(i2); - }); - - double availableCapacity = currentSupply; // totalSupply - - for (int i = 0; i < inputSize; i++) { - double d = tempDemands[i].value; - - if (d == 0.0) { - continue; - } - - double availableShare = availableCapacity / (inputSize - i); - double r = Math.min(d, availableShare); - - int idx = tempDemands[i].idx; - supplies[idx] = r; // Update the rates - availableCapacity -= r; - } - - return supplies; - } - /** * Add a new consumer. * Set its demand and supply to 0.0 @@ -260,6 +233,15 @@ public class FlowDistributor extends FlowNode implements FlowSupplier, FlowConsu } @Override + public void handleIncomingDemand(FlowEdge consumerEdge, double newDemand, ResourceType resourceType) { + if (resourceType != this.getSupplierResourceType()) { + throw new IllegalArgumentException("Resource type " + resourceType + + " does not match distributor resource type " + this.getSupplierResourceType()); + } + this.handleIncomingDemand(consumerEdge, newDemand); + } + + @Override public void handleIncomingSupply(FlowEdge supplierEdge, double newSupply) { this.currentIncomingSupply = newSupply; @@ -268,7 +250,7 @@ public class FlowDistributor extends FlowNode implements FlowSupplier, FlowConsu @Override public void pushOutgoingDemand(FlowEdge supplierEdge, double newDemand) { - this.supplierEdge.pushDemand(newDemand); + this.supplierEdge.pushDemand(newDemand, false, this.getSupplierResourceType()); } @Override @@ -284,7 +266,8 @@ public class FlowDistributor extends FlowNode implements FlowSupplier, FlowConsu } outgoingSupplies.set(idx, newSupply); - consumerEdge.pushSupply(newSupply); + consumerEdge.pushSupply(newSupply, false, this.getSupplierResourceType()); + consumerEdge.pushSupply(newSupply, false, this.getSupplierResourceType()); } @Override @@ -293,4 +276,14 @@ public class FlowDistributor extends FlowNode implements FlowSupplier, FlowConsu return Map.of(FlowEdge.NodeType.CONSUMING, supplyingEdges, FlowEdge.NodeType.SUPPLYING, this.consumerEdges); } + + @Override + public ResourceType getSupplierResourceType() { + return this.supplierEdge.getSupplierResourceType(); + } + + @Override + public ResourceType getConsumerResourceType() { + return this.consumerEdges.getFirst().getConsumerResourceType(); + } } diff --git a/opendc-simulator/opendc-simulator-flow/src/main/java/org/opendc/simulator/engine/graph/FlowEdge.java b/opendc-simulator/opendc-simulator-flow/src/main/java/org/opendc/simulator/engine/graph/FlowEdge.java index 95eac20b..aa3894c1 100644 --- a/opendc-simulator/opendc-simulator-flow/src/main/java/org/opendc/simulator/engine/graph/FlowEdge.java +++ b/opendc-simulator/opendc-simulator-flow/src/main/java/org/opendc/simulator/engine/graph/FlowEdge.java @@ -22,6 +22,8 @@ package org.opendc.simulator.engine.graph; +import org.opendc.common.ResourceType; + /** * An edge that connects two FlowStages. * A connection between FlowStages always consist of a FlowStage that demands @@ -38,7 +40,9 @@ public class FlowEdge { private double demand = 0.0; private double supply = 0.0; - private double capacity; + private final double capacity; + + private final ResourceType resourceType; public enum NodeType { CONSUMING, @@ -46,6 +50,10 @@ public class FlowEdge { } public FlowEdge(FlowConsumer consumer, FlowSupplier supplier) { + this(consumer, supplier, ResourceType.AUXILIARY); + } + + public FlowEdge(FlowConsumer consumer, FlowSupplier supplier, ResourceType resourceType) { if (!(consumer instanceof FlowNode)) { throw new IllegalArgumentException("Flow consumer is not a FlowNode"); } @@ -55,8 +63,9 @@ public class FlowEdge { this.consumer = consumer; this.supplier = supplier; + this.resourceType = resourceType; - this.capacity = supplier.getCapacity(); + this.capacity = supplier.getCapacity(resourceType); this.consumer.addSupplierEdge(this); this.supplier.addConsumerEdge(this); @@ -112,6 +121,33 @@ public class FlowEdge { return this.supply; } + /** + * Get the resource type of this edge. + * + * @return The resource type of this edge. + */ + public ResourceType getResourceType() { + return this.resourceType; + } + + /** + * Get the resource type of the supplier of this edge. + * + * @return The resource type of the supplier. + */ + public ResourceType getSupplierResourceType() { + return this.supplier.getSupplierResourceType(); + } + + /** + * Get the resource type of the consumer of this edge. + * + * @return The resource type of the consumer. + */ + public ResourceType getConsumerResourceType() { + return this.consumer.getConsumerResourceType(); + } + public int getConsumerIndex() { return consumerIndex; } @@ -128,6 +164,16 @@ public class FlowEdge { this.supplierIndex = supplierIndex; } + public void pushDemand(double newDemand, boolean forceThrough, ResourceType resourceType) { + // or store last resource type in the edge + if ((newDemand == this.demand) && !forceThrough) { + return; + } + + this.demand = newDemand; + this.supplier.handleIncomingDemand(this, newDemand, resourceType); + } + /** * Push new demand from the Consumer to the Supplier */ @@ -150,19 +196,19 @@ public class FlowEdge { /** * Push new supply from the Supplier to the Consumer */ - public void pushSupply(double newSupply, boolean forceThrough) { + public void pushSupply(double newSupply, boolean forceThrough, ResourceType resourceType) { if ((newSupply == this.supply) && !forceThrough) { return; } this.supply = newSupply; - this.consumer.handleIncomingSupply(this, newSupply); + this.consumer.handleIncomingSupply(this, newSupply, resourceType); } /** * Push new supply from the Supplier to the Consumer */ public void pushSupply(double newSupply) { - this.pushSupply(newSupply, false); + this.pushSupply(newSupply, false, this.supplier.getSupplierResourceType()); } } diff --git a/opendc-simulator/opendc-simulator-flow/src/main/java/org/opendc/simulator/engine/graph/FlowSupplier.java b/opendc-simulator/opendc-simulator-flow/src/main/java/org/opendc/simulator/engine/graph/FlowSupplier.java index da65392b..eb665b8c 100644 --- a/opendc-simulator/opendc-simulator-flow/src/main/java/org/opendc/simulator/engine/graph/FlowSupplier.java +++ b/opendc-simulator/opendc-simulator-flow/src/main/java/org/opendc/simulator/engine/graph/FlowSupplier.java @@ -22,15 +22,35 @@ package org.opendc.simulator.engine.graph; +import org.opendc.common.ResourceType; + public interface FlowSupplier { void handleIncomingDemand(FlowEdge consumerEdge, double newDemand); + default void handleIncomingDemand(FlowEdge consumerEdge, double newDemand, ResourceType resourceType) { + handleIncomingDemand(consumerEdge, newDemand); + } + void pushOutgoingSupply(FlowEdge consumerEdge, double newSupply); + default void pushOutgoingSupply(FlowEdge consumerEdge, double newSupply, ResourceType resourceType) { + pushOutgoingSupply(consumerEdge, newSupply); + } + ; + void addConsumerEdge(FlowEdge consumerEdge); void removeConsumerEdge(FlowEdge consumerEdge); double getCapacity(); + + default double getCapacity(ResourceType resourceType) { + return getCapacity(); + } + + default ResourceType getSupplierResourceType() { + return ResourceType.AUXILIARY; + } + ; } diff --git a/opendc-simulator/opendc-simulator-flow/src/main/java/org/opendc/simulator/engine/graph/distributionPolicies/DistributionPolicy.java b/opendc-simulator/opendc-simulator-flow/src/main/java/org/opendc/simulator/engine/graph/distributionPolicies/DistributionPolicy.java new file mode 100644 index 00000000..9d2246cd --- /dev/null +++ b/opendc-simulator/opendc-simulator-flow/src/main/java/org/opendc/simulator/engine/graph/distributionPolicies/DistributionPolicy.java @@ -0,0 +1,29 @@ +/* + * Copyright (c) 2025 AtLarge Research + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +package org.opendc.simulator.engine.graph.distributionPolicies; + +import java.util.ArrayList; + +public interface DistributionPolicy { + double[] distributeSupply(ArrayList<Double> supply, double currentSupply); +} diff --git a/opendc-simulator/opendc-simulator-flow/src/main/java/org/opendc/simulator/engine/graph/distributionPolicies/DistributionPolicyFactory.java b/opendc-simulator/opendc-simulator-flow/src/main/java/org/opendc/simulator/engine/graph/distributionPolicies/DistributionPolicyFactory.java new file mode 100644 index 00000000..53cded87 --- /dev/null +++ b/opendc-simulator/opendc-simulator-flow/src/main/java/org/opendc/simulator/engine/graph/distributionPolicies/DistributionPolicyFactory.java @@ -0,0 +1,42 @@ +/* + * Copyright (c) 2025 AtLarge Research + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +package org.opendc.simulator.engine.graph.distributionPolicies; + +public class DistributionPolicyFactory { + + public enum DistributionPolicyType { + MaxMinFairness, + FixedShare; + } + + public static DistributionPolicy getDistributionStrategy(DistributionPolicyType distributionPolicyType) { + + return switch (distributionPolicyType) { + case MaxMinFairness -> new MaxMinFairnessPolicy(); + case FixedShare -> new FixedShare(1); + // actively misspelling + default -> throw new IllegalArgumentException( + "Unknown distribution strategy type: " + distributionPolicyType); + }; + } +} diff --git a/opendc-simulator/opendc-simulator-flow/src/main/java/org/opendc/simulator/engine/graph/distributionPolicies/FixedShare.java b/opendc-simulator/opendc-simulator-flow/src/main/java/org/opendc/simulator/engine/graph/distributionPolicies/FixedShare.java new file mode 100644 index 00000000..40d70b5e --- /dev/null +++ b/opendc-simulator/opendc-simulator-flow/src/main/java/org/opendc/simulator/engine/graph/distributionPolicies/FixedShare.java @@ -0,0 +1,48 @@ +/* + * Copyright (c) 2025 AtLarge Research + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +package org.opendc.simulator.engine.graph.distributionPolicies; + +import java.util.ArrayList; + +/** + * A distribution policy that distributes supply equally among all nodes. + * The share can be set to a fixed value, defaulting to 1. + * This policy not implemented yet and is used as a placeholder. + */ +public class FixedShare implements DistributionPolicy { + + private int share; + + public FixedShare() { + this.share = 1; + } + + public FixedShare(int share) { + this.share = share; + } + + @Override + public double[] distributeSupply(ArrayList<Double> supply, double currentSupply) { + return new double[0]; + } +} diff --git a/opendc-simulator/opendc-simulator-flow/src/main/java/org/opendc/simulator/engine/graph/distributionPolicies/MaxMinFairnessPolicy.java b/opendc-simulator/opendc-simulator-flow/src/main/java/org/opendc/simulator/engine/graph/distributionPolicies/MaxMinFairnessPolicy.java new file mode 100644 index 00000000..1d387349 --- /dev/null +++ b/opendc-simulator/opendc-simulator-flow/src/main/java/org/opendc/simulator/engine/graph/distributionPolicies/MaxMinFairnessPolicy.java @@ -0,0 +1,72 @@ +/* + * Copyright (c) 2025 AtLarge Research + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +package org.opendc.simulator.engine.graph.distributionPolicies; + +import java.util.ArrayList; +import java.util.Arrays; + +/** + * A distribution policy that implements the Max-Min Fairness algorithm. + * This policy distributes supply to demands in a way that maximizes the minimum + * allocation across all demands, ensuring fairness. + */ +public class MaxMinFairnessPolicy implements DistributionPolicy { + private record Demand(int idx, double value) {} + + @Override + public double[] distributeSupply(ArrayList<Double> demands, double currentSupply) { + int inputSize = demands.size(); + + final double[] supplies = new double[inputSize]; + final Demand[] tempDemands = new Demand[inputSize]; + + for (int i = 0; i < inputSize; i++) { + tempDemands[i] = new Demand(i, demands.get(i)); + } + + Arrays.sort(tempDemands, (o1, o2) -> { + Double i1 = o1.value; + Double i2 = o2.value; + return i1.compareTo(i2); + }); + + double availableCapacity = currentSupply; // totalSupply + + for (int i = 0; i < inputSize; i++) { + double d = tempDemands[i].value; + + if (d == 0.0) { + continue; + } + + double availableShare = availableCapacity / (inputSize - i); + double r = Math.min(d, availableShare); + + int idx = tempDemands[i].idx; + supplies[idx] = r; // Update the rates + availableCapacity -= r; + } + + return supplies; + } +} |