skip to main content
article

ILP formulations for p-cycle design without candidate cycle enumeration

Published: 01 February 2010 Publication History

Abstract

The concept of p-cycle (preconfigured protection cycle) allows fast and efficient span protection in wavelength division multiplexing (WDM) mesh networks. To design p-cycles for a given network, conventional algorithms need to enumerate cycles in the network to form a candidate set, and then use an integer linear program (ILP) to find a set of p-cycles from the candidate set. Because the size of the candidate set increases exponentially with the network size, candidate cycle enumeration introduces a huge number of ILP variables and slows down the optimization process. In this paper, we focus on p-cycle design without candidate cycle enumeration. Three ILPs for solving the problem of spare capacity placement (SCP) are first formulated. They are based on recursion, flow conservation, and cycle exclusion, respectively. We show that the number of ILP variables/constraints in our cycle exclusion approach only increases linearly with the network size. Then, based on cycle exclusion, we formulate an ILP for solving the joint capacity placement (JCP) problem. Numerical results show that our ILPs are very efficient in generating p-cycle solutions.

References

[1]
W. D. Grover and D. Stamatelakis, "Cycle-oriented distributed preconfiguration: Ring-like speed with mesh-like capacity for self-planning network restoration," in Proc. IEEE ICC, Jun. 1998, vol. 1, pp. 537-543.
[2]
D. A. A. Mello, D. A. Schupke, and H. Waldman, "A matrix-based analytical approach to connection unavailability estimation in shared backup path protection," IEEE Commun. Lett., vol. 9, no. 9, pp. 844-846, Sep. 2005.
[3]
H. Liu and F. A. Tobagi, "Traffic grooming in WDM/SONET BLSR rings with multiple line speeds," in Proc. IEEE GLOBECOM, Dec. 2005, vol. 4, pp. 2096-2101.
[4]
D. Stamatelakis and W. D. Grover, "Theoretical underpinnings for the efficiency of restorable networks using preconfigured cycles ("p-cycles")," IEEE Trans. Commun., vol. 48, no. 8, pp. 1262-1265, Aug. 2000.
[5]
D. Stamatelakis and W. D. Grover, "IP layer restoration and network planning based on virtual protection cycles," IEEE J. Sel. Areas Commun., vol. 18, no. 10, pp. 1938-1949, Oct. 2000.
[6]
A. Kodian, W. D. Grover, J. Slevinsky, and D. Moore, "Ring-mining to p-cycles as a target architecture: Riding demand growth into network efficiency," in Proc. 19th Annu. NFOEC, Sep. 2003, pp. 1543-1552.
[7]
G. X. Shen and W. D. Grover, "Design of protected working capacity envelopes based on p-cycles: An alternative framework for survivable automated lightpath provisioning," in Performance Evaluation and Planning Methods for the Next Generation Internet, A. Girard, B. Sansò, and F. Vazquez-Abad, Eds. Norwell, MA: Kluwer, 2005.
[8]
G. X. Shen and W. D. Grover, "Performance of protected working capacity envelopes based on p-cycles: Fast, simple, and scalable dynamic service provisioning of survivable services," in Proc. APOC, Nov. 2004, vol. 5626, pp. 519-533.
[9]
D. A. Schupke, C. G. Gruber, and A. Autenrieth, "Optimal configuration of p-cycles in WDM network," in Proc. IEEE ICC, May 2002, vol. 5, pp. 2761-2765.
[10]
W. S. He, J. Fang, and A. K. Somani, "A p-cycle based survivable design for dynamic traffic in WDM networks," in Proc. IEEE GLOBECOM, Dec. 2005, vol. 4, pp. 1869-1873.
[11]
H. Huang and J. A. Copeland, "A series of Hamiltonian cycle-based solutions to provide simple and scalable mesh optical network resilience," IEEE Commun. Mag., vol. 40, no. 11, pp. 46-51, Nov. 2002.
[12]
D. A. Schupke, "Multiple failure survivability in WDM networks with p-cycles," in Proc. Circuits Syst., Int. Symp. ISCAS '03, May 2003, vol. 3, pp. 866-869.
[13]
D. A. Schupke, "The tradeoff between the number of deployed p-cycles and the survivability to dual fiber duct failures," in Proc. IEEE ICC, May 2003, vol. 2, pp. 1428-1432.
[14]
A. Kodian, A. Sack, and W. D. Grover, "p-cycle network design with hop limits and circumference limits," in Proc. 1st Int. Conf. Broadband Netw. BroadNets, 2004, pp. 244-253.
[15]
W. Li, J. Doucette, and M. Zuo, "p-cycle network design for specified minimum dual-failure restorability," in Proc. IEEE ICC, Jun. 2007, pp. 2204-2210.
[16]
D. A. Schupke, "Analysis of p-cycle capacity in WDM networks," Photon. Netw. Commun., vol. 12, no. 1, pp. 41-51, Jul. 2006.
[17]
H. N. Nguyen, D. Habibi, V. Q. Phung, S. Lachowicz, K. Lo, and B. Kang, "Joint optimization in capacity design of networks with p-cycle using the fundamental cycle set," in Proc. IEEE GLOBECOM, Nov. 2006, pp. 1-5, QRP02-5.
[18]
W. D. Grover and J. Doucette, "Advances in optical network design with p-cycles: Joint optimization and pre-selection of candidate p-cycles," in Proc. IEEE LEOS Summer Topic., Jul. 2002, pp. 49-50.
[19]
J. Doucette, D. He, W. D. Grover, and O. Yang, "Algorithmic approaches for efficient enumeration of candidate p-cycles and capacitated p-cycle network design," in Proc. 4th Int. Workshop DRCN, Oct. 2003, pp. 212-220.
[20]
H. X. Zhang and O. Yang, "Finding protection cycles in DWDM networks," in Proc. IEEE ICC, May 2002, vol. 5, pp. 2756-2760.
[21]
C. Liu and L. Ruan, "Finding good candidate cycles for efficient p-cycle network design," in Proc. IEEE ICCCN, 2004, pp. 321-326.
[22]
D. A. Schupke, "An ILP for optimal p-cycle selection without cycle enumeration," in Proc. 8th Conf. ONDM, 2004.
[23]
A. Sack and W. D. Grover, "Hamiltonian p-cycles for fiber-level protection in homogeneous and semi-homogeneous optical networks," IEEE Netw., vol. 18, no. 2, pp. 49-56, Apr. 2004.
[24]
A. Kodian and W. D. Grover, "Failure-independent path-protecting p-cycles: Efficient and simple fully preconnected optical-path protection," J. Lightw. Technol., vol. 23, no. 10, pp. 3241-3259, Oct. 2005.
[25]
G. X. Shen and W. D. Grover, "Extending the p-cycle concept to path segment protection for span and node failure recovery," IEEE J. Sel. Areas Commun., vol. 21, no. 8, pp. 1306-1319, Oct. 2003.
[26]
W. D. Grover, Mesh-Based Survivable Networks: Options and Strategies for Pptical, MPLS, SONET and ATM Networking. Englewood Cliffs, NJ: Prentice-Hall PTR, 2003.
[27]
B. J. Donald, "Finding all the elementary circuits of a directed graph," SIAM J. Comput., vol. 4, no. 1, pp. 77-84, Mar. 1975.
[28]
B. Jaumard, C. Rocha, D. Baloukov, and W. Grover, "A column generation approach for design of networks using path-protecting p-cycles," in Proc. 6th Int. Workshop DRCN, Oct. 2007.
[29]
C. Rocha and B. Jaumard, "Revisiting p-cycles/FIPP p-cycles vs. shared link/path protection," in Proc. 17th ICCCN, Aug. 2008, pp. 1-6.
[30]
R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications. Upper Saddle River, NJ: Prentice-Hall, 1993.
[31]
CPLEX Solver {Online}. Available: www.ilog.com
[32]
P. Batchelor et al., "Ultra high capacity optical transmission networks," Final rep. action COST 239, 1999.

Cited By

View all
  • (2017)Diversity Coding in Two-Connected NetworksIEEE/ACM Transactions on Networking10.1109/TNET.2017.268490925:4(2308-2319)Online publication date: 1-Aug-2017
  • (2016)Finding Tie-sets with the Minimal Number of Total Elements for Effective Failure RecoveryProceedings of the 7th International Conference on Computing Communication and Networking Technologies10.1145/2967878.2967888(1-5)Online publication date: 6-Jul-2016
  • (2016)Cloud service provisioning in two types of DCN with awareness of delay and link failure probabilityPhotonic Network Communications10.1007/s11107-015-0537-831:2(217-227)Online publication date: 1-Apr-2016
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 18, Issue 1
February 2010
332 pages

Publisher

IEEE Press

Publication History

Published: 01 February 2010
Revised: 15 November 2008
Received: 05 January 2008
Published in TON Volume 18, Issue 1

Author Tags

  1. integer linear program (ILP)
  2. p-cycle (pre-configured protection cycle)
  3. protection
  4. wavelength division multiplexing (WDM) mesh networks

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

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

Other Metrics

Citations

Cited By

View all
  • (2017)Diversity Coding in Two-Connected NetworksIEEE/ACM Transactions on Networking10.1109/TNET.2017.268490925:4(2308-2319)Online publication date: 1-Aug-2017
  • (2016)Finding Tie-sets with the Minimal Number of Total Elements for Effective Failure RecoveryProceedings of the 7th International Conference on Computing Communication and Networking Technologies10.1145/2967878.2967888(1-5)Online publication date: 6-Jul-2016
  • (2016)Cloud service provisioning in two types of DCN with awareness of delay and link failure probabilityPhotonic Network Communications10.1007/s11107-015-0537-831:2(217-227)Online publication date: 1-Apr-2016
  • (2014)On signaling-free failure dependent restoration in all-optical mesh networksIEEE/ACM Transactions on Networking10.1109/TNET.2013.227259922:4(1067-1078)Online publication date: 1-Aug-2014
  • (2011)Energy saving and cost reduction in multi-granularity green optical networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2010.10.00955:3(676-688)Online publication date: 1-Feb-2011
  • (2008)Preconfigured structures for survivable WDM networksProceedings of the 2008 International Conference on Advanced Infocomm Technology10.1145/1509315.1509392(1-7)Online publication date: 29-Jul-2008

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