×

SONET/SDH ring assignment with capacity constraints. (English) Zbl 1023.68003

Summary: We consider the problem of interconnecting a set of customer sites using bidirectional SONET rings of equal capacity. Each site is assigned to exactly one ring and a special ring, called the federal ring, interconnects the other rings together. The objective is to minimize the total cost of the network subject to a ring capacity limit where the capacity of a ring is determined by the total bandwidth required between sites assigned to the same ring plus the total bandwidth request between these sites and sites assigned to other rings.
We present exact, integer-programming based solution techniques and fast heuristic algorithms for this problem. We compare the results from applying the heuristic algorithms with those produced by the exact methods for real-world as well as randomly generated problem instances. We show that two of the heuristics find solutions that cost at most twice that of an optimal solution. Empirical evidence indicates that in practice the algorithms perform much better than their theoretical bound and often find optimal solutions.

MSC:

68M10 Network design and communication in computer systems
90C35 Programming involving graphs or networks
90B18 Communication networks in operations research
68W25 Approximation algorithms
90C59 Approximation methods and heuristics in mathematical programming

Software:

SONET
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chlamtac, I.; Elek, V.; Fumagalli, A.; Szabo, C., Scalable wdm access network architecture based on photonic slot routing, IEEE/ACM Trans. Networking, 7, 1, 1-9 (1999)
[2] Cosares, S.; Deutsch, D. N.; Saniee, I.; Wasem, O. J., SONET toolkit: a decision support system for designing robust and cost-effective fiber-optic networks, Interfaces, 25, 1, 20-40 (1995)
[3] Cosares, S.; Saniee, I., An optimization problem related to balancing loads on SONET rings, Telecommun. Syst., 3, 165-181 (1994)
[4] Dell’Amico, M.; Labbé, M.; Maffioli, F., Exact solution of the SONET ring loading problem, Oper. Res. Lett., 25, 119-129 (1999) · Zbl 0934.90010
[5] Fischetti, M.; Salazar Gonzalez, J. J.; Toth, P., The symmetric generalized traveling salesman polytope, Networks, 26, 2, 113-123 (1995) · Zbl 0856.90116
[6] O. Goldschmidt, D. Hochbaum, E.V. Olinick, The SONET edge-partitioning problem, Working Paper available online at http:/www.engr.smu.edu/ olinick/papers/sepp.ps.; O. Goldschmidt, D. Hochbaum, E.V. Olinick, The SONET edge-partitioning problem, Working Paper available online at http:/www.engr.smu.edu/ olinick/papers/sepp.ps.
[7] Khanna, S., A polynomial time approximation scheme for the sonet ring loading problem, Bell Labs Tech. J., 2, 2, 36-41 (1997)
[8] Laguna, M., Clustering for the design of SONET rings in interoffice telecommunications, Manage. Sci., 40, 11, 1533-1541 (1994) · Zbl 0823.90040
[9] Lee, Y.; Sherali, H.; Han, J.; Kim, S., A branch-and-cut algorithm for solving an intra-ring synchronous optical network design problem, Networks, 35, 3, 223-232 (2000) · Zbl 0985.90093
[10] Myung, Y.-S.; Kim, H.-G.; Tcha, D.-W., Optimal load balancing on SONET bidirectional rings, Oper. Res., 45, 1, 148-152 (1997) · Zbl 0892.90067
[11] Schrijver, A.; Seymour, P.; Winkler, P., The ring loading problem, SIAM J. Discrete Math., 11, 1, 1-14 (1998) · Zbl 0910.90135
[12] Sutter, A.; Vanderbeck, F.; Wolsey, L., Optimal placement of add/drop multiplexers: heuristic and exact algorithms, Oper. Res., 46, 5, 719-728 (1998) · Zbl 0987.90014
[13] D. Wagner, F. Wagner, Between min cut and graph bisection, Lecture Notes in Computer Science, Vol. 711, Springer, New York, 1993, pp. 744-750.; D. Wagner, F. Wagner, Between min cut and graph bisection, Lecture Notes in Computer Science, Vol. 711, Springer, New York, 1993, pp. 744-750. · Zbl 0925.05053
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.