Offline Routing and Regenerator Placement and Dimensioning for Translucent OBS Networks

The deployment of translucent optical networks is considered the most promising short term solution to decrease costs and energy consumption in optical backbone networks. Currently usage of translucent wavelength switched optical networks (WSON) are very popular but to be more efficient this networks are used with optical burst switching (OBS). There are two semiconductor optical amplifier architectures applied upon OBS: broadcast-and-select (BAS) and tune-and-select (TAS). Both of them rely on the SOA technology and on wavelength converters switching modules. Authors suggested to use TAS as it reduced some drawbacks of BAS (high power requirements and large interchannel crosstalk). However, in this project it's better to use modification of the TAS architecture by replacing each in-line electrical wavelength converter with a block consisting of a tunable laser and a wavelength conversion-type SOA device.

In translucent OBS (T-OBS) network architecture in which core nodes switch incoming data bursts to their output ports either in an all-optical fashion or through regenerators when signal regeneration is required.

As the Routing and Regenerators Placement and Dimensioning problem could become very complex, a possible solution is to divide the problem into two parts - routing, and regenerators placement and dimensioning. This problem can often be found in WSON with T-OBS switching technology.

RRPD is a Routing and Regenerators Placement and Dimensioning problem made out of two parts. The first part of this problem is the minimization of average paths that goes through one link. In the second part it is searched where to place the necessary regenerators in order to reduce the number of them in the network and provide an acceptable signal-to-noise ratio.

As the problem is very complicated and needs a lot of resources, it is better to split the problem into two parts:

  • MILP for the routing problem. As the solution of this problem is suppose to be precise, in the paper it was solved only through ILP, and not with heuristic.
  • Deal with regenerator placement and dimensioning. We have chosen the Biased Random Key General Algorithm (BRKGA) heuristic as it is the most effective among the proposed heuristics. The solutions in the paper only describe the heuristic method, but we have also implemented an ILP for this problem in CPLEX. The main idea was to compare both ILP and heuristic, and perform an analysis based on it.

Report with all the details

Appendix

Routing Problem ILP CPLEX

Input

E = 11;
D = 3;
P = 7;
%PATHS[PATHS][EDGES]
PATHS = [
[0 0 0 1 0 0 1 0 0 0 0],
[0 1 0 0 0 0 0 1 0 0 0],
[1 0 0 0 0 0 0 0 1 0 0],
[0 0 0 1 0 0 0 0 0 0 1],
[0 1 1 0 0 0 0 0 0 0 0],
[0 0 1 0 1 0 0 0 0 0 0],
[0 0 0 0 0 0 0 0 1 1 0]
];
%PD[DEMAND][PATHS]
PD = [
[1 1 1 0 0 0 0],
[0 0 0 1 1 0 0],
[0 0 0 0 0 1 1]
];

PART 1

int E = ...;
int D = ...;
int P = ...;
range EDGE = 1..E;
range DEMAND = 1..D;
range NUMPATH = 1..P;
/*Number of all paths that take part in the routing*/
//Predefined candidate paths (contain bool if there is edge e in the path p)
int PATHS[NUMPATH][EDGE] = ...; 
//Set of paths supporting demand(1,0 - if the path support the demand)
int PD[DEMAND][NUMPATH] = ...;
dvar int+ y;
dvar boolean X[NUMPATH];
minimize y;
subject to {
  forall (e in EDGE) 
    sum(p in NUMPATH) PATHS[p, e] * X[p] <= y;
  
  forall (d in DEMAND)  
    sum(p in NUMPATH) PD[d, p] * X[p] == 1;
}

PART 2

int E = ...;
int D = ...;
int P = ...;
range EDGE = 1..E;
range DEMAND = 1..D;
range NUMPATH = 1..P;
/*Number of all paths that take part in the routing*/
//Predefined candidate paths (contain bool if there is edge e in the path p)
int PATHS[NUMPATH][EDGE] = ...; 
//Set of paths supporting demand(1,0 - if the path support the demand)
int PD[DEMAND][NUMPATH] = ...;
int y = ...;
dvar boolean X[NUMPATH];
minimize 
  sum (e in EDGE)
    sum (p in NUMPATH) PATHS[p, e] * X[p];
subject to {
  forall (e in EDGE) 
    sum(p in NUMPATH) PATHS[p, e] * X[p] <= y;
  
  forall (d in DEMAND)  
    sum(p in NUMPATH) PD[d, p] * X[p] == 1;
}

PART 3

int P = ...;
int N = ...;
int R = ...;
int S = ...;
range NODES = 1..N;
range NUMPATH = 1..P;
range NUMREGEN = 1..R;
range NUMSOL = 1..S;
int PATHNODE[NUMPATH][NODES] = ...;
int PATHSOLUT[NUMPATH][NUMSOL][NODES] = ...;
int AREGEN[NUMREGEN] = ...;
int XA[NODES] = ...;
execute {  
  for(var i in NODES) 
    for(var j in NUMPATH)
      XA[i] = 0;  
  for(var k in NODES) 
    for(var l in NUMPATH)
      XA[k] = XA[k]+ PATHNODE[l][k];
  }
dvar boolean U[NODES][NUMREGEN];
dvar boolean Z[NUMPATH][NUMSOL];
dvar int LOAD[NODES];
minimize 
  sum (n in NODES)
      sum (r in NUMREGEN) U[n, r] * r;
subject to { 
forall (n in NODES) 
  sum(r in NUMREGEN) U[n, r] * AREGEN[r] - LOAD[n] >= 0;    
forall (n in NODES)  
  sum(r in NUMREGEN) U[n, r] == 1;    
forall (p in NUMPATH)  
  sum(s in NUMSOL) Z[p, s] == 1;    
forall (n in NODES)  
  sum(p in NUMPATH)
    sum(s in NUMSOL) PATHNODE[p, n] * PATHSOLUT[p, s, n] * Z[p, s] * XA[n] == LOAD[n];      
} 
optimization_problem_rrpd.txt · Last modified: 2012/05/31 12:17 by julia
 
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki