Abstract

A FIPP-iterative joint design (IJD) approach is proposed to fast design failure-independent path-protecting (FIPP) p-cycle networks. The basic procedure is first to enumerate a set of candidate cycles, then to create one or several disjoint route sets for each cycle by the difficult share first method or full protection method, and finally to iteratively place FIPP p-cycles. Multiple route options are provided for each demand and standard protection efficiency is considered to choose the best FIPP p-cycle. A pseudothreshold effect of the number of candidate routes per demand to standard spare capacity cost is observed. Compared to the optimal designs, the FIPP-IJD method greatly improves solving speed without drastically reducing solution quality.

© 2007 Optical Society of America

PDF Article

References

  • View by:
  • |
  • |
  • |

  1. W. D. Grover and D. Stamatelakis, 'Cycle-oriented distributed preconfiguration: ring-like speed with mesh-like capacity for self-planning network restoration,' in Proceedings of IEEE International Conference on Communications (IEEE, 1998), pp. 537-543.
  2. D. A. Schupke, C. G. Gruber, and A. Autenrieth, 'Optimal configuration of p-cycles in WDM networks,' in Proceedings of IEEE International Conference on Communications (IEEE, 2002), pp. 2761-2765.
  3. G. Shen and W. D. Grover, 'Design and performance of protected working capacity envelopes based on p-cycles for dynamic provisioning of survivable services,' J. Opt. Netw. 4, 361-390 (2005).
    [CrossRef]
  4. D. A. Schupke, 'Automatic protection switching for p-cycles in WDM networks,' Opt. Switching Networking 2, 35-48 (2005).
  5. D. Stamatelakis and W. D. Grover, 'IP layer restoration and network planning based on virtual protection cycles,' IEEE J. Sel. Areas Commun. 18, 1938-1949 (2000).
  6. G. 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. 21, 1306-1319 (2003).
    [CrossRef]
  7. J. Doucette, W. D. Grover, and P. A. Giese, 'Physical-layer p-cycles adapted for router-level node protection: a multi-layer design and operation strategy,' IEEE J. Sel. Areas Commun. 25, 963-973 (2007).
  8. A. Kodian and W. D. Grover, 'Failure-independent path-protecting p-cycles: efficient and simple fully preconnected optical-path protection,' J. Lightwave Technol. 23, 3241-3259 (2005).
    [CrossRef]
  9. A. Kodian, W. D. Grover, and J. Doucette, 'A disjoint route-sets approach to design of path-protecting p-cycle networks,' in Proceedings of Design of Reliable Communication Networks (IEEE, 2005), pp. 231-238.
  10. B. Jaumard, C. Rocha, D. Baloukov, and W. D. Grover, 'A column generation approach for design of networks using path-protecting p-cycles,' in the Sixth International Workshop on Design of Reliable Communication Networks (DRCN) 2007, La Rochelle, France, 7-10 October 2007.
  11. 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 Proceedings of Design of Reliable Communication Networks (IEEE, 2003), pp. 212-220.
  12. Z. Zhang, W. D. Zhong, and B. Mukherjee, 'A heuristic method for design of survivable WDM networks with p-cycles,' IEEE Commun. Lett. 8, 467-469 (2004).
    [CrossRef]
  13. W. D. Grover and J. Doucette, 'Advances in optical network design with p-cycles: joint optimization and pre-selection of candidate p-cycles,' in Proceedings of IEEE-LEOS Summer Topical Meeting (IEEE, 2002), pp. 49-50.
  14. A. Kodian, A. Sack, and W. D. Grover, 'p-Cycle network design with hop limits and circumference limits,' in Proceedings of First International Conference on Broadband Networks (IEEE, 2004), pp. 244-253.
  15. D. A. Schupke, 'Analysis of p-cycle capacity in WDM networks,' Photonic Network Commun. 12, 41-51 (2006).
  16. D. B. Johnson, 'Finding all the elementary circuits of a directed graph,' SIAM J. Comput. 4, 77-84 (1975).
    [CrossRef]
  17. J. Doucette, 'Advances on design and analysis of mesh-restorable networks,' Ph.D. dissertation (University of Alberta, 2004).

2007 (1)

