I

I

II

III (C B ) (C L )

(HL) Min c ij x ij f i y i i H j H i H s.t. y i 1, k K, i W k C B C L p (HL) x ij y i, i H, k K i, j W k x ij y i {0,1}, i, j H. K W k k H K i i f i i d ij i j r ij i j c ij r ij X d ij y i i x ij i j

K D K I K D K I [HLDN] Max g j z j f ij y ij c ij x k, ij j J {i, j} E {i, j} A r k, i o(k), x k ij x k ji r k, i d(k), k K, j N i N 0, otherwise, r k (x k ij x k ji) Q ij y ij, k K x k ij z i, (i, j) E, i J, x k ji z i, (i, j) E, i J, x k ij 0, y ij, z i (i, j) E, {0,1}, i J{i, j} E. K K I K D, c k ij : k Commodity (i, j). f ij : (i, j). g j : Hub j. r k : Commodity k. Q ij : (i, j). x k ij : (i, j) k Commodity. y ij : (i, j). z j : Hub j.

IV

(IR) (IR) (IR) Min c t r y t r r R t T s.t. a ir x t ir r i, i K r R t T

x t ir q t y t r, i K(r) t T, r R x t ir P ir, x t ir 0, y t r {0,1}, N E K R, i K, r R K(r) : r T i K, r R, t T q t t t T, r i : i P ir i r c r : r a ir i r c t r : t r y t r t r x t ir : t r i

V P NL P NP P BL P BP P BP

P NP P NP P BP P BL P BL P NL P NL P NP P BL P NP P NP P NP P NP P NP VI

[1],, 1993. 12. [2],, 1994. 12. [3],,,, 2, 1, 17-29, 1995. 9. [4],,,,, 11, 3, 103-128. 1994. 11. [5],,, 32, 441-459, 1994. 10. [6] G. N. Brown, W. D. Grover, J. B Slevinsky and M.H. MacGregor, "Mesh/Arc Networking : An Architecture for Efficient Survivable Self-Healing Networks," Globecom'94, 471-477, 1994. [7] B. Coan, W. Leland, M. Vecchi, A. Weinrib and L. Wu, "Using Distributed Topology Update and Preplanned Configurations to Achieve Trunk Network Survivability," IEEE Transactions on Reliability, V.40, No.4, 404-416, 1991. [8] S. Cosares and I. Sanieei, "An Optimization Problem Related to Balancing Loads on SONET Rings," Telecommunication Systems, V.3, II, 1994. [9] S. Cosares, D. N. Deutsch, I. Sanieei and O. J. Wasem, "SONET Toolkit : A Decision Support System for Designing Robust and Cost-effective Fiber-Optic Networks," Interfaces, Vol. 25, No. 1, 20-40, 1995. [10] R. D. Doverspike, J.A. Morgan and W. Leland, "Network Design Sensitivity for Use of Digital Crossconnect Systems in Survivable Network Architectures", IEEE Journal on SAC, 12, 69-78,1994 [11] W. D. Grover, "Case Studies of Survivable Ring, Mesh and Mesh-Arc Hybrid Networks," Globecom'92, 633-638, 1992. [12] W. D. Grover, T. Bilodeau and B. Venables, "Near Optimal Spare Capacity Planning in a Mesh Restorable Network," Globecom'91, 2007-2012, 1991. [13] M. Herzberg, "An Optimal Spare-Capacity Assignment Model for Survivable Networks with Hop Limits," Globecom'94, 1601-1606, 1994. [14] H. G. Kim, Self-healing Network Design and Analysis, Ph.D. Desertation, Department of Industrial Management, KAIST, 1996. [15] D. Medhi, "A Unified Approach to Network Survivability for Teletraffic Networks : Models, Algorithms and Analysis," IEEE Transactions on Comm., Vol. 42, No. 2/3/4, 534-548, 1994. [16] M. Minoux, "Network Synthesis and Optimum Network Design Problems : Models, Solution Methods and Applications," Networks, V.19, 1989. [17] Y. S. Myung, H. J. Kim and D. W. Tcha, "Design of Communication Networks with Survivability Constraints," Proceedings of Korea Telecom International Symposium '94, 1994. [18] Y. S. Myung, H. G. Kim and D. W. Tcha, "Optimal Load Balancing in SONET Bidirectional Rings," Operations Research, Vol, 45, 148-152, 1997. [19] H. Sakauchi, Y. Nishimura and S. Hasegawa, "A Self- Healing Network with an Economical Spare-Channel Assignment," Globecom'90, 438-443, 1990. [20] J. Suurballe and R. Tarjan, "A Quick Method of Finding Shortest Pairs of Disjoint Paths," Networks, V.14, 325-336, 1984. [21] D. W. Tcha, "Design Issues in Survivable Synchronous Optical Transmission Networks," Proceedings of Korea Telecom International Symposium '94, 35-41, 1994. [22] B. Venables, W. Grover and M. MacGregor, "Two Strategies for Spare Capacity Placement in Mesh Restorable Networks," ICC'93, 267-271, 1993. [23] O. J. Wasem," An Algorithm for Designing Rings for Survivable Fiber Networks," IEEE Transactions on Reliability, Vol. 40, 428-432, 1991 [24] O. J. Wasem, T.-H. Wu and R. H. Cardwell, " Survivable SONET Networks -Design Methodology," IEEE Journal on Selected Areas in Communications, Vol. 12, No. 1, 205-212, 1994. [25] T.-H. Wu and R. C. Lau, "A Class of Self-Healing Ring Architectures for SONET Network Applications,"

IEEE Transactions on Communications., V.40, No.11, 1746-1756, 1992. [26] T.-H. Wu, Fiber Network Service Survivability, Artech House, 1992. [27] T.-H. Wu, D. J. Kolar and R. H. Cardwell, "Survivable Network Architectures for Broad-Band Fiber Optic Networks : Model and Performance Comparison," Journal of Lightwave Technology, Vol.6, No.11, 1698-1709, 1988. [28] T.-H. Wu, "A Passive Protected Self-Healing Mesh Network Architectures and Applications," IEEE/ACM Transactions on Networking, Vol.2, No.1, 40-52, 1994. [29] M. G. Yoon and J. R. Current, "Dual Based Heuristic for Hub Location and Network Design Problem," Working Paper, Dept. of Management Science, Ohio State University, 1996. [30] M. G. Yoon, On Facility-Network Design for Broadband Communications, Ph.D. Desertation, Deptment of Management Science, KAIST, 1992. [31] M. G. Yoon, Y. H. Baek and D. W. Tcha, "Optimal Design of a Distributed Fiber Transport Network with Hubbing Topology," European Journal of Operational Research, Vol. 104, No. 3, 510-520, 1998.