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