-
Klervie Toczé authoredKlervie Toczé authored
Code owners
Assign users and groups as approvers for specific file changes. Learn more.
Network.java 28.85 KiB
package system;
import application.Application;
import device.Device;
import device.EnergyModel;
import device.PiecewiseLinear;
import org.apache.commons.math3.util.Pair;
import placement.RequestPlacementOutput;
import utils.Config;
import utils.Distribution;
import utils.NormalDistribution;
import utils.Utils;
import org.jgrapht.Graph;
import org.jgrapht.GraphPath;
import org.jgrapht.alg.interfaces.ShortestPathAlgorithm;
import org.jgrapht.alg.shortestpath.DijkstraShortestPath;
import org.jgrapht.graph.DefaultUndirectedWeightedGraph;
import org.jgrapht.graph.DefaultWeightedEdge;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Network {
List<Device> edgeDevices = new ArrayList<Device>();
Map<String, Device> nameToDevice;
Application application;
Graph<Device, DefaultWeightedEdge> graph;
DijkstraShortestPath<Device, DefaultWeightedEdge> dijkstraAlg;
Map<String,Double> utilization;
Map<String,Double> time_links = new HashMap<>();//Create container
Map<String,Double> energy_links = new HashMap<>();//Create container
Map<String,Double> energy_residual_links = new HashMap<>();//Create container
Map<String,Double> time_devices = new HashMap<>();//Create container
Map<String,Double> energy_devices = new HashMap<>();//Create container
Map<String,Double> energy_residual_devices = new HashMap<>();//Create container
String placingDevice;
EnergyModel energyModel;
Boolean oneCoreAllocation;
public Network(Application applicationConsidered, String placingDevice, boolean oneCoreAllocation_){
application= applicationConsidered;
this.placingDevice=placingDevice;
//Locations according to Abilene
Map<Integer,Location> locationInfo = new HashMap<Integer,Location>();
Location location0= new Location(40.71427,-74.00597);
locationInfo.put(0,location0);
Location location1= new Location(41.85003,-87.65005);
locationInfo.put(1,location1);
Location location2= new Location(38.89511,-77.03637);
locationInfo.put(2,location2);
Location location3= new Location(47.60621,-122.33207);
locationInfo.put(3,location3);
Location location4= new Location(37.36883,-122.03635);
locationInfo.put(4,location4);
Location location5= new Location(34.05223,-118.24368);
locationInfo.put(5,location5);
Location location6= new Location(39.73915,-104.9847);
locationInfo.put(6,location6);
Location location7= new Location(39.11417,-94.62746);
locationInfo.put(7,location7);
Location location8= new Location(29.76328,-95.36327);
locationInfo.put(8,location8);
Location location9= new Location(33.749,-84.38798);
locationInfo.put(9,location9);
Location location10= new Location(39.76838,-86.15804);
locationInfo.put(10,location10);
for (int i = 0; i < 11; i++) {
Device gateway = createEdgeDevice("gateway_" + i, 300 , Device.EDGE);
gateway.setLocationInformation(locationInfo.get(i));
edgeDevices.add(gateway);
}
createNetworkGraph();
dijkstraAlg = new DijkstraShortestPath<>(graph);
energyModel = new PiecewiseLinear();
oneCoreAllocation=oneCoreAllocation_;
}
private void createNetworkGraph(){
graph = new DefaultUndirectedWeightedGraph<>(DefaultWeightedEdge.class);
//Utility map returning Device based on name - used for creating the links easier
nameToDevice= new HashMap<String, Device>();
// Add vertices
for (Device edgeDevice: edgeDevices) {
if(edgeDevice.getName().contains("gateway")){ //All of them should
graph.addVertex(edgeDevice);
//Adding the node to the map
nameToDevice.put(edgeDevice.getName(), edgeDevice);
}
}
//Add edges - hardcoded to Abilene
graph.addEdge(nameToDevice.get("gateway_0"),nameToDevice.get("gateway_1"));
graph.addEdge(nameToDevice.get("gateway_0"),nameToDevice.get("gateway_2"));
graph.addEdge(nameToDevice.get("gateway_1"),nameToDevice.get("gateway_10"));
graph.addEdge(nameToDevice.get("gateway_2"),nameToDevice.get("gateway_9"));
graph.addEdge(nameToDevice.get("gateway_3"),nameToDevice.get("gateway_6"));
graph.addEdge(nameToDevice.get("gateway_3"),nameToDevice.get("gateway_4"));
graph.addEdge(nameToDevice.get("gateway_4"),nameToDevice.get("gateway_5"));
graph.addEdge(nameToDevice.get("gateway_4"),nameToDevice.get("gateway_6"));
graph.addEdge(nameToDevice.get("gateway_6"),nameToDevice.get("gateway_7"));
graph.addEdge(nameToDevice.get("gateway_7"),nameToDevice.get("gateway_8"));
graph.addEdge(nameToDevice.get("gateway_7"),nameToDevice.get("gateway_10"));
graph.addEdge(nameToDevice.get("gateway_5"),nameToDevice.get("gateway_8"));
graph.addEdge(nameToDevice.get("gateway_8"),nameToDevice.get("gateway_9"));
graph.addEdge(nameToDevice.get("gateway_9"),nameToDevice.get("gateway_10"));
//Set the edge weights
for (DefaultWeightedEdge edge: graph.edgeSet()){
double calculatedWeight = calculateWeight(graph.getEdgeSource(edge), graph.getEdgeTarget(edge));
graph.setEdgeWeight(edge,calculatedWeight);
}
}
public double getLinkTransmissionTime(String startFunctionInstance, String destinationFunctionInstance){
//Check if we already have it
Double linkTiming = time_links.get(startFunctionInstance+"=>"+destinationFunctionInstance);
if(linkTiming==null){
//We need to calculate it
//Get size to be transmitted
Double size = application.getTargetFunctionNwSize(Utils.getTargetFunction(startFunctionInstance+"=>"+destinationFunctionInstance));
//Get current utilization
Pair<String, String> nameSplitStart= Utils.splitLongFunctionInstanceName(startFunctionInstance);
Pair<String, String> nameSplitDestination= Utils.splitLongFunctionInstanceName(destinationFunctionInstance);
//Check for start/end nodes
if(nameSplitStart.getKey().equals(Utils.START)||nameSplitStart.getKey().equals(Utils.END)){
//OBS for now start and end are the same
String value= nameSplitStart.getValue();//Should be empty string
nameSplitStart=new Pair<>(placingDevice,value);
}
if(nameSplitDestination.getKey().equals(Utils.START)||nameSplitDestination.getKey().equals(Utils.END)){
//OBS for now start and end are the same
String value= nameSplitDestination.getValue();//Should be empty string
nameSplitDestination=new Pair<>(placingDevice,value);
}
//Special case where end and start are the same - then transmission time is 0
if(nameSplitStart.getKey().equals(nameSplitDestination.getKey())){
linkTiming=0.0;
}else {
Double currentUtilization = utilization.get(nameSplitStart.getKey() + "=>" + nameSplitDestination.getKey());
//Get available capacity
Double availableCapacity = Config.DEFAULT_LINK_CAPACITY * (1-(currentUtilization / 100));
//Get link latency
Double linkLatency = getLinkLatency(nameSplitStart.getKey(), nameSplitDestination.getKey());
//Calculate according to formula
if (availableCapacity==0){
linkTiming = Double.valueOf(Config.INFINITE);
}else {
linkTiming = (size / availableCapacity) + linkLatency;
}
}
//Add to the Map variable
time_links.put(startFunctionInstance+"=>"+destinationFunctionInstance, linkTiming);
}
return linkTiming;
}
public double getExecutionTime(String device, String functionInstance){
//Check if we already have it
Double deviceTiming = time_devices.get(device+"-"+functionInstance);
if(deviceTiming==null){
//We need to calculate it
//Get utilization value for this device
Double currentUtilization = utilization.get(device);
//Get size to be calculated
Double size = application.getTargetFunctionCPUSize(functionInstance);
//Get capacity allocated to the function instance
Double allocatedCapacity=getAllocatedCapacity(currentUtilization);
//Calculate according to formula
if (allocatedCapacity==0){
deviceTiming=Double.valueOf(Config.INFINITE);
}else {
deviceTiming = (size / allocatedCapacity);
}
//Add to the Map variable
time_devices.put(device+"-"+functionInstance, deviceTiming);
}
return deviceTiming;
}
private Double getAllocatedCapacity(Double currentUtilization){
//Get available capacity
Double availableCapacity = Config.DEFAULT_DEVICE_CAPACITY_PER_CORE*Config.DEFAULT_DEVICE_NB_CORES * (1-(currentUtilization / 100));
//A function instance gets up to one core of capacity or the full remaining capacity
Double allocatedCapacity=0.0;
if(availableCapacity-Config.DEFAULT_DEVICE_CAPACITY_PER_CORE >=0 && oneCoreAllocation){
//At least one core is available, we allocate one core
allocatedCapacity= (double) Config.DEFAULT_DEVICE_CAPACITY_PER_CORE;
}
else{
//We allocate what is available
allocatedCapacity=availableCapacity;
}
return allocatedCapacity;
}
private double calculateWeight(Device source, Device destination){
//For this scenario the weight is the latency calculated as the distance between the nodes divided by 100
double distance = calculateDistance(source.getLocationInformation(),destination.getLocationInformation())/100;
return distance;
}
public double calculateDistance(Location loc1, Location loc2) {
final int R = 6371; // Radius of the earth in Kilometers
double latDistance = Math.toRadians(loc1.latitude - loc2.latitude);
double lonDistance = Math.toRadians(loc1.longitude - loc2.longitude);
double a = Math.sin(latDistance / 2) * Math.sin(latDistance / 2)
+ Math.cos(Math.toRadians(loc1.latitude)) * Math.cos(Math.toRadians(loc2.latitude))
* Math.sin(lonDistance / 2) * Math.sin(lonDistance / 2);
double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
double distance = R * c; // kms
distance = Math.pow(distance, 2);
return Math.sqrt(distance);
}
private double getLinkLatency(String startDeviceName, String endDeviceName){
Device startDevice=nameToDevice.get(startDeviceName);
Device endDevice=nameToDevice.get(endDeviceName);
ShortestPathAlgorithm.SingleSourcePaths<Device, DefaultWeightedEdge> iPaths = dijkstraAlg.getPaths(startDevice);
GraphPath<Device, DefaultWeightedEdge> pathToDestination = iPaths.getPath(endDevice);
//Calculate the latency of the path by summing the edge latency of its edges
double totalLatency = 0;
for (DefaultWeightedEdge link : pathToDestination.getEdgeList()){
totalLatency+=graph.getEdgeWeight(link);
}
//Calculate latency
return totalLatency;
}
/*private double getDynamicPowerForUtilization(double utilizationWithServicePlaced, double dynPower){
//We consider a linear model were the dynamic power part is 0 at 0% utilization (OBS it still has idle power but this is another constant)
// and Dyn power att 100% utilization
//utilization in percentage
return dynPower*(utilizationWithServicePlaced/100);
}*/ //TODO Move to a new Linear energy model class
public double getLinkEnergyConsumption(String startFunctionInstanceName, String destinationFunctionInstanceName,
String startLocation, String destinationLocation){
// 0 - Get names
String startDeviceName;
if (startFunctionInstanceName==Utils.START){
startDeviceName=startLocation;
}
else if (startFunctionInstanceName==Utils.END){
startDeviceName=destinationLocation;
}
else{
Pair<String,String> startSplit = Utils.splitLongFunctionInstanceName(startFunctionInstanceName);
startDeviceName= startSplit.getKey();
}
String destinationDeviceName;
if (destinationFunctionInstanceName==Utils.END){
destinationDeviceName = destinationLocation;
}
else if (destinationFunctionInstanceName==Utils.START){
destinationDeviceName = startLocation;
}
else{
Pair<String,String> destinationSplit = Utils.splitLongFunctionInstanceName(destinationFunctionInstanceName);
destinationDeviceName= destinationSplit.getKey();
}
Double currentUtilization = utilization.get(startDeviceName + "=>" + destinationDeviceName);
// 1- get the linkTiming
double linkTiming=getLinkTransmissionTime(startFunctionInstanceName,destinationFunctionInstanceName);
// 2 - Check whether we already have calculated the energy
double energy_link;
if(energy_links.get(startFunctionInstanceName + "=>" + destinationFunctionInstanceName)!= null) {
energy_link=energy_links.get(startFunctionInstanceName + "=>" + destinationFunctionInstanceName);
}
else {
//We need to calculate it
//Get Pidle
int p_link_idle = Config.DEFAULT_LINK_P_IDLE;
//GetPdyn
int p_link_dyn = Config.DEFAULT_LINK_P_DYN;
//Calculate energy
energy_link = p_link_idle * linkTiming + p_link_dyn * linkTiming;
//Add to Map variables
energy_links.put(startFunctionInstanceName + "=>" + destinationFunctionInstanceName, energy_link);
}
return energy_link;
}
public double getLinkMarginalEnergyConsumption(String startFunctionInstanceName, String destinationFunctionInstanceName,
String startLocation, String destinationLocation){
// 0 - Get names
String startDeviceName;
if (startFunctionInstanceName==Utils.START){
startDeviceName=startLocation;
}
else if (startFunctionInstanceName==Utils.END){
startDeviceName=destinationLocation;
}
else{
Pair<String,String> startSplit = Utils.splitLongFunctionInstanceName(startFunctionInstanceName);
startDeviceName= startSplit.getKey();
}
String destinationDeviceName;
if (destinationFunctionInstanceName==Utils.END){
destinationDeviceName = destinationLocation;
}
else if (destinationFunctionInstanceName==Utils.START){
destinationDeviceName = startLocation;
}
else{
Pair<String,String> destinationSplit = Utils.splitLongFunctionInstanceName(destinationFunctionInstanceName);
destinationDeviceName= destinationSplit.getKey();
}
double linkTiming=getLinkTransmissionTime(startFunctionInstanceName,destinationFunctionInstanceName);
// 2 - Check whether we already have calculated the residual energy
double energy_residual_link;
if(energy_residual_links.get(startFunctionInstanceName + "=>" + destinationFunctionInstanceName)!= null) {
energy_residual_link=energy_residual_links.get(startFunctionInstanceName + "=>" + destinationFunctionInstanceName);
}
else {
//We need to calculate it
//First check if the timing is 0 (self loop)
if (linkTiming==0.0){
energy_residual_link=0.0;
}else {
//Get Pidle
int p_link_idle = Config.DEFAULT_LINK_P_IDLE;
//GetPdyn
int p_link_dyn = Config.DEFAULT_LINK_P_DYN;
//Calculate residual energy
energy_residual_link = p_link_idle * linkTiming + p_link_dyn * linkTiming;
}
//Add to Map variables
energy_residual_links.put(startFunctionInstanceName + "=>" + destinationFunctionInstanceName, energy_residual_link);
}
return energy_residual_link;
}
public double getInstanceEnergyConsumption(String functionInstanceName){
// 1- Getting the hardware name
Pair<String, String> nameSplit = Utils.splitLongFunctionInstanceName(functionInstanceName);
String deviceName = nameSplit.getKey();
//Check whether we already have info about this
double energy_consumption;
if(energy_devices.get(functionInstanceName)!=null){
energy_consumption=energy_devices.get(functionInstanceName);
}else{
//We need to calculate it
//Get execution time
double deviceTiming=getExecutionTime(deviceName,nameSplit.getValue());
//Get Pidle
int p_device_idle = Config.DEFAULT_DEVICE_P_IDLE;
//Calculate utilization after allocation
double utilizationAfterAllocation = calculateUtilizationAfterAllocation(deviceName);
//Calculate energy
energy_consumption = p_device_idle * deviceTiming + energyModel.getDynamicPowerForUtilization(utilizationAfterAllocation) * deviceTiming;
if(energy_consumption <0){
System.out.println("PRoblem");
}
//Add to Map variables
energy_devices.put(functionInstanceName, energy_consumption);
}
return energy_consumption;
}
private double calculateUtilizationAfterAllocation(String device){
Double currentUtilization = utilization.get(device);
Double allocatedCapacity = getAllocatedCapacity(currentUtilization);
//Calculate share of utilization of this allocated capacity
Double allocatedUtilization= allocatedCapacity/(Config.DEFAULT_DEVICE_CAPACITY_PER_CORE*Config.DEFAULT_DEVICE_NB_CORES)*100; //In percentage
return currentUtilization+allocatedUtilization;
}
public double getInstanceMarginalEnergyConsumption(String functionInstanceName){
// 1- Getting the hardware name
Pair<String, String> nameSplit = Utils.splitLongFunctionInstanceName(functionInstanceName);
String deviceName = nameSplit.getKey();
//Check whether we already have info about this
double energy_marginal_consumption;
if(energy_residual_devices.get(functionInstanceName)!=null){
energy_marginal_consumption =energy_residual_devices.get(functionInstanceName);
}else{
//We need to calculate it
//Get execution time
double deviceTiming=getExecutionTime(deviceName,nameSplit.getValue());
//Get Pidle
int p_device_idle = Config.DEFAULT_DEVICE_P_IDLE;
//Calculate utilization after allocation
double utilizationAfterAllocation = calculateUtilizationAfterAllocation(deviceName);
//Get utilization value for this device
Double beforeUtilization = utilization.get(deviceName);
if (beforeUtilization == 0) {
energy_marginal_consumption = p_device_idle * deviceTiming + energyModel.getDynamicPowerForUtilization(utilizationAfterAllocation) * deviceTiming;
} else {
//How much power does the utilization increase due to the placement requires?
double powerIncrease = energyModel.getDynamicPowerForUtilization(utilizationAfterAllocation) - energyModel.getDynamicPowerForUtilization(beforeUtilization);
energy_marginal_consumption = powerIncrease * deviceTiming; //Only the dynamic part
}
//Add to Map variables
energy_residual_devices.put(functionInstanceName, energy_marginal_consumption);
}
return energy_marginal_consumption;
}
public void evaluatePlacementOutput(RequestPlacementOutput output, String startLocationMathematical, String endLocationMathematical){
if(output==null){
System.out.println("No evaluation of the placement, request was infeasible");
}else {
List<String> elementsToCalculateTime = output.getElementsForTiming();
Map<String, String> placement = output.getAppFunctionToDevice();
for (String element : elementsToCalculateTime) {
if (Utils.isLink(element)) {
//It is a link
//Get start and end device
Pair<String, String> devices = Utils.getLinkStartAndEndDevices(element);
//Get utilization value for this link
if (devices.getKey().equals(Utils.START)) {
//In our setup the start device=end device=the current device
String endDevice = devices.getValue();
devices = new Pair<>(startLocationMathematical, endDevice);
}
if (devices.getValue().equals(Utils.END)) {
//In our setup the start device=end device=the current device
String startDevice = devices.getKey();
devices = new Pair<>(startDevice, endLocationMathematical);
}
//We should have already calculated the value when the optimizer picked it
Double linkTiming = time_links.get(element);
if (linkTiming == null) {
System.out.println("ERROR link timing value not available");
}
//We should have already calculated the value when the optimizer picked it
Double energy_link = energy_links.get(element);
if (energy_link == null) {
System.out.println("ERROR link energy value not available");
}
Double energy_residual_link = energy_residual_links.get(element);
if (energy_residual_link == null) {
//Calculate it
Pair<String, String> linkSplit = Utils.splitLinkName(element);
getLinkMarginalEnergyConsumption(linkSplit.getKey(), linkSplit.getValue(), startLocationMathematical, endLocationMathematical);
}
} else {
//It is a node
//Get device name and function instance name
Pair<String, String> deviceAndFunction = Utils.splitLongFunctionInstanceName(element);
//We should have already calculated the value when the optimizer picked it
Double deviceTiming = time_devices.get(element);
if (deviceTiming == null) {
System.out.println("ERROR device timing value not available");
}
//We should have already calculated the value when the optimizer picked it
Double energy_device = energy_devices.get(element);
if (energy_device == null) {
System.out.println("ERROR device energy value not available");
}
Double energy_residual_device = energy_residual_devices.get(element);
if (energy_residual_device == null) {
//Calculate it
getInstanceMarginalEnergyConsumption(element);
}
}
}
//Calculate the total - sum over the elements
double timeLink = 0;
double timeDevice = 0;
double timeLinkDevice = 0;
for (String element : elementsToCalculateTime) {
if (Utils.isLink(element)) {
timeLink += time_links.get(element);
} else {
timeDevice += time_devices.get(element);
}
}
timeLinkDevice = timeLink + timeDevice;
double energyLink = 0;
double energyDevice = 0;
double energyLinkDevice = 0;
for (String element : elementsToCalculateTime) {
if (Utils.isLink(element)) {
energyLink += energy_links.get(element);
} else {
energyDevice += energy_devices.get(element);
}
}
energyLinkDevice = energyLink + energyDevice;
double energyResLink = 0;
double energyResDevice = 0;
double energyResLinkDevice = 0;
for (String element : elementsToCalculateTime) {
if (Utils.isLink(element)) {
energyResLink += energy_residual_links.get(element);
} else {
energyResDevice += energy_residual_devices.get(element);
}
}
energyResLinkDevice = energyResLink + energyResDevice;
//Print the results in a usable way
System.out.println("Evaluated placement: Completion time " + timeLinkDevice + " Overall energy " + energyLinkDevice + " Marginal energy " + energyResLinkDevice + " In details - completion time link "+ timeLink + " completion time device " + timeDevice + " overall energy link " + energyLink + " overall energy device " + energyDevice + " marginal energy link "+energyResLink + " marginal energy device "+energyResDevice);
}
}
private static Device createEdgeDevice(String nodeName, long mips,
String deviceType) {
Device edgedevice = null;
try {
edgedevice = new Device(nodeName, deviceType,mips);
} catch (Exception e) {
e.printStackTrace();
}
return edgedevice;
}
public void clear(){
time_devices.clear();
time_links.clear();
energy_links.clear();
energy_devices.clear();
energy_residual_links.clear();
energy_residual_devices.clear();
}
public void createUtilizationData(int scenarioIndex, int repetitionNumber, Boolean usingUniformLoadDistribution,int standardDeviation, Boolean linksAreLoaded){
//First create a list of all element that need to have information
//Devices
List<String> deviceNames = new ArrayList<>();
for (Device device : edgeDevices) {
if (device.getName().contains("gateway")) {//Note: with current setup should be all of them so this is only to double check
deviceNames.add(device.getName());
}
}
//Links
List<String> linkNames = new ArrayList<>();
for (String device1 : deviceNames) {
for (String device2 : deviceNames) {
if (!device1.equals(device2)) {
//Self loops are not interesting
linkNames.add(device1 + "=>" + device2);
}
}
}
//Non-uniform
Distribution utilizationDistribution = new NormalDistribution(scenarioIndex * 10, standardDeviation, Config.SEED +repetitionNumber+scenarioIndex);
//Then create the information
utilization = new HashMap<>();
for (String element : deviceNames) {
//Get a value from the chosen distribution
//For this scenario - not random
Double randomUtil = utilizationDistribution.getNextValue();
if (randomUtil < 0) {
randomUtil = 0.0;
}
if (randomUtil > 100) {
randomUtil = 100.0;
}
if(usingUniformLoadDistribution){
randomUtil= scenarioIndex*10.0;
}
utilization.put(element, randomUtil);
}
for (String element : linkNames) {
//Get a value from the chosen distribution
//For this scenario - not random
Double randomUtil = utilizationDistribution.getNextValue();
if (randomUtil <0){
randomUtil=0.0;
}
if (randomUtil >100){
randomUtil=100.0;
}
//Not random variant
if(!linksAreLoaded){
randomUtil = 0.0;
}
utilization.put(element, randomUtil);
}
System.out.println(utilization);
}
public List<Device> getEdgeDevices(){
return edgeDevices;
}
// Used for the random beginning device case
public void modifyPlacingDevice(String newPlacingDevice){
this.placingDevice=newPlacingDevice;
}
}