J. Doucette, W. D. Grover, and P. A. Giese, 'Physical-layer p-cycles adapted for router-level node protection: a multi-layer design and operation strategy,' IEEE J. Sel. Areas Commun. 25, 963-973 (2007).

2006 (1)

D. A. Schupke, 'Analysis of p-cycle capacity in WDM networks,' Photonic Network Commun. 12, 41-51 (2006).

2005 (3)

2004 (1)

Z. Zhang, W. D. Zhong, and B. Mukherjee, 'A heuristic method for design of survivable WDM networks with p-cycles,' IEEE Commun. Lett. 8, 467-469 (2004).
[CrossRef]

2003 (1)

G. 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. 21, 1306-1319 (2003).
[CrossRef]

2000 (1)

D. Stamatelakis and W. D. Grover, 'IP layer restoration and network planning based on virtual protection cycles,' IEEE J. Sel. Areas Commun. 18, 1938-1949 (2000).

1975 (1)

D. B. Johnson, 'Finding all the elementary circuits of a directed graph,' SIAM J. Comput. 4, 77-84 (1975).
[CrossRef]

Autenrieth, A.

D. A. Schupke, C. G. Gruber, and A. Autenrieth, 'Optimal configuration of p-cycles in WDM networks,' in Proceedings of IEEE International Conference on Communications (IEEE, 2002), pp. 2761-2765.

Baloukov, D.

B. Jaumard, C. Rocha, D. Baloukov, and W. D. Grover, 'A column generation approach for design of networks using path-protecting p-cycles,' in the Sixth International Workshop on Design of Reliable Communication Networks (DRCN) 2007, La Rochelle, France, 7-10 October 2007.

Doucette, J.

J. Doucette, W. D. Grover, and P. A. Giese, 'Physical-layer p-cycles adapted for router-level node protection: a multi-layer design and operation strategy,' IEEE J. Sel. Areas Commun. 25, 963-973 (2007).

J. Doucette, 'Advances on design and analysis of mesh-restorable networks,' Ph.D. dissertation (University of Alberta, 2004).

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 Proceedings of Design of Reliable Communication Networks (IEEE, 2003), pp. 212-220.

A. Kodian, W. D. Grover, and J. Doucette, 'A disjoint route-sets approach to design of path-protecting p-cycle networks,' in Proceedings of Design of Reliable Communication Networks (IEEE, 2005), pp. 231-238.

W. D. Grover and J. Doucette, 'Advances in optical network design with p-cycles: joint optimization and pre-selection of candidate p-cycles,' in Proceedings of IEEE-LEOS Summer Topical Meeting (IEEE, 2002), pp. 49-50.

Giese, P. A.

J. Doucette, W. D. Grover, and P. A. Giese, 'Physical-layer p-cycles adapted for router-level node protection: a multi-layer design and operation strategy,' IEEE J. Sel. Areas Commun. 25, 963-973 (2007).

Grover, W. D.

J. Doucette, W. D. Grover, and P. A. Giese, 'Physical-layer p-cycles adapted for router-level node protection: a multi-layer design and operation strategy,' IEEE J. Sel. Areas Commun. 25, 963-973 (2007).

G. Shen and W. D. Grover, 'Design and performance of protected working capacity envelopes based on p-cycles for dynamic provisioning of survivable services,' J. Opt. Netw. 4, 361-390 (2005).
[CrossRef]

A. Kodian and W. D. Grover, 'Failure-independent path-protecting p-cycles: efficient and simple fully preconnected optical-path protection,' J. Lightwave Technol. 23, 3241-3259 (2005).
[CrossRef]

G. 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. 21, 1306-1319 (2003).
[CrossRef]

D. Stamatelakis and W. D. Grover, 'IP layer restoration and network planning based on virtual protection cycles,' IEEE J. Sel. Areas Commun. 18, 1938-1949 (2000).

W. D. Grover and D. Stamatelakis, 'Cycle-oriented distributed preconfiguration: ring-like speed with mesh-like capacity for self-planning network restoration,' in Proceedings of IEEE International Conference on Communications (IEEE, 1998), pp. 537-543.

