Abstract

This paper develops a novel mesh network protection scheme that guarantees a quantifiable minimum grade of service upon a failure within the network using multipath routing. Typically, networks fully guarantee service after a single-link failure, which is often an over-provisioning of resources to maintain essential traffic for the infrequent event of a failure. Our scheme guarantees that a fraction q of each demand remains after any single-link failure, at a fraction of the price of full protection. A linear program is developed to find the minimum-cost capacity allocation to meet both demand and protection requirements. For q12, an exact algorithmic solution for the minimum-cost routing and capacity allocation is developed using multiple shortest paths. For q>12, an algorithm is developed based on disjoint path routing that performs, on average, within 1.4% of optimal, and runs four orders of magnitude faster than the minimum-cost solution achieved via the linear program. Moreover, the partial protection strategies developed achieve reductions of up to 83% over traditional full protection schemes.

© 2014 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. B. Mukherjee, “WDM optical communication networks: Progress and challenges,” IEEE J. Sel. Areas Commun., vol.  18, no. 10, pp. 1810–1824, 2000.
    [CrossRef]
  2. W. Grover, Mesh-Based Survivable Networks: Options and Strategies for Optical, MPLS, SONET, and ATM Networking. Prentice-Hall, 2004.
  3. T. H. Shake, B. Hazzard, and D. Marquis, “Assessing network infrastructure vulnerabilities to physical layer attacks,” in 22nd National Information Systems Security Conf., Arlington, VA, Oct. 18–21, 1999.
  4. S. Ramamurthy, L. Sahasrabuddhe, and B. Mukherjee, “Survivable WDM mesh networks,” J. Lightwave Technol., vol.  21, no. 4, pp. 870–883, 2003.
    [CrossRef]
  5. R. Iraschko, M. MacGregor, and W. 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, 1998.
    [CrossRef]
  6. W. Yao and B. Ramamurthy, “Survivable traffic grooming with path protection at the connection level in WDM mesh networks,” J. Lightwave Technol., vol.  23, no. 10, p. 2846, 2005.
    [CrossRef]
  7. C. Ou, J. Zhang, H. Zang, L. Sahasrabuddhe, and B. Mukherjee, “New and improved approaches for shared-path protection in WDM mesh networks,” J. Lightwave Technol., vol.  22, no. 5, pp. 1223–1232, 2004.
    [CrossRef]
  8. G. Mohan, S. Murthy, and A. Somani, “Efficient algorithms for routing dependable connections in WDM optical networks,” IEEE/ACM Trans. Netw., vol.  9, no. 5, pp. 553–566, 2002.
    [CrossRef]
  9. A. Fumagalli, I. Cerutti, M. Tacca, F. Masetti, R. Jagannathan, and S. Alagar, “Survivable networks based on optimal routing and WDM self-healing rings,” in 18th Annu. Joint Conf. of the IEEE Computer and Communications Societies (IEEE INFOCOM), 1999, pp. 726–733.
  10. A. Saleh and J. Simmons, “Evolution toward the next-generation core optical network,” J. Lightwave Technol., vol.  24, no. 9, pp. 3303–3321, 2006.
    [CrossRef]
  11. W. Grover and M. Clouqueur, “Span-restorable mesh networks with multiple quality of protection (QoP) service classes,” Photon. Netw. Commun., vol.  9, no. 1, pp. 19–34, 2005.
  12. O. Gerstel and G. Sasaki, “Quality of protection (QoP): A quantitative unifying paradigm to protection service grades,” Opt. Netw. Mag., vol.  3, no. 3, pp. 40–49, 2002.
  13. O. O. Gerstel and G. H. Sasaki, “A new protection paradigm for digital video distribution networks,” in IEEE Int. Conf. on Communications (ICC), 2006, pp. 2518–2523.
  14. G. H. Sasaki, K. Wang, and Y. Wang, “Fractional survivable network bandwidth: A comparison of IP over WDM schemes,” in Optical Fiber Communication Conf., 2010, paper OWH5.
  15. J. Fang and A. Somani, “On partial protection in groomed optical WDM mesh networks,” in Proc. of the 2005 Int. Conf. on Dependable Systems and Networks, 2005, pp. 228–237.
  16. A. Das, C. Martel, and B. Mukherjee, “A partial-protection approach using multipath provisioning,” in IEEE Int. Conf. on Communications (ICC), 2009, pp. 1–5.
  17. G. Kuperman, E. Modiano, and A. Narula-Tam, “Analysis and algorithms for partial protection in mesh networks,” in Proc. IEEE INFOCOM, 2011, pp. 516–520.
  18. G. Kuperman, E. Modiano, and A. Narula-Tam, “Partial protection in networks with backup capacity sharing,” in Optical Fiber Communication Conf. and Expo. and the Nat. Fiber Optic Engineers Conf. (OFC/NFOEC), 2012, paper NW3K.4.
  19. L. Ruan and N. Xiao, “Survivable multipath routing and spectrum allocation in OFDM-based flexible optical networks,” J. Opt. Commun. Netw., vol.  5, no. 3, pp. 172–182, 2013.
    [CrossRef]
  20. I. Cidon, R. Rom, and Y. Shavitt, “Analysis of multi-path routing,” IEEE/ACM Trans. Netw., vol.  7, no. 6, pp. 885–896, 1999.
    [CrossRef]
  21. J. Suurballe and R. Tarjan, “A quick method for finding shortest pairs of disjoint paths,” Networks, vol.  14, no. 2, pp. 325–336, 1984.
    [CrossRef]
  22. H. Wang, E. Modiano, and M. Medard, “Partial path protection for WDM networks: End-to-end recovery using local failure information,” in 7th Int. Symp. on Computers and Communications (ISCC), 2002, pp. 719–725.
  23. R. Ahuja, T. Magnanti, and J. Orlin, Network Flows: Theory, Algorithms, and Applications. New Jersey: Prentice-Hall, 1993.
  24. D. Bertsimas and J. Tsitsiklis, Introduction to Linear Optimization. Belmont, Massachusetts: Athena Scientific, 1997.

