Better bounds for minimizing SONET ADMs

被引：6

作者：

Epstein, Leah ^{[2
]}

Levin, Asaf ^{[1
]}

机构：

[1] Hebrew Univ Jerusalem, Dept Stat, IL-91905 Jerusalem, Israel

[2] Univ Haifa, Dept Math, IL-31905 Haifa, Israel

来源：

JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 2009年 / 75卷 / 02期

关键词：

Approximation algorithms; Optical network design; ADM minimization; RINGS; COST;

D O I：

10.1016/j.jcss.2008.08.003

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

SONET add-drop multiplexers (ADMs) are the dominant cost factor in SONET/WDM rings. The number of SONET ADMs required by a set of traffic streams is determined by the routing and wavelength assignment of the traffic streams. Following previous work, we consider the problem where the route of each traffic stream is given as input, and we need to assign wavelengths so as to minimize the total number of used SONET ADMs. This problem is known to be NP-hard, and the best known approximation algorithm for this problem has a performance guarantee of 3/2. We improve this result, and present a 98/69 approximate to 1.42029-approximation algorithm. We also study some of tile previously proposed 9 algorithms for this problem, and give either tight or tighter analysis of their approximation ratio. (c) 2008 Elsevier Inc. All rights reserved.

引用

页码：122 / 136

页数：15

共 10 条

[1]

[Anonymous], 2003, COMBINATORIAL OPTIMI

[2] Traffic partition in WDM/SONET rings to minimize SONET ADMs [J].

Calinescu, G ;

Wan, PJ .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2002, 6 (04) :425-453

[3] Minimizing electronic line terminals for automatic ring protection in general WDM optical networks [J].

Calinescu, G ;

Frieder, O ;

Wang, PJ .

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 2002, 20 (01) :183-189

[4] Lightpath arrangement in survivable rings to minimize the switching cost [J].

Eilam, T ;

Moran, S ;

Zaks, S .

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 2002, 20 (01) :172-182

[5]

EPSTEIN L, 2004, P 2 WORKSH APPR ONL, P281

[6]

Gerstel O, 1998, IEEE INFOCOM SER, P94, DOI 10.1109/INFCOM.1998.659642

[7]

LIU L, 2000, P IEEE INFOCOM 2000, P1020

[8] A FASTER STRONGLY POLYNOMIAL MINIMUM COST FLOW ALGORITHM [J].

ORLIN, JB .

OPERATIONS RESEARCH, 1993, 41 (02) :338-350

[9] A 10/7+ε approximation for minimizing the number of ADMs in SONET rings [J].

Shalom, M ;

Zaks, S .

FIRST INTERNATIONAL CONFERENCE ON BROADBAND NETWORKS, PROCEEDINGS, 2004, :254-262

[10] Grooming of arbitrary traffic in SONET/WDM BLSRs [J].

Wan, PJ ;

Calinescu, G ;

Liu, LW ;

Frieder, O .

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 2000, 18 (10) :1995-2003

← 1 →