W. D. Grover and J. Doucette, 'Advances in optical network design with p-cycles: joint optimization and pre-selection of candidate p-cycles,' in Proceedings of IEEE-LEOS Summer Topical Meeting (IEEE, 2002), pp. 49-50.

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 Proceedings of Design of Reliable Communication Networks (IEEE, 2003), pp. 212-220.

A. Kodian, W. D. Grover, and J. Doucette, 'A disjoint route-sets approach to design of path-protecting p-cycle networks,' in Proceedings of Design of Reliable Communication Networks (IEEE, 2005), pp. 231-238.

B. Jaumard, C. Rocha, D. Baloukov, and W. D. Grover, 'A column generation approach for design of networks using path-protecting p-cycles,' in the Sixth International Workshop on Design of Reliable Communication Networks (DRCN) 2007, La Rochelle, France, 7-10 October 2007.

A. Kodian, A. Sack, and W. D. Grover, 'p-Cycle network design with hop limits and circumference limits,' in Proceedings of First International Conference on Broadband Networks (IEEE, 2004), pp. 244-253.

Gruber, C. G.

D. A. Schupke, C. G. Gruber, and A. Autenrieth, 'Optimal configuration of p-cycles in WDM networks,' in Proceedings of IEEE International Conference on Communications (IEEE, 2002), pp. 2761-2765.

He, D.

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 Proceedings of Design of Reliable Communication Networks (IEEE, 2003), pp. 212-220.

Jaumard, B.

B. Jaumard, C. Rocha, D. Baloukov, and W. D. Grover, 'A column generation approach for design of networks using path-protecting p-cycles,' in the Sixth International Workshop on Design of Reliable Communication Networks (DRCN) 2007, La Rochelle, France, 7-10 October 2007.

Johnson, D. B.

D. B. Johnson, 'Finding all the elementary circuits of a directed graph,' SIAM J. Comput. 4, 77-84 (1975).
[CrossRef]

Kodian, A.

A. Kodian and W. D. Grover, 'Failure-independent path-protecting p-cycles: efficient and simple fully preconnected optical-path protection,' J. Lightwave Technol. 23, 3241-3259 (2005).
[CrossRef]

A. Kodian, W. D. Grover, and J. Doucette, 'A disjoint route-sets approach to design of path-protecting p-cycle networks,' in Proceedings of Design of Reliable Communication Networks (IEEE, 2005), pp. 231-238.

A. Kodian, A. Sack, and W. D. Grover, 'p-Cycle network design with hop limits and circumference limits,' in Proceedings of First International Conference on Broadband Networks (IEEE, 2004), pp. 244-253.

Mukherjee, B.

Z. Zhang, W. D. Zhong, and B. Mukherjee, 'A heuristic method for design of survivable WDM networks with p-cycles,' IEEE Commun. Lett. 8, 467-469 (2004).
[CrossRef]

Rocha, C.

B. Jaumard, C. Rocha, D. Baloukov, and W. D. Grover, 'A column generation approach for design of networks using path-protecting p-cycles,' in the Sixth International Workshop on Design of Reliable Communication Networks (DRCN) 2007, La Rochelle, France, 7-10 October 2007.

Sack, A.

A. Kodian, A. Sack, and W. D. Grover, 'p-Cycle network design with hop limits and circumference limits,' in Proceedings of First International Conference on Broadband Networks (IEEE, 2004), pp. 244-253.

Schupke, D. A.

D. A. Schupke, 'Analysis of p-cycle capacity in WDM networks,' Photonic Network Commun. 12, 41-51 (2006).

D. A. Schupke, 'Automatic protection switching for p-cycles in WDM networks,' Opt. Switching Networking 2, 35-48 (2005).

D. A. Schupke, C. G. Gruber, and A. Autenrieth, 'Optimal configuration of p-cycles in WDM networks,' in Proceedings of IEEE International Conference on Communications (IEEE, 2002), pp. 2761-2765.

Shen, G.

G. Shen and W. D. Grover, 'Design and performance of protected working capacity envelopes based on p-cycles for dynamic provisioning of survivable services,' J. Opt. Netw. 4, 361-390 (2005).
[CrossRef]

G. 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. 21, 1306-1319 (2003).
[CrossRef]

Stamatelakis, D.

