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}