com.net2plan.examples.general.offline

Class Offline_ipOverWdm_routingSpectrumAndModulationAssignmentILPNotGrooming

Object

com.net2plan.examples.general.offline.Offline_ipOverWdm_routingSpectrumAndModulationAssignmentILPNotGrooming

All Implemented Interfaces:

com.net2plan.interfaces.networkDesign.IAlgorithm, com.net2plan.internal.IExternal

public class Offline_ipOverWdm_routingSpectrumAndModulationAssignmentILPNotGrooming
extends Object
implements com.net2plan.interfaces.networkDesign.IAlgorithm

Algorithm based on an ILP solving the Routing, Spectrum, Modulation Assignment (RSMA) problem with regenerator placement, in flexi (elastic) or fixed grid optical WDM networks, with or without fault tolerance, latency and/or lightpath bidirectionality requisites.

The input design is assumed to have a WDM layer compatible with WDMUtils Net2Plan library usual assumptions:

• Each network node is assumed to be an Optical Add/Drop Multiplexer WDM node
• Each network link at WDM layer is assumed to be an optical fiber.
• The spectrum in the fibers is assumed to be composed of a number of frequency slots. In fixed-grid network, each frequency slot would correspond to a wavelength channel. In flexi-grid networks, it is just a frequency slot, and lightpaths can occupy more than one. In any case, two lightpaths that use overlapping frequency slots cannot traverse the same fiber, since their signals would mix.
• Each traffic demand is a need to transmit an amount of Gbps between two nodes. A demand traffic can be carried using one or more lightpaths.

Each lightpath produced by the design is returned as a Route object. Protection lightpaths in 1+1 case are returned as ProtectionSegment objects attached to the Route. They represent a set of reserved frequency slots in a set of fibers, to be used to protect other lightpaths.

Each lightpath starts and ends in a transponder. The user is able to define a set of available transpoder types, so the design can create lightpaths using any combination of them. The information user-defined per transponder is:

• Line rate in Gbps (typically 10, 40, 100 in fixed-grid cases, and other multiples in flexi-grid networks).
• Cost
• Number of frequency slots occupied (for a given line rate, this depends on the modulation the transponder uses)
• Optical reach in km: Maximum allowed length in km of the lightpaths with this transponder. Higher distances can be reached using signal regenerators.
• Cost of a regenerator for this transponder. Regenerators can be placed at intermdiate nodes of the lightpath route, regenerate its optical signal, and then permit extending its reach. We consider that regenerators cannot change the frequency slots occupied by the lightpath (that is, they are not capable of wavelength conversion)

In addition, the user can force the design to use bidirectional transponders (the usual case). This means that (i) in each transponder we have the transmission and reception side inseparable (so you cannot e.g. buy just the transmission side), and (ii) a couple of transponders (of course of the same type) being the end points of a lightpath from node 1 to node 2, also are used for a lightpath from node 2 to node 1, (iii) note however that the two opposite lightpaths can follow arbitrary routes (they do not have to traverse the reversed sequence of nodes). This bidirectionality constraint is a common requirement if the lightpath will be used for carrying IP traffic, since IP assumes that its links (the lightpaths) are bidirectional pipes.

We assume that all the fibers use the same wavelength grid, composed of a user-defined number of frequency slots. The user can also select a limit in the maximum propagation delay of a lightpath.

The output design consists in the set of lightpaths to establish, in the 1+1 case also with a 1+1 lightpath each. Each lightpath is characterized by the transponder type used (which sets its line rate and number of occupied slots in the traversed fibers), the particular set of contiguous frequency slots occupied, and the set of signal regeneration points (if any). This information is stored in the Route and ProtectionSegment object using the regular methods in WDMUTils, and can be retrieved in the same form (e.g. by a report showing the WDM network information). If a feasible solution is not found (one where all the demands are satisfied with the given constraints), a message is shown.

.

Failure tolerance

The user can choose among three possibilities for designing the network:

• No failure tolerant: The lightpaths established should be enough to carry the traffic of all the demands when no failure occurs in the network, but any losses are accepted if the network suffers failures in links or nodes.
• Tolerant to single-SRG (Shared Risk Group) failures with static lightpaths: All the traffic demands should be satisfied using lightpaths, so that under any single-SRG failure (SRGs are taken from the input design), the surviving lightpaths are enough to carry the 100% of the traffic. Note that lightpaths are static, in the sense that they are not rerouted when affected by a failure (they just also fail), and the design should just overprovision the number of lightpaths to establish with that in mind.
• 1+1 SRG-disjoint protection: This is another form to provide single-SRG failure tolerance. Each lightpath is backed up by a SRG-disjoint lightpath (returned as a ProtectionSegment object). The backup lightpath uses the same type of transponder as the primary (and thus the same line rate, an occupies the same number of slots), its path is SRG-disjoint, and the particular set of slots occupied can be different.

Optimization targets

The user can choose between two optimization targets:

• Minimizing the total cost, given by the transponders and regenerators (if any).
• Minimizing congestion at the WDM layer. This means looking for the design that maximizes the number of idle slots in the bottleneck fiber (the one with less idle frequency slots).

