001/******************************************************************************* 002 * Copyright (c) 2017 Pablo Pavon Marino and others. 003 * All rights reserved. This program and the accompanying materials 004 * are made available under the terms of the 2-clause BSD License 005 * which accompanies this distribution, and is available at 006 * https://opensource.org/licenses/BSD-2-Clause 007 * 008 * Contributors: 009 * Pablo Pavon Marino and others - initial API and implementation 010 *******************************************************************************/ 011package com.net2plan.examples.ocnbook.onlineSim; 012 013 014import cern.colt.matrix.tdouble.DoubleFactory1D; 015import cern.colt.matrix.tdouble.DoubleMatrix1D; 016import cern.colt.matrix.tdouble.DoubleMatrix2D; 017import cern.jet.math.tdouble.DoubleFunctions; 018import com.net2plan.examples.ocnbook.offline.Offline_ca_wirelessCsmaWindowSize; 019import com.net2plan.interfaces.networkDesign.Link; 020import com.net2plan.interfaces.networkDesign.Net2PlanException; 021import com.net2plan.interfaces.networkDesign.NetPlan; 022import com.net2plan.interfaces.simulation.IEventProcessor; 023import com.net2plan.interfaces.simulation.SimEvent; 024import com.net2plan.libraries.NetworkPerformanceMetrics; 025import com.net2plan.libraries.WirelessUtils; 026import com.net2plan.utils.InputParameter; 027import com.net2plan.utils.Pair; 028import com.net2plan.utils.TimeTrace; 029import com.net2plan.utils.Triple; 030 031import java.io.File; 032import java.util.HashMap; 033import java.util.List; 034import java.util.Map; 035import java.util.Random; 036 037/** 038 * This module implements a distributed dual-gradient based algorithm for adjusting the backoff windows sizes in a wireless network with a CSMA-mased MAC, to maximize the network utility enforcing a fair allocation of the resources. 039 * 040 * Ths event processor is adapted to permit observing the algorithm performances under user-defined conditions, 041 * including asynchronous distributed executions, where signaling can be affected by losses and/or delays, and/or measurement errors. 042 * The time evolution of different metrics can be stored in output files, for later processing. 043 * As an example, see the <a href="../../../../../../graphGeneratorFiles/fig_sec10_5_csmaBackoffOptimizationDual.m">{@code fig_sec10_5_csmaBackoffOptimizationDual.m}</a> MATLAB file used for generating the graph/s of the case study in the 044 * <a href="http://eu.wiley.com/WileyCDA/WileyTitle/productCd-1119013356.html">book</a> using this algorithm. 045 * 046 * To simulate a network with this module, use the {@code Online_evGen_doNothing} generator. 047 * 048 * @net2plan.keywords Wireless, CSMA, Capacity assignment (CA), Dual gradient algorithm 049 * @net2plan.ocnbooksections Section 10.5 050 * @net2plan.inputParameters 051 * @author Pablo Pavon-Marino 052 */ 053public class Online_evProc_csmaBackoffOptimizationDual extends IEventProcessor 054{ 055 private InputParameter update_isSynchronous = new InputParameter ("update_isSynchronous", false , "true if all the distributed agents involved wake up synchronousely to update its state"); 056 private InputParameter update_averageInterUpdateTime = new InputParameter ("update_averageInterUpdateTime", 1.0 , "Average time between two updates of an agent" , 0 , false , Double.MAX_VALUE , true); 057 private InputParameter update_maxFluctuationInterUpdateTime = new InputParameter ("update_maxFluctuationInterUpdateTime", 0.5 , "Max fluctuation in time in the update interval of an agent, in absolute time values. The update intervals are sampled from a uniform distribution within the given interval" , 0 , true , Double.MAX_VALUE , true); 058 private InputParameter gradient_gammaStep = new InputParameter ("gradient_gammaStep", 5.0 , "Gamma step in the gradient algorithm" , 0 , false , Double.MAX_VALUE , true); 059 private InputParameter control_fairnessFactor = new InputParameter ("control_fairnessFactor", 1.0 , "Fairness factor in utility function of link capacity assignment" , 0 , true , Double.MAX_VALUE , true); 060 private InputParameter simulation_randomSeed = new InputParameter ("simulation_randomSeed", (long) 1 , "Seed of the random number generator"); 061 private InputParameter simulation_maxNumberOfUpdateIntervals = new InputParameter ("simulation_maxNumberOfUpdateIntervals", 1000.0 , "Maximum number of update intervals in average per agent" , 0 , false , Double.MAX_VALUE , true); 062 private InputParameter control_linkNominalCapacity = new InputParameter ("control_linkNominalCapacity", 1.0 , "Nominal rate of the links. If non positive, nominal rates are rates of the initial design"); 063 private InputParameter simulation_outFileNameRoot = new InputParameter ("simulation_outFileNameRoot", "csmaBackoffOptimizationDual" , "Root of the file name to be used in the output files. If blank, no output"); 064 065 private InputParameter control_betaFactor = new InputParameter ("control_betaFactor", 10.0 , "Factor weighting the network utility in the objective function" , 0 , true , Double.MAX_VALUE , true); 066 private InputParameter control_maxSeMeasurementRelativeNoise = new InputParameter ("control_maxSeMeasurementRelativeNoise", 0.1 , "Max relative fluctuation in gradient coordinate" , 0 , true , Double.MAX_VALUE , true); 067 068 private Random rng; 069 070 private static final int UPDATE_WAKEUPTOUPDATE = 202; 071 072 private int E , N , M; 073 074 private NetPlan currentNetPlan , copyInitialNetPlan; 075 076 private DoubleMatrix2D A_em; 077 private DoubleMatrix1D control_linkNominalCapacities_e; 078 private DoubleMatrix1D control_r_e; 079 private DoubleMatrix1D control_intendedU_e; 080 private DoubleMatrix1D pi_m; 081 082 private TimeTrace stat_traceOf_ue; 083 private TimeTrace stat_traceOf_re; 084 private TimeTrace stat_traceOf_objFun; 085 private TimeTrace stat_traceOf_netUtilityWithoutBeta; 086 private TimeTrace stat_traceOf_netUtilityWithBeta; 087 088 @Override 089 public String getDescription() 090 { 091 return "This module implements a distributed dual-gradient based algorithm for adjusting the backoff windows sizes in a wireless network with a CSMA-mased MAC, to maximize the network utility enforcing a fair allocation of the resources."; 092 } 093 094 @Override 095 public List<Triple<String, String, String>> getParameters() 096 { 097 /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */ 098 return InputParameter.getInformationAllInputParameterFieldsOfObject(this); 099 } 100 101 @Override 102 public void initialize(NetPlan currentNetPlan, Map<String, String> algorithmParameters, Map<String, String> simulationParameters, Map<String, String> net2planParameters) 103 { 104 /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */ 105 InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters); 106 107 this.currentNetPlan = currentNetPlan; 108 this.copyInitialNetPlan = currentNetPlan.copy(); 109 110 if (currentNetPlan.getNumberOfLayers() != 1) throw new Net2PlanException ("This algorithm works in single layer networks"); 111 this.N = currentNetPlan.getNumberOfNodes (); 112 this.E = currentNetPlan.getNumberOfLinks (); 113 if (E == 0) throw new Net2PlanException ("The input design should have links"); 114 115 if (control_linkNominalCapacity.getDouble() > 0) currentNetPlan.setVectorLinkCapacity(DoubleFactory1D.dense.make (E , control_linkNominalCapacity.getDouble())); 116 control_linkNominalCapacities_e = currentNetPlan.getVectorLinkCapacity(); 117 118 this.rng = new Random (simulation_randomSeed.getLong()); 119 120 this.E = this.currentNetPlan.getNumberOfLinks(); 121 this.N = this.currentNetPlan.getNumberOfNodes(); 122 this.A_em = WirelessUtils.computeSchedulingMatrix(currentNetPlan.getLinks ()); 123 this.M = A_em.columns(); 124 125 /* Take link nominal capacities */ 126 this.control_r_e = DoubleFactory1D.dense.make(E); 127 this.control_intendedU_e = DoubleFactory1D.dense.make(E); 128 for (Link e : currentNetPlan.getLinks ()) 129 { 130 control_r_e.set(e.getIndex () , 1.0); 131 e.setAttribute("r_e" , "" + 1.0); 132 } 133 134 this.updateLinkCapacities(); 135 136 /* Initially all nodes receive a "wake up to transmit" event, aligned at time zero or y asynchr => randomly chosen */ 137 for (Link e : currentNetPlan.getLinks()) 138 { 139 final double updateTime = (update_isSynchronous.getBoolean())? update_averageInterUpdateTime.getDouble() : Math.max(0 , update_averageInterUpdateTime.getDouble() + update_maxFluctuationInterUpdateTime.getDouble() * (rng.nextDouble() - 0.5)); 140 this.scheduleEvent(new SimEvent (updateTime , SimEvent.DestinationModule.EVENT_PROCESSOR , UPDATE_WAKEUPTOUPDATE , e)); 141 } 142 143 /* Intialize the traces */ 144 this.stat_traceOf_ue = new TimeTrace (); 145 this.stat_traceOf_re = new TimeTrace (); 146 this.stat_traceOf_objFun = new TimeTrace (); 147 this.stat_traceOf_netUtilityWithoutBeta = new TimeTrace (); 148 this.stat_traceOf_netUtilityWithBeta = new TimeTrace (); 149 150 this.stat_traceOf_ue.add(0.0, currentNetPlan.getVectorLinkCapacity()); 151 this.stat_traceOf_re.add(0.0, control_r_e.copy ()); 152 Pair<Double,Double> objFunc = computeObjectiveFunction (); 153 this.stat_traceOf_objFun.add(0.0, objFunc.getFirst()); 154 this.stat_traceOf_netUtilityWithBeta.add(0.0, objFunc.getSecond()); 155 this.stat_traceOf_netUtilityWithoutBeta.add(0.0, objFunc.getSecond() / control_betaFactor.getDouble()); 156 } 157 158 @Override 159 public void processEvent(NetPlan currentNetPlan, SimEvent event) 160 { 161 final double t = event.getEventTime(); 162 switch (event.getEventType()) 163 { 164 case UPDATE_WAKEUPTOUPDATE: // a node updates its p_n, p_e values, using most updated info available 165 { 166 final Link eMe = (Link) event.getEventObject(); 167 final int eIdMe_index = eMe.getIndex (); 168 169 //final double gradientThisLink = this.currentNetPlan.getLinkCapacity(eIdMe_SN) - this.control_intendedU_e.get(eIdMe_index) + 2*mac_maxSeMeasurementRelativeNoise*(r.nextDouble()-0.5); 170 //final double gradientThisLink = (this.currentNetPlan.getLinkCapacity(eIdMe_SN) - this.control_intendedU_e.get(eIdMe_index)) * (1 + 2*mac_maxSeMeasurementRelativeNoise*(r.nextDouble()-0.5)); 171 final double gradientThisLink = eMe.getCapacity() * (1 + 2*control_maxSeMeasurementRelativeNoise.getDouble()*(rng.nextDouble()-0.5)) - this.control_intendedU_e.get(eIdMe_index); 172 final double newRe = Math.max(0.001 , control_r_e.get(eIdMe_index) - this.gradient_gammaStep.getDouble() * gradientThisLink); 173 174 if (Double.isNaN(gradientThisLink)) 175 { 176 System.out.println("Gradient this links: " + gradientThisLink); 177 System.out.println("control_intendedU_e: " + control_intendedU_e); 178 System.out.println("getLinkCapacity: " + this.currentNetPlan.getVectorLinkCapacity()); 179 throw new RuntimeException ("Bad"); 180 } 181 182 this.control_r_e.set(eIdMe_index, newRe); 183 eMe.setAttribute("r_e" , "" + control_r_e.get(eIdMe_index)); 184 this.updateLinkCapacities(); 185 186 final double updateTime = update_isSynchronous.getBoolean()? t + update_averageInterUpdateTime.getDouble() : Math.max(t , t + update_averageInterUpdateTime.getDouble() + update_maxFluctuationInterUpdateTime.getDouble() * (rng.nextDouble() - 0.5)); 187 this.scheduleEvent(new SimEvent (updateTime , SimEvent.DestinationModule.EVENT_PROCESSOR , UPDATE_WAKEUPTOUPDATE, eMe)); 188 189 this.stat_traceOf_ue.add(t, currentNetPlan.getVectorLinkCapacity()); 190 this.stat_traceOf_re.add(t, control_r_e.copy ()); 191 Pair<Double,Double> objFunc = computeObjectiveFunction (); 192 this.stat_traceOf_objFun.add(t, objFunc.getFirst()); 193 this.stat_traceOf_netUtilityWithBeta.add(t, objFunc.getSecond()); 194 this.stat_traceOf_netUtilityWithoutBeta.add(t, objFunc.getSecond() / control_betaFactor.getDouble()); 195 196 if (t > this.simulation_maxNumberOfUpdateIntervals.getDouble() * this.update_averageInterUpdateTime.getDouble()) { this.endSimulation (); } 197 198 break; 199 } 200 201 202 default: throw new RuntimeException ("Unexpected received event"); 203 } 204 } 205 206 public String finish (StringBuilder st , double simTime) 207 { 208 if (simulation_outFileNameRoot.getString().equals("")) return null; 209 stat_traceOf_ue.printToFile(new File (simulation_outFileNameRoot.getString() + "_ue.txt")); 210 stat_traceOf_re.printToFile(new File (simulation_outFileNameRoot.getString() + "_re.txt")); 211 stat_traceOf_netUtilityWithoutBeta.printToFile(new File (simulation_outFileNameRoot.getString() + "_netUtilityWithoutBeta.txt")); 212 stat_traceOf_netUtilityWithBeta.printToFile(new File (simulation_outFileNameRoot.getString() + "_netUtilityWithBeta.txt")); 213 stat_traceOf_objFun.printToFile(new File (simulation_outFileNameRoot.getString() + "_objFunc.txt")); 214 215 Map<String,String> par = new HashMap<String,String> (); 216 par.put("solverName", "ipopt"); 217 par.put("solverLibraryName", ""); 218 par.put("maxSolverTimeInSeconds", "-1"); 219 par.put("alphaFairnessFactor", "" + this.control_fairnessFactor.getDouble()); 220 par.put("betaFactor", "" + this.control_betaFactor.getDouble()); 221 par.put("linkNominalCapacity", "" + this.control_linkNominalCapacity.getDouble()); 222 par.put("minimumSchedFractionTime", "0.00001"); 223 new Offline_ca_wirelessCsmaWindowSize ().executeAlgorithm(copyInitialNetPlan, par, null); 224 final double optimumCSMAObjectiveFunction = Double.parseDouble(copyInitialNetPlan.getAttribute("optimumCSMAObjectiveFunction")); 225 final double optimumCSMAUtilityByBeta = Double.parseDouble(copyInitialNetPlan.getAttribute("optimumCSMAUtilityByBeta")); 226 final double optimumCSMAUtility = Double.parseDouble(copyInitialNetPlan.getAttribute("optimumCSMAUtility")); 227 TimeTrace.printToFile(new File (simulation_outFileNameRoot.getString() + "_jom_ue.txt"), copyInitialNetPlan.getVectorLinkCapacity()); 228 DoubleMatrix1D optimum_re = DoubleFactory1D.dense.make (E); for (Link e : copyInitialNetPlan.getLinks ()) optimum_re.set (e.getIndex () , Double.parseDouble (e.getAttribute("r_e"))); 229 TimeTrace.printToFile(new File (simulation_outFileNameRoot.getString() + "_jom_re.txt"), optimum_re); 230 TimeTrace.printToFile(new File (simulation_outFileNameRoot.getString() + "_jom_netUtilityWithoutBeta.txt"), optimumCSMAUtility); 231 TimeTrace.printToFile(new File (simulation_outFileNameRoot.getString() + "_jom_netUtilityWithBeta.txt"), optimumCSMAUtilityByBeta); 232 TimeTrace.printToFile(new File (simulation_outFileNameRoot.getString() + "_jom_objFunc.txt"), optimumCSMAObjectiveFunction); 233 return null; 234 } 235 236 237 /* Applies the TAs and recomputes the link capacities from it */ 238 private void updateLinkCapacities () 239 { 240 this.pi_m = A_em.zMult(control_r_e, null , 1 , 0 , true); // for each m, the sum of the associated r_es 241 final double maxRm = pi_m.getMaxLocation() [0]; 242 for (int m = 0 ; m < M ; m ++) this.pi_m.set(m , this.pi_m.get(m) - maxRm); 243 this.pi_m.assign(DoubleFunctions.exp); 244 this.pi_m.assign(DoubleFunctions.div(pi_m.zSum())); 245 246 DoubleMatrix1D u_e = A_em.zMult(pi_m,null); 247 for (Link e : currentNetPlan.getLinks ()) 248 { 249 e.setCapacity(u_e.get(e.getIndex ()) * control_linkNominalCapacities_e.get(e.getIndex ())); 250 final double intended_ue = Math.pow(control_betaFactor.getDouble() / control_r_e.get(e.getIndex ()) , 1/control_fairnessFactor.getDouble()); 251 this.control_intendedU_e.set(e.getIndex (), intended_ue); 252 } 253 } 254 255 private Pair<Double,Double> computeObjectiveFunction () 256 { 257 double objFunc = 0; 258 for (int m = 0 ; m < M ; m ++) 259 objFunc -= (pi_m.get(m) == 0)? 0 : pi_m.get(m) * Math.log(pi_m.get(m)); 260 double netUtilityByBeta = control_betaFactor.getDouble() * NetworkPerformanceMetrics.alphaUtility(currentNetPlan.getVectorLinkCapacity() , control_fairnessFactor.getDouble()); 261 if (!Double.isFinite(netUtilityByBeta)) 262 netUtilityByBeta = -Double.MAX_VALUE; 263 objFunc += netUtilityByBeta; 264 return Pair.of(objFunc, netUtilityByBeta); 265 } 266 267}