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.general.onlineSim; 019 020import java.util.ArrayList; 021import java.util.HashMap; 022import java.util.HashSet; 023import java.util.LinkedList; 024import java.util.List; 025import java.util.Map; 026import java.util.Random; 027import java.util.Set; 028 029import cern.colt.matrix.tdouble.DoubleFactory1D; 030import cern.colt.matrix.tdouble.DoubleFactory2D; 031import cern.colt.matrix.tdouble.DoubleMatrix1D; 032import cern.colt.matrix.tdouble.DoubleMatrix2D; 033import cern.colt.matrix.tint.IntFactory1D; 034import cern.jet.math.tdouble.DoubleFunctions; 035 036import com.net2plan.interfaces.networkDesign.Demand; 037import com.net2plan.interfaces.networkDesign.Link; 038import com.net2plan.interfaces.networkDesign.Net2PlanException; 039import com.net2plan.interfaces.networkDesign.NetPlan; 040import com.net2plan.interfaces.networkDesign.NetworkElement; 041import com.net2plan.interfaces.networkDesign.NetworkLayer; 042import com.net2plan.interfaces.networkDesign.Node; 043import com.net2plan.interfaces.networkDesign.ProtectionSegment; 044import com.net2plan.interfaces.networkDesign.Route; 045import com.net2plan.interfaces.networkDesign.SharedRiskGroup; 046import com.net2plan.interfaces.simulation.IEventProcessor; 047import com.net2plan.interfaces.simulation.SimEvent; 048import com.net2plan.libraries.WDMUtils; 049import com.net2plan.utils.Constants.RoutingType; 050import com.net2plan.utils.InputParameter; 051import com.net2plan.utils.Pair; 052import com.net2plan.utils.Quadruple; 053import com.net2plan.utils.RandomUtils; 054import com.net2plan.utils.Triple; 055 056/** 057 * Implements the reactions of a WDM network carrying lightpaths in a fixed grid of wavelengths 058 * 059 * This algorithm implements the reactions of a WDM network carrying lightpaths in a fixed wavelength grid, to a the following events: 060 * <ul> 061 * <li>WDMUtils.LightpathAdd: Adds the corresponding lightpath to the network (the Route object and potentially a ProtectionSegment object if the lightpath is asked to be 1+1 protected), if enough resources exist for it. If the event includes a Demand object, the lightpath is associated to it. If not, a new demand is created.</li> 062 * <li>WDMUtils.LightpathRemove: Removes the corresponding lightpath (including the Demand and Route objects, and potentially the 1+1 segment if any), releasing the resources.</li> 063 * <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> 064 * <li>SimEvent.DemandModify: Modifies the offered traffic of a demand (a lightpath).</li> 065 * <li>SimEvent.DemandRemove: Removes a demand, and all its associated lightpaths if any, releasing the resources.</li> 066 * </ul> 067 * 068 * This module can be used in conjunction with the {@code Online_evGen_wdm} generator for simulating the WDM layer. 069 * 070 * See the technology conventions used in Net2Plan built-in algorithms and libraries to represent WDM networks. 071 * @net2plan.keywords WDM, Network recovery: protection, Network recovery: restoration 072 * @net2plan.inputParameters 073 * @author Pablo Pavon-Marino, Jose-Luis Izquierdo-Zaragoza 074 */ 075public class Online_evProc_wdm extends IEventProcessor 076{ 077 private InputParameter wdmNumWavelengthsPerFiber = new InputParameter ("wdmNumWavelengthsPerFiber", (int) 40 , "Set the number of wavelengths per link. If < 1, the number of wavelengths set in the input file is used."); 078 private InputParameter wdmRwaType = new InputParameter ("wdmRwaType", "#select# srg-disjointness-aware-route-first-fit alternate-routing least-congested-routing load-sharing" , "Criteria to decide the route of a connection among the available paths"); 079 private InputParameter wdmKShortestPathType = new InputParameter ("wdmKShortestPathType", "#select# hops km" , "Criteria to compute the shortest path. Valid values: 'hops' or 'km'"); 080 private InputParameter wdmK = new InputParameter ("wdmK", (int) 5 , "Maximum number of admissible paths per demand in the candidate list computation" , 1 , Integer.MAX_VALUE); 081 private InputParameter wdmRandomSeed = new InputParameter ("wdmRandomSeed", (long) 1 , "Seed for the random generator (-1 means random)"); 082 private InputParameter wdmMaxLightpathLengthInKm = new InputParameter ("wdmMaxLightpathLengthInKm", (double) -1 , "Lightpaths longer than this are considered not admissible. A non-positive number means this limit does not exist"); 083 private InputParameter wdmMaxLightpathNumHops = new InputParameter ("wdmMaxLightpathNumHops", (int) -1 , "A lightpath cannot have more than this number of hops. A non-positive number means this limit does not exist"); 084 private InputParameter wdmLayerIndex = new InputParameter ("wdmLayerIndex", (int) 0 , "Index of the WDM layer (-1 means default layer)"); 085 private InputParameter wdmRecoveryType = new InputParameter ("wdmRecoveryType", "#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."); 086 private InputParameter wdmRemovePreviousLightpaths = new InputParameter ("wdmRemovePreviousLightpaths", false , "If true, previous lightpaths are removed from the system during initialization."); 087 private InputParameter wdmProtectionTypeToNewRoutes = new InputParameter ("wdmProtectionTypeToNewRoutes", "#select# none 1+1-link-disjoint 1+1-node-disjoint 1+1-srg-disjoint" , "New lightpaths are not protected, or are protected by a 1+1 link disjoint, or a node disjoint or a SRG disjoint lightpath"); 088 private InputParameter wdmLineRatePerLightpath_Gbps = new InputParameter ("wdmLineRatePerLightpath_Gbps", (double) 40 , "All the lightpaths have this carried traffic by default, when a lightpath is added and this quantity is not specified in the add lightpath event" , 0 , false , Double.MAX_VALUE , true); 089 090 private NetworkLayer wdmLayer; 091 private Map<Route,Pair<RWA,RWA>> wdmRouteOriginalRwa; 092 private NetPlan cplWdm; 093 private DoubleMatrix2D wavelengthFiberOccupancy; 094 private DoubleMatrix2D cplA_rs , cplA_pss; 095 096 private boolean newRoutesHave11Protection; 097 private boolean isRestorationRecovery , isProtectionRecovery , isShortestPathNumHops; 098 private boolean isAlternateRouting , isLeastCongestedRouting , isLoadSharing , isSrgDisjointAwareLpRouting; 099 private Random rng; 100 private int E_wdm; 101 private int protectionTypeCode; 102 103 private double stat_trafficOfferedConnections , stat_trafficCarriedConnections; 104 private double stat_trafficAttemptedToRecoverConnections , stat_trafficSuccessfullyRecoveredConnections; 105 private long stat_numOfferedConnections , stat_numCarriedConnections; 106 private long stat_numAttemptedToRecoverConnections , stat_numSuccessfullyRecoveredConnections; 107 private double stat_transitoryInitTime; 108 109 110 @Override 111 public String getDescription() 112 { 113 return "Implements the reactions of a WDM network carrying lightpaths in a fixed grid of wavelengths"; 114 } 115 116 @Override 117 public List<Triple<String, String, String>> getParameters() 118 { 119 /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */ 120 return InputParameter.getInformationAllInputParameterFieldsOfObject(this); 121 } 122 123 @Override 124 public void initialize(NetPlan initialNetPlan, Map<String, String> algorithmParameters, Map<String, String> simulationParameters, Map<String, String> net2planParameters) 125 { 126 /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */ 127 InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters); 128 if (!wdmKShortestPathType.getString ().equalsIgnoreCase("km") && !wdmKShortestPathType.getString ().equalsIgnoreCase("hops")) 129 throw new Net2PlanException("Wrong 'shortestPathType' parameter"); 130 131 this.wdmLayer = wdmLayerIndex.getInt () == -1? initialNetPlan.getNetworkLayerDefault() : initialNetPlan.getNetworkLayer(wdmLayerIndex.getInt ()); 132 this.isShortestPathNumHops = wdmKShortestPathType.getString ().equalsIgnoreCase("hops"); 133 this.wdmRouteOriginalRwa = new HashMap<Route,Pair<RWA,RWA>> (); 134 this.isRestorationRecovery = wdmRecoveryType.getString ().equalsIgnoreCase("restoration"); 135 this.isProtectionRecovery = wdmRecoveryType.getString ().equalsIgnoreCase("protection"); 136 this.isAlternateRouting = wdmRwaType.getString().equalsIgnoreCase("alternate-routing"); 137 this.isLeastCongestedRouting = wdmRwaType.getString().equalsIgnoreCase("least-congested-routing"); 138 this.isSrgDisjointAwareLpRouting = wdmRwaType.getString().equalsIgnoreCase("srg-disjointness-aware-route-first-fit");; 139 this.isLoadSharing = wdmRwaType.getString().equalsIgnoreCase("load-sharing"); 140 this.newRoutesHave11Protection = !wdmProtectionTypeToNewRoutes.getString ().equalsIgnoreCase("none"); 141 this.rng = new Random(wdmRandomSeed.getLong () == -1? (long) RandomUtils.random(0, Long.MAX_VALUE - 1) : wdmRandomSeed.getLong ()); 142 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"); 143 144 if (wdmRemovePreviousLightpaths.getBoolean()) 145 { 146 initialNetPlan.removeAllDemands(wdmLayer); 147 initialNetPlan.removeAllMulticastDemands(wdmLayer); 148 } 149 initialNetPlan.setRoutingType(RoutingType.SOURCE_ROUTING , wdmLayer); 150 if (wdmNumWavelengthsPerFiber.getInt() > 0) WDMUtils.setFibersNumWavelengths(initialNetPlan , wdmNumWavelengthsPerFiber.getInt() , wdmLayer); 151 152 153 /* Compute the candidate path list */ 154 this.E_wdm = initialNetPlan.getNumberOfLinks(wdmLayer); 155 final DoubleMatrix1D linkCostVector = isShortestPathNumHops? DoubleFactory1D.dense.make (E_wdm , 1.0) : initialNetPlan.getVectorLinkLengthInKm(wdmLayer); 156 this.cplWdm = initialNetPlan.copy(); 157 for (NetworkLayer cplLayer : new HashSet<NetworkLayer> (cplWdm.getNetworkLayers())) if (cplLayer.getId () != wdmLayer.getId ()) cplWdm.removeNetworkLayer(cplLayer); 158 cplWdm.removeAllDemands(); 159 for (Node n1 : cplWdm.getNodes ()) for (Node n2 : cplWdm.getNodes ()) if (n1 != n2) cplWdm.addDemand(n1 , n2 , 0 , null); 160 final Map<Demand,List<List<Link>>> cplPaths = cplWdm.computeUnicastCandidatePathList(linkCostVector.toArray() , "K", Integer.toString(wdmK.getInt ()), "maxLengthInKm", Double.toString(wdmMaxLightpathLengthInKm.getDouble () > 0? wdmMaxLightpathLengthInKm.getDouble () : Double.MAX_VALUE) , "maxNumHops", Integer.toString(wdmMaxLightpathNumHops.getInt () > 0? wdmMaxLightpathNumHops.getInt () : Integer.MAX_VALUE)); 161 this.protectionTypeCode = wdmProtectionTypeToNewRoutes.getString ().equals("1+1-srg-disjoint") ? 0 : wdmProtectionTypeToNewRoutes.getString ().equals("1+1-node-disjoint")? 1 : 2; 162 if (newRoutesHave11Protection) 163 { 164// System.out.println ("cplWdm.getLinksDownAllLayers(): " + cplWdm.getLinksDownAllLayers()); 165// System.out.println ("cplWdm.getRoutes(): " + cplWdm.getRoutes()); 166// System.out.println ("INITIALIZE WDM WITH 1+1: protectionTypeCode: " + protectionTypeCode + ", linkCostVector: " + linkCostVector); 167 final Map<Demand,List<Pair<List<Link>,List<Link>>>> pathPairs = NetPlan.computeUnicastCandidate11PathList(cplPaths, linkCostVector, protectionTypeCode); 168// for (Demand d : pathPairs.keySet()) 169// System.out.println ("Demand " + d + ", path pairs: " + pathPairs.get(d)); 170// System.out.println ("PathPairs: " + pathPairs); 171 this.cplWdm.addRoutesAndProtectionSegmentFromCandidate11PathList(pathPairs); 172 for (Route r : cplWdm.getRoutes()) 173 { 174// System.out.println ("Route: " + r + ", demand: " + r.getDemand () + ", SEQ LINKS: " + r.getSeqLinksRealPath() + ", backup: " + r.getPotentialBackupProtectionSegments().iterator().next().getSeqLinks()); 175 checkDisjointness (r.getSeqLinksRealPath() , r.getPotentialBackupProtectionSegments().iterator().next().getSeqLinks() , protectionTypeCode); 176 } 177 } 178 else 179 { 180// System.out.println ("INITIALIZE WDM WITHOUT 1+1"); 181 this.cplWdm.addRoutesFromCandidatePathList(cplPaths); 182 } 183// for (Demand d : cplWdm.getDemands()) if (d.getRoutes().isEmpty()) throw new Net2PlanException ("Some demands in the candidate path list have no routes: increase 'k' (or maybe the topology is not connected)"); 184 this.cplA_rs = cplWdm.getMatrixRoute2SRGAffecting(); 185 this.cplA_pss = cplWdm.getMatrixProtectionSegment2SRGAffecting(); 186 187// System.out.println ("******************* cplWDM: " + cplWdm); 188 189 this.wavelengthFiberOccupancy = WDMUtils.getMatrixWavelength2FiberOccupancy(initialNetPlan, true , wdmLayer); 190 initialNetPlan.setLinkCapacityUnitsName("Wavelengths" , wdmLayer); 191 192 for (Route r : initialNetPlan.getRoutes(wdmLayer)) 193 { 194 if (!r.getSeqLinksAndProtectionSegments().equals (r.getSeqLinksRealPath())) throw new Net2PlanException ("Some of the initial routes are traversing protection segments"); 195 final int [] seqWavelengths = WDMUtils.getLightpathSeqWavelengths(r); 196 for (int cont = 1; cont < seqWavelengths.length ; cont ++) if (seqWavelengths [cont] != seqWavelengths [0]) throw new Net2PlanException ("Initial lightpaths must have route continuity"); 197 final RWA thisRouteRWA = new RWA (r.getSeqLinksRealPath() , seqWavelengths [0]); 198 RWA segmentRWA = null; 199 if (r.getPotentialBackupProtectionSegments().size () > 1) throw new Net2PlanException ("The number of protection segments of a route cannot be higher than one"); 200 if ((r.getPotentialBackupProtectionSegments().size () == 1) && (!isProtectionRecovery)) throw new Net2PlanException ("Initial routes have protection segments, which would be unused since the recovery type is not protection"); 201 if (r.getPotentialBackupProtectionSegments().size () == 1) 202 { 203 final ProtectionSegment backupPath = r.getPotentialBackupProtectionSegments().iterator().next(); 204 final int [] seqWavelengths_backup = WDMUtils.getLightpathSeqWavelengths(backupPath); 205 for (int cont = 1; cont < seqWavelengths_backup.length ; cont ++) if (seqWavelengths_backup [cont] != seqWavelengths_backup [0]) throw new Net2PlanException ("Initial lightpaths must have route continuity"); 206 segmentRWA = new RWA (backupPath.getSeqLinks() , seqWavelengths_backup [0]); 207 } 208 wdmRouteOriginalRwa.put (r , Pair.of (thisRouteRWA , segmentRWA)); 209 } 210 211 this.finishTransitory(0); 212 checkClashing (initialNetPlan); 213 } 214 215 @Override 216 public void processEvent(NetPlan currentNetPlan, SimEvent event) 217 { 218 if (event.getEventObject () instanceof WDMUtils.LightpathAdd) 219 { 220 WDMUtils.LightpathAdd addLpEvent = (WDMUtils.LightpathAdd) event.getEventObject (); 221 if (addLpEvent.layer != this.wdmLayer) throw new Net2PlanException ("Lightpaths cannot be added to layer " + addLpEvent.demand.getLayer() + ", and just to the WDM layer (" + wdmLayer + ")"); 222 final Node ingressNode = addLpEvent.ingressNode; 223 final Node egressNode = addLpEvent.egressNode; 224 final Demand cplDemand = this.cplWdm.getNodePairDemands(cplWdm.getNodeFromId(ingressNode.getId()) , cplWdm.getNodeFromId(egressNode.getId()) , false).iterator().next(); 225 final double lineRateThisLp_Gbps = addLpEvent.lineRateGbps > 0? addLpEvent.lineRateGbps : wdmLineRatePerLightpath_Gbps.getDouble(); 226 227// System.out.println ("EVENT LightpathAddAsPrimary: " + addLpEvent + ", demand: " + addLpEvent.demand); 228 /* update the offered traffic of the demand */ 229 this.stat_numOfferedConnections ++; 230 this.stat_trafficOfferedConnections += lineRateThisLp_Gbps; 231 232 /* 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 */ 233 if (newRoutesHave11Protection) 234 { 235 /* The RWA may be computed by me, or mandated by the event */ 236 Pair<RWA,RWA> rwa; 237 if (addLpEvent.seqLinks_backup == null) 238 rwa = computeValid11PathPairNewRoute(cplDemand , currentNetPlan); 239 else 240 { 241 if (!WDMUtils.isNonConflictingRWAPair(addLpEvent.seqLinks_primary , addLpEvent.seqWavelengths_primary , addLpEvent.seqLinks_backup , addLpEvent.seqWavelengths_backup , wavelengthFiberOccupancy)) 242 throw new Net2PlanException ("A request was received to add a conflicting lightpath 1+1 pair"); 243 rwa = Pair.of (new RWA (addLpEvent.seqLinks_primary , addLpEvent.seqWavelengths_primary [0]) , new RWA (addLpEvent.seqLinks_backup , addLpEvent.seqWavelengths_backup [0])); 244 } 245// System.out.println ("------ ADD LP: rwa: " + rwa); 246 if (rwa != null) 247 { 248 for (Link e : rwa.getFirst ().path) if (wavelengthFiberOccupancy.get (rwa.getFirst ().w , e.getIndex()) != 0) throw new RuntimeException ("Bad"); 249 for (Link e : rwa.getSecond ().path) if (wavelengthFiberOccupancy.get (rwa.getSecond ().w , e.getIndex()) != 0) throw new RuntimeException ("Bad"); 250 for (Link e : rwa.getFirst ().path) if (e.getNetPlan() != currentNetPlan) throw new RuntimeException ("Bad"); 251 for (Link e : rwa.getSecond ().path) if (e.getNetPlan() != currentNetPlan) throw new RuntimeException ("Bad"); 252 253 final Demand wdmLayerDemand = addLpEvent.demand == null? currentNetPlan.addDemand(addLpEvent.ingressNode, addLpEvent.egressNode, lineRateThisLp_Gbps , null, wdmLayer) : addLpEvent.demand; 254 final Route wdmLayerRoute = WDMUtils.addLightpathAndUpdateOccupancy(wdmLayerDemand, rwa.getFirst().path, lineRateThisLp_Gbps, rwa.getFirst ().w , wavelengthFiberOccupancy); 255 final ProtectionSegment wdmLayerSegment = WDMUtils.addLightpathAsProtectionSegmentAndUpdateOccupancy(rwa.getSecond().path, rwa.getSecond ().w, wavelengthFiberOccupancy); 256 checkDisjointness(wdmLayerRoute.getSeqLinksRealPath() , wdmLayerSegment.getSeqLinks() , protectionTypeCode); 257 wdmLayerRoute.addProtectionSegment(wdmLayerSegment); 258 this.wdmRouteOriginalRwa.put (wdmLayerRoute , rwa); 259 this.stat_numCarriedConnections ++; 260 this.stat_trafficCarriedConnections += lineRateThisLp_Gbps; 261 addLpEvent.lpAddedToFillByProcessor = wdmLayerRoute; 262 checkClashing (currentNetPlan); 263 } 264 checkClashing (currentNetPlan); 265 } 266 else 267 { 268 /* The RWA may be computed by me, or mandated by the event */ 269 RWA rwa; 270 if (addLpEvent.seqLinks_primary == null) 271 rwa = computeValidPathNewRoute(cplDemand , currentNetPlan); 272 else 273 { 274 if (!WDMUtils.isNonConflictingRWA(addLpEvent.seqLinks_primary , addLpEvent.seqWavelengths_primary , wavelengthFiberOccupancy)) 275 throw new Net2PlanException ("A request was received to add a conflicting lightpath"); 276 rwa = new RWA (addLpEvent.seqLinks_primary , addLpEvent.seqWavelengths_primary [0]); 277 } 278// System.out.println ("------ ADD LP: rwa: " + rwa); 279 if (rwa != null) 280 { 281 final Demand wdmLayerDemand = addLpEvent.demand == null? currentNetPlan.addDemand(addLpEvent.ingressNode, addLpEvent.egressNode, lineRateThisLp_Gbps , null, wdmLayer) : addLpEvent.demand; 282 final Route wdmLayerRoute = WDMUtils.addLightpathAndUpdateOccupancy(wdmLayerDemand, rwa.path, lineRateThisLp_Gbps, rwa.w , wavelengthFiberOccupancy); 283 this.wdmRouteOriginalRwa.put (wdmLayerRoute , Pair.of(rwa,(RWA)null)); 284 this.stat_numCarriedConnections ++; 285 this.stat_trafficCarriedConnections += lineRateThisLp_Gbps; 286 addLpEvent.lpAddedToFillByProcessor = wdmLayerRoute; 287// System.out.println ("Added lp: " + wdmLayerRoute); 288 } 289 } 290 checkClashing (currentNetPlan); 291 } 292 else if (event.getEventObject () instanceof WDMUtils.LightpathRemove) 293 { 294 WDMUtils.LightpathRemove lpEvent = (WDMUtils.LightpathRemove) event.getEventObject (); 295 final Route lpToRemove = lpEvent.lp; 296 final Pair<RWA,RWA> originalRwa = wdmRouteOriginalRwa.get(lpToRemove); 297 if (originalRwa == null) return; // the ligtpath was already removed, because it was first accepted, but then blocked because of failures 298// System.out.println ("lpToRemvoe: " + lpToRemove + ", links: " + lpToRemove.getSeqLinksAndProtectionSegments() + ", w: " + Arrays.toString (WDMUtils.getLightpathSeqWavelengths(lpToRemove))); 299// System.out.println ("wavelengthFiberOccupancy: " + wavelengthFiberOccupancy); 300 if (isRestorationRecovery) // restoration => the current route is the one to release 301 removeRoute_restoration(lpToRemove , true); 302 else 303 removeRoute_protection(lpToRemove , originalRwa); 304// if (!WDMUtils.getMatrixWavelength2FiberOccupancy(currentNetPlan,true,wdmLayer).equals(wavelengthFiberOccupancy)) 305// { 306// System.out.println ("WDMUtils.getMatrixWavelength2FiberOccupancy(currentNetPlan,wdmLayer): " + WDMUtils.getMatrixWavelength2FiberOccupancy(currentNetPlan,true,wdmLayer)); 307// System.out.println ("wavelengthFiberOccupancy: " + wavelengthFiberOccupancy); 308// throw new RuntimeException ("Bad"); 309// } 310 checkClashing (currentNetPlan); 311// WDMUtils.checkConsistency(currentNetPlan , true , wdmLayer); 312 } else if (event.getEventObject () instanceof SimEvent.NodesAndLinksChangeFailureState) 313 { 314 SimEvent.NodesAndLinksChangeFailureState ev = (SimEvent.NodesAndLinksChangeFailureState) event.getEventObject (); 315 316// System.out.println ("----------- Event NodesAndLinksChangeFailureState: links up" + ev.linksUp + ", links down: " + ev.linksDown); 317 318 checkClashing (currentNetPlan); 319 320 /* 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 */ 321 Set<Route> routesFromDownToUp = currentNetPlan.getRoutesDown(wdmLayer); 322 323 currentNetPlan.setLinksAndNodesFailureState(ev.linksToUp , ev.linksToDown , ev.nodesToUp , ev.nodesToDown); 324 routesFromDownToUp.removeAll(currentNetPlan.getRoutesDown(wdmLayer)); 325 326// if (!WDMUtils.getMatrixWavelength2FiberOccupancy(currentNetPlan,true,wdmLayer).equals(wavelengthFiberOccupancy)) 327// { 328// System.out.println ("WDMUtils.getMatrixWavelength2FiberOccupancy(currentNetPlan,wdmLayer): " + WDMUtils.getMatrixWavelength2FiberOccupancy(currentNetPlan,true,wdmLayer)); 329// System.out.println ("wavelengthFiberOccupancy: " + wavelengthFiberOccupancy); 330// System.out.println ("1 minus 2: " + WDMUtils.getMatrixWavelength2FiberOccupancy(currentNetPlan,true,wdmLayer).assign(wavelengthFiberOccupancy , DoubleFunctions.minus)); 331// throw new RuntimeException ("Bad"); 332// } 333 334 checkClashing (currentNetPlan); 335 336 /* If something failed, and I am supposed to use protection or restoration... */ 337 if (isProtectionRecovery || isRestorationRecovery) 338 { 339// System.out.println ("currentNetPlan.getRoutesDown(wdmLayer): " + currentNetPlan.getRoutesDown(wdmLayer)); 340 341 /* Try to reroute the routes that are still failing */ 342 for (Route r : new HashSet<Route> (currentNetPlan.getRoutesDown(wdmLayer))) 343 { 344// if (isRestorationRecovery) 345// WDMUtils.releaseResources(r.getSeqLinksRealPath() , WDMUtils.getLightpathSeqWavelengths(r) , wavelengthFiberOccupancy, null , null); 346 347 this.stat_numAttemptedToRecoverConnections ++; 348 this.stat_trafficAttemptedToRecoverConnections += r.getCarriedTrafficInNoFailureState(); 349 final Demand cplDemand = this.cplWdm.getNodePairDemands(cplWdm.getNodeFromId(r.getIngressNode().getId()) , cplWdm.getNodeFromId(r.getEgressNode().getId()) , false).iterator().next(); 350 RWA rwa = isProtectionRecovery? computeValidReroute_protection(r) : computeValidPathNewRoute (cplDemand , currentNetPlan); 351// System.out.println ("Route down: " + r + ", r.getSeqLinksAndProtectionSegments() " + r.getSeqLinksAndProtectionSegments() + ", r.getSeqLinksRealPath(): " + r.getSeqLinksRealPath() + ", r.wavelengths: " + Arrays.toString (WDMUtils.getLightpathSeqWavelengths(r))); 352 if (rwa != null) 353 { 354// System.out.println ("Pair<List<Link>,Integer> rwa: " + rwa); 355// if (!(rwa.path.get(0) instanceof ProtectionSegment)) for (Link e: rwa.path) if (wavelengthFiberOccupancy.get(rwa.w , e.getIndex ()) != 0) { System.out.println (wavelengthFiberOccupancy); throw new RuntimeException ("Bad"); } 356 if (isRestorationRecovery) 357 { 358 WDMUtils.releaseResources(r.getSeqLinksRealPath() , WDMUtils.getLightpathSeqWavelengths(r) , wavelengthFiberOccupancy, null , null); 359 WDMUtils.allocateResources(rwa.path , IntFactory1D.dense.make(E_wdm,rwa.w).toArray() , wavelengthFiberOccupancy , null , null); 360 } 361 r.setSeqLinksAndProtectionSegments(rwa.path); 362 WDMUtils.setLightpathSeqWavelengths(r , rwa.w); 363 364 this.stat_numSuccessfullyRecoveredConnections ++; 365 this.stat_trafficSuccessfullyRecoveredConnections += r.getCarriedTrafficInNoFailureState(); 366 checkClashing (currentNetPlan); 367 } 368// else 369// { 370// if (isRestorationRecovery) // restoration => the current route is the one to release 371// removeRoute_restoration(r , false); 372// else 373// removeRoute_protection(r , wdmRouteOriginalRwa.get(r)); 374//// if (!WDMUtils.getMatrixWavelength2FiberOccupancy(currentNetPlan,true,wdmLayer).equals(wavelengthFiberOccupancy)) 375//// { 376//// System.out.println ("WDMUtils.getMatrixWavelength2FiberOccupancy(currentNetPlan,wdmLayer): " + WDMUtils.getMatrixWavelength2FiberOccupancy(currentNetPlan,true,wdmLayer)); 377//// System.out.println ("wavelengthFiberOccupancy: " + wavelengthFiberOccupancy); 378//// System.out.println ("1 minus 2: " + WDMUtils.getMatrixWavelength2FiberOccupancy(currentNetPlan,true,wdmLayer).copy ().assign(wavelengthFiberOccupancy , DoubleFunctions.minus)); 379//// System.out.println ("Route : " + r + ", w: " + Arrays.toString (WDMUtils.getLightpathSeqWavelengths(r)) + ", seq links real: " + r.getSeqLinksRealPath() + ", r.get seq links and prot: " + r.getSeqLinksAndProtectionSegments() + ", links down: " + currentNetPlan.getLinksDownAllLayers()); 380//// throw new RuntimeException ("Bad"); 381//// } 382// checkClashing (currentNetPlan); 383//// WDMUtils.checkConsistency(currentNetPlan , true , wdmLayer); 384// } 385 } 386 } 387// if (!WDMUtils.getMatrixWavelength2FiberOccupancy(currentNetPlan,true,wdmLayer).equals(wavelengthFiberOccupancy)) 388// { 389// System.out.println ("WDMUtils.getMatrixWavelength2FiberOccupancy(currentNetPlan,wdmLayer): " + WDMUtils.getMatrixWavelength2FiberOccupancy(currentNetPlan,true,wdmLayer)); 390// System.out.println ("wavelengthFiberOccupancy: " + wavelengthFiberOccupancy); 391// System.out.println ("1 minus 2: " + WDMUtils.getMatrixWavelength2FiberOccupancy(currentNetPlan,true,wdmLayer).copy ().assign(wavelengthFiberOccupancy , DoubleFunctions.minus)); 392// throw new RuntimeException ("Bad"); 393// } 394 checkClashing (currentNetPlan); 395// WDMUtils.checkConsistency(currentNetPlan , true, wdmLayer); 396 } else if (event.getEventObject () instanceof SimEvent.DemandModify) 397 { 398 SimEvent.DemandModify ev = (SimEvent.DemandModify) event.getEventObject (); 399 Demand d = ev.demand; 400 if (ev.modificationIsRelativeToCurrentOfferedTraffic) 401 d.setOfferedTraffic(d.getOfferedTraffic() + ev.offeredTraffic); 402 else 403 d.setOfferedTraffic(ev.offeredTraffic); 404// if (!WDMUtils.getMatrixWavelength2FiberOccupancy(currentNetPlan,true,wdmLayer).equals(wavelengthFiberOccupancy)) 405// { 406// System.out.println ("WDMUtils.getMatrixWavelength2FiberOccupancy(currentNetPlan,wdmLayer): " + WDMUtils.getMatrixWavelength2FiberOccupancy(currentNetPlan,true,wdmLayer)); 407// System.out.println ("wavelengthFiberOccupancy: " + wavelengthFiberOccupancy); 408// throw new RuntimeException ("Bad"); 409// } 410 checkClashing (currentNetPlan); 411// WDMUtils.checkConsistency(currentNetPlan , true,wdmLayer); 412 } else if (event.getEventObject () instanceof SimEvent.DemandRemove) 413 { 414 SimEvent.DemandRemove ev = (SimEvent.DemandRemove) event.getEventObject (); 415 Demand d = ev.demand; 416 for (Route lpToRemove : d.getRoutes()) 417 { 418 final Pair<RWA,RWA> originalRwa = wdmRouteOriginalRwa.get(lpToRemove); 419 if (originalRwa == null) return; // the ligtpath was already removed, because it was first accepted, but then blocked because of failures 420 if (isRestorationRecovery) // restoration => the current route is the one to release 421 removeRoute_restoration(lpToRemove , true); 422 else 423 removeRoute_protection(lpToRemove , originalRwa); 424 } 425 checkClashing (currentNetPlan); 426 d.remove(); 427 checkClashing (currentNetPlan); 428 } 429 else throw new Net2PlanException ("Unknown event type: " + event); 430 } 431 @Override 432 public String finish(StringBuilder output, double simTime) 433 { 434 final double trafficBlockingOnConnectionSetup = stat_trafficOfferedConnections == 0? 0 : 1 - (stat_trafficCarriedConnections / stat_trafficOfferedConnections ); 435 final double connectionBlockingOnConnectionSetup = stat_numOfferedConnections == 0? 0.0 : 1 - (((double) stat_numCarriedConnections) / ((double) stat_numOfferedConnections)); 436 final double successProbabilityRecovery = stat_numAttemptedToRecoverConnections == 0? 0.0 : (((double) stat_numSuccessfullyRecoveredConnections) / ((double) stat_numAttemptedToRecoverConnections)); 437 final double successProbabilityTrafficRecovery = stat_trafficAttemptedToRecoverConnections == 0? 0.0 : (((double) stat_trafficSuccessfullyRecoveredConnections) / ((double) stat_trafficAttemptedToRecoverConnections)); 438 final double dataTime = simTime - stat_transitoryInitTime; 439 if (dataTime <= 0) { output.append ("<p>No time for data acquisition</p>"); return ""; } 440 441 output.append (String.format("<p>Total traffic of offered connections: number connections %d, total time average traffic: %f</p>", stat_numOfferedConnections, stat_trafficOfferedConnections / dataTime)); 442 output.append (String.format("<p>Total traffic of carried connections: number connections %d, total time average traffic: %f</p>", stat_numCarriedConnections, stat_trafficCarriedConnections / dataTime)); 443 output.append (String.format("<p>Blocking at connection setup: Probability of blocking a connection: %f, Fraction of blocked traffic: %f</p>", connectionBlockingOnConnectionSetup , trafficBlockingOnConnectionSetup)); 444 output.append (String.format("<p>Number connections attempted to recover: %d (summing time average traffic: %f). </p>", stat_numAttemptedToRecoverConnections, stat_trafficAttemptedToRecoverConnections / dataTime)); 445 output.append (String.format("<p>Number connections successfully recovered: %d (summing time average traffic: %f). </p>", stat_numSuccessfullyRecoveredConnections, stat_trafficSuccessfullyRecoveredConnections / dataTime)); 446 output.append (String.format("<p>Probability of successfully recover a connection: %f. Proability weighted by the connection traffic: %f). </p>", successProbabilityRecovery, successProbabilityTrafficRecovery)); 447// output.append (String.format("<p>Total traffic carried at current state: %f. </p>", -1); 448 return ""; 449 } 450 451 @Override 452 public void finishTransitory(double simTime) 453 { 454 this.stat_trafficOfferedConnections = 0; 455 this.stat_trafficCarriedConnections = 0; 456 this.stat_trafficAttemptedToRecoverConnections = 0; 457 this.stat_trafficSuccessfullyRecoveredConnections = 0; 458 this.stat_numOfferedConnections = 0; 459 this.stat_numCarriedConnections = 0; 460 this.stat_numAttemptedToRecoverConnections = 0; 461 this.stat_numSuccessfullyRecoveredConnections = 0; 462 this.stat_transitoryInitTime = simTime; 463 } 464 465 /* down links or segments cannot be used */ 466 private RWA computeValidPathNewRoute (Demand cplDemand , NetPlan currentNetPlan) 467 { 468// System.out.println ("computeValidPathNewRoute, demand: " + demand + " occupied: " + occupiedLinkCapacity); 469 /* If load sharing */ 470 if (isLoadSharing) 471 { 472 final ArrayList<Route> paths = new ArrayList<Route> (cplDemand.getRoutes()); 473 final int randomChosenIndex = rng.nextInt(paths.size ()); 474 final Route cplRoute = paths.get(randomChosenIndex); 475 final List<Link> seqLinksThisNetPlan = cplToNetPlanLinks(cplRoute.getSeqLinksRealPath(), currentNetPlan); 476 final Triple<Boolean,Integer,Double> rwaEval = computeValidWAFirstFit_path (seqLinksThisNetPlan); 477 if (rwaEval.getFirst()) return new RWA (seqLinksThisNetPlan, rwaEval.getSecond()); else return null; 478 } 479 else if (isAlternateRouting || isLeastCongestedRouting) 480 { 481 /* If alternate or LCR */ 482 RWA lcrSoFar = null; double lcrIdleCapacitySoFar = -Double.MAX_VALUE; 483 for (Route cplRoute : cplDemand.getRoutes()) 484 { 485 final List<Link> seqLinks = cplToNetPlanLinks(cplRoute.getSeqLinksRealPath() , currentNetPlan); 486 final Triple<Boolean,Integer,Double> rwaEval = computeValidWAFirstFit_path (seqLinks); 487// System.out.println ("Route: " + cplRoute + ", links : " + seqLinks + ", eval: " + rwaEval); 488 if (!rwaEval.getFirst()) continue; 489 if (isAlternateRouting) return new RWA (seqLinks, rwaEval.getSecond()); 490 if (rwaEval.getThird() > lcrIdleCapacitySoFar) 491 { 492 lcrIdleCapacitySoFar = rwaEval.getThird(); 493 lcrSoFar = new RWA (seqLinks , rwaEval.getSecond()); 494 } 495 } 496 return (isAlternateRouting || (lcrSoFar == null))? (RWA) null : lcrSoFar; 497 } 498 else if (isSrgDisjointAwareLpRouting) 499 { 500 final Node thisNpIngressNode = currentNetPlan.getNodeFromId (cplDemand.getIngressNode().getId ()); 501 final Node thisNpEgressNode = currentNetPlan.getNodeFromId (cplDemand.getEgressNode().getId ()); 502 RWA chosenRWA = null; 503 Set<Route> existingRoutesBetweenPairOfNodes = currentNetPlan.getNodePairRoutes(thisNpIngressNode, thisNpEgressNode , false , wdmLayer); 504 int cplChosenRoute_numSRGOverlappingRoutes = Integer.MAX_VALUE; 505 for(Route cplCandidateRoute : cplDemand.getRoutes()) 506 { 507// if (forbiddenCplRoutes.contains (cplCandidateRoute)) continue; 508 /* Check that the route has an available wavlength */ 509 final List<Link> seqLinks = cplToNetPlanLinks(cplCandidateRoute.getSeqLinksRealPath() , currentNetPlan); 510 final Triple<Boolean,Integer,Double> rwaEval = computeValidWAFirstFit_path (seqLinks); 511 if (!rwaEval.getFirst()) continue; 512 /* compute the number of SRG-route pairs this route overlaps with, respect to the already existing lightpaths */ 513 final DoubleMatrix1D affectingSRGs = cplA_rs.viewRow (cplCandidateRoute.getIndex()); 514 int numOverlappingSRGs = 0; 515 for (Route currentRoute : existingRoutesBetweenPairOfNodes) 516 for (SharedRiskGroup srg : currentRoute.getSRGs()) if (affectingSRGs.get(srg.getIndex()) == 1) numOverlappingSRGs ++; 517 if (numOverlappingSRGs < cplChosenRoute_numSRGOverlappingRoutes) 518 { 519 cplChosenRoute_numSRGOverlappingRoutes = numOverlappingSRGs; 520 chosenRWA = new RWA (seqLinks , rwaEval.getSecond()); 521 if (numOverlappingSRGs == 0) break; // no need to search more 522 } 523 } 524 return chosenRWA; 525 } 526 throw new RuntimeException ("Bad"); 527 } 528 529 private Pair<RWA,RWA> computeValid11PathPairNewRoute (Demand cplDemand , NetPlan currentNetPlan) 530 { 531// final List<Pair<List<Link>,List<Link>>> pathPairs = cpl11.get(demand); 532 /* If load sharing */ 533 if (isLoadSharing) 534 { 535 final ArrayList<Route> primaryRoutes = new ArrayList<Route> (cplDemand.getRoutes()); 536 final int randomChosenIndex = rng.nextInt(primaryRoutes.size()); 537 final Route cplRoute = primaryRoutes.get(randomChosenIndex); 538 final ProtectionSegment cplSegment = cplRoute.getPotentialBackupProtectionSegments().iterator().next(); 539 final List<Link> seqLinksPrimaryThisNetPlan = cplToNetPlanLinks(cplRoute.getSeqLinksRealPath(), currentNetPlan); 540 final List<Link> seqLinksBackupThisNetPlan = cplToNetPlanLinks(cplSegment.getSeqLinks(), currentNetPlan); 541 final Quadruple<Boolean,Integer,Integer,Double> rwaEval = computeValidWAFirstFit_pathPair (seqLinksPrimaryThisNetPlan , seqLinksBackupThisNetPlan); 542 if (rwaEval.getFirst()) 543 return Pair.of(new RWA (seqLinksPrimaryThisNetPlan, rwaEval.getSecond()) , new RWA (seqLinksBackupThisNetPlan, rwaEval.getThird())); 544 else 545 return null; 546 } 547 else if (isAlternateRouting || isLeastCongestedRouting) 548 { 549 Pair<RWA,RWA> lcrSoFar = null; double lcrIdleCapacitySoFar= -Double.MAX_VALUE; 550 for (Route cplRoute : cplDemand.getRoutes()) 551 { 552 if (cplRoute.getPotentialBackupProtectionSegments().isEmpty()) throw new RuntimeException ("Bad"); 553 final ProtectionSegment cplSegment = cplRoute.getPotentialBackupProtectionSegments().iterator().next(); 554 final List<Link> seqLinksPrimaryThisNetPlan = cplToNetPlanLinks(cplRoute.getSeqLinksRealPath(), currentNetPlan); 555 final List<Link> seqLinksBackupThisNetPlan = cplToNetPlanLinks(cplSegment.getSeqLinks(), currentNetPlan); 556 final Quadruple<Boolean,Integer,Integer,Double> rwaEval = computeValidWAFirstFit_pathPair (seqLinksPrimaryThisNetPlan , seqLinksBackupThisNetPlan); 557// System.out.println ("Route: " + cplRoute + ", links primary: " + seqLinksPrimaryThisNetPlan + ", backup: " + seqLinksBackupThisNetPlan + ", eval: " + rwaEval); 558 if (!rwaEval.getFirst()) continue; 559 if (isAlternateRouting) return Pair.of(new RWA (seqLinksPrimaryThisNetPlan, rwaEval.getSecond()) , new RWA (seqLinksBackupThisNetPlan, rwaEval.getThird())); 560 if (rwaEval.getFourth() > lcrIdleCapacitySoFar) 561 { 562 lcrIdleCapacitySoFar = rwaEval.getFourth(); 563 lcrSoFar = Pair.of(new RWA (seqLinksPrimaryThisNetPlan , rwaEval.getSecond()) , new RWA (seqLinksBackupThisNetPlan , rwaEval.getThird())); 564 } 565 } 566 return lcrSoFar; //if alternate, this is null also 567 } else if (isSrgDisjointAwareLpRouting) 568 { 569 final Node thisNpIngressNode = currentNetPlan.getNodeFromId (cplDemand.getIngressNode().getId ()); 570 final Node thisNpEgressNode = currentNetPlan.getNodeFromId (cplDemand.getEgressNode().getId ()); 571 Pair<RWA,RWA> chosenRWA = null; 572 Set<Route> existingRoutesBetweenPairOfNodes = currentNetPlan.getNodePairRoutes(thisNpIngressNode, thisNpEgressNode , false , wdmLayer); 573 int cplChosenRoute_numSRGOverlappingRoutes = Integer.MAX_VALUE; 574 for(Route cplCandidateRoute : cplDemand.getRoutes()) 575 { 576 if (cplCandidateRoute.getPotentialBackupProtectionSegments().isEmpty()) throw new RuntimeException ("Bad"); 577 final ProtectionSegment cplSegment = cplCandidateRoute.getPotentialBackupProtectionSegments().iterator().next(); 578 final List<Link> seqLinksPrimaryThisNetPlan = cplToNetPlanLinks(cplCandidateRoute.getSeqLinksRealPath(), currentNetPlan); 579 final List<Link> seqLinksBackupThisNetPlan = cplToNetPlanLinks(cplSegment.getSeqLinks(), currentNetPlan); 580 final Quadruple<Boolean,Integer,Integer,Double> rwaEval = computeValidWAFirstFit_pathPair (seqLinksPrimaryThisNetPlan , seqLinksBackupThisNetPlan); 581// System.out.println ("Route: " + cplCandidateRoute + ", links primary: " + seqLinksPrimaryThisNetPlan + ", backup: " + seqLinksBackupThisNetPlan + ", eval: " + rwaEval); 582 if (!rwaEval.getFirst()) continue; 583 /* compute the number of SRG-route pairs this route overlaps with, respect to the already existing lightpaths */ 584 final DoubleMatrix1D affectingSRGs_primary = cplA_rs.viewRow (cplCandidateRoute.getIndex()); 585 final DoubleMatrix1D affectingSRGs_backup = cplA_pss.viewRow (cplSegment.getIndex()); 586 int numOverlappingSRGs = 0; 587 for (Route currentRoute : existingRoutesBetweenPairOfNodes) 588 { 589 for (SharedRiskGroup srg : currentRoute.getSRGs()) if (affectingSRGs_primary.get(srg.getIndex()) == 1) numOverlappingSRGs ++; 590 final ProtectionSegment currentSegment = currentRoute.getPotentialBackupProtectionSegments().iterator().next(); 591 for (SharedRiskGroup srg : currentSegment.getSRGs()) if (affectingSRGs_backup.get(srg.getIndex()) == 1) numOverlappingSRGs ++; 592 } 593 if (numOverlappingSRGs < cplChosenRoute_numSRGOverlappingRoutes) 594 { 595 cplChosenRoute_numSRGOverlappingRoutes = numOverlappingSRGs; 596 chosenRWA = Pair.of (new RWA (seqLinksPrimaryThisNetPlan , rwaEval.getSecond()) , new RWA (seqLinksBackupThisNetPlan , rwaEval.getThird())); 597 if (numOverlappingSRGs == 0) break; // no need to search more 598 } 599 } 600 return chosenRWA; 601 } 602 throw new RuntimeException ("Bad"); 603 } 604 605 /* down links or segments cannot be used */ 606 private RWA computeValidReroute_protection (Route routeToReroute) 607 { 608 final NetPlan np = routeToReroute.getNetPlan(); 609 final Pair<RWA,RWA> originalRWA = wdmRouteOriginalRwa.get(routeToReroute); 610 final boolean primaryUp = np.isUp (originalRWA.getFirst().path); 611 final boolean backupUp = originalRWA.getSecond() == null? false : np.isUp (originalRWA.getSecond().path); 612 if (primaryUp) 613 { 614 if (originalRWA.getFirst ().path.contains(null)) throw new RuntimeException ("Bad"); 615 return originalRWA.getFirst (); 616 } 617 else if (backupUp) 618 { 619 List<Link> res = new LinkedList<Link> (); res.add (routeToReroute.getPotentialBackupProtectionSegments().iterator().next()); 620 if (routeToReroute.getPotentialBackupProtectionSegments().iterator().next() == null) throw new RuntimeException ("Bad"); 621 if (res.contains(null)) throw new RuntimeException ("Bad"); 622 return new RWA (res , originalRWA.getSecond().w); 623 } 624 else return null; 625 } 626 627 628 private List<Link> cplToNetPlanLinks(List<Link> cplLinkList, NetPlan netPlan) 629 { 630 List<Link> list = new LinkedList<>(); 631 for(Link cplLink : cplLinkList) list.add(netPlan.getLinkFromId (cplLink.getId ())); 632 return list; 633 } 634 635 private Triple<Boolean,Integer,Double> computeValidWAFirstFit_path (List<Link> seqLinks) 636 { 637 if (seqLinks.isEmpty()) throw new RuntimeException ("Bad"); 638 if (seqLinks.get(0).getOriginNode().isDown()) return Triple.of(false,-1,-1.0); 639 double worseCaseSpareCapacity = Double.MAX_VALUE; 640 for (Link e : seqLinks) 641 { 642 worseCaseSpareCapacity = Math.min(worseCaseSpareCapacity, e.getCapacity() - e.getOccupiedCapacityIncludingProtectionSegments()); 643 if (e.getDestinationNode().isDown() || e.isDown()) return Triple.of(false,-1,-1.0); 644 } 645 int [] seqWavelengths = WDMUtils.WA_firstFit(seqLinks, wavelengthFiberOccupancy); 646 if (seqWavelengths.length != 0) 647 return Triple.of(true , seqWavelengths [0] , worseCaseSpareCapacity); 648 else return Triple.of(false,-1,-1.0); 649 } 650 651 private Quadruple<Boolean,Integer,Integer,Double> computeValidWAFirstFit_pathPair (List<Link> seqLinks_1 , List<Link> seqLinks_2) 652 { 653 if (seqLinks_1.isEmpty() || seqLinks_2.isEmpty()) throw new RuntimeException ("Bad"); 654 if (seqLinks_1.get(0).getOriginNode().isDown()) return Quadruple.of(false,-1,-1,-1.0); 655 if (seqLinks_2.get(0).getOriginNode().isDown()) return Quadruple.of(false,-1,-1,-1.0); 656 double worseCaseSpareCapacity = Double.MAX_VALUE; 657 for (Link e : seqLinks_1) 658 { 659 worseCaseSpareCapacity = Math.min(worseCaseSpareCapacity, e.getCapacity() - e.getOccupiedCapacityIncludingProtectionSegments()); 660 if (e.getDestinationNode().isDown() || e.isDown()) return Quadruple.of(false,-1,-1,-1.0); 661 } 662 for (Link e : seqLinks_2) 663 { 664 worseCaseSpareCapacity = Math.min(worseCaseSpareCapacity, e.getCapacity() - e.getOccupiedCapacityIncludingProtectionSegments()); 665 if (e.getDestinationNode().isDown() || e.isDown()) return Quadruple.of(false,-1,-1,-1.0); 666 } 667 Pair<int [],int[]> seqWavelengths = WDMUtils.WA_firstFitTwoRoutes(seqLinks_1, seqLinks_2, wavelengthFiberOccupancy); 668 if (seqWavelengths != null) 669 return Quadruple.of(true , seqWavelengths.getFirst () [0] , seqWavelengths.getSecond() [0] , worseCaseSpareCapacity); 670 else return Quadruple.of(false,-1,-1,-1.0); 671 } 672 673 private class RWA 674 { 675 public final List<Link> path; public final int w; 676 public RWA (List<Link> path , int w) {this.path = new LinkedList<Link> (path); this.w = w; } 677 public String toString () { return "Links: " + path + ", w: " + w; } 678 } 679 680 private void removeRoute_restoration (Route lpToRemove , boolean releaseWDMResources) 681 { 682 if (releaseWDMResources) WDMUtils.releaseResources(lpToRemove.getSeqLinksRealPath() , WDMUtils.getLightpathSeqWavelengths(lpToRemove) , wavelengthFiberOccupancy, null , null); 683 lpToRemove.remove (); 684 this.wdmRouteOriginalRwa.remove(lpToRemove); 685 } 686 private void removeRoute_protection (Route lpToRemove , Pair<RWA,RWA> originalRwa) 687 { 688 /* Release WDM resources */ 689 WDMUtils.releaseResources(originalRwa.getFirst ().path , IntFactory1D.dense.make (E_wdm , originalRwa.getFirst().w).toArray() , wavelengthFiberOccupancy, null , null); 690 if (originalRwa.getSecond() != null) 691 WDMUtils.releaseResources(originalRwa.getSecond ().path , IntFactory1D.dense.make (E_wdm , originalRwa.getSecond ().w).toArray() , wavelengthFiberOccupancy, null , null); 692 /* Release NetPlan resources */ 693 lpToRemove.remove (); for (ProtectionSegment s : lpToRemove.getPotentialBackupProtectionSegments()) s.remove (); 694 this.wdmRouteOriginalRwa.remove(lpToRemove); 695 } 696 697 private void checkClashing (NetPlan np) 698 { 699 DoubleMatrix2D mat = DoubleFactory2D.dense.make (wavelengthFiberOccupancy.rows () , E_wdm); 700 for (Route r : np.getRoutes(wdmLayer)) 701 { 702 703 704 if (newRoutesHave11Protection) 705 { 706 Pair<RWA,RWA> origRouting = wdmRouteOriginalRwa.get(r); 707// System.out.println ("Route " + r + ", origRouting: " + origRouting); 708 for (Link e : origRouting.getFirst().path) { if (mat.get (origRouting.getFirst().w , e.getIndex()) != 0) throw new RuntimeException ("Bad"); mat.set (origRouting.getFirst().w , e.getIndex() , 1); } 709 if (origRouting.getSecond() != null) 710 { 711 if (!r.getSeqLinksRealPath().equals (origRouting.getFirst().path) && !r.getPotentialBackupProtectionSegments().iterator().next().getSeqLinks().equals (origRouting.getSecond().path)) throw new RuntimeException ("Bad"); 712 for (Link e : origRouting.getSecond().path) { if (mat.get (origRouting.getSecond().w , e.getIndex()) != 0) throw new RuntimeException ("Bad"); mat.set (origRouting.getSecond().w , e.getIndex() , 1); } 713 } 714 else if (!r.getSeqLinksRealPath().equals (origRouting.getFirst().path)) throw new RuntimeException ("Bad"); 715 716 } 717 else 718 { 719 final int [] wavelengths = WDMUtils.getLightpathSeqWavelengths(r); 720 int counter = 0; 721 for (Link e : r.getSeqLinksRealPath()) 722 { 723 final int w = wavelengths [counter ++]; 724 if (mat.get (w , e.getIndex()) != 0) throw new RuntimeException ("Bad"); mat.set (w , e.getIndex() , 1); 725 } 726 } 727 } 728 if (!mat.equals (wavelengthFiberOccupancy)) 729 { 730 System.out.println ("mat: " + mat); 731 System.out.println ("wavelengthFiberOccupancy: " + wavelengthFiberOccupancy); 732 System.out.println ("1 minus 2: " + mat.copy ().assign(wavelengthFiberOccupancy , DoubleFunctions.minus)); 733 throw new RuntimeException ("Bad"); 734 } 735 736 } 737 738 private void checkDisjointness (List<Link> p1 , List<Link> p2 , int disjointnessType) 739 { 740 if ((p1 == null) || (p2 == null)) throw new RuntimeException ("Bad"); 741 if (disjointnessType == 0) // SRG disjoint 742 { 743 Set<SharedRiskGroup> srg1 = new HashSet<SharedRiskGroup> (); for (Link e : p1) srg1.addAll (e.getSRGs()); 744 for (Link e : p2) for (SharedRiskGroup srg : e.getSRGs()) if (srg1.contains(srg)) throw new RuntimeException ("Bad"); 745 } 746 else if (disjointnessType == 1) // link and node 747 { 748 Set<NetworkElement> resourcesP1 = new HashSet<NetworkElement> (); boolean firstLink = true; 749 for (Link e : p1) { resourcesP1.add (e); if (firstLink) firstLink = false; else resourcesP1.add (e.getOriginNode()); } 750 for (Link e : p2) if (resourcesP1.contains(e)) throw new RuntimeException ("Bad"); 751 } 752 else if (disjointnessType == 2) // link 753 { 754 Set<Link> linksP1 = new HashSet<Link> (p1); 755 for (Link e : p2) if (linksP1.contains (e)) throw new RuntimeException ("Bad: p1: " + p1 + ", p2: " + p2); 756 } 757 else throw new RuntimeException ("Bad"); 758 759 } 760}