skip to main content
article

Generalized survivable network

Published: 01 August 2007 Publication History

Abstract

Two important requirements for future backbone networks are full survivability against link failures and dynamic bandwidth provisioning. We demonstrate how these two requirements can be met by introducing a new survivable network concept called the Generalized Survivable Network (GSN), which has the special property that it remains survivable no matter how traffic is provisioned dynamically, as long as the input and output constraints at the nodes are fixed. A rigorous mathematical framework for designing the GSN is presented. In particular, we focus on the GSN Capacity Planning Problem, which finds the edge capacities for a given physical network topology with the input/output constraints at the nodes. We employ fixed single-path routing which leads to wide-sense nonblocking GSNs. We show how the initial, infeasible formal mixed integer linear programming formulation can be transformed into a more feasible problem using the duality transformation. A procedure for finding the realizable lower bound for the cost is also presented. A two-phase approach is proposed for solving the GSNCPP. We have carried out numerical computations for ten networks with different topologies and found that the cost of a GSN is only a fraction (from 39% to 97%) more than the average cost of a static survivable network. The framework is applicable to survivable network planning for ASTN/ASON, VPN, and IP networks as well as bandwidth-on-demand resource allocation.

References

[1]
{1} News Release, "AT&T Deploys Nationwide Intelligent Optical Network" AT&T, San Antonio, TX, 2002 {Online}. Available: http://www. att.com/news/2002/02/11-4206
[2]
{2} A. Gladisch and M. K. Jaeger, "Concepts and standardization of ASON/GMPLS for transport networks: Applications and tests in Europe," in Proc. Plenary Session 5, Asia-Pacific Opt. Commun. Conf., Beijing, Nov. 6-10, 2005.
[3]
{3} G. Birkan et al., "Making a case for using integer programming to design DWDM networks," Opt. Netw. Mag., vol. 4, no. 6, pp. 107-119, 2003.
[4]
{4} D. Leung and W. D. Grover, "Capacity planning of survivable mesh-based transport networks under demand uncertainty," Photon. Netw. Commun., vol. 10, no. 2, pp. 123-140, 2005.
[5]
{5} W. D. Grover, "The protected working capacity envelope concept: An alternate paradigm for automated service provisioning," IEEE Commun. Mag., vol. 42, no. 1, pp. 62-69, 2004.
[6]
{6} C. Clos, "A study of nonblocking networks," Bell Syst. Tech. J., vol. 32, pp. 406-424, 1953.
[7]
{7} V. E. Benes, Mathematical Theory of Connecting Networks and Telephone Traffic. New York: Academic, 1965.
[8]
{8} K. W. Cheung, "Acousto-optic tunable filters in dense WDM networks: System issues and network applications," IEEE J. Sel. Areas Commun., vol. 8, pp. 1015-1025, 1990.
[9]
{9} J. Sharony, S. Jiang, T. E. Stern, and K. W. Cheung, "Wavelength-rearrangeable and strictly nonblocking networks," Electron. Lett., vol. 28, pp. 536-7, 1992.
[10]
{10} J. A. Fingerhut, S. Suri, and J. Turner, "Designing least-cost nonblocking broadband networks," J. Algorithms, vol. 24, no. 2, pp. 287-309, 1997.
[11]
{11} N. G. Duffield et al., "A flexible model for resource management in virtual private networks," in Proc. ACM Sigcomm'99, Computer Commun. Rev., 1999, vol. 29, pp. 95-108.
[12]
{12} S. Erlander and N. F. Stewart, The Gravity Model in Transportation Analysis : Theory and Extensions. Utrecht, The Netherlands: VSP, 1990.
[13]
{13} R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms and Applications. Upper Saddle River, NJ: Prentice-Hall, 1993.
[14]
{14} W. D. Grover, V. Rawat, and M. H. MacGregor, "Fast heuristic principle for spare capacity placement in mesh-restorable SONET/SDH transport networks," Electron. Lett., vol. 33, pp. 195-6, 1997.
[15]
{15} Y. Liu, D. Tipper, and P. Siripongwutikorn, "Approximating optimal spare capacity allocation by successive survivable routing," IEEE/ACM Trans. Netw., vol. 13, no. 1, pp. 198-211, Feb. 2005.
[16]
{16} K. S. Ho and K. W. Cheung, "Capacity planning of link restorable optical networks under dynamic change of traffic," in Proc. APOC'05, Shanghai, China, Nov. 6-10, 2005, vol. 6022, 6022-38.
[17]
{17} K. S. Ho and K. W. Cheung, "A framework for planning survivable optical mesh network with dynamic demands and single link failure protection," in Proc. APOC'04, Beijing, Nov. 04, 2004, vol. 5626, 5626-56.
[18]
{18} R. R. Iraschko, M. H. MacGregor, and W. D. Grover, "Optimal capacity placement for path restoration in STM or ATM mesh-survivable networks," IEEE/ACM Trans. Netw., vol. 6, no. 3, pp. 325-336, Jun. 1998.
[19]
{19} P. Batchelor et al., "Study on the implementation of optical transparent transport networks in the European environment-Results of the research project Cost 239," Photonic Network Commun., vol. 2, no. 1, pp. 15-32, 2000.
[20]
{20} B. V. Caenegem, W. V. Parys, F. D. Turck, and P. M. Demeester, "Dimensioning of survivable WDM networks," IEEE J. Sel. Areas Commun., vol. 16, no. 7, pp. 1146-1157, Sep. 1998.
[21]
{21} ILOG CPLEX 9.0 User's Manual. McClean, VA: ILOG Inc., 2003.

Cited By

View all
  • (2017)Novel Survivable Logical Topology Routing by Logical Protecting Spanning Trees in IP-Over-WDM NetworksIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2016.263936225:3(1673-1685)Online publication date: 1-Jun-2017

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 15, Issue 4
August 2007
243 pages

Publisher

IEEE Press

Publication History

Published: 01 August 2007
Published in TON Volume 15, Issue 4

Author Tags

  1. ASON
  2. ASTN
  3. IP network
  4. VPN
  5. network design
  6. nonblocking network
  7. survivable network

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2017)Novel Survivable Logical Topology Routing by Logical Protecting Spanning Trees in IP-Over-WDM NetworksIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2016.263936225:3(1673-1685)Online publication date: 1-Jun-2017

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media