2013 (1)

2006 (1)

2005 (2)

W. Grover and M. Clouqueur, “Span-restorable mesh networks with multiple quality of protection (QoP) service classes,” Photon. Netw. Commun., vol.  9, no. 1, pp. 19–34, 2005.

W. Yao and B. Ramamurthy, “Survivable traffic grooming with path protection at the connection level in WDM mesh networks,” J. Lightwave Technol., vol.  23, no. 10, p. 2846, 2005.
[CrossRef]

2004 (1)

2003 (1)

2002 (2)

G. Mohan, S. Murthy, and A. Somani, “Efficient algorithms for routing dependable connections in WDM optical networks,” IEEE/ACM Trans. Netw., vol.  9, no. 5, pp. 553–566, 2002.
[CrossRef]

O. Gerstel and G. Sasaki, “Quality of protection (QoP): A quantitative unifying paradigm to protection service grades,” Opt. Netw. Mag., vol.  3, no. 3, pp. 40–49, 2002.

2000 (1)

B. Mukherjee, “WDM optical communication networks: Progress and challenges,” IEEE J. Sel. Areas Commun., vol.  18, no. 10, pp. 1810–1824, 2000.
[CrossRef]

1999 (1)

I. Cidon, R. Rom, and Y. Shavitt, “Analysis of multi-path routing,” IEEE/ACM Trans. Netw., vol.  7, no. 6, pp. 885–896, 1999.
[CrossRef]

1998 (1)

R. Iraschko, M. MacGregor, and W. 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, 1998.
[CrossRef]

1984 (1)

J. Suurballe and R. Tarjan, “A quick method for finding shortest pairs of disjoint paths,” Networks, vol.  14, no. 2, pp. 325–336, 1984.
[CrossRef]

Ahuja, R.

R. Ahuja, T. Magnanti, and J. Orlin, Network Flows: Theory, Algorithms, and Applications. New Jersey: Prentice-Hall, 1993.

Alagar, S.

A. Fumagalli, I. Cerutti, M. Tacca, F. Masetti, R. Jagannathan, and S. Alagar, “Survivable networks based on optimal routing and WDM self-healing rings,” in 18th Annu. Joint Conf. of the IEEE Computer and Communications Societies (IEEE INFOCOM), 1999, pp. 726–733.

Bertsimas, D.

D. Bertsimas and J. Tsitsiklis, Introduction to Linear Optimization. Belmont, Massachusetts: Athena Scientific, 1997.

Cerutti, I.

A. Fumagalli, I. Cerutti, M. Tacca, F. Masetti, R. Jagannathan, and S. Alagar, “Survivable networks based on optimal routing and WDM self-healing rings,” in 18th Annu. Joint Conf. of the IEEE Computer and Communications Societies (IEEE INFOCOM), 1999, pp. 726–733.

