TY - JOUR

T1 - Design of WDM networks under economy of scale pricing and shortest path routing

AU - Saad, Mohamed

AU - Luo, Zhi-Quan

PY - 2006/4/1

Y1 - 2006/4/1

N2 - Given a combination of unprotected and dedicated edge-disjoint path (1+1) protected connection requests and a finite set of fiber types, we consider the problem of allocating fibers on the links of a WDM network at minimum cost, such that all connection requests can be simultaneously realized. Each fiber type is characterized by its capacity and its cost per unit length, where costs reflect an economy of scale. It is known that a solution induced by "simply" routing each unprotected (respectively 1+1 protected) connection along the shortest path (respectively shortest pair of edge-disjoint paths) minimizes the total wavelength mileage, but may not minimize the total fiber cost. In this paper, we quantify the increase in fiber cost due to shortest path routing. In particular, we prove that the total cost of a shortest path based solution is guaranteed to lie within a certain factor of the minimum possible cost. This leads also to the fact that shortest path routing is asymptotically cost-optimal for a large total number of connection requests. Furthermore, for sparse topologies, e.g., the ring, the ShuffleNet and the mesh(-torus), we show that shortest path routing is asymptotically cost-optimal in large-scale networks supporting all-to-all communication. En route, we prove that by shortest path routing we obtain a provably optimal solution to the linear programming (LP-) relaxation of the problem. We have thus presented a provably good upper bound and a lower bound on the total fiber cost, that can be computed in polynomial-time. These bounds can be used as benchmarks against which heuristic approaches are compared.

AB - Given a combination of unprotected and dedicated edge-disjoint path (1+1) protected connection requests and a finite set of fiber types, we consider the problem of allocating fibers on the links of a WDM network at minimum cost, such that all connection requests can be simultaneously realized. Each fiber type is characterized by its capacity and its cost per unit length, where costs reflect an economy of scale. It is known that a solution induced by "simply" routing each unprotected (respectively 1+1 protected) connection along the shortest path (respectively shortest pair of edge-disjoint paths) minimizes the total wavelength mileage, but may not minimize the total fiber cost. In this paper, we quantify the increase in fiber cost due to shortest path routing. In particular, we prove that the total cost of a shortest path based solution is guaranteed to lie within a certain factor of the minimum possible cost. This leads also to the fact that shortest path routing is asymptotically cost-optimal for a large total number of connection requests. Furthermore, for sparse topologies, e.g., the ring, the ShuffleNet and the mesh(-torus), we show that shortest path routing is asymptotically cost-optimal in large-scale networks supporting all-to-all communication. En route, we prove that by shortest path routing we obtain a provably optimal solution to the linear programming (LP-) relaxation of the problem. We have thus presented a provably good upper bound and a lower bound on the total fiber cost, that can be computed in polynomial-time. These bounds can be used as benchmarks against which heuristic approaches are compared.

KW - Algorithms

KW - Complexity

KW - Integer linear programming

KW - Performance guarantee

KW - Survivable network design

UR - http://www.scopus.com/inward/record.url?scp=33645941797&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33645941797&partnerID=8YFLogxK

U2 - 10.1109/JSAC.2006.1613770

DO - 10.1109/JSAC.2006.1613770

M3 - Article

AN - SCOPUS:33645941797

VL - 24

SP - 26

EP - 36

JO - IEEE Journal on Selected Areas in Communications

JF - IEEE Journal on Selected Areas in Communications

SN - 0733-8716

IS - 4

ER -