Abstract

Shared risk link groups (SRLGs) have been defined and implemented in many network planning tools and routing protocols. A single SRLG represents one potential failure, and a large service provider’s network could easily contain tens of thousands of potential failures. The greater the number of SRLGs, the more difficult it is to attain good performance from planning tools (like routers) whose computations are dependent on the number of SRLGs. For many routing protocols using SRLG information, the situation becomes even worse, because a routing protocol may have space constraints to hold a limited number of SRLGs. These issues create a challenge to optimize the SRLG calculations such that the SRLG-related functions are not impacted or the impacts on the SRLG-related functions are limited. This paper takes a closer look at the SRLG optimization issue and identifies the facts/observations of SRLGs. Then we propose algorithms for how to reduce the number of SRLGs for different applications based on our observations.

© 2012 OSA

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. K. Kompella and Y. Rekhter, “OSPF extensions in support of generalized multi-protocol label switching (GMPLS),” IETF RFC 4203.
  2. P. Angu and B. Ramamurthy, CoreDirector CI System Description [Online]. Available: http://groups.geni.net/geni/wiki/Ciena%20Core%20Director%20switch%20component%20manager%20interface.
  3. B. Cortez, “The emerging intelligent optical network: Now a reality,” in OFC, 2002, WH1.
  4. G. Ellinas, E. Bouillet, R. Ramamurthy, J. Labourdette, S. Chaudhuri, and K. Bala, “Routing and restoration architectures in mesh optical networks,” Opt. Networks Mag., vol. 4, no. 1, pp. 91–106, 2003.
  5. P. Sebos, J. Yates, D. Rubenstein, and A. Greenberg, “Effectiveness of shared risk link group auto-discovery in optical networks,” in OFC, 2002, Th05.
  6. J. Hu, “Diverse routing in optical mesh networks,” IEEE Trans. Commun., vol. 51, pp. 489–494, 2003.
  7. J. Doucette and W. D. Grover, “Capacity design studies of span-restorable mesh transport networks with shared-risk link group (SRLG) effects,” Proc. SPIE, 2002, vol. 4874, pp. 25–38, 2002.
  8. Y. Liu, D. Tipper, and P. Siripongwutikorn, “Approximating optimal spare capacity allocation by successive survivable routing,” in Proc. INFOCOM, 2001, pp. 699–708.
  9. G. Li, R. Doverspike, and C. Kalmanek, “Fiber span failure protection in mesh optical networks,” Opt. Networks Mag., vol. 3, no. 3, May/June2002.
  10. G. Li, D. Wang, R. Doverspike, and C. Kalmanek, “Efficient distributed restoration path selection for shared mesh restoration,” IEEE/ACM Trans. Netw., vol. 11, no. 5, pp. 761–771, Oct.2003.
  11. C. Qiao and D. Xu, “Distributed partial information management (DPIM) schemes for survivable networks—Part I,” in Proc. INFOCOM, June 2002, pp. 302–311.
  12. R. Bhandari, Survivable Networks: Algorithms for Diverse Routing. Kluwer, Norwell, MA, 1999.
  13. K. Lee and K. Siu, “An algorithmic framework for protection switching WDM networks,” in NFOEC, July 2001, pp. 402–410.
  14. M. Kodialam and T. V. Lakshman, “Dynamic routing of bandwidth guaranteed tunnels with restoration,” in Proc. INFOCOM, 2000, pp. 902–911.
  15. D. Xu, Y. Xiong, C. Qiao, and G. Li, “Trap avoidance and protection schemes in networks with shared risk link groups,” J. Lightwave Technol., vol. 21, no. 11, Nov.2003.
  16. G. Li, D. Wang, T. Gallivan, and R. Doverspike, “On shared risk link group optimization,” in OFC, 2012, WH2.

2003 (4)

G. Ellinas, E. Bouillet, R. Ramamurthy, J. Labourdette, S. Chaudhuri, and K. Bala, “Routing and restoration architectures in mesh optical networks,” Opt. Networks Mag., vol. 4, no. 1, pp. 91–106, 2003.

J. Hu, “Diverse routing in optical mesh networks,” IEEE Trans. Commun., vol. 51, pp. 489–494, 2003.

G. Li, D. Wang, R. Doverspike, and C. Kalmanek, “Efficient distributed restoration path selection for shared mesh restoration,” IEEE/ACM Trans. Netw., vol. 11, no. 5, pp. 761–771, Oct.2003.

