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; } }