Cidon, I.

I. Cidon, R. Rom, and Y. Shavitt, “Analysis of multi-path routing,” IEEE/ACM Trans. Netw., vol.  7, no. 6, pp. 885–896, 1999.
[CrossRef]

Clouqueur, M.

W. Grover and M. Clouqueur, “Span-restorable mesh networks with multiple quality of protection (QoP) service classes,” Photon. Netw. Commun., vol.  9, no. 1, pp. 19–34, 2005.

Das, A.

A. Das, C. Martel, and B. Mukherjee, “A partial-protection approach using multipath provisioning,” in IEEE Int. Conf. on Communications (ICC), 2009, pp. 1–5.

Fang, J.

J. Fang and A. Somani, “On partial protection in groomed optical WDM mesh networks,” in Proc. of the 2005 Int. Conf. on Dependable Systems and Networks, 2005, pp. 228–237.

Fumagalli, A.

A. Fumagalli, I. Cerutti, M. Tacca, F. Masetti, R. Jagannathan, and S. Alagar, “Survivable networks based on optimal routing and WDM self-healing rings,” in 18th Annu. Joint Conf. of the IEEE Computer and Communications Societies (IEEE INFOCOM), 1999, pp. 726–733.

Gerstel, O.

O. Gerstel and G. Sasaki, “Quality of protection (QoP): A quantitative unifying paradigm to protection service grades,” Opt. Netw. Mag., vol.  3, no. 3, pp. 40–49, 2002.

Gerstel, O. O.

O. O. Gerstel and G. H. Sasaki, “A new protection paradigm for digital video distribution networks,” in IEEE Int. Conf. on Communications (ICC), 2006, pp. 2518–2523.

Grover, W.

W. Grover and M. Clouqueur, “Span-restorable mesh networks with multiple quality of protection (QoP) service classes,” Photon. Netw. Commun., vol.  9, no. 1, pp. 19–34, 2005.

R. Iraschko, M. MacGregor, and W. 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, 1998.
[CrossRef]

W. Grover, Mesh-Based Survivable Networks: Options and Strategies for Optical, MPLS, SONET, and ATM Networking. Prentice-Hall, 2004.

Hazzard, B.

T. H. Shake, B. Hazzard, and D. Marquis, “Assessing network infrastructure vulnerabilities to physical layer attacks,” in 22nd National Information Systems Security Conf., Arlington, VA, Oct. 18–21, 1999.

Iraschko, R.

R. Iraschko, M. MacGregor, and W. 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, 1998.
[CrossRef]

Jagannathan, R.

A. Fumagalli, I. Cerutti, M. Tacca, F. Masetti, R. Jagannathan, and S. Alagar, “Survivable networks based on optimal routing and WDM self-healing rings,” in 18th Annu. Joint Conf. of the IEEE Computer and Communications Societies (IEEE INFOCOM), 1999, pp. 726–733.

Kuperman, G.

G. Kuperman, E. Modiano, and A. Narula-Tam, “Analysis and algorithms for partial protection in mesh networks,” in Proc. IEEE INFOCOM, 2011, pp. 516–520.

G. Kuperman, E. Modiano, and A. Narula-Tam, “Partial protection in networks with backup capacity sharing,” in Optical Fiber Communication Conf. and Expo. and the Nat. Fiber Optic Engineers Conf. (OFC/NFOEC), 2012, paper NW3K.4.

MacGregor, M.

R. Iraschko, M. MacGregor, and W. 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, 1998.
[CrossRef]

Magnanti, T.

R. Ahuja, T. Magnanti, and J. Orlin, Network Flows: Theory, Algorithms, and Applications. New Jersey: Prentice-Hall, 1993.

Marquis, D.

T. H. Shake, B. Hazzard, and D. Marquis, “Assessing network infrastructure vulnerabilities to physical layer attacks,” in 22nd National Information Systems Security Conf., Arlington, VA, Oct. 18–21, 1999.

Martel, C.

A. Das, C. Martel, and B. Mukherjee, “A partial-protection approach using multipath provisioning,” in IEEE Int. Conf. on Communications (ICC), 2009, pp. 1–5.

Masetti, F.

A. Fumagalli, I. Cerutti, M. Tacca, F. Masetti, R. Jagannathan, and S. Alagar, “Survivable networks based on optimal routing and WDM self-healing rings,” in 18th Annu. Joint Conf. of the IEEE Computer and Communications Societies (IEEE INFOCOM), 1999, pp. 726–733.