D. Xu, Y. Xiong, C. Qiao, and G. Li, “Trap avoidance and protection schemes in networks with shared risk link groups,” J. Lightwave Technol., vol. 21, no. 11, Nov.2003.

2002 (2)

J. Doucette and W. D. Grover, “Capacity design studies of span-restorable mesh transport networks with shared-risk link group (SRLG) effects,” Proc. SPIE, 2002, vol. 4874, pp. 25–38, 2002.

G. Li, R. Doverspike, and C. Kalmanek, “Fiber span failure protection in mesh optical networks,” Opt. Networks Mag., vol. 3, no. 3, May/June2002.

Angu, P.

P. Angu and B. Ramamurthy, CoreDirector CI System Description [Online]. Available: http://groups.geni.net/geni/wiki/Ciena%20Core%20Director%20switch%20component%20manager%20interface.

Bala, K.

G. Ellinas, E. Bouillet, R. Ramamurthy, J. Labourdette, S. Chaudhuri, and K. Bala, “Routing and restoration architectures in mesh optical networks,” Opt. Networks Mag., vol. 4, no. 1, pp. 91–106, 2003.

Bhandari, R.

R. Bhandari, Survivable Networks: Algorithms for Diverse Routing. Kluwer, Norwell, MA, 1999.

Bouillet, E.

G. Ellinas, E. Bouillet, R. Ramamurthy, J. Labourdette, S. Chaudhuri, and K. Bala, “Routing and restoration architectures in mesh optical networks,” Opt. Networks Mag., vol. 4, no. 1, pp. 91–106, 2003.

Chaudhuri, S.

G. Ellinas, E. Bouillet, R. Ramamurthy, J. Labourdette, S. Chaudhuri, and K. Bala, “Routing and restoration architectures in mesh optical networks,” Opt. Networks Mag., vol. 4, no. 1, pp. 91–106, 2003.

Cortez, B.

B. Cortez, “The emerging intelligent optical network: Now a reality,” in OFC, 2002, WH1.

Doucette, J.

J. Doucette and W. D. Grover, “Capacity design studies of span-restorable mesh transport networks with shared-risk link group (SRLG) effects,” Proc. SPIE, 2002, vol. 4874, pp. 25–38, 2002.

Doverspike, R.

G. Li, D. Wang, R. Doverspike, and C. Kalmanek, “Efficient distributed restoration path selection for shared mesh restoration,” IEEE/ACM Trans. Netw., vol. 11, no. 5, pp. 761–771, Oct.2003.

G. Li, R. Doverspike, and C. Kalmanek, “Fiber span failure protection in mesh optical networks,” Opt. Networks Mag., vol. 3, no. 3, May/June2002.

G. Li, D. Wang, T. Gallivan, and R. Doverspike, “On shared risk link group optimization,” in OFC, 2012, WH2.

Ellinas, G.

G. Ellinas, E. Bouillet, R. Ramamurthy, J. Labourdette, S. Chaudhuri, and K. Bala, “Routing and restoration architectures in mesh optical networks,” Opt. Networks Mag., vol. 4, no. 1, pp. 91–106, 2003.

Gallivan, T.

G. Li, D. Wang, T. Gallivan, and R. Doverspike, “On shared risk link group optimization,” in OFC, 2012, WH2.

Greenberg, A.

P. Sebos, J. Yates, D. Rubenstein, and A. Greenberg, “Effectiveness of shared risk link group auto-discovery in optical networks,” in OFC, 2002, Th05.

Grover, W. D.

J. Doucette and W. D. Grover, “Capacity design studies of span-restorable mesh transport networks with shared-risk link group (SRLG) effects,” Proc. SPIE, 2002, vol. 4874, pp. 25–38, 2002.

Hu, J.

J. Hu, “Diverse routing in optical mesh networks,” IEEE Trans. Commun., vol. 51, pp. 489–494, 2003.

Kalmanek, C.

G. Li, D. Wang, R. Doverspike, and C. Kalmanek, “Efficient distributed restoration path selection for shared mesh restoration,” IEEE/ACM Trans. Netw., vol. 11, no. 5, pp. 761–771, Oct.2003.

G. Li, R. Doverspike, and C. Kalmanek, “Fiber span failure protection in mesh optical networks,” Opt. Networks Mag., vol. 3, no. 3, May/June2002.

Kodialam, M.

M. Kodialam and T. V. Lakshman, “Dynamic routing of bandwidth guaranteed tunnels with restoration,” in Proc. INFOCOM, 2000, pp. 902–911.

