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 ******************************************************************************/
008
009
010
011
012
013 
014
015
016
017
018package com.net2plan.examples.ocnbook.onlineSim;
019
020import java.util.HashMap;
021import java.util.HashSet;
022import java.util.LinkedList;
023import java.util.List;
024import java.util.Map;
025import java.util.Random;
026import java.util.Set;
027
028import cern.colt.matrix.tdouble.DoubleFactory1D;
029import cern.colt.matrix.tdouble.DoubleMatrix1D;
030
031import com.net2plan.interfaces.networkDesign.Demand;
032import com.net2plan.interfaces.networkDesign.Link;
033import com.net2plan.interfaces.networkDesign.Net2PlanException;
034import com.net2plan.interfaces.networkDesign.NetPlan;
035import com.net2plan.interfaces.networkDesign.NetworkLayer;
036import com.net2plan.interfaces.networkDesign.Node;
037import com.net2plan.interfaces.networkDesign.ProtectionSegment;
038import com.net2plan.interfaces.networkDesign.Route;
039import com.net2plan.interfaces.simulation.IEventProcessor;
040import com.net2plan.interfaces.simulation.SimEvent;
041import com.net2plan.libraries.GraphUtils;
042import com.net2plan.utils.Constants.RoutingType;
043import com.net2plan.utils.InputParameter;
044import com.net2plan.utils.Pair;
045import com.net2plan.utils.RandomUtils;
046import com.net2plan.utils.Triple;
047
048/** 
049 * Implements the reactions of a technology-agnostic network to connection requests under various CAC options, and reactions to failures and repairs under different recovery schemes.
050 * 
051 * The algorithm reacts to the following events: 
052 * <ul>
053 * <li>SimEvent.RouteAdd: Adds a route associated to the given demand. This can mean creating also a protection segment if the 1+1 protection options are active. If there is not enough resources for the route, it is not created.</li>
054 * <li>SimEvent.RouteRemove: Removes the corresponding Route object, and any associated protection segments.</li>
055 * <li>SimEvent.DemandModify: Modifies the offered traffic of a demand, caused by a traffic fluctuation.</li>
056 * <li>SimEvent.NodesAndLinksChangeFailureState: Fails/repairs the indicated nodes and/or links, and reacts to such failures (the particular form depends on the network recovery options selected).</li>
057 * </ul>
058 * 
059 * This module can be used to simulate a number of Connection-Admission-Control strategies, that decide on the route if the incoming connection requests. 
060 * This can be done separately or in conjuntion with different network recovery schemes that can be chosen, that define how the network reacts to node/link failures and repairs.
061 * 
062 * This module can be used in conjunction with the {@code Online_evGen_generalGenerator} generator for simulating networks. 
063 * 
064 * @net2plan.keywords CAC (Connection-Admission-Control), Network recovery: protection, Network recovery: restoration
065 * @net2plan.ocnbooksections Section 3.3.3, Exercise 3.7, Exercise 3.8
066 * @net2plan.inputParameters 
067 * @author Pablo Pavon-Marino
068 */
069public class Online_evProc_generalProcessor extends IEventProcessor
070{
071        private InputParameter cacType = new InputParameter ("cacType", "#select# alternate-routing least-congested-routing load-sharing" , "Criteria to decide the route of a connection among the available paths");
072        private InputParameter shortestPathType = new InputParameter ("shortestPathType", "#select# hops km" , "Criteria to compute the shortest path. Valid values: 'hops' or 'km'");
073        private InputParameter randomSeed = new InputParameter ("randomSeed", (long) 1 , "Seed for the random generator (-1 means random)");
074        private InputParameter k = new InputParameter ("k", (int) 2 , "Maximum number of admissible paths per demand, from where to choose their route" , 1 , Integer.MAX_VALUE);
075        private InputParameter maxLengthInKm = new InputParameter ("maxLengthInKm", (double) -1 , "Paths longer than this are considered not admissible. A non-positive number means this limit does not exist");
076        private InputParameter maxNumHops = new InputParameter ("maxNumHops", (int) -1 , "The path from an origin to any destination in cannot have more than this number of hops. A non-positive number means this limit does not exist");
077        private InputParameter layerId = new InputParameter ("layerId", (long) -1 , "Layer containing traffic demands (-1 means default layer)");
078        private InputParameter recoveryType = new InputParameter ("recoveryType", "#select# protection restoration none" , "None, nothing is done, so affected routes fail. Restoration, affected routes are visited sequentially, and we try to reroute them in the available capacity; in protection, affected routes are rerouted using the protection segments.");
079        private InputParameter removePreviousRoutes = new InputParameter ("removePreviousRoutes", false  , "If true, previous routes are removed from the system.");
080        private InputParameter protectionTypeToNewRoutes = new InputParameter ("protectionTypeToNewRoutes", "#select# 1+1-link-disjoint 1+1-node-disjoint srg-disjoint none" , "The new routes to add, may be associated a 1+1 segment protection (link, node or SRG disjoint), or no segment protection is added (none)");
081        
082        private List<Node> nodes;
083        private NetworkLayer layer;
084        private Map<Route,List<Link>> routeOriginalLinks;
085        private Map<Demand,List<List<Link>>> cpl;
086        private Map<Demand,List<Pair<List<Link>,List<Link>>>> cpl11; 
087
088        private boolean newRoutesHave11Protection;
089        private boolean isRestorationRecovery , isProtectionRecovery , isShortestPathNumHops;
090        private boolean isAlternateRouting , isLeastCongestedRouting , isLoadSharing;
091        private Random rng;
092
093        private double stat_trafficOfferedConnections , stat_trafficCarriedConnections;
094        private double stat_trafficAttemptedToRecoverConnections , stat_trafficSuccessfullyRecoveredConnections;
095        private long stat_numOfferedConnections , stat_numCarriedConnections;
096        private long stat_numAttemptedToRecoverConnections , stat_numSuccessfullyRecoveredConnections;
097        private double stat_transitoryInitTime;
098
099        
100        @Override
101        public String getDescription()
102        {
103                return "Implements the reactions of a technology-agnostic network to connection requests under various CAC options, and reactions to failures and repairs under different recovery schemes.";
104        }
105        
106        
107        
108        @Override
109        public List<Triple<String, String, String>> getParameters()
110        {
111                /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */
112                return InputParameter.getInformationAllInputParameterFieldsOfObject(this);
113        }
114
115        @Override
116        public void initialize(NetPlan initialNetPlan, Map<String, String> algorithmParameters, Map<String, String> simulationParameters, Map<String, String> net2planParameters)
117        {
118                /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */
119                InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters);
120                
121                this.layer = layerId.getLong () == -1? initialNetPlan.getNetworkLayerDefault() : initialNetPlan.getNetworkLayerFromId(layerId.getLong ());
122                this.nodes = initialNetPlan.getNodes ();
123                this.isShortestPathNumHops = shortestPathType.getString ().equalsIgnoreCase("hops");
124                this.routeOriginalLinks = new HashMap<Route,List<Link>> ();
125                this.isRestorationRecovery = recoveryType.getString ().equalsIgnoreCase("restoration");
126                this.isProtectionRecovery = recoveryType.getString ().equalsIgnoreCase("protection");
127                this.isAlternateRouting = cacType.getString().equalsIgnoreCase("alternate-routing");
128                this.isLeastCongestedRouting = cacType.getString().equalsIgnoreCase("least-congested-routing");
129                this.isLoadSharing = cacType.getString().equalsIgnoreCase("load-sharing");
130                this.newRoutesHave11Protection = !protectionTypeToNewRoutes.getString ().equalsIgnoreCase("none");
131                this.rng = new Random(randomSeed.getLong () == -1? (long) RandomUtils.random(0, Long.MAX_VALUE - 1) : randomSeed.getLong ());
132                if (!isProtectionRecovery && newRoutesHave11Protection) throw new Net2PlanException ("In the input parameter you ask to assign protection paths to new connections, while the recovery type chosen does not use them");
133                
134                /* Compute the candidate path list */
135                final int E = initialNetPlan.getNumberOfLinks(layer);
136                final DoubleMatrix1D linkCostVector = isShortestPathNumHops? DoubleFactory1D.dense.make (E , 1.0) : initialNetPlan.getVectorLinkLengthInKm();
137                this.cpl = initialNetPlan.computeUnicastCandidatePathList(linkCostVector.toArray() , "K", Integer.toString(k.getInt ()), "maxLengthInKm", Double.toString(maxLengthInKm.getDouble () > 0? maxLengthInKm.getDouble () : Double.MAX_VALUE) , "maxNumHops", Integer.toString(maxNumHops.getInt () > 0? maxNumHops.getInt () : Integer.MAX_VALUE));
138                final int protectionTypeCode = protectionTypeToNewRoutes.equals("srg-disjoint") ? 0 : protectionTypeToNewRoutes.equals("1+1-node-disjoint")? 1 : 2;
139                this.cpl11 = !newRoutesHave11Protection? null : NetPlan.computeUnicastCandidate11PathList(cpl, linkCostVector, protectionTypeCode); 
140
141                
142                //              System.out.println ("cpl: " + cpl);
143                System.out.println ("cpl11: " + cpl11);
144                
145                if (removePreviousRoutes.getBoolean())
146                {
147                        initialNetPlan.removeAllUnicastRoutingInformation(layer);
148                        initialNetPlan.removeAllMulticastTrees(layer);
149                }
150
151                initialNetPlan.setRoutingType(RoutingType.SOURCE_ROUTING);
152                for (Route r : initialNetPlan.getRoutes(layer)) routeOriginalLinks.put (r , r.getSeqLinksRealPath());
153                this.finishTransitory(0);
154        }
155
156        @Override
157        public void processEvent(NetPlan currentNetPlan, SimEvent event)
158        {
159                if (event.getEventObject () instanceof SimEvent.RouteAdd)
160                {
161                        SimEvent.RouteAdd addRouteEvent = (SimEvent.RouteAdd) event.getEventObject ();
162                        if (addRouteEvent.demand.getLayer() != this.layer) throw new Net2PlanException ("Routes cannot be added at layers different to layer " + layerId.getLong ());
163
164                        System.out.println ("Recevie RouteAdd: " + addRouteEvent + ", demand: " + addRouteEvent.demand);
165                        /* update the offered traffic of the demand */
166                        this.stat_numOfferedConnections ++;
167                        this.stat_trafficOfferedConnections += addRouteEvent.carriedTraffic;
168                        
169                        /* Computes one or two paths over the links (the second path would be a segment). You cannot use the already existing segments in these paths */
170                        if (newRoutesHave11Protection)
171                        {
172                                Pair<List<Link>,List<Link>> spLinks = computeValid11PathPairNewRoute(addRouteEvent.demand , addRouteEvent.occupiedLinkCapacity); // cannot use protection segments for this path, since the route still does not have them!!
173//                              System.out.println ("protectionTypeToNewRoutes: " + protectionTypeToNewRoutes.getString());
174//                              System.out.println ("spLinks : " + spLinks);
175                                if (spLinks != null)
176                                {
177                                        final Route addedRoute = currentNetPlan.addRoute(addRouteEvent.demand , addRouteEvent.carriedTraffic , addRouteEvent.occupiedLinkCapacity, spLinks.getFirst() , null);
178                                        final ProtectionSegment addedSegment = currentNetPlan.addProtectionSegment(spLinks.getSecond() , addRouteEvent.occupiedLinkCapacity , null);
179                                        addedRoute.addProtectionSegment(addedSegment);
180                                        addRouteEvent.routeAddedToFillByProcessor = addedRoute;
181                                        this.routeOriginalLinks.put (addedRoute , spLinks.getFirst());
182                                        this.stat_numCarriedConnections ++;
183                                        this.stat_trafficCarriedConnections += addRouteEvent.carriedTraffic;
184                                        System.out.println ("Added route: " + addedRoute);
185                                }
186                        }
187                        else
188                        {
189                                List<Link> spLinks = computeValidPathNewRoute(addRouteEvent.demand , addRouteEvent.occupiedLinkCapacity); // cannot use protection segments for this path, since the route still does not have them!!
190                                if (!spLinks.isEmpty())
191                                {
192                                        final Route addedRoute = currentNetPlan.addRoute(addRouteEvent.demand , addRouteEvent.carriedTraffic , addRouteEvent.occupiedLinkCapacity, spLinks , null);
193                                        this.routeOriginalLinks.put (addedRoute , spLinks);
194                                        this.stat_numCarriedConnections ++;
195                                        this.stat_trafficCarriedConnections += addRouteEvent.carriedTraffic;
196                                        addRouteEvent.routeAddedToFillByProcessor = addedRoute;
197                                }
198                        }
199                        
200                }
201                else if (event.getEventObject () instanceof SimEvent.RouteRemove)
202                {
203                        SimEvent.RouteRemove routeEvent = (SimEvent.RouteRemove) event.getEventObject ();
204                        Route routeToRemove = routeEvent.route;
205                        if (routeToRemove == null) throw new RuntimeException ("Bad");
206                        routeToRemove.remove();
207                        for (ProtectionSegment s : routeToRemove.getPotentialBackupProtectionSegments()) s.remove ();
208                        this.routeOriginalLinks.remove(routeToRemove);
209                } else if (event.getEventObject () instanceof SimEvent.DemandModify)
210                {
211                        SimEvent.DemandModify ev = (SimEvent.DemandModify) event.getEventObject ();
212                        Demand d = ev.demand; 
213                        if (ev.modificationIsRelativeToCurrentOfferedTraffic) 
214                                d.setOfferedTraffic(d.getOfferedTraffic() + ev.offeredTraffic);
215                        else
216                                d.setOfferedTraffic(ev.offeredTraffic);
217                } else if (event.getEventObject () instanceof SimEvent.NodesAndLinksChangeFailureState)
218                {
219                        SimEvent.NodesAndLinksChangeFailureState ev = (SimEvent.NodesAndLinksChangeFailureState) event.getEventObject ();
220
221//                      System.out.println ("Event NodesAndLinksChangeFailureState: links up" + ev.linksUp + ", links down: " + ev.linksDown);
222                        /* This automatically sets as up the routes affected by a repair in its current path, and sets as down the affected by a failure in its current path */
223                        currentNetPlan.setLinksAndNodesFailureState(ev.linksToUp , ev.linksToDown , ev.nodesToUp , ev.nodesToDown);
224                        
225                        if (isProtectionRecovery || isRestorationRecovery)
226                        {
227                                /* Try to reroute the routes that are still failing */
228                                for (Route r : new HashSet<Route> (currentNetPlan.getRoutesDown(layer)))
229                                {
230                                        this.stat_numAttemptedToRecoverConnections ++;
231                                        this.stat_trafficAttemptedToRecoverConnections += r.getCarriedTrafficInNoFailureState();
232                                        List<Link> spLinks = isProtectionRecovery? computeValidReroute_protection(r) : computeValidPathNewRoute (r.getDemand() , r.getOccupiedCapacityInNoFailureState());
233                                        if (!spLinks.isEmpty()) 
234                                        { 
235                                                r.setSeqLinksAndProtectionSegments(spLinks);
236                                                this.stat_numSuccessfullyRecoveredConnections ++; 
237                                                this.stat_trafficSuccessfullyRecoveredConnections += r.getCarriedTrafficInNoFailureState(); 
238                                        }
239                                }
240                        }
241                }
242                else throw new Net2PlanException ("Unknown event type: " + event);
243        }       
244        @Override
245        public String finish(StringBuilder output, double simTime)
246        {
247                final double trafficBlockingOnConnectionSetup = stat_trafficOfferedConnections == 0? 0 : 1 - (stat_trafficCarriedConnections / stat_trafficOfferedConnections );
248                final double connectionBlockingOnConnectionSetup = stat_numOfferedConnections == 0? 0.0 : 1 - (((double) stat_numCarriedConnections) / ((double) stat_numOfferedConnections));
249                final double successProbabilityRecovery = stat_numAttemptedToRecoverConnections == 0? 0.0 : (((double) stat_numSuccessfullyRecoveredConnections) / ((double) stat_numAttemptedToRecoverConnections));
250                final double successProbabilityTrafficRecovery = stat_trafficAttemptedToRecoverConnections == 0? 0.0 : (((double) stat_trafficSuccessfullyRecoveredConnections) / ((double) stat_trafficAttemptedToRecoverConnections));
251                final double dataTime = simTime - stat_transitoryInitTime;
252                if (dataTime <= 0) { output.append ("<p>No time for data acquisition</p>"); return ""; }
253
254                output.append (String.format("<p>Total traffic of offered connections: number connections %d, total time average traffic: %f</p>", stat_numOfferedConnections, stat_trafficOfferedConnections / dataTime));
255                output.append (String.format("<p>Total traffic of carried connections: number connections %d, total time average traffic: %f</p>", stat_numCarriedConnections, stat_trafficCarriedConnections / dataTime));
256                output.append (String.format("<p>Blocking at connection setup: Probability of blocking a connection: %f, Fraction of blocked traffic: %f</p>", connectionBlockingOnConnectionSetup , trafficBlockingOnConnectionSetup));
257                output.append (String.format("<p>Number connections attempted to recover: %d (summing time average traffic: %f). </p>", stat_numAttemptedToRecoverConnections, stat_trafficAttemptedToRecoverConnections / dataTime));
258                output.append (String.format("<p>Number connections successfully recovered: %d (summing time average traffic: %f). </p>", stat_numSuccessfullyRecoveredConnections, stat_trafficSuccessfullyRecoveredConnections / dataTime));
259                output.append (String.format("<p>Probability of successfully recover a connection: %f. Proability weighted by the connection traffic: %f). </p>", successProbabilityRecovery, successProbabilityTrafficRecovery));
260//              output.append (String.format("<p>Total traffic carried at current state: %f. </p>", -1);
261                return "";
262        }
263
264        @Override
265        public void finishTransitory(double simTime)
266        {
267                this.stat_trafficOfferedConnections = 0;
268                this.stat_trafficCarriedConnections = 0;
269                this.stat_trafficAttemptedToRecoverConnections  = 0;
270                this.stat_trafficSuccessfullyRecoveredConnections = 0;
271                this.stat_numOfferedConnections = 0;
272                this.stat_numCarriedConnections = 0;
273                this.stat_numAttemptedToRecoverConnections = 0;
274                this.stat_numSuccessfullyRecoveredConnections = 0;
275                this.stat_transitoryInitTime = simTime;
276        }
277
278        /* down links or segments cannot be used */
279        private List<Link> computeValidPathNewRoute (Demand demand , double occupiedLinkCapacity)
280        {
281//              System.out.println ("computeValidPathNewRoute, demand: " + demand + " occupied: " + occupiedLinkCapacity);
282                final List<List<Link>> paths = cpl.get(demand);
283                /* If load sharing */
284                if (isLoadSharing)
285                {
286                        final int randomChosenIndex = rng.nextInt(paths.size());
287                        final List<Link> seqLinks = cpl.get(demand).get(randomChosenIndex);
288                        if (isValidPath(seqLinks, occupiedLinkCapacity).getFirst()) return seqLinks; else return new LinkedList<Link> ();
289                }
290                /* If alternate or LCR */
291                List<Link> lcrSoFar = null; double lcrIdleCapacitySoFar = -Double.MAX_VALUE;
292                for (List<Link> seqLinks : paths)
293                {
294                        Pair<Boolean,Double> isValid = isValidPath(seqLinks, occupiedLinkCapacity);
295//                      System.out.println ("path: " + seqLinks + ", occuied: " + occupiedLinkCapacity + ", isValid: " + isValid);
296                        if (isValid.getFirst()) 
297                        {
298                                if (isAlternateRouting) return seqLinks; 
299                                if (isValid.getSecond() > lcrIdleCapacitySoFar)
300                                {
301                                        lcrIdleCapacitySoFar = isValid.getSecond();
302                                        lcrSoFar = seqLinks;
303                                }
304                        }
305                }
306                return (isAlternateRouting || (lcrSoFar == null))? new LinkedList<Link> () : lcrSoFar; 
307        }
308
309        private Pair<List<Link>,List<Link>> computeValid11PathPairNewRoute (Demand demand , double occupiedLinkCapacity)
310        {
311                final List<Pair<List<Link>,List<Link>>> pathPairs = cpl11.get(demand);
312                /* If load sharing */
313                if (isLoadSharing)
314                {
315                        final int randomChosenIndex = rng.nextInt(pathPairs.size());
316                        final Pair<List<Link>,List<Link>> pathPair = pathPairs.get(randomChosenIndex);
317                        if (isValidPath(pathPair.getFirst(), occupiedLinkCapacity).getFirst() && isValidPath(pathPair.getSecond(), occupiedLinkCapacity).getFirst ())
318                                return pathPair; else return null;
319                }
320
321                Pair<List<Link>,List<Link>> lcrSoFar = null; double lcrIdleCapacitySoFar= -Double.MAX_VALUE;
322                for (Pair<List<Link>,List<Link>> pathPair : this.cpl11.get(demand))
323                {
324                        Pair<Boolean,Double> validityFirstPath = isValidPath(pathPair.getFirst(), occupiedLinkCapacity); 
325                        if (!validityFirstPath.getFirst()) continue;
326                        Pair<Boolean,Double> validitySecondPath = isValidPath(pathPair.getSecond(), occupiedLinkCapacity); 
327                        if (!validitySecondPath.getFirst()) continue;
328                        if (isAlternateRouting) return pathPair;
329                        final double thisPairIdleCapacity = Math.min(validityFirstPath.getSecond(), validitySecondPath.getSecond());
330                        if (thisPairIdleCapacity > lcrIdleCapacitySoFar)
331                        {
332                                lcrIdleCapacitySoFar = thisPairIdleCapacity;
333                                lcrSoFar = pathPair;
334                        }
335                }
336                return lcrSoFar; //if alternate, this is null also
337        }
338
339        /* down links or segments cannot be used */
340        private List<Link> computeValidReroute_protection (Route routeToReroute)
341        {
342                Map<Link,Double> costMap = new HashMap<Link,Double> (); Set<Link> linkMap = new HashSet<Link> (); 
343                final double minimumCapacityNeeded = routeToReroute.getOccupiedCapacityInNoFailureState();
344                for (Link e : this.routeOriginalLinks.get(routeToReroute)) 
345                        if (!e.isDown() && !e.getOriginNode().isDown() && !e.getDestinationNode().isDown())
346                                if (e.getCapacity() - e.getReservedCapacityForProtection() - e.getCarriedTrafficNotIncludingProtectionSegments() >= minimumCapacityNeeded) 
347                                {
348                                        linkMap.add (e);
349                                        costMap.put (e , isShortestPathNumHops? 1 : e.getLengthInKm());
350                                }
351                                        
352                for (ProtectionSegment s : routeToReroute.getPotentialBackupProtectionSegments()) 
353                        if ((s.getReservedCapacityForProtection() - s.getCarriedTraffic() >= minimumCapacityNeeded) && (!s.isDown()))
354                        { 
355                                linkMap.add (s);
356                                costMap.put (s , isShortestPathNumHops? s.getNumberOfHops() : s.getLengthInKm()); 
357                        }
358
359                List<Link> res = GraphUtils.getShortestPath(nodes , linkMap , routeToReroute.getIngressNode() , routeToReroute.getEgressNode() , costMap);
360                return res;
361        }
362
363        private Pair<Boolean,Double> isValidPath (List<Link> seqLinks , double routeOccupiedCapacity)
364        {
365                final double minimumCapacityNeeded = routeOccupiedCapacity;
366                boolean validPath = true; double thisPathIdleCapacity = Double.MAX_VALUE; 
367                for (Link e : seqLinks) 
368                {
369                        final double thisLinkIdleCapacity = e.getCapacity() - e.getCarriedTrafficNotIncludingProtectionSegments();
370                        thisPathIdleCapacity = Math.min(thisPathIdleCapacity, thisLinkIdleCapacity);
371                        if (e.isDown() || e.getOriginNode().isDown() || e.getDestinationNode().isDown() || (thisLinkIdleCapacity <= minimumCapacityNeeded))
372                        { validPath = false; break; }
373                }
374                return Pair.of(validPath, thisPathIdleCapacity);
375        }
376}