Use cases

This algorithm is quite general, and fits a number of use cases designing WDM networks, for instance:

• Single line rate, fixed grid networks: Then, one single type of transponder will be available, which occupies one frequency slot
• Mixed-Line Rate fixed-grid networks: In this case, several transponders can be available at different line rates and with different optical reaches. However, all of them occupy one slot (one wavelength channel)
• Single line rate, flexi-grid networks using varying-modulation transponders: Several transponders are available (or the same transponder with varying configurations), all of them with the same line rate, but thanks to the different usable modulations they can have different optical reaches and/or number of occupied slots.
• Multiple line rate, flexi-grid networks using Bandwidth Variable Transponders: Here, it is possible to use different transponders with different line rates, e.g. to reflect more sophisticated transponders which can have different configurations, varying its line rate, optical reach, and number of occupied slots.
• ...

Some details of the algorithm

The algorithm is based on solving a set of MILPs (Mixed Integer Linear Programs) interfacing from JOM to the user-defined solver. The algorithm uses a flow-path formulation, where a number of candidate paths are pre-computed for each demand. The user-defined parameter k limits the maximum number of paths computed per demand. In the 1+1 case, the usable SRG-disjoint path pairs for each demand are computed from the candidate paths. Increasing the number of paths k also increases the computational complexity of the algorithm, but can produce better solutions. In some occasions, a low k number is the reason for the algorithm failing in finding a feasible solution.

The details of the algorithm will be provided in a publication currently under elaboration.

Keywords:

• JOM, WDM

Input parameters:

k: Default: 5 Maximum number of admissible paths per input-output node pair solverName: Value to select within {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 solverLibraryName: Default: The solver library full or relative path, to be used by JOM. Leave blank to use JOM default. maxSolverTimeInSeconds: Default: -1.0 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) numFrequencySlotsPerFiber: Default: 40 Number of wavelengths per link transponderTypesInfo: Default: 10 1 1 9600 1 Transpoder types separated by ";" . Each type is characterized by the space-separated values: (i) Line rate in Gbps, (ii) cost of the transponder, (iii) number of slots occupied in each traversed fiber, (iv) optical reach in km (a non-positive number means no reach limit), (v) cost of the optical signal regenerator (regenerators do NOT make wavelength conversion ; if negative, regeneration is not possible). ipLayerIndex: Default: 1 Index of the IP layer (-1 means default layer) wdmLayerIndex: Default: 0 Index of the WDM layer (-1 means default layer) networkRecoveryType: Value to select within {not-fault-tolerant, single-srg-tolerant-static-lp, 1+1-srg-disjoint-lps} Establish if the design should be tolerant or not to single SRG failures (SRGs are as defined in the input NetPlan). First option is that the design should not be fault tolerant, the second means that failed lightpaths are not recovered, but an overprovisioned should be made so enough lightpaths survive to carry all the traffic in every failure. The third means that each lightpath is 1+1 protceted by a SRG-disjoint one, that uses the same transponder optimizationTarget: Value to select within {min-cost, maximin-fiber-number-idle-slots} Type of optimization target. Choose among minimize the network cost given by the su mof the transponders cost, and maximize the number of idle frequency slots in the fiber with less idle frequency slot maxPropagationDelayMs: Default: -1.0 Maximum allowed propagation time of a lighptath in miliseconds. If non-positive, no limit is assumed bidirectionalTransponders: Boolean type (default: true). If true, the transponders used are bidirectional. Then, the number of lightpaths of each type from node 1 to node 2, equals the number of lightpahts from 2 to 1 (see that both directions can have different routes and slots)

Constructor Summary

Constructors

Constructor and Description
Offline_ipOverWdm_routingSpectrumAndModulationAssignmentILPNotGrooming()

Method Summary

Modifier and Type	Method and Description
String	executeAlgorithm(com.net2plan.interfaces.networkDesign.NetPlan netPlan, Map<String,String> algorithmParameters, Map<String,String> net2planParameters)
String	getDescription()
List<com.net2plan.utils.Triple<String,String,String>>	getParameters()

Methods inherited from class Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Offline_ipOverWdm_routingSpectrumAndModulationAssignmentILPNotGrooming

public Offline_ipOverWdm_routingSpectrumAndModulationAssignmentILPNotGrooming()

Method Detail

executeAlgorithm

public String executeAlgorithm(com.net2plan.interfaces.networkDesign.NetPlan netPlan,
                               Map<String,String> algorithmParameters,
                               Map<String,String> net2planParameters)

Specified by:

executeAlgorithm in interface com.net2plan.interfaces.networkDesign.IAlgorithm

getDescription

public String getDescription()

Specified by:

getDescription in interface com.net2plan.interfaces.networkDesign.IAlgorithm

Specified by:

getDescription in interface com.net2plan.internal.IExternal

getParameters

public List<com.net2plan.utils.Triple<String,String,String>> getParameters()

Specified by:

getParameters in interface com.net2plan.interfaces.networkDesign.IAlgorithm

Specified by:

getParameters in interface com.net2plan.internal.IExternal