Kompella, K.

K. Kompella and Y. Rekhter, “OSPF extensions in support of generalized multi-protocol label switching (GMPLS),” IETF RFC 4203.

Labourdette, J.

G. Ellinas, E. Bouillet, R. Ramamurthy, J. Labourdette, S. Chaudhuri, and K. Bala, “Routing and restoration architectures in mesh optical networks,” Opt. Networks Mag., vol. 4, no. 1, pp. 91–106, 2003.

Lakshman, T. V.

M. Kodialam and T. V. Lakshman, “Dynamic routing of bandwidth guaranteed tunnels with restoration,” in Proc. INFOCOM, 2000, pp. 902–911.

Lee, K.

K. Lee and K. Siu, “An algorithmic framework for protection switching WDM networks,” in NFOEC, July 2001, pp. 402–410.

Li, G.

G. Li, D. Wang, R. Doverspike, and C. Kalmanek, “Efficient distributed restoration path selection for shared mesh restoration,” IEEE/ACM Trans. Netw., vol. 11, no. 5, pp. 761–771, Oct.2003.

D. Xu, Y. Xiong, C. Qiao, and G. Li, “Trap avoidance and protection schemes in networks with shared risk link groups,” J. Lightwave Technol., vol. 21, no. 11, Nov.2003.

G. Li, R. Doverspike, and C. Kalmanek, “Fiber span failure protection in mesh optical networks,” Opt. Networks Mag., vol. 3, no. 3, May/June2002.

G. Li, D. Wang, T. Gallivan, and R. Doverspike, “On shared risk link group optimization,” in OFC, 2012, WH2.

Liu, Y.

Y. Liu, D. Tipper, and P. Siripongwutikorn, “Approximating optimal spare capacity allocation by successive survivable routing,” in Proc. INFOCOM, 2001, pp. 699–708.

Qiao, C.

D. Xu, Y. Xiong, C. Qiao, and G. Li, “Trap avoidance and protection schemes in networks with shared risk link groups,” J. Lightwave Technol., vol. 21, no. 11, Nov.2003.

C. Qiao and D. Xu, “Distributed partial information management (DPIM) schemes for survivable networks—Part I,” in Proc. INFOCOM, June 2002, pp. 302–311.

Ramamurthy, B.

P. Angu and B. Ramamurthy, CoreDirector CI System Description [Online]. Available: http://groups.geni.net/geni/wiki/Ciena%20Core%20Director%20switch%20component%20manager%20interface.

Ramamurthy, R.

G. Ellinas, E. Bouillet, R. Ramamurthy, J. Labourdette, S. Chaudhuri, and K. Bala, “Routing and restoration architectures in mesh optical networks,” Opt. Networks Mag., vol. 4, no. 1, pp. 91–106, 2003.

Rekhter, Y.

K. Kompella and Y. Rekhter, “OSPF extensions in support of generalized multi-protocol label switching (GMPLS),” IETF RFC 4203.

Rubenstein, D.

P. Sebos, J. Yates, D. Rubenstein, and A. Greenberg, “Effectiveness of shared risk link group auto-discovery in optical networks,” in OFC, 2002, Th05.

Sebos, P.

P. Sebos, J. Yates, D. Rubenstein, and A. Greenberg, “Effectiveness of shared risk link group auto-discovery in optical networks,” in OFC, 2002, Th05.

Siripongwutikorn, P.

Y. Liu, D. Tipper, and P. Siripongwutikorn, “Approximating optimal spare capacity allocation by successive survivable routing,” in Proc. INFOCOM, 2001, pp. 699–708.

Siu, K.

K. Lee and K. Siu, “An algorithmic framework for protection switching WDM networks,” in NFOEC, July 2001, pp. 402–410.

Tipper, D.

Y. Liu, D. Tipper, and P. Siripongwutikorn, “Approximating optimal spare capacity allocation by successive survivable routing,” in Proc. INFOCOM, 2001, pp. 699–708.

Wang, D.

G. Li, D. Wang, R. Doverspike, and C. Kalmanek, “Efficient distributed restoration path selection for shared mesh restoration,” IEEE/ACM Trans. Netw., vol. 11, no. 5, pp. 761–771, Oct.2003.

G. Li, D. Wang, T. Gallivan, and R. Doverspike, “On shared risk link group optimization,” in OFC, 2012, WH2.

Xiong, Y.

