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.offline; 019 020import java.util.List; 021import java.util.Map; 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; 028 029import com.jom.OptimizationProblem; 030import com.net2plan.interfaces.networkDesign.Demand; 031import com.net2plan.interfaces.networkDesign.IAlgorithm; 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.utils.Constants.RoutingType; 038import com.net2plan.utils.InputParameter; 039import com.net2plan.utils.Triple; 040 041/** 042 * Solves a general multilayer optimization problem formulation. 043 * @net2plan.description 044 * @net2plan.keywords Multilayer, Flow assignment (FA), Flow-link formulation, Destination-link formulation, Modular capacities 045 * @net2plan.ocnbooksections Section 7.4 046 * @net2plan.inputParameters 047 * @author Pablo Pavon-Marino 048 */ 049public class Offline_tcfa_generalMultilayer implements IAlgorithm 050{ 051 private InputParameter solverName = new InputParameter ("solverName", "#select# glpk cplex ipopt", "The solver name to be used by JOM. GLPK and IPOPT are free, CPLEX commercial. GLPK 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"); 052 private InputParameter solverLibraryName = new InputParameter ("solverLibraryName", "", "The solver library full or relative path, to be used by JOM. Leave blank to use JOM default."); 053 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)"); 054 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); 055 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); 056 057 private NetworkLayer lowerLayer, upperLayer; 058 059 @Override 060 public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters) 061 { 062 /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */ 063 InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters); 064 if (netPlan.getNumberOfLayers() > 2) throw new Net2PlanException ("The design must have one or two layers"); 065 066 /* Set a two layer network topology, maybe starting from a single layer design */ 067 if (netPlan.isSingleLayer()) 068 { 069 this.lowerLayer = netPlan.getNetworkLayerDefault(); 070 this.upperLayer = netPlan.addLayer("UP LAYER" , "Upper layer of the design" , "Gbps" , "Gbps" , null); 071 /* Save the demands in the upper layer, and remove them from the lower layer */ 072 for (Demand d : netPlan.getDemands (lowerLayer)) netPlan.addDemand(d.getIngressNode() , d.getEgressNode() , d.getOfferedTraffic() , null , upperLayer); 073 } 074 else 075 { 076 this.lowerLayer = netPlan.getNetworkLayer(0); 077 this.upperLayer = netPlan.getNetworkLayer(1); 078 } 079 netPlan.setRoutingType(RoutingType.HOP_BY_HOP_ROUTING, upperLayer); 080 netPlan.setRoutingType(RoutingType.SOURCE_ROUTING, lowerLayer); 081 082 /* Initialize some variables */ 083 final double PRECISION_FACTOR = Double.parseDouble(net2planParameters.get("precisionFactor")); 084 final int N = netPlan.getNumberOfNodes(); 085 final int D_up = netPlan.getNumberOfDemands (upperLayer); 086 final int E_lo = netPlan.getNumberOfLinks (lowerLayer); 087 if (N == 0 || D_up == 0) throw new Net2PlanException("This algorithm requires a topology and a demand set"); 088 089 netPlan.removeAllLinks(upperLayer); 090 netPlan.removeAllDemands(lowerLayer); 091 netPlan.setLinkCapacityUnitsName("Gbps" , lowerLayer); 092 netPlan.setLinkCapacityUnitsName("Gbps" , upperLayer); 093 netPlan.setDemandTrafficUnitsName("Gbps" , lowerLayer); 094 netPlan.setDemandTrafficUnitsName("Gbps" , upperLayer); 095 netPlan.setVectorLinkCapacity(DoubleFactory1D.dense.make (E_lo , capLowLayerLinksInNumCircuits.getInt() * ciurcuitCapacityGbps.getDouble()) , lowerLayer); 096 097 /* Create a full mesh of upper layer links in the netPlan object (index "c" in the variables), coupled to the 098 * corresponding demand in the lower layer */ 099 for (Node i : netPlan.getNodes ()) for (Node j : netPlan.getNodes ()) if (i != j) 100 { 101 if ((i.getIndex() == 0) && (j.getIndex() == 1)) continue; 102 final Link link = netPlan.addLink (i, j,0 , netPlan.getNodePairEuclideanDistance(i, j), 200000 , null , upperLayer); 103 final Demand demand = netPlan.addDemand(i, j, 0, null, lowerLayer); 104 if (link.getIndex() != demand.getIndex()) throw new RuntimeException ("Bad"); 105 link.coupleToLowerLayerDemand(demand); 106 } 107 108 /* Compute the distances of the potential links */ 109 final int E_ul = netPlan.getNumberOfLinks(upperLayer); 110 final int E_ll = netPlan.getNumberOfLinks(lowerLayer); 111 112 /* Create the optimization problem object (JOM library) */ 113 OptimizationProblem op = new OptimizationProblem(); 114 115 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) */ 116 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 */ 117 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 */ 118 119 /* Set some input parameters */ 120 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 */ 121 final DoubleMatrix1D egressTraffic_t = netPlan.getVectorNodeEgressUnicastTraffic(upperLayer); 122 final DoubleMatrix2D trafficMatrixDiagonalNegative = netPlan.getMatrixNode2NodeOfferedTraffic(upperLayer); 123 trafficMatrixDiagonalNegative.assign (DoubleFactory2D.sparse.diagonal(egressTraffic_t) , DoubleFunctions.minus); 124 op.setInputParameter("TM", trafficMatrixDiagonalNegative); 125 op.setInputParameter("U_hi", ciurcuitCapacityGbps.getDouble()); 126 op.setInputParameter("U_lo", capLowLayerLinksInNumCircuits.getInt()); 127 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 */ 128 op.setInputParameter("h_d", netPlan.getVectorDemandOfferedTraffic(upperLayer) , "row"); 129 op.setInputParameter("EPSILON", 0.001 / (E_ul * netPlan.getVectorDemandOfferedTraffic(upperLayer).zSum())); 130 131 /* Sets the objective function */ 132 op.setObjectiveFunction("minimize", "sum(z_c) + EPSILON * sum(x_tc) + EPSILON*sum(x_ce)"); 133 134 /* Compute some matrices required for writing the constraints */ 135 op.addConstraint("A_nc * (x_tc') == TM"); /* the flow-conservation constraints (NxE_hi constraints) */ 136 op.addConstraint("sum(x_tc,1) <= U_hi * z_c"); /* the capacity constraints (E_hi constraints) */ 137 op.addConstraint("A_ne * (x_ce') == A_nc * diag(z_c)"); /* the lower layer flow-conservation constraints (NxE_hi constraints) */ 138 op.addConstraint("sum(x_ce,1) <= U_lo"); /* the capacity constraints (E constraints) */ 139 140 /* Call the solver to solve the problem */ 141 op.solve(solverName.getString (), "solverLibraryName", solverLibraryName.getString () , "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble ()); 142 143 /* If no solution is found, quit */ 144 if (op.feasibleSolutionDoesNotExist()) throw new Net2PlanException("The problem has no feasible solution"); 145 if (!op.solutionIsFeasible()) throw new Net2PlanException("A feasible solution was not found"); 146 147 /* Retrieve the optimum solutions */ 148 final DoubleMatrix1D z_c = op.getPrimalSolution("z_c").view1D(); 149 final DoubleMatrix2D x_tc = op.getPrimalSolution("x_tc").view2D(); 150 final DoubleMatrix2D x_ce = op.getPrimalSolution("x_ce").view2D(); 151 152 /* Sets the routing in both layers, which also establish the capacity in the upper layer links */ 153 netPlan.setRoutingFromDemandLinkCarriedTraffic(x_ce.copy ().assign(DoubleFunctions.mult(ciurcuitCapacityGbps.getDouble())) , false , true , lowerLayer); 154 netPlan.setRoutingFromDestinationLinkCarriedTraffic(x_tc , true , upperLayer); // remove the cycles if any 155 156 for (Link eHi : netPlan.getLinks (upperLayer)) 157 if (Math.abs(eHi.getCapacity() - ciurcuitCapacityGbps.getDouble() * z_c.get(eHi.getIndex())) > 1e-3) throw new RuntimeException ("Bad"); 158 netPlan.removeAllLinksUnused (PRECISION_FACTOR , upperLayer); 159 160 /* check */ 161 if (netPlan.getVectorDemandBlockedTraffic(upperLayer).zSum() > PRECISION_FACTOR) throw new RuntimeException ("Bad: " + netPlan.getVectorDemandBlockedTraffic(upperLayer)); 162 if (netPlan.getVectorDemandBlockedTraffic(lowerLayer).zSum() > PRECISION_FACTOR) throw new RuntimeException ("Bad"); 163 if (netPlan.getVectorLinkOversubscribedTraffic(upperLayer).zSum() > PRECISION_FACTOR) throw new RuntimeException ("Bad"); 164 if (netPlan.getVectorLinkOversubscribedTraffic(lowerLayer).zSum() > PRECISION_FACTOR) throw new RuntimeException ("Bad"); 165 166 return "Ok! Num circuits: " + Math.round(netPlan.getVectorLinkCapacity(upperLayer).zSum() / ciurcuitCapacityGbps.getDouble()); 167 } 168 169 @Override 170 public String getDescription() 171 { 172 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. "; 173 } 174 175 @Override 176 public List<Triple<String, String, String>> getParameters() 177 { 178 /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */ 179 return InputParameter.getInformationAllInputParameterFieldsOfObject(this); 180 } 181}