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}