D. Stamatelakis and W. D. Grover, 'IP layer restoration and network planning based on virtual protection cycles,' IEEE J. Sel. Areas Commun. 18, 1938-1949 (2000).

W. D. Grover and D. Stamatelakis, 'Cycle-oriented distributed preconfiguration: ring-like speed with mesh-like capacity for self-planning network restoration,' in Proceedings of IEEE International Conference on Communications (IEEE, 1998), pp. 537-543.

Yang, O.

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 Proceedings of Design of Reliable Communication Networks (IEEE, 2003), pp. 212-220.

Zhang, Z.

Z. Zhang, W. D. Zhong, and B. Mukherjee, 'A heuristic method for design of survivable WDM networks with p-cycles,' IEEE Commun. Lett. 8, 467-469 (2004).
[CrossRef]

Zhong, W. D.

Z. Zhang, W. D. Zhong, and B. Mukherjee, 'A heuristic method for design of survivable WDM networks with p-cycles,' IEEE Commun. Lett. 8, 467-469 (2004).
[CrossRef]

IEEE Commun. Lett. (1)

Z. Zhang, W. D. Zhong, and B. Mukherjee, 'A heuristic method for design of survivable WDM networks with p-cycles,' IEEE Commun. Lett. 8, 467-469 (2004).
[CrossRef]

IEEE J. Sel. Areas Commun. (3)

D. Stamatelakis and W. D. Grover, 'IP layer restoration and network planning based on virtual protection cycles,' IEEE J. Sel. Areas Commun. 18, 1938-1949 (2000).

G. 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. 21, 1306-1319 (2003).
[CrossRef]

J. Doucette, W. D. Grover, and P. A. Giese, 'Physical-layer p-cycles adapted for router-level node protection: a multi-layer design and operation strategy,' IEEE J. Sel. Areas Commun. 25, 963-973 (2007).

J. Lightwave Technol. (1)

J. Opt. Netw. (1)

Opt. Switching Networking (1)

D. A. Schupke, 'Automatic protection switching for p-cycles in WDM networks,' Opt. Switching Networking 2, 35-48 (2005).

Photonic Network Commun. (1)

D. A. Schupke, 'Analysis of p-cycle capacity in WDM networks,' Photonic Network Commun. 12, 41-51 (2006).

SIAM J. Comput. (1)

D. B. Johnson, 'Finding all the elementary circuits of a directed graph,' SIAM J. Comput. 4, 77-84 (1975).
[CrossRef]

Other (8)

J. Doucette, 'Advances on design and analysis of mesh-restorable networks,' Ph.D. dissertation (University of Alberta, 2004).

W. D. Grover and D. Stamatelakis, 'Cycle-oriented distributed preconfiguration: ring-like speed with mesh-like capacity for self-planning network restoration,' in Proceedings of IEEE International Conference on Communications (IEEE, 1998), pp. 537-543.

D. A. Schupke, C. G. Gruber, and A. Autenrieth, 'Optimal configuration of p-cycles in WDM networks,' in Proceedings of IEEE International Conference on Communications (IEEE, 2002), pp. 2761-2765.

W. D. Grover and J. Doucette, 'Advances in optical network design with p-cycles: joint optimization and pre-selection of candidate p-cycles,' in Proceedings of IEEE-LEOS Summer Topical Meeting (IEEE, 2002), pp. 49-50.

A. Kodian, A. Sack, and W. D. Grover, 'p-Cycle network design with hop limits and circumference limits,' in Proceedings of First International Conference on Broadband Networks (IEEE, 2004), pp. 244-253.

A. Kodian, W. D. Grover, and J. Doucette, 'A disjoint route-sets approach to design of path-protecting p-cycle networks,' in Proceedings of Design of Reliable Communication Networks (IEEE, 2005), pp. 231-238.

B. Jaumard, C. Rocha, D. Baloukov, and W. D. Grover, 'A column generation approach for design of networks using path-protecting p-cycles,' in the Sixth International Workshop on Design of Reliable Communication Networks (DRCN) 2007, La Rochelle, France, 7-10 October 2007.

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 Proceedings of Design of Reliable Communication Networks (IEEE, 2003), pp. 212-220.

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.