IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v45y1999i2p238-252.html
   My bibliography  Save this article

Design of Communication Networks with Survivability Constraints

Author

Listed:
  • Young-Soo Myung

    (Department of Business Administration, Dankook University, Cheonan, Chungnam 330-714, Korea)

  • Hyun-joon Kim

    (Department of Management Information Systems, University of Ulsan, Ulsan, Korea)

  • Dong-wan Tcha

    (Graduate School of Management, Korea Advanced Institute of Science and Technology, Seoul, Korea)

Abstract

The rapid growth of telecommunication capacity, driven in part by the wide-ranging deployment of fiber-optic technology has led to increasing concern regarding the survivability of such networks. In communication networks, survivability is usually defined as the percentage of total traffic surviving some network failures in the worst case. Most of the survivable network design models proposed to date indirectly ensure network survivability by invoking a connectivity constraint, which calls for a prespecified number of paths between every distinct pair of nodes in the network. In this paper, we introduce a new network design model which directly addresses survivability in terms of a survivability constraint which specifies the allowable level of lost traffic during a network failure under prescribed conditions. The new model enables a network designer to consider a richer set of alternative network topologies than the existing connectivity models, and encompasses the connectivity models as special cases. The paper presents a procedure to compute link survivability, develops an integer programming formulation of the proposed survivability model, and discusses a special case of practical interest and its associated heuristic procedure. The proposed heuristic is tested on data from real-world problems as well as randomly generated problems.

