Minimizing the number of electronic switches in optical networks has been a main research topic in some recent studies. In such networks, we assign colors to a given set of lightpaths, and they are partitioned into unicolor cycles and paths; the switching cost is minimized when the number of paths is minimized. Most approximation and heuristic algorithms for this problem have a preprocessing stage, in which possible cycles are found. Among them, the basic algorithm eliminates cycles of size at most l, and has a performance guarantee of OPT+0.5(1+epsilon)N, where OPT is the cost of an optimal solution, N is the number of lightpaths and 0 <= epsilon <= 1/(l+2), for any given odd l. The time complexity of the algorithm is exponential in l. We improve the analysis of this algorithm, by showing that epsilon <= 1/ (1.5(l+2)), which implies a reduction of the exponent in the time complexity. We also improve the lower bound by showing that epsilon >= 1/(2l+3). The results shed more light on the structure of this basic algorithm. In addition, in our analysis we suggest a novel technique - including a new combinatorial lemma - to deal with this problem.

On Minimizing the Number of ADMs in a General Topology Optical Network

FLAMMINI, MICHELE;
2009-01-01

Abstract

Minimizing the number of electronic switches in optical networks has been a main research topic in some recent studies. In such networks, we assign colors to a given set of lightpaths, and they are partitioned into unicolor cycles and paths; the switching cost is minimized when the number of paths is minimized. Most approximation and heuristic algorithms for this problem have a preprocessing stage, in which possible cycles are found. Among them, the basic algorithm eliminates cycles of size at most l, and has a performance guarantee of OPT+0.5(1+epsilon)N, where OPT is the cost of an optimal solution, N is the number of lightpaths and 0 <= epsilon <= 1/(l+2), for any given odd l. The time complexity of the algorithm is exponential in l. We improve the analysis of this algorithm, by showing that epsilon <= 1/ (1.5(l+2)), which implies a reduction of the exponent in the time complexity. We also improve the lower bound by showing that epsilon >= 1/(2l+3). The results shed more light on the structure of this basic algorithm. In addition, in our analysis we suggest a novel technique - including a new combinatorial lemma - to deal with this problem.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11697/13063
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 2
social impact