A DECOMPOSITION APPROACH FOR SPARE CAPACITY ASSIGNMENT FOR PATH RESTORABLE MESH NETWORKS

J.L. Kennington, V.S.S. Nair, and G. Spiride

References

  1. [1] W. Grover, Mesh-based survivable networks: Options andstrategies for optical, MPLS, SONET, and ATM networks(Upper Saddle River, NJ: Prentice-Hall PTR, 2004).
  2. [2] R. Ramaswami & K. Sivarajan, Optical networks: A practical perspective (San Francisco, CA: Morgan Kauffman Publishers Inc., 2002).
  3. [3] A. Balakrishnan, T. Magnanti, J. Sokol & Y. Wang, Telecommunication link restoration planning with multiple facility types, Annals of Operations Research, 106, 2001, 127–154. doi:10.1023/A:1014509708610
  4. [4] A. Balakrishnan, T.L. Magnanti, & P. Mirchandani, Designing hierarchical survivable networks, Operations Research, 46(1), 1998, 116–136.
  5. [5] B. Coan, W. Leland, M. Vecchi, A. Weinrib et al. Usingdistributed topology update and preplanned configurations to achieve trunk network survivability, IEEE Trans. on Reliability, 40(4), 1991, 404–416. doi:10.1109/24.93760
  6. [6] R. Doverspike & B. Wilson, Comparison of capacity efficiency of DCS network restoration routing techniques, Journal of Network and Systems Management, 2(2), 1994, 95–123. doi:10.1007/BF02139308
  7. [7] M. Herzberg, S.J. Bye, & A. Utano, The hop-limit approach for spare-capacity assignment in survivable networks, IEEE/ACM Trans. on Networking, 3(6), 1995, 775–784. doi:10.1109/90.477723
  8. [8] R.R. Iraschko, M.H. MacGregor, & W.D. Grover, Optimalcapacity placement for path restoration in STM or ATM mesh-survivable networks, IEEE/ACM Trans. on Networking, 6(3), 1998, 325–336. doi:10.1109/90.700896
  9. [9] J. Kennington & J. Whitler, An efficient decomposition algorithm to optimize spare capacity in a telecommunications network, INFORMS Journal on Computing, 11, 1999, 149–160.
  10. [10] K. Murakami & H. Kim, Optimal capacity and flow assignment for self-healing ATM networks based on line and end-to-end restoration, IEEE/ACM Trans. on Networking, 6(2), 1998, 207–221. doi:10.1109/90.664269
  11. [11] H. Sakauchi, Y. Nishimura, & S. Hasegawa, A self-healing network with economical spare-channel assignment, Proc. IEEE Global Telecomm. Conf. (GLOBECOM), San Diego, CA, 1990, 403.1.1–403.1.16.
  12. [12] P. Belotti, Multi-commodity network design with survivability constraints: Some models and Algorithms, Ph.D. Thesis, Politecnico di Milano, Dipartimento di Elettronica ed Informazione, Spring 2003.
  13. [13] J. Kennington, E. Olinick, & G. Spiride, Basic mathematical programming models for capacity allocation in mesh-based survivable networks, OMEGA, 2007 (to appear).
  14. [14] W. Ben-Ameur & L. Gouveia, Some recent contributions to network optimization, Networks, 44, 2004, 27–30. doi:10.1002/net.20010
  15. [15] J. Kennington, V.S.S. Nair, & G. Spiride, optimal spare capacity assignment for path restorable mesh networks: Cuts, decomposition, and an empirical analysis, Technical Report 06-EMIS-02, Department of Engineering Management, Information, and Systems, Southern Methodist University, Dallas, TX, 2006.
  16. [16] M. Groetschel, C. Monma, & M. Stoer, Computational results with a cutting plane algorithm for designing communication networks with low-connectivity constraints, Operations Research, 40(2), 1992, 309–330.
  17. [17] M. Groetschel, C. Monma, & M. Stoer, Polyhedral and computational investigations for designing communication networks with high survivability requirements, Operations Research, 43(6), 1995, 1012–1024.
  18. [18] J. Kalvenes, J. Kennington, & E. Olinick, Base station location and service assignments in w-cdma networks, INFORMS Journal on Computing, 18(3), 2006, 366–376. doi:10.1287/ijoc.1040.0129
  19. [19] W. Grover & D. Stamatelakis, Cycle-oriented distributed preconfiguration: Ring-like speed with mesh-like capacity for self-planning mesh network restoration, Proc. Int. Conf. Communications (ICC), Altanta, GA, 1998, 537–543.
  20. [20] D. Stamatelakis & W. Grover, Theoretical underpinnings for the efficiency of restorable networks using pre-configured p-cycles, IEEE Trans. on Communications, 48(8), 2000, 1262–1265. doi:10.1109/26.864163
  21. [21] P. Belotti & F. Malucelli, Shared protection network design: valid inequalities and a decomposition approach, Technical Report, Politecnico di Milano, Dipartimento di Elettronica ed Informazione, Operations Research Group, 2003.
  22. [22] M. Lewis, Spare capacity planning for telecommunications networks: Models and algorithms for path restoration, Ph.D.Thesis, School of Engineering, Southern Methodist University, Dallas, TX, 2000.
  23. [23] R. Gomory & T. Hu, Multi-terminal network flows, Journal of SIAM, 9, 1961, 551–570.
  24. [24] M. Abou-Sayed, J. Kennington, & S. Nair, Joint working and spare capacity assignment in a link restorable mesh network, Technical Report 96-CSE-16, Department of Computer Science and Engineering, Southern Methodist University, Dallas, TX, 1996.
  25. [25] M. Parsa, Q. Zhu, & J. Garcia-Aceves, An iterative algorithm for delay-constrained minimum cost multicasting, IEEE/ACM Trans. on Networking, 6(4), 1998, 461–474. doi:10.1109/90.720901

Important Links:

Go Back