001/******************************************************************************* 002 * Copyright (c) 2017 Pablo Pavon Marino and others. 003 * All rights reserved. This program and the accompanying materials 004 * are made available under the terms of the 2-clause BSD License 005 * which accompanies this distribution, and is available at 006 * https://opensource.org/licenses/BSD-2-Clause 007 * 008 * Contributors: 009 * Pablo Pavon Marino and others - initial API and implementation 010 *******************************************************************************/ 011 012 013 014 015 016 017 018 019 020 021package com.net2plan.examples.ocnbook.offline; 022 023import cern.colt.matrix.tdouble.DoubleFactory1D; 024import cern.colt.matrix.tdouble.DoubleFactory2D; 025import cern.colt.matrix.tdouble.DoubleMatrix1D; 026import cern.colt.matrix.tdouble.DoubleMatrix2D; 027import cern.jet.math.tdouble.DoubleFunctions; 028import com.jom.OptimizationProblem; 029import com.net2plan.interfaces.networkDesign.*; 030import com.net2plan.utils.Constants.RoutingType; 031import com.net2plan.utils.InputParameter; 032import com.net2plan.utils.Triple; 033 034import java.util.List; 035import java.util.Map; 036 037/** 038 * Solves a general multilayer optimization problem formulation. 039 * @net2plan.description 040 * @net2plan.keywords Multilayer, Flow assignment (FA), Flow-link formulation, Destination-link formulation, Modular capacities 041 * @net2plan.ocnbooksections Section 7.4 042 * @net2plan.inputParameters 043 * @author Pablo Pavon-Marino 044 */ 045public class Offline_tcfa_generalMultilayer implements IAlgorithm 046{ 047 private InputParameter solverName = new InputParameter ("solverName", "#select# glpk ipopt xpress cplex", "The solver name to be used by JOM. GLPK and IPOPT are free, XPRESS and CPLEX commercial. GLPK, XPRESS and CPLEX solve linear problems w/w.o integer contraints. IPOPT is can solve nonlinear problems (if convex, returns global optimum), but cannot handle integer constraints"); 048 private InputParameter solverLibraryName = new InputParameter ("solverLibraryName", "", "The solver library full or relative path, to be used by JOM. Leave blank to use JOM default."); 049 private InputParameter maxSolverTimeInSeconds = new InputParameter ("maxSolverTimeInSeconds", (double) -1 , "Maximum time granted to the solver to solve the problem. If this time expires, the solver returns the best solution found so far (if a feasible solution is found)"); 050 private InputParameter ciurcuitCapacityGbps = new InputParameter ("ciurcuitCapacityGbps", (double) 1.0 , "Capacity of a circuit in Gbps, the assumed units for upper layer traffic" , 0 , false , Double.MAX_VALUE , true); 051 private InputParameter capLowLayerLinksInNumCircuits = new InputParameter ("capLowLayerLinksInNumCircuits", (int) 100 , "The capacity of a lower layer link, measured as the maximum number of circuits that can traverse it." , 1 , Integer.MAX_VALUE); 052 053 private NetworkLayer lowerLayer, upperLayer; 054 055 @Override 056 public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters) 057 { 058 /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */ 059 InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters); 060 if (netPlan.getNumberOfLayers() > 2) throw new Net2PlanException ("The design must have one or two layers"); 061 062 /* Set a two layer network topology, maybe starting from a single layer design */ 063 if (netPlan.isSingleLayer()) 064 { 065 this.lowerLayer = netPlan.getNetworkLayerDefault(); 066 this.upperLayer = netPlan.addLayer("UP LAYER" , "Upper layer of the design" , "Gbps" , "Gbps" , null , null); 067 /* Save the demands in the upper layer, and remove them from the lower layer */ 068 for (Demand d : netPlan.getDemands (lowerLayer)) netPlan.addDemand(d.getIngressNode() , d.getEgressNode() , d.getOfferedTraffic() , RoutingType.HOP_BY_HOP_ROUTING , null , upperLayer); 069 } 070 else 071 { 072 this.lowerLayer = netPlan.getNetworkLayer(0); 073 this.upperLayer = netPlan.getNetworkLayer(1); 074 } 075 netPlan.setRoutingTypeAllDemands(RoutingType.HOP_BY_HOP_ROUTING, upperLayer); 076 netPlan.setRoutingTypeAllDemands (RoutingType.SOURCE_ROUTING, lowerLayer); 077 078 /* Initialize some variables */ 079 final double PRECISION_FACTOR = 0.05; //Double.parseDouble(net2planParameters.get("precisionFactor")); 080 final int N = netPlan.getNumberOfNodes(); 081 final int D_up = netPlan.getNumberOfDemands (upperLayer); 082 final int E_lo = netPlan.getNumberOfLinks (lowerLayer); 083 if (N == 0 || D_up == 0) throw new Net2PlanException("This algorithm requires a topology and a demand set"); 084 085 netPlan.removeAllLinks(upperLayer); 086 netPlan.removeAllDemands(lowerLayer); 087 netPlan.setLinkCapacityUnitsName("Gbps" , lowerLayer); 088 netPlan.setLinkCapacityUnitsName("Gbps" , upperLayer); 089 netPlan.setDemandTrafficUnitsName("Gbps" , lowerLayer); 090 netPlan.setDemandTrafficUnitsName("Gbps" , upperLayer); 091 netPlan.setVectorLinkCapacity(DoubleFactory1D.dense.make (E_lo , capLowLayerLinksInNumCircuits.getInt() * ciurcuitCapacityGbps.getDouble()) , lowerLayer); 092 093 /* Create a full mesh of upper layer links in the netPlan object (index "c" in the variables), coupled to the 094 * corresponding demand in the lower layer */ 095 for (Node i : netPlan.getNodes ()) for (Node j : netPlan.getNodes ()) if (i != j) 096 { 097 if ((i.getIndex() == 0) && (j.getIndex() == 1)) continue; 098 final Link link = netPlan.addLink (i, j,0 , netPlan.getNodePairEuclideanDistance(i, j), 200000 , null , upperLayer); 099 final Demand demand = netPlan.addDemand(i, j, 0, RoutingType.HOP_BY_HOP_ROUTING , null,lowerLayer); 100 if (link.getIndex() != demand.getIndex()) throw new RuntimeException ("Bad"); 101 link.coupleToLowerLayerDemand(demand); 102 } 103 104 /* Compute the distances of the potential links */ 105 final int E_ul = netPlan.getNumberOfLinks(upperLayer); 106 final int E_ll = netPlan.getNumberOfLinks(lowerLayer); 107 108 /* Create the optimization problem object (JOM library) */ 109 OptimizationProblem op = new OptimizationProblem(); 110 111 op.addDecisionVariable("x_tc", false , new int[] { N, E_ul }, 0, Double.MAX_VALUE); /* the amount of traffic targeted to node t, that is carried by link c (upper layer virtual link) */ 112 op.addDecisionVariable("z_c", true , new int[] { 1 , E_ul }, 0, Double.MAX_VALUE); /* number of circuits established between end nodes of virtual link c */ 113 op.addDecisionVariable("x_ce", true , new int[] { E_ul , E_ll }, 0, Double.MAX_VALUE); /* number of circuits corresponding to virtual link c, that traverse low layer link e */ 114 115 /* Set some input parameters */ 116 op.setInputParameter("A_nc", netPlan.getMatrixNodeLinkIncidence(upperLayer)); /* 1 in position (n,e) if link e starts in n, -1 if it ends in n, 0 otherwise */ 117 final DoubleMatrix1D egressTraffic_t = netPlan.getVectorNodeEgressUnicastTraffic(upperLayer); 118 final DoubleMatrix2D trafficMatrixDiagonalNegative = netPlan.getMatrixNode2NodeOfferedTraffic(upperLayer); 119 trafficMatrixDiagonalNegative.assign (DoubleFactory2D.sparse.diagonal(egressTraffic_t) , DoubleFunctions.minus); 120 op.setInputParameter("TM", trafficMatrixDiagonalNegative); 121 op.setInputParameter("U_hi", ciurcuitCapacityGbps.getDouble()); 122 op.setInputParameter("U_lo", capLowLayerLinksInNumCircuits.getInt()); 123 op.setInputParameter("A_ne", netPlan.getMatrixNodeLinkIncidence(lowerLayer)); /* 1 in position (n,e) if link e starts in n, -1 if it ends in n, 0 otherwise */ 124 op.setInputParameter("h_d", netPlan.getVectorDemandOfferedTraffic(upperLayer) , "row"); 125 op.setInputParameter("EPSILON", 0.001 / (E_ul * netPlan.getVectorDemandOfferedTraffic(upperLayer).zSum())); 126 127 /* Sets the objective function */ 128 op.setObjectiveFunction("minimize", "sum(z_c) + EPSILON * sum(x_tc) + EPSILON*sum(x_ce)"); 129 130 /* Compute some matrices required for writing the constraints */ 131 op.addConstraint("A_nc * (x_tc') == TM"); /* the flow-conservation constraints (NxE_hi constraints) */ 132 op.addConstraint("sum(x_tc,1) <= U_hi * z_c"); /* the capacity constraints (E_hi constraints) */ 133 op.addConstraint("A_ne * (x_ce') == A_nc * diag(z_c)"); /* the lower layer flow-conservation constraints (NxE_hi constraints) */ 134 op.addConstraint("sum(x_ce,1) <= U_lo"); /* the capacity constraints (E constraints) */ 135 136 /* Call the solver to solve the problem */ 137 op.solve(solverName.getString (), "solverLibraryName", solverLibraryName.getString () , "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble ()); 138 139 /* If no solution is found, quit */ 140 if (op.feasibleSolutionDoesNotExist()) throw new Net2PlanException("The problem has no feasible solution"); 141 if (!op.solutionIsFeasible()) throw new Net2PlanException("A feasible solution was not found"); 142 143 /* Retrieve the optimum solutions */ 144 final DoubleMatrix1D z_c = op.getPrimalSolution("z_c").view1D(); 145 final DoubleMatrix2D x_tc = op.getPrimalSolution("x_tc").view2D(); 146 final DoubleMatrix2D x_ce = op.getPrimalSolution("x_ce").view2D(); 147 148 /* Sets the routing in both layers, which also establish the capacity in the upper layer links */ 149 netPlan.setRoutingFromDemandLinkCarriedTraffic(x_ce.copy ().assign(DoubleFunctions.mult(ciurcuitCapacityGbps.getDouble())) , false , true , null , lowerLayer); 150 netPlan.setRoutingFromDestinationLinkCarriedTraffic(x_tc , true , upperLayer); // remove the cycles if any 151 152 for (Link eHi : netPlan.getLinks (upperLayer)) 153 if (Math.abs(eHi.getCapacity() - ciurcuitCapacityGbps.getDouble() * z_c.get(eHi.getIndex())) > 1e-3) throw new RuntimeException ("Bad"); 154 netPlan.removeAllLinksUnused (PRECISION_FACTOR , upperLayer); 155 156 /* check */ 157 if (netPlan.getVectorDemandBlockedTraffic(upperLayer).zSum() > PRECISION_FACTOR) throw new RuntimeException ("Bad: " + netPlan.getVectorDemandBlockedTraffic(upperLayer)); 158 if (netPlan.getVectorDemandBlockedTraffic(lowerLayer).zSum() > PRECISION_FACTOR) throw new RuntimeException ("Bad"); 159 if (netPlan.getVectorLinkOversubscribedTraffic(upperLayer).zSum() > PRECISION_FACTOR) throw new RuntimeException ("Bad"); 160 if (netPlan.getVectorLinkOversubscribedTraffic(lowerLayer).zSum() > PRECISION_FACTOR) throw new RuntimeException ("Bad"); 161 162 return "Ok! Num circuits: " + Math.round(netPlan.getVectorLinkCapacity(upperLayer).zSum() / ciurcuitCapacityGbps.getDouble()); 163 } 164 165 @Override 166 public String getDescription() 167 { 168 return "Given a network composed of two layers, with traffic demands defined at the upper layer and links defined at the lower. The upper laye traffic is supposed to be routed through fixed capacity circuits. Each circuit, which is a direct link or the upper layer, is actually realized by a demand in the lower layer, that is routed through the lower layer links. Each lower layer link can host a given number of circuits traversing it. The algorithm searches for (i) the circuits to establish, (ii) the routing of the upper layer over the circuits, and (iii) the routing of the circuits over the lower layer links. The target is minimizing the number of circuits needed, a measure of the network cost. For finding the solution, the algorithm solves using JOM a formulation that combines a destination-link formulation in the upper layer routing, and a flow-link formulation in the lower layer. "; 169 } 170 171 @Override 172 public List<Triple<String, String, String>> getParameters() 173 { 174 /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */ 175 return InputParameter.getInformationAllInputParameterFieldsOfObject(this); 176 } 177}