D. Xu, Y. Xiong, C. Qiao, and G. Li, “Trap avoidance and protection schemes in networks with shared risk link groups,” J. Lightwave Technol., vol. 21, no. 11, Nov.2003.

Xu, D.

D. Xu, Y. Xiong, C. Qiao, and G. Li, “Trap avoidance and protection schemes in networks with shared risk link groups,” J. Lightwave Technol., vol. 21, no. 11, Nov.2003.

C. Qiao and D. Xu, “Distributed partial information management (DPIM) schemes for survivable networks—Part I,” in Proc. INFOCOM, June 2002, pp. 302–311.

Yates, J.

P. Sebos, J. Yates, D. Rubenstein, and A. Greenberg, “Effectiveness of shared risk link group auto-discovery in optical networks,” in OFC, 2002, Th05.

IEEE Trans. Commun. (1)

J. Hu, “Diverse routing in optical mesh networks,” IEEE Trans. Commun., vol. 51, pp. 489–494, 2003.

IEEE/ACM Trans. Netw. (1)

G. Li, D. Wang, R. Doverspike, and C. Kalmanek, “Efficient distributed restoration path selection for shared mesh restoration,” IEEE/ACM Trans. Netw., vol. 11, no. 5, pp. 761–771, Oct.2003.

J. Lightwave Technol. (1)

D. Xu, Y. Xiong, C. Qiao, and G. Li, “Trap avoidance and protection schemes in networks with shared risk link groups,” J. Lightwave Technol., vol. 21, no. 11, Nov.2003.

Opt. Networks Mag. (2)

G. Li, R. Doverspike, and C. Kalmanek, “Fiber span failure protection in mesh optical networks,” Opt. Networks Mag., vol. 3, no. 3, May/June2002.

G. Ellinas, E. Bouillet, R. Ramamurthy, J. Labourdette, S. Chaudhuri, and K. Bala, “Routing and restoration architectures in mesh optical networks,” Opt. Networks Mag., vol. 4, no. 1, pp. 91–106, 2003.

Proc. SPIE (1)

J. Doucette and W. D. Grover, “Capacity design studies of span-restorable mesh transport networks with shared-risk link group (SRLG) effects,” Proc. SPIE, 2002, vol. 4874, pp. 25–38, 2002.

Other (10)

Y. Liu, D. Tipper, and P. Siripongwutikorn, “Approximating optimal spare capacity allocation by successive survivable routing,” in Proc. INFOCOM, 2001, pp. 699–708.

G. Li, D. Wang, T. Gallivan, and R. Doverspike, “On shared risk link group optimization,” in OFC, 2012, WH2.

P. Sebos, J. Yates, D. Rubenstein, and A. Greenberg, “Effectiveness of shared risk link group auto-discovery in optical networks,” in OFC, 2002, Th05.

K. Kompella and Y. Rekhter, “OSPF extensions in support of generalized multi-protocol label switching (GMPLS),” IETF RFC 4203.

P. Angu and B. Ramamurthy, CoreDirector CI System Description [Online]. Available: http://groups.geni.net/geni/wiki/Ciena%20Core%20Director%20switch%20component%20manager%20interface.

B. Cortez, “The emerging intelligent optical network: Now a reality,” in OFC, 2002, WH1.

C. Qiao and D. Xu, “Distributed partial information management (DPIM) schemes for survivable networks—Part I,” in Proc. INFOCOM, June 2002, pp. 302–311.

R. Bhandari, Survivable Networks: Algorithms for Diverse Routing. Kluwer, Norwell, MA, 1999.

K. Lee and K. Siu, “An algorithmic framework for protection switching WDM networks,” in NFOEC, July 2001, pp. 402–410.

M. Kodialam and T. V. Lakshman, “Dynamic routing of bandwidth guaranteed tunnels with restoration,” in Proc. INFOCOM, 2000, pp. 902–911.

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 (3)

Fig. 1
Fig. 1

(Color online) A sample of overlay networks.

Fig. 2
Fig. 2

(Color online) Overlay network with fiber spans.

Fig. 3
Fig. 3

(Color online) Example of grouping spans into SRLGs.

Tables (2)

Tables Icon

Algorithm 1 SRLGs for complete diverse routing

Tables Icon

Algorithm 2 SRLGs for maximal diverse routing

Equations (1)

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

Importance(bundle) = 1000000 * isSuperSet(bundle) + 10000 * linkCount(bundle) + mileage(bundle) ,