×

Design of a distributed finer transport network with hubbing topology. (English) Zbl 0955.90007

Summary: This paper deals with the comprehensive design of a distributed network, whose structure includes a large-scale fiber transport network where switching centers are interconnected via optical fiber cable. For real-world applicability, this design study covers in an integrated framework all three major decision sets: locating hub facilities, placing conduits and installing cables therein. The complex problem is formulated as a simple variant of the classical network design model by judiciously redefining commodity-flows. Exploiting the special structure of the problem, a dual-based heuristic is then developed which yields near-optimal design plans. Computational experiments show that the performance of the proposed heuristic is satisfactory in both speed and the quality of the design solutions generated.

MSC:

90B10 Deterministic network models in operations research
49M29 Numerical methods involving duality
Full Text: DOI

References:

[1] AT&T Bell Lab., Engineering and operation in the Bell System (1984), Bell Telephone Lab. Inc
[2] Balakrishnan, A.; Magnanti, T. L.; Wong, R. T., A dual-ascent procedure for large-scale uncapacitated network design, Operations Research, 37, 716-740 (1989) · Zbl 0681.90083
[3] Bannister, J. A.; Fratta, L.; Gerla, M., Topological design of the wavelength-division optical network, (Proceedings of IEEE INFOCOM’90 (1990)), 1005-1013
[4] Cardwell, R. H.; Monma, C. L.; Wu, T. H., Computer-aided design procedure for survivable fiber optic networks, IEEE Journal on SAC, 7, 1188-1197 (1989)
[5] CCITT, General Network Planning (1983), Geneva
[6] Chang, S.; Gavish, B., Telecommunications network topological design and capacity expansion: formulations and algorithms, Telecommunication Systems, 1, 99-131 (1993)
[7] Chen, K. J.; Wu, T. H.; Stach, J. E., Topological and architectural design for pre-ISDN integration of fiber optic voice and data networks, IEEE Journal on SAC, 4, 1414-1423 (1986)
[8] Chung, S.; Myung, Y.; Tcha, D., Optimal design of a distributed network with a two-level hierarchical structure, European Journal of Operational Research, 62, 105-115 (1992) · Zbl 0758.90072
[9] Claus, A.; Kratzig, S., Optimal planning of network structures within an exchange area, European Journal of Operational Research, 7, 67-76 (1981) · Zbl 0456.90019
[10] Gavish, B.; Trudeau, P.; Dror, M.; Gendreau, M.; Mason, L., Fiberoptic circuit work design under reliability constraints, IEEE Journal on SAC, 7, 1181-1187 (1989)
[11] Kerner, M.; Lemberg, H. L.; Simons, D. M., An analysis of alternative architectures for the interoffice network, IEEE Journal on SAC, 4, 1404-1413 (1986)
[12] Lee, C.; Ro, H.; Tcha, D., Topological design of a twolevel network with ring-star configuration, Computers & Operations Research, 20, 625-637 (1993) · Zbl 0771.90041
[13] May, G.; Jammu, D., A distributed architecture for survivable SONET transport networks, (Proceedings of IEEE GLOBECOM’91 (1991)), 2013-2017
[14] Medhi, D., A unified approach to network survivability for teletraffic networks: models, algorithms and analysis, IEEE Transactions on Communications, 42, 534-547 (1994)
[15] O’Kelly, M.; Skorin-Kapov, D.; Skorin-Kapov, J., Lower bounds for the Hub Location Problem, Management Science, 41, 713-721 (1995) · Zbl 0836.90109
[16] Tcha, D.; Yoon, M., Conduit and cable installation for a centralized network with logical star-star topology, IEEE Transactions on Communications, 43, 958-967 (1995)
[17] Wu, T. H., Fiber Network Service Survivability (1992), Artech House, Inc: Artech House, Inc Boston
[18] Wu, T. H.; Kolar, D. J.; Cardwell, R. H., Survivable network architectures for broad-band fiber optic networks: models and performance comparison, IEEE Journal of Lightwave Technology, 6, 1698-1709 (1988)
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.