Suggested Citation

  • Young-Soo Myung & Hyun-joon Kim & Dong-wan Tcha, 1999. "Design of Communication Networks with Survivability Constraints," Management Science, INFORMS, vol. 45(2), pages 238-252, February.
    • Handle: RePEc:inm:ormnsc:v:45:y:1999:i:2:p:238-252
    DOI: 10.1287/mnsc.45.2.238
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.45.2.238
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.45.2.238?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Steven Cosares & David N. Deutsch & Iraj Saniee & Ondria J. Wasem, 1995. "SONET Toolkit: A Decision Support System for Designing Robust and Cost-Effective Fiber-Optic Networks," Interfaces, INFORMS, vol. 25(1), pages 20-40, February.
    2. Clyde L. Monma & David F. Shallcross, 1989. "Methods for Designing Communications Networks with Certain Two-Connected Survivability Constraints," Operations Research, INFORMS, vol. 37(4), pages 531-541, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Akgün, Ibrahim & Tansel, Barbaros Ç. & Kevin Wood, R., 2011. "The multi-terminal maximum-flow network-interdiction problem," European Journal of Operational Research, Elsevier, vol. 211(2), pages 241-251, June.
    2. Myung, Young-Soo & Kim, Hyun-joon, 2004. "A cutting plane algorithm for computing k-edge survivability of a network," European Journal of Operational Research, Elsevier, vol. 156(3), pages 579-589, August.
    3. Mohit Tawarmalani & Yanjun Li, 2011. "Multi‐period maintenance scheduling of tree networks with minimum flow disruption," Naval Research Logistics (NRL), John Wiley & Sons, vol. 58(5), pages 507-530, August.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Juan Ma & Foad Mahdavi Pajouh & Balabhaskar Balasundaram & Vladimir Boginski, 2016. "The Minimum Spanning k -Core Problem with Bounded CVaR Under Probabilistic Edge Failures," INFORMS Journal on Computing, INFORMS, vol. 28(2), pages 295-307, May.
    2. Yogesh Agarwal, 2013. "Design of Survivable Networks Using Three- and Four-Partition Facets," Operations Research, INFORMS, vol. 61(1), pages 199-213, February.
    3. Gunhak Lee & Ningchuan Xiao, 2009. "Examining the tradeoff between residential broadband service coverage and network connectivity using a bi‐objective facility location model," Papers in Regional Science, Wiley Blackwell, vol. 88(3), pages 547-562, August.
    4. Luss, Hanan & Rosenwein, Moshe B., 1997. "Operations Research applications: Opportunities and accomplishments," European Journal of Operational Research, Elsevier, vol. 97(2), pages 220-244, March.
    5. Frederick Kaefer & June S. Park, 1998. "Interconnecting LANs and a FDDI Backbone Using Transparent Bridges: A Model and Solution Algorithms," INFORMS Journal on Computing, INFORMS, vol. 10(1), pages 25-39, February.
    6. Lawrence V. Snyder & Mark S. Daskin, 2005. "Reliability Models for Facility Location: The Expected Failure Cost Case," Transportation Science, INFORMS, vol. 39(3), pages 400-416, August.
    7. Young‐Soo Myung & Hyun‐Joon Kim, 2007. "Network disconnection problems in a centralized network," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(7), pages 710-719, October.
    8. Peter C. Bell & Chris K. Anderson, 2002. "In Search of Strategic Operations Research/Management Science," Interfaces, INFORMS, vol. 32(2), pages 28-40, April.
    9. Agarwal, Y.K. & Venkateshan, Prahalad, 2014. "Survivable network design with shared-protection routing," European Journal of Operational Research, Elsevier, vol. 238(3), pages 836-845.
    10. Kennington, Jeffery L. & Olinick, Eli V. & Spiride, Gheorghe, 2007. "Basic mathematical programming models for capacity allocation in mesh-based survivable networks," Omega, Elsevier, vol. 35(6), pages 629-644, December.
    11. Dorit S. Hochbaum & Eli V. Olinick, 2001. "The Bounded Cycle-Cover Problem," INFORMS Journal on Computing, INFORMS, vol. 13(2), pages 104-119, May.
    12. Peter C. Bell & Chris K. Anderson & Stephen P. Kaiser, 2003. "Strategic Operations Research and the Edelman Prize Finalist Applications 1989--1998," Operations Research, INFORMS, vol. 51(1), pages 17-31, February.
    13. Ellis L. Johnson & George L. Nemhauser & Martin W.P. Savelsbergh, 2000. "Progress in Linear Programming-Based Algorithms for Integer Programming: An Exposition," INFORMS Journal on Computing, INFORMS, vol. 12(1), pages 2-23, February.
    14. Cabral, Edgar Alberto & Erkut, Erhan & Laporte, Gilbert & Patterson, Raymond A., 2007. "The network design problem with relays," European Journal of Operational Research, Elsevier, vol. 180(2), pages 834-844, July.
    15. Juan Ma & Balabhaskar Balasundaram, 2019. "On the chance-constrained minimum spanning k-core problem," Journal of Global Optimization, Springer, vol. 74(4), pages 783-801, August.
    16. Konak, Abdullah & Bartolacci, Michael R., 2007. "Designing survivable resilient networks: A stochastic hybrid genetic algorithm approach," Omega, Elsevier, vol. 35(6), pages 645-658, December.
    17. Abdullah Konak & Alice E. Smith, 2011. "Efficient Optimization of Reliable Two-Node Connected Networks: A Biobjective Approach," INFORMS Journal on Computing, INFORMS, vol. 23(3), pages 430-445, August.
    18. Hyun Kim, 2012. "P-hub protection models for survivable hub network design," Journal of Geographical Systems, Springer, vol. 14(4), pages 437-461, October.
    19. Amiri, Ali & Pirkul, Hasan, 1999. "Routing and capacity assignment in backbone communication networks under time varying traffic conditions," European Journal of Operational Research, Elsevier, vol. 117(1), pages 15-29, August.
    20. Gianpaolo Ghiani & Gilbert Laporte & Frédéric Semet, 2006. "The Black and White Traveling Salesman Problem," Operations Research, INFORMS, vol. 54(2), pages 366-378, April.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:45:y:1999:i:2:p:238-252. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.