Medard, M.

H. Wang, E. Modiano, and M. Medard, “Partial path protection for WDM networks: End-to-end recovery using local failure information,” in 7th Int. Symp. on Computers and Communications (ISCC), 2002, pp. 719–725.

Modiano, E.

H. Wang, E. Modiano, and M. Medard, “Partial path protection for WDM networks: End-to-end recovery using local failure information,” in 7th Int. Symp. on Computers and Communications (ISCC), 2002, pp. 719–725.

G. Kuperman, E. Modiano, and A. Narula-Tam, “Analysis and algorithms for partial protection in mesh networks,” in Proc. IEEE INFOCOM, 2011, pp. 516–520.

G. Kuperman, E. Modiano, and A. Narula-Tam, “Partial protection in networks with backup capacity sharing,” in Optical Fiber Communication Conf. and Expo. and the Nat. Fiber Optic Engineers Conf. (OFC/NFOEC), 2012, paper NW3K.4.

Mohan, G.

G. Mohan, S. Murthy, and A. Somani, “Efficient algorithms for routing dependable connections in WDM optical networks,” IEEE/ACM Trans. Netw., vol.  9, no. 5, pp. 553–566, 2002.
[CrossRef]

Mukherjee, B.

C. Ou, J. Zhang, H. Zang, L. Sahasrabuddhe, and B. Mukherjee, “New and improved approaches for shared-path protection in WDM mesh networks,” J. Lightwave Technol., vol.  22, no. 5, pp. 1223–1232, 2004.
[CrossRef]

S. Ramamurthy, L. Sahasrabuddhe, and B. Mukherjee, “Survivable WDM mesh networks,” J. Lightwave Technol., vol.  21, no. 4, pp. 870–883, 2003.
[CrossRef]

B. Mukherjee, “WDM optical communication networks: Progress and challenges,” IEEE J. Sel. Areas Commun., vol.  18, no. 10, pp. 1810–1824, 2000.
[CrossRef]

A. Das, C. Martel, and B. Mukherjee, “A partial-protection approach using multipath provisioning,” in IEEE Int. Conf. on Communications (ICC), 2009, pp. 1–5.

Murthy, S.

G. Mohan, S. Murthy, and A. Somani, “Efficient algorithms for routing dependable connections in WDM optical networks,” IEEE/ACM Trans. Netw., vol.  9, no. 5, pp. 553–566, 2002.
[CrossRef]

Narula-Tam, A.

G. Kuperman, E. Modiano, and A. Narula-Tam, “Analysis and algorithms for partial protection in mesh networks,” in Proc. IEEE INFOCOM, 2011, pp. 516–520.

G. Kuperman, E. Modiano, and A. Narula-Tam, “Partial protection in networks with backup capacity sharing,” in Optical Fiber Communication Conf. and Expo. and the Nat. Fiber Optic Engineers Conf. (OFC/NFOEC), 2012, paper NW3K.4.

Orlin, J.

R. Ahuja, T. Magnanti, and J. Orlin, Network Flows: Theory, Algorithms, and Applications. New Jersey: Prentice-Hall, 1993.

Ou, C.

Ramamurthy, B.

Ramamurthy, S.

Rom, R.

I. Cidon, R. Rom, and Y. Shavitt, “Analysis of multi-path routing,” IEEE/ACM Trans. Netw., vol.  7, no. 6, pp. 885–896, 1999.
[CrossRef]

Ruan, L.

Sahasrabuddhe, L.

Saleh, A.

Sasaki, G.

O. Gerstel and G. Sasaki, “Quality of protection (QoP): A quantitative unifying paradigm to protection service grades,” Opt. Netw. Mag., vol.  3, no. 3, pp. 40–49, 2002.

Sasaki, G. H.

O. O. Gerstel and G. H. Sasaki, “A new protection paradigm for digital video distribution networks,” in IEEE Int. Conf. on Communications (ICC), 2006, pp. 2518–2523.

G. H. Sasaki, K. Wang, and Y. Wang, “Fractional survivable network bandwidth: A comparison of IP over WDM schemes,” in Optical Fiber Communication Conf., 2010, paper OWH5.

Shake, T. H.

T. H. Shake, B. Hazzard, and D. Marquis, “Assessing network infrastructure vulnerabilities to physical layer attacks,” in 22nd National Information Systems Security Conf., Arlington, VA, Oct. 18–21, 1999.

