Offline_ipOverWdm_routingSpectrumAndModulationAssignmentILPNotGrooming implements IAlgorithm { @Override public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters) { InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters); if (netPlan.getNumberOfLayers() == 1) { this.wdmLayer = netPlan.getNetworkLayerDefault(); netPlan.setDemandTrafficUnitsName("Gbps"); netPlan.setLinkCapacityUnitsName("Frequency slots"); this.ipLayer = netPlan.addLayer("IP" , "IP layer" , "Gbps" , "Gbps" , null , null); for (Demand wdmDemand : netPlan.getDemands(wdmLayer)) netPlan.addDemand(wdmDemand.getIngressNode(), wdmDemand.getEgressNode() , wdmDemand.getOfferedTraffic() , RoutingType.SOURCE_ROUTING , wdmDemand.getAttributes() , ipLayer); } else { this.wdmLayer = wdmLayerIndex.getInt () == -1? netPlan.getNetworkLayerDefault() : netPlan.getNetworkLayer(wdmLayerIndex.getInt ()); this.ipLayer = ipLayerIndex.getInt () == -1? netPlan.getNetworkLayerDefault() : netPlan.getNetworkLayer(ipLayerIndex.getInt ()); } final NetworkLayer wdmLayer = wdmLayerIndex.getInt () == -1? netPlan.getNetworkLayerDefault() : netPlan.getNetworkLayer(wdmLayerIndex.getInt ()); final int N = netPlan.getNumberOfNodes(); final int Ewdm = netPlan.getNumberOfLinks(wdmLayer); final int Dip = netPlan.getNumberOfDemands(ipLayer); final int S = numFrequencySlotsPerFiber.getInt(); if (N == 0 || Ewdm == 0 || Dip == 0) throw new Net2PlanException("This algorithm requires a topology with links and a demand set"); if (networkRecoveryType.getString().equals("not-fault-tolerant") || networkRecoveryType.getString().equals("single-srg-tolerant-static-lp")) recoveryTypeNewLps = Demand.IntendedRecoveryType.NONE; else if (networkRecoveryType.getString().equals("1+1-srg-disjoint-lps")) recoveryTypeNewLps = Demand.IntendedRecoveryType.PROTECTION_REVERT; else throw new Net2PlanException ("Wrong input parameters"); WDMUtils.TransponderTypesInfo tpInfo = new WDMUtils.TransponderTypesInfo(transponderTypesInfo.getString()); final int T = tpInfo.getNumTypes(); netPlan.removeAllLinks (ipLayer); netPlan.removeAllDemands (wdmLayer); netPlan.removeAllMulticastDemands(wdmLayer); final SortedMap<Pair<Node,Node>,List<List<Link>>> cpl = netPlan.computeUnicastCandidatePathList(netPlan.getVectorLinkLengthInKm(wdmLayer) , k.getInt(), tpInfo.getMaxOpticalReachKm() , -1, maxPropagationDelayMs.getDouble(), -1, -1, -1 , null , wdmLayer); final SortedMap<Pair<Node,Node>,List<Pair<List<Link>,List<Link>>>> cpl11 = networkRecoveryType.getString().equals("1+1-srg-disjoint-lps")? NetPlan.computeUnicastCandidate11PathList(cpl,0) : null; Map<Link,Double> linkLengthMap = new HashMap<Link,Double> (); for (Link e : netPlan.getLinks(wdmLayer)) linkLengthMap.put(e , e.getLengthInKm()); final int maximumNumberOfPaths = T*k.getInt()*Dip; List<Integer> transponderType_p = new ArrayList<Integer> (maximumNumberOfPaths); List<Double> cost_p = new ArrayList<Double> (maximumNumberOfPaths); List<Double> lineRate_p = new ArrayList<Double> (maximumNumberOfPaths); List<Integer> numSlots_p = new ArrayList<Integer> (maximumNumberOfPaths); List<List<Link>> seqLinks_p = new ArrayList<List<Link>> (maximumNumberOfPaths); List<List<Link>> seqLinks2_p = cpl11 == null? null : new ArrayList<List<Link>> (maximumNumberOfPaths); List<int []> regPositions_p = new ArrayList<int []> (maximumNumberOfPaths); List<int []> regPositions2_p = new ArrayList<int []> (maximumNumberOfPaths); List<Demand> ipDemand_p = new ArrayList<Demand> (maximumNumberOfPaths); for (Demand ipDemand : netPlan.getDemands(ipLayer)) { ipDemand.setRoutingType(RoutingType.SOURCE_ROUTING); boolean atLeastOnePathOrPathPair = false; for (int t = 0 ; t < T ; t ++) { final Pair<Node,Node> nodePair = Pair.of(ipDemand.getIngressNode() , ipDemand.getEgressNode()); final double regeneratorCost = tpInfo.getRegeneratorCost(t); final boolean isRegenerable = regeneratorCost >= 0; for (Object sp : cpl11 != null? cpl11.get(nodePair) : cpl.get(nodePair)) { List<Link> firstPath = (cpl11 == null)? ((List<Link>) sp) : ((Pair<List<Link>,List<Link>>) sp).getFirst(); List<Link> secondPath = (cpl11 == null)? null : ((Pair<List<Link>,List<Link>>) sp).getSecond (); if (!isRegenerable && (getLengthInKm(firstPath) > tpInfo.getOpticalReachKm(t))) break; if (secondPath != null) if (!isRegenerable && (getLengthInKm(secondPath) > tpInfo.getOpticalReachKm(t))) break; final int [] regPositions1 = isRegenerable? WDMUtils.computeRegeneratorPositions(firstPath , tpInfo.getOpticalReachKm(t)) : new int [firstPath.size()]; final int [] regPositions2 = cpl11 == null? null : isRegenerable? WDMUtils.computeRegeneratorPositions(secondPath , tpInfo.getOpticalReachKm(t)) : new int [secondPath.size()]; final int numRegeneratorsNeeded = !isRegenerable? 0 : (int) IntUtils.sum(regPositions1) + (secondPath == null? 0 : (int) IntUtils.sum(regPositions2)) ; final double costOfLightpathOr11Pair = tpInfo.getCost(t) * (cpl11 != null? 2 : 1) + (tpInfo.getRegeneratorCost(t) * numRegeneratorsNeeded); cost_p.add (costOfLightpathOr11Pair); transponderType_p.add (t); lineRate_p.add(tpInfo.getLineRateGbps(t)); numSlots_p.add(tpInfo.getNumSlots(t)); ipDemand_p.add(ipDemand); seqLinks_p.add(firstPath); regPositions_p.add(regPositions1); if (cpl11 != null) { seqLinks2_p.add(secondPath); regPositions2_p.add(regPositions2); } atLeastOnePathOrPathPair = true; } } if (!atLeastOnePathOrPathPair) throw new Net2PlanException ("There are no possible routes (or 1+1 pairs) for a demand (" + ipDemand + "). The topology may be not connected enough, or the optical reach may be too small"); } final int P = transponderType_p.size(); DoubleMatrix2D A_dp = DoubleFactory2D.sparse.make(Dip,P); DoubleMatrix2D A_ep = DoubleFactory2D.sparse.make(Ewdm,P); DoubleMatrix2D A2_ep = DoubleFactory2D.sparse.make(Ewdm,P); DoubleMatrix2D A_psrg = DoubleFactory2D.sparse.make(P,netPlan.getNumberOfSRGs()); double [][] feasibleAssignment_ps = new double [P][S]; DoubleMatrix2D [] A_n1Mn2p = new DoubleMatrix2D [T]; if (bidirectionalTransponders.getBoolean()) for (int t = 0 ; t < T ; t ++) A_n1Mn2p [t] = DoubleFactory2D.sparse.make(N*N , P); for (int p = 0 ; p < P ; p ++) { A_dp.set(ipDemand_p.get(p).getIndex() , p , 1.0); for (Link e : seqLinks_p.get(p)) A_ep.set (e.getIndex() , p , 1.0); if (cpl11 != null) for (Link e : seqLinks2_p.get(p)) A2_ep.set (e.getIndex() , p , 1.0); if (networkRecoveryType.getString().equals("single-srg-tolerant-static-lp")) for (Link e : seqLinks_p.get(p)) { for (SharedRiskGroup srg : e.getSRGs()) A_psrg.set(p,srg.getIndex(),1.0); for (SharedRiskGroup srg : e.getOriginNode().getSRGs()) A_psrg.set(p,srg.getIndex(),1.0); for (SharedRiskGroup srg : e.getDestinationNode().getSRGs()) A_psrg.set(p,srg.getIndex(),1.0); } for (int s = 0; s < S + 1 - numSlots_p.get(p) ; s ++) feasibleAssignment_ps [p][s] = 1; if (bidirectionalTransponders.getBoolean()) { final int t = transponderType_p.get(p); final int n1 = ipDemand_p.get(p).getIngressNode().getIndex(); final int n2 = ipDemand_p.get(p).getEgressNode().getIndex(); final int nLower = n1 < n2? n1 : n2; final int nGreater = n1 > n2? n1 : n2; A_n1Mn2p [t].set(nLower + N * nGreater , p , nLower == n1? 1.0 : -1.0); } } OptimizationProblem op = new OptimizationProblem(); op.addDecisionVariable("x_ps", true, new int[] {P, S}, new DoubleMatrixND (new int [] {P,S}) , new DoubleMatrixND (feasibleAssignment_ps)); if (cpl11 != null) op.addDecisionVariable("x2_ps", true, new int[] {P, S}, new DoubleMatrixND (new int [] {P,S}) , new DoubleMatrixND (feasibleAssignment_ps)); op.setInputParameter("S", S); op.setInputParameter("h_d", netPlan.getVectorDemandOfferedTraffic(ipLayer), "row"); op.setInputParameter("rate_p", lineRate_p , "row"); op.setInputParameter("c_p", cost_p , "row"); op.setInputParameter("A_dp", A_dp); op.setInputParameter("A_ep", A_ep); if (cpl11 != null) op.setInputParameter("A2_ep", A2_ep); if (optimizationTarget.getString().equals("min-cost")) op.setObjectiveFunction("minimize", "sum(c_p * x_ps)"); else if (optimizationTarget.getString().equals("maximin-fiber-number-idle-slots")) { op.addDecisionVariable("u", true, new int[] {1, 1} , 0 , S); op.setObjectiveFunction("maximize", "u"); op.setInputParameter("numSlots_p", numSlots_p , "row"); if (cpl11 == null) op.addConstraint("sum(A_ep * diag(numSlots_p) * x_ps , 2) <= S - u"); else op.addConstraint("sum(A_ep * diag(numSlots_p) * x_ps + A2_ep * diag(numSlots_p) * x2_ps , 2) <= S - u"); } op.addConstraint("A_dp * diag (rate_p) * x_ps * ones([S; 1]) >= h_d'"); if (cpl11 != null) op.addConstraint("sum(x_ps,2) == sum(x2_ps,2)"); if (networkRecoveryType.getString().equals("single-srg-tolerant-static-lp")) { for (int srg = 0 ; srg < A_psrg.columns() ; srg ++) { DoubleMatrix2D Asrg_pp = DoubleFactory2D.sparse.make(P,P); for (int p = 0; p < P ; p ++) Asrg_pp.set(p,p,1 - A_psrg.get(p , srg)); op.setInputParameter("Asrg_pp" , Asrg_pp); op.addConstraint("A_dp * Asrg_pp * diag (rate_p) * x_ps * ones([S; 1]) >= h_d'"); } } String constraintString = ""; for (int t = 0; t < T ; t ++) { { final String name_At_pp = "A" + Integer.toString(t) + "_pp"; final String name_At_s1s2 = "A" + Integer.toString(t) + "_s1s2"; DoubleMatrix2D At_pp = DoubleFactory2D.sparse.make(P,P); int p = 0; for (int type : transponderType_p) { if (type == t) At_pp.set(p,p,1.0); p++; } DoubleMatrix2D At_s1s2 = DoubleFactory2D.sparse.make(S,S); for (int s1 = 0 ; s1 < S ; s1 ++) for (int cont = 0 ; cont < tpInfo.getNumSlots(t) ; cont ++) if (s1 - cont >= 0) At_s1s2.set(s1-cont,s1,1.0); op.setInputParameter(name_At_pp, At_pp); op.setInputParameter(name_At_s1s2, At_s1s2); constraintString += (t == 0? "" : " + ") + "( A_ep * " + name_At_pp + " * x_ps * " + name_At_s1s2 + " ) "; } if (cpl11 != null) { final String name_A2t_pp = "A2" + Integer.toString(t) + "_pp"; final String name_A2t_s1s2 = "A2" + Integer.toString(t) + "_s1s2"; DoubleMatrix2D A2t_pp = DoubleFactory2D.sparse.make(P,P); int p = 0; for (int type : transponderType_p) { if (type == t) A2t_pp.set(p,p,1.0); p++; } DoubleMatrix2D A2t_s1s2 = DoubleFactory2D.sparse.make(S,S); for (int s1 = 0 ; s1 < S ; s1 ++) for (int cont = 0 ; cont < tpInfo.getNumSlots(t) ; cont ++) if (s1 - cont >= 0) A2t_s1s2.set(s1-cont,s1,1.0); op.setInputParameter(name_A2t_pp, A2t_pp); op.setInputParameter(name_A2t_s1s2, A2t_s1s2); constraintString += " + ( A2_ep * " + name_A2t_pp + " * x2_ps * " + name_A2t_s1s2 + " ) "; } } op.addConstraint(constraintString + " <= 1"); if (bidirectionalTransponders.getBoolean()) { for (int t = 0 ; t < T ; t ++) { op.setInputParameter("At_n1Mn2p" , A_n1Mn2p [t]); if (cpl11 != null) op.addConstraint("sum (At_n1Mn2p * (x_ps + x2_ps) , 2) == 0"); else op.addConstraint("sum (At_n1Mn2p * x_ps , 2) == 0"); } } op.solve(solverName.getString(), "solverLibraryName", solverLibraryName.getString() , "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble()); if (!op.solutionIsFeasible()) throw new Net2PlanException("A feasible solution was not found"); DoubleMatrix2D x_ps = op.getPrimalSolution("x_ps").view2D(); DoubleMatrix2D x2_ps = cpl11 == null? null : op.getPrimalSolution("x2_ps").view2D(); WDMUtils.setFibersNumFrequencySlots(netPlan , numFrequencySlotsPerFiber.getInt() , wdmLayer); IntArrayList slots = new IntArrayList (); DoubleArrayList vals = new DoubleArrayList (); IntArrayList slots2 = new IntArrayList (); DoubleArrayList vals2 = new DoubleArrayList (); for (int p = 0; p < P ; p ++) { slots.clear(); vals.clear(); x_ps.viewRow(p).getNonZeros(slots , vals); if (cpl11 != null) { slots2.clear(); vals.clear(); x2_ps.viewRow(p).getNonZeros(slots2 , vals2); if (slots.size() != slots2.size()) throw new RuntimeException ("Bad"); } if (slots.size() == 0) continue; final Demand ipDemand = ipDemand_p.get(p); for (int cont = 0 ; cont < slots.size() ; cont ++) { final int s = slots.get (cont); final Demand newWDMDemand = netPlan.addDemand(ipDemand.getIngressNode() , ipDemand.getEgressNode() , lineRate_p.get(p) , RoutingType.SOURCE_ROUTING , null , wdmLayer); final Route r = WDMUtils.addLightpath(newWDMDemand , new WDMUtils.RSA(seqLinks_p.get(p) , s , numSlots_p.get(p) , regPositions_p.get(p)) , lineRate_p.get(p)); final Link ipLink = newWDMDemand.coupleToNewLinkCreated(ipLayer); final double ipTrafficToCarry = Math.min(lineRate_p.get(p) , ipDemand.getBlockedTraffic()); netPlan.addRoute(ipDemand , ipTrafficToCarry , ipTrafficToCarry , Arrays.asList(ipLink), null); if (cpl11 != null) { final int s2 = slots2.get(cont); final Route backupRoute = WDMUtils.addLightpath(newWDMDemand , new WDMUtils.RSA(seqLinks2_p.get(p) , s2 , numSlots_p.get(p) , regPositions2_p.get(p)) , 0); r.addBackupRoute(backupRoute); } } } WDMUtils.checkResourceAllocationClashing(netPlan,true,true,wdmLayer); return "Ok!"; }  @Override String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters); @Override String getDescription(); @Override List<Triple<String, String, String>> getParameters();  }
@Test public void testExecuteAlgorithm() { Map<String,List<String>> testingParameters = new HashMap<> (); testingParameters.put("solverName" , Arrays.asList("cplex")); testingParameters.put("solverLibraryName" , Arrays.asList("cplex.dll")); testingParameters.put("maxSolverTimeInSeconds" , Arrays.asList("10")); testingParameters.put("k" , Arrays.asList("5")); testingParameters.put("numFrequencySlotsPerFiber" , Arrays.asList("30")); testingParameters.put("transponderTypesInfo" , Arrays.asList("2000.0 1.0 1 9600.0 1.0 ; 4000.0 1.5 2 5000.0 1.5")); testingParameters.put("wdmLayerIndex" , Arrays.asList("0")); testingParameters.put("ipLayerIndex" , Arrays.asList("1")); testingParameters.put("networkRecoveryType" , Arrays.asList("not-fault-tolerant", "single-srg-tolerant-static-lp" , "1+1-srg-disjoint-lps")); testingParameters.put("optimizationTarget" , Arrays.asList("min-cost" , "maximin-fiber-number-idle-slots")); testingParameters.put("bidirectionalTransponders" , Arrays.asList("true" , "false")); testingParameters.put("maxPropagationDelayMs" , Arrays.asList("-1")); List<Map<String,String>> testsParam = InputParameter.getCartesianProductOfParameters (testingParameters); for (Map<String,String> params : testsParam) { final NetPlan npInput = np.copy (); try { new Offline_ipOverWdm_routingSpectrumAndModulationAssignmentILPNotGrooming ().executeAlgorithm(np , params , null); } catch (UnsatisfiedLinkError e) { System.err.println(this.getClass().getName() + ": Cplex not found"); return; } checkValidity (npInput , np , params); } }