Network Capacity and Routing Optimization Implementation
Algorithm Implementation: executeAlgorithm
This method executes the core network optimization algorithm, setting up the problem, defining constraints, and applying the resulting routing and capacity plan to the NetPlan object.
Method Signature
public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters)
{Parameter Initialization
The algorithm first parses the required input parameters, defining key constraints and costs:
final double maximumLinkCapacity = Double.parseDouble(algorithmParameters.get("maximumLinkCapacity"));
final double capacityModule = Double.parseDouble(algorithmParameters.get("capacityModule"));
final double costPerGbps = Double.parseDouble(algorithmParameters.get("costPerGbps"));
final double costPerKm = Double.parseDouble(algorithmParameters.get("costPerKm"));
netPlan.removeAllLinks();
netPlan.setRoutingType(RoutingType.SOURCE_ROUTING);Network Setup: Full Mesh Creation
A full mesh of potential links is created between all nodes, initially with zero capacity. This ensures all possible connections are considered by the optimization solver.
/* Create a full-mesh of links between all nodes, of capacity 0 */
for (Node n1 : netPlan.getNodes())
for (Node n2 : netPlan.getNodes())
if (n1 != n2)
netPlan.addLink(n1, n2, 0, netPlan.getNodePairEuclideanDistance(n1, n2), 200000, null);
final int D = netPlan.getNumberOfDemands();
final int Efm = netPlan.getNumberOfLinks();Optimization Problem Definition
An OptimizationProblem object is instantiated to define the Mixed Integer Linear Program (MILP) structure.
OptimizationProblem op = new OptimizationProblem();Decision Variables
Three sets of decision variables are defined:
x_de: Continuous variable representing the traffic flow of demand d carried over link e.a_e: Integer variable representing the number of capacity modules installed on link e.z_e: Binary variable indicating if link e is active (has capacity installed).
op.addDecisionVariable("x_de", false, new int[] {D, Efm}, 0, Double.MAX_VALUE);
op.addDecisionVariable("a_e", true, new int[] {1, Efm}, 0, maximumLinkCapacity / capacityModule);
op.addDecisionVariable("z_e", true, new int[] {1, Efm}, 0, 1);Input Parameters and Objective Function
Input parameters are set, including link lengths and cost factors. The objective is to minimize total cost, which includes both distance-based costs (for active links) and capacity installation costs.
op.setInputParameter("d_e", netPlan.getVectorLinkLengthInKm(), "row");
op.setInputParameter("c_km", costPerKm);
op.setInputParameter("c_Gbps", costPerGbps);
op.setInputParameter("C", capacityModule);
op.setInputParameter("U", maximumLinkCapacity);
op.setObjectiveFunction("minimize", "c_km * d_e * z_e' + c_Gbps * C * sum(a_e)");Constraints
Capacity Activation Constraint
Ensures that capacity C * a_e(e) is only installed if the link is active (z_e(e) = 1), bounded by the maximum capacity U.
for (Link e : netPlan.getLinks())
{
op.setInputParameter("e", e.getIndex());
op.addConstraint("C * a_e(e) <= U * z_e(e)");
}Flow Conservation Constraints
Standard flow conservation constraints applied per node and per demand:
for (Node n : netPlan.getNodes())
{
op.setInputParameter("deltaPlus", NetPlan.getIndexes(n.getOutgoingLinks()), "row");
op.setInputParameter("deltaMinus", NetPlan.getIndexes(n.getIncomingLinks()), "row");
for (Demand d : netPlan.getDemands())
{
op.setInputParameter("d", d.getIndex());
op.setInputParameter("h_d", d.getOfferedTraffic());
if (n == d.getIngressNode())
op.addConstraint("sum(x_de(d,deltaPlus)) - sum(x_de(d,deltaMinus)) == h_d");
else if (n == d.getEgressNode())
op.addConstraint("sum(x_de(d,deltaPlus)) - sum(x_de(d,deltaMinus)) == -h_d");
else
op.addConstraint("sum(x_de(d,deltaPlus)) - sum(x_de(d,deltaMinus)) == 0");
}
}Link Capacity Constraint
The total traffic carried over link e must not exceed the installed capacity (which is a multiple of capacityModule).
for (Link e : netPlan.getLinks())
{
op.setInputParameter("e", e.getIndex());
op.addConstraint("sum(x_de(all,e)) <= C * a_e(e)");
}Solving and Applying the Solution
The optimization problem is solved using GLPK with a maximum time limit of 10 seconds. If a feasible solution is found, the results are applied to the NetPlan.
op.solve("glpk", "maxSolverTimeInSeconds", 10);
if (!op.solutionIsFeasible())
throw new Net2PlanException("A feasible solution was not found");
// Apply routing
final DoubleMatrix2D x_de = op.getPrimalSolution("x_de").view2D();
netPlan.setRoutingFromDemandLinkCarriedTraffic(x_de, false, false);
// Apply capacity
final double[] a_e = op.getPrimalSolution("a_e").to1DArray();
for (Link e : netPlan.getLinks())
e.setCapacity(capacityModule * a_e[e.getIndex()]);
// Cleanup unused links
netPlan.removeAllLinksUnused(0.01);
return "Ok! Optimal solution found: " + op.solutionIsOptimal() + ", Number of links " + netPlan.getNumberOfLinks() + ", total capacity installed: " + netPlan.getVectorLinkCapacity().zSum();
}Algorithm Metadata
Description
Returns a description message that will be shown in the graphical user interface.
@Override
public String getDescription()
{
return "";
}Input Parameters Definition
This method defines the list of input parameters required by the algorithm, including their names, default values, and descriptions.
/** Returns the list of input parameters of the algorithm. For each parameter, you should return a Triple with its name, default value, and a description. */
@Override
public List<Triple<String, String, String>> getParameters()
{
final List<Triple<String, String, String>> param = new LinkedList<Triple<String, String, String>>();
param.add(Triple.of("maximumLinkCapacity", "1000", "The maximum capacity allowed for a link between two nodes."));
param.add(Triple.of("capacityModule", "10", "The capacity of one capacity module (link capacities have to be a multiple of this)."));
param.add(Triple.of("costPerGbps", "1", "The cost per Gbps of capacity in any link."));
param.add(Triple.of("costPerKm", "1", "The cost per km in any link."));
return param;
}
}