Shavitt, Y.

I. Cidon, R. Rom, and Y. Shavitt, “Analysis of multi-path routing,” IEEE/ACM Trans. Netw., vol.  7, no. 6, pp. 885–896, 1999.
[CrossRef]

Simmons, J.

Somani, A.

G. Mohan, S. Murthy, and A. Somani, “Efficient algorithms for routing dependable connections in WDM optical networks,” IEEE/ACM Trans. Netw., vol.  9, no. 5, pp. 553–566, 2002.
[CrossRef]

J. Fang and A. Somani, “On partial protection in groomed optical WDM mesh networks,” in Proc. of the 2005 Int. Conf. on Dependable Systems and Networks, 2005, pp. 228–237.

Suurballe, J.

J. Suurballe and R. Tarjan, “A quick method for finding shortest pairs of disjoint paths,” Networks, vol.  14, no. 2, pp. 325–336, 1984.
[CrossRef]

Tacca, M.

A. Fumagalli, I. Cerutti, M. Tacca, F. Masetti, R. Jagannathan, and S. Alagar, “Survivable networks based on optimal routing and WDM self-healing rings,” in 18th Annu. Joint Conf. of the IEEE Computer and Communications Societies (IEEE INFOCOM), 1999, pp. 726–733.

Tarjan, R.

J. Suurballe and R. Tarjan, “A quick method for finding shortest pairs of disjoint paths,” Networks, vol.  14, no. 2, pp. 325–336, 1984.
[CrossRef]

Tsitsiklis, J.

D. Bertsimas and J. Tsitsiklis, Introduction to Linear Optimization. Belmont, Massachusetts: Athena Scientific, 1997.

Wang, H.

H. Wang, E. Modiano, and M. Medard, “Partial path protection for WDM networks: End-to-end recovery using local failure information,” in 7th Int. Symp. on Computers and Communications (ISCC), 2002, pp. 719–725.

Wang, K.

G. H. Sasaki, K. Wang, and Y. Wang, “Fractional survivable network bandwidth: A comparison of IP over WDM schemes,” in Optical Fiber Communication Conf., 2010, paper OWH5.

Wang, Y.

G. H. Sasaki, K. Wang, and Y. Wang, “Fractional survivable network bandwidth: A comparison of IP over WDM schemes,” in Optical Fiber Communication Conf., 2010, paper OWH5.

Xiao, N.

Yao, W.

Zang, H.

Zhang, J.

IEEE J. Sel. Areas Commun. (1)

B. Mukherjee, “WDM optical communication networks: Progress and challenges,” IEEE J. Sel. Areas Commun., vol.  18, no. 10, pp. 1810–1824, 2000.
[CrossRef]

IEEE/ACM Trans. Netw. (3)

R. Iraschko, M. MacGregor, and W. 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, 1998.
[CrossRef]

G. Mohan, S. Murthy, and A. Somani, “Efficient algorithms for routing dependable connections in WDM optical networks,” IEEE/ACM Trans. Netw., vol.  9, no. 5, pp. 553–566, 2002.
[CrossRef]

I. Cidon, R. Rom, and Y. Shavitt, “Analysis of multi-path routing,” IEEE/ACM Trans. Netw., vol.  7, no. 6, pp. 885–896, 1999.
[CrossRef]

J. Lightwave Technol. (4)

J. Opt. Commun. Netw. (1)

Networks (1)

J. Suurballe and R. Tarjan, “A quick method for finding shortest pairs of disjoint paths,” Networks, vol.  14, no. 2, pp. 325–336, 1984.
[CrossRef]

Opt. Netw. Mag. (1)

O. Gerstel and G. Sasaki, “Quality of protection (QoP): A quantitative unifying paradigm to protection service grades,” Opt. Netw. Mag., vol.  3, no. 3, pp. 40–49, 2002.

Photon. Netw. Commun. (1)

W. Grover and M. Clouqueur, “Span-restorable mesh networks with multiple quality of protection (QoP) service classes,” Photon. Netw. Commun., vol.  9, no. 1, pp. 19–34, 2005.

Other (12)

A. Fumagalli, I. Cerutti, M. Tacca, F. Masetti, R. Jagannathan, and S. Alagar, “Survivable networks based on optimal routing and WDM self-healing rings,” in 18th Annu. Joint Conf. of the IEEE Computer and Communications Societies (IEEE INFOCOM), 1999, pp. 726–733.

W. Grover, Mesh-Based Survivable Networks: Options and Strategies for Optical, MPLS, SONET, and ATM Networking. Prentice-Hall, 2004.

T. H. Shake, B. Hazzard, and D. Marquis, “Assessing network infrastructure vulnerabilities to physical layer attacks,” in 22nd National Information Systems Security Conf., Arlington, VA, Oct. 18–21, 1999.

O. O. Gerstel and G. H. Sasaki, “A new protection paradigm for digital video distribution networks,” in IEEE Int. Conf. on Communications (ICC), 2006, pp. 2518–2523.

G. H. Sasaki, K. Wang, and Y. Wang, “Fractional survivable network bandwidth: A comparison of IP over WDM schemes,” in Optical Fiber Communication Conf., 2010, paper OWH5.

J. Fang and A. Somani, “On partial protection in groomed optical WDM mesh networks,” in Proc. of the 2005 Int. Conf. on Dependable Systems and Networks, 2005, pp. 228–237.

A. Das, C. Martel, and B. Mukherjee, “A partial-protection approach using multipath provisioning,” in IEEE Int. Conf. on Communications (ICC), 2009, pp. 1–5.

G. Kuperman, E. Modiano, and A. Narula-Tam, “Analysis and algorithms for partial protection in mesh networks,” in Proc. IEEE INFOCOM, 2011, pp. 516–520.

G. Kuperman, E. Modiano, and A. Narula-Tam, “Partial protection in networks with backup capacity sharing,” in Optical Fiber Communication Conf. and Expo. and the Nat. Fiber Optic Engineers Conf. (OFC/NFOEC), 2012, paper NW3K.4.

H. Wang, E. Modiano, and M. Medard, “Partial path protection for WDM networks: End-to-end recovery using local failure information,” in 7th Int. Symp. on Computers and Communications (ISCC), 2002, pp. 719–725.

R. Ahuja, T. Magnanti, and J. Orlin, Network Flows: Theory, Algorithms, and Applications. New Jersey: Prentice-Hall, 1993.

D. Bertsimas and J. Tsitsiklis, Introduction to Linear Optimization. Belmont, Massachusetts: Athena Scientific, 1997.

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.


Figures (9)

Fig. 1.
Fig. 1.

Standard protection schemes.

Fig. 2.
Fig. 2.

Protection using risk distribution.

Fig. 3.
Fig. 3.

Example of flow not being conserved at node v.

Fig. 4.
Fig. 4.

Without backup capacity sharing: capacity cost versus q.

Fig. 5.
Fig. 5.

14-node NSFNET backbone network.

Fig. 6.
Fig. 6.

With backup capacity sharing: capacity cost versus q.

Fig. 7.
Fig. 7.

Two-node network with link costs.

Fig. 8.
Fig. 8.

Algorithm comparison: cost versus q.

Fig. 9.
Fig. 9.

Sharing algorithm comparison: cost versus q.

Equations (24)

Equations on this page are rendered with MathJax. Learn more.

min{i,j}Ecij(wij+sij),
{i,j}Exijst{j,i}Exjist={dstifi=sdstifi=t0otherwise,iV,(s,t)(V,V).
{i,j}E{i,j}{k,l}fij,klst{j,i}E{j,i}{k,l}fji,klst={dstqstifi=sdstqstifi=t0otherwise,iV,{k,l}E,(s,t)(V,V).
(s,t)(V,V)xijst=wij,{i,j}E.
fij,klstxijst+yij,klst,{i,j}E,{k,l}E(s,t)(V,V).
(s,t)(V,V)yij,klstsij,{i,j}E{k,l}E.
(s,t)(V,V)fij,klstwij+sij,{i,j}E{k,l}E.
LPq.5:min{i,j}Ecijxij,
{i,j}Exij{j,i}Exji={1ifi=s1ifi=t0otherwise,iV,
xij(1q),{i,j}E.
LP2:minxNcN,
s.t.iExi1,
ANxNqeN,
xi0,iE.
LP2K:minxKcK,
s.t.AKxK=qeK,
xi0,i=1,,K.
LP2:mincNxN,
s.t.ANxNqeN,
i=1Nxi=1,
xi0,iE.
LP2d:maxi=1,,Nqpi+pN+1,
s.t.pN+1[ANeN]cN,
pi0,i=1,,(N+1).