Abstract

This paper proposes a new heuristic algorithm, called Quick Method with Shared Protection (QMSP), to protect the single-link failure in survivable WDM optical networks. QMSP first computes one primary path for each connection request. If the primary path is a trap path, QMSP will compute two segment-backup paths to avoid the trap problem based on the routing policy. Compared to previous algorithms, QMSP not only has better time complexity but also can obtain higher resource utilization ratio and lower blocking probability.

© 2006 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. S. Ramamurthy, L. Sahasrabuddhe, B. Mukherjee, "Survivable WDM mesh networks," J. Lightwave. Technol. 21, 870-883 (2003).
    [CrossRef]
  2. R. He, H. Wen, L. Li, G. Wang, "Shared sub-path protection algorithm in traffic-grooming WDM mesh networks," Photonic Netw. Commun. 8, 239-249 (2004).
    [CrossRef]
  3. H. Wen, L. Li, R. He, H. Yu, S. Wang, N. Song, "Dynamic grooming algorithms for survivable WDM mesh networks," Photonic Netw. Commun. 7, 253-263 (2003).
    [CrossRef]
  4. Y. Wang, Q. Zeng, H. Zhao, "Dynamic survivability in WDM mesh networks under dynamic traffic," Photonic Netw. Commun. 6, 5-24 (2003).
    [CrossRef]
  5. C. Ou, J. Zhang, H. Zang, L. Sahasrabuddhe, B. Mukherjee, "New and improved approaches for shared-path protection in WDM mesh networks," J. Lightwave. Technol. 22, 1223-1232 (2004).
    [CrossRef]
  6. J. Suurballe, R. Tarjan, "A quick method for finding shortest pairs of disjoint paths," Networks,  14, 325-326 (1984).
    [CrossRef]
  7. H. Wen, S. Wang, L. Li, "A routing algorithm for finding low-cost pair of no shared-risk paths," J. Electron. Info. Technol. 25, 824-830 (2003).
  8. M. Barbehenn, "A note on the complexity of Dijkstra’s algorithm for graphs with weighted vertices," IEEE Trans. Comp. 47, 263 (1998).
    [CrossRef]

2004 (2)

R. He, H. Wen, L. Li, G. Wang, "Shared sub-path protection algorithm in traffic-grooming WDM mesh networks," Photonic Netw. Commun. 8, 239-249 (2004).
[CrossRef]

C. Ou, J. Zhang, H. Zang, L. Sahasrabuddhe, B. Mukherjee, "New and improved approaches for shared-path protection in WDM mesh networks," J. Lightwave. Technol. 22, 1223-1232 (2004).
[CrossRef]

2003 (4)

H. Wen, L. Li, R. He, H. Yu, S. Wang, N. Song, "Dynamic grooming algorithms for survivable WDM mesh networks," Photonic Netw. Commun. 7, 253-263 (2003).
[CrossRef]

Y. Wang, Q. Zeng, H. Zhao, "Dynamic survivability in WDM mesh networks under dynamic traffic," Photonic Netw. Commun. 6, 5-24 (2003).
[CrossRef]

H. Wen, S. Wang, L. Li, "A routing algorithm for finding low-cost pair of no shared-risk paths," J. Electron. Info. Technol. 25, 824-830 (2003).

S. Ramamurthy, L. Sahasrabuddhe, B. Mukherjee, "Survivable WDM mesh networks," J. Lightwave. Technol. 21, 870-883 (2003).
[CrossRef]

1998 (1)

M. Barbehenn, "A note on the complexity of Dijkstra’s algorithm for graphs with weighted vertices," IEEE Trans. Comp. 47, 263 (1998).
[CrossRef]

1984 (1)

J. Suurballe, R. Tarjan, "A quick method for finding shortest pairs of disjoint paths," Networks,  14, 325-326 (1984).
[CrossRef]

Barbehenn, M.

M. Barbehenn, "A note on the complexity of Dijkstra’s algorithm for graphs with weighted vertices," IEEE Trans. Comp. 47, 263 (1998).
[CrossRef]

He, R.

R. He, H. Wen, L. Li, G. Wang, "Shared sub-path protection algorithm in traffic-grooming WDM mesh networks," Photonic Netw. Commun. 8, 239-249 (2004).
[CrossRef]

H. Wen, L. Li, R. He, H. Yu, S. Wang, N. Song, "Dynamic grooming algorithms for survivable WDM mesh networks," Photonic Netw. Commun. 7, 253-263 (2003).
[CrossRef]

Li, L.

R. He, H. Wen, L. Li, G. Wang, "Shared sub-path protection algorithm in traffic-grooming WDM mesh networks," Photonic Netw. Commun. 8, 239-249 (2004).
[CrossRef]

H. Wen, L. Li, R. He, H. Yu, S. Wang, N. Song, "Dynamic grooming algorithms for survivable WDM mesh networks," Photonic Netw. Commun. 7, 253-263 (2003).
[CrossRef]

H. Wen, S. Wang, L. Li, "A routing algorithm for finding low-cost pair of no shared-risk paths," J. Electron. Info. Technol. 25, 824-830 (2003).

Mukherjee, B.

C. Ou, J. Zhang, H. Zang, L. Sahasrabuddhe, B. Mukherjee, "New and improved approaches for shared-path protection in WDM mesh networks," J. Lightwave. Technol. 22, 1223-1232 (2004).
[CrossRef]

S. Ramamurthy, L. Sahasrabuddhe, B. Mukherjee, "Survivable WDM mesh networks," J. Lightwave. Technol. 21, 870-883 (2003).
[CrossRef]

Ou, C.

C. Ou, J. Zhang, H. Zang, L. Sahasrabuddhe, B. Mukherjee, "New and improved approaches for shared-path protection in WDM mesh networks," J. Lightwave. Technol. 22, 1223-1232 (2004).
[CrossRef]

Ramamurthy, S.

S. Ramamurthy, L. Sahasrabuddhe, B. Mukherjee, "Survivable WDM mesh networks," J. Lightwave. Technol. 21, 870-883 (2003).
[CrossRef]

Sahasrabuddhe, L.

C. Ou, J. Zhang, H. Zang, L. Sahasrabuddhe, B. Mukherjee, "New and improved approaches for shared-path protection in WDM mesh networks," J. Lightwave. Technol. 22, 1223-1232 (2004).
[CrossRef]

S. Ramamurthy, L. Sahasrabuddhe, B. Mukherjee, "Survivable WDM mesh networks," J. Lightwave. Technol. 21, 870-883 (2003).
[CrossRef]

Song, N.

H. Wen, L. Li, R. He, H. Yu, S. Wang, N. Song, "Dynamic grooming algorithms for survivable WDM mesh networks," Photonic Netw. Commun. 7, 253-263 (2003).
[CrossRef]

Suurballe, J.

J. Suurballe, R. Tarjan, "A quick method for finding shortest pairs of disjoint paths," Networks,  14, 325-326 (1984).
[CrossRef]

Tarjan, R.

J. Suurballe, R. Tarjan, "A quick method for finding shortest pairs of disjoint paths," Networks,  14, 325-326 (1984).
[CrossRef]

Wang, G.

R. He, H. Wen, L. Li, G. Wang, "Shared sub-path protection algorithm in traffic-grooming WDM mesh networks," Photonic Netw. Commun. 8, 239-249 (2004).
[CrossRef]

Wang, S.

H. Wen, S. Wang, L. Li, "A routing algorithm for finding low-cost pair of no shared-risk paths," J. Electron. Info. Technol. 25, 824-830 (2003).

H. Wen, L. Li, R. He, H. Yu, S. Wang, N. Song, "Dynamic grooming algorithms for survivable WDM mesh networks," Photonic Netw. Commun. 7, 253-263 (2003).
[CrossRef]

Wang, Y.

Y. Wang, Q. Zeng, H. Zhao, "Dynamic survivability in WDM mesh networks under dynamic traffic," Photonic Netw. Commun. 6, 5-24 (2003).
[CrossRef]

Wen, H.

R. He, H. Wen, L. Li, G. Wang, "Shared sub-path protection algorithm in traffic-grooming WDM mesh networks," Photonic Netw. Commun. 8, 239-249 (2004).
[CrossRef]

H. Wen, L. Li, R. He, H. Yu, S. Wang, N. Song, "Dynamic grooming algorithms for survivable WDM mesh networks," Photonic Netw. Commun. 7, 253-263 (2003).
[CrossRef]

H. Wen, S. Wang, L. Li, "A routing algorithm for finding low-cost pair of no shared-risk paths," J. Electron. Info. Technol. 25, 824-830 (2003).

Yu, H.

H. Wen, L. Li, R. He, H. Yu, S. Wang, N. Song, "Dynamic grooming algorithms for survivable WDM mesh networks," Photonic Netw. Commun. 7, 253-263 (2003).
[CrossRef]

Zang, H.

C. Ou, J. Zhang, H. Zang, L. Sahasrabuddhe, B. Mukherjee, "New and improved approaches for shared-path protection in WDM mesh networks," J. Lightwave. Technol. 22, 1223-1232 (2004).
[CrossRef]

Zeng, Q.

Y. Wang, Q. Zeng, H. Zhao, "Dynamic survivability in WDM mesh networks under dynamic traffic," Photonic Netw. Commun. 6, 5-24 (2003).
[CrossRef]

Zhang, J.

C. Ou, J. Zhang, H. Zang, L. Sahasrabuddhe, B. Mukherjee, "New and improved approaches for shared-path protection in WDM mesh networks," J. Lightwave. Technol. 22, 1223-1232 (2004).
[CrossRef]

Zhao, H.

Y. Wang, Q. Zeng, H. Zhao, "Dynamic survivability in WDM mesh networks under dynamic traffic," Photonic Netw. Commun. 6, 5-24 (2003).
[CrossRef]

IEEE Trans. Comp. (1)

M. Barbehenn, "A note on the complexity of Dijkstra’s algorithm for graphs with weighted vertices," IEEE Trans. Comp. 47, 263 (1998).
[CrossRef]

J. Electron. Info. Technol. (1)

H. Wen, S. Wang, L. Li, "A routing algorithm for finding low-cost pair of no shared-risk paths," J. Electron. Info. Technol. 25, 824-830 (2003).

J. Lightwave. Technol. (2)

C. Ou, J. Zhang, H. Zang, L. Sahasrabuddhe, B. Mukherjee, "New and improved approaches for shared-path protection in WDM mesh networks," J. Lightwave. Technol. 22, 1223-1232 (2004).
[CrossRef]

S. Ramamurthy, L. Sahasrabuddhe, B. Mukherjee, "Survivable WDM mesh networks," J. Lightwave. Technol. 21, 870-883 (2003).
[CrossRef]

Networks (1)

J. Suurballe, R. Tarjan, "A quick method for finding shortest pairs of disjoint paths," Networks,  14, 325-326 (1984).
[CrossRef]

Photonic Netw. Commun. (3)

R. He, H. Wen, L. Li, G. Wang, "Shared sub-path protection algorithm in traffic-grooming WDM mesh networks," Photonic Netw. Commun. 8, 239-249 (2004).
[CrossRef]

H. Wen, L. Li, R. He, H. Yu, S. Wang, N. Song, "Dynamic grooming algorithms for survivable WDM mesh networks," Photonic Netw. Commun. 7, 253-263 (2003).
[CrossRef]

Y. Wang, Q. Zeng, H. Zhao, "Dynamic survivability in WDM mesh networks under dynamic traffic," Photonic Netw. Commun. 6, 5-24 (2003).
[CrossRef]

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

Fig. 1.
Fig. 1.

Illustration of TASA based on Suurballe’s algorithm: (a) a primary path A-B-C-D-E; (b) a testing path A-F-G-D-C-H-I-E; (c) a primary path A-F-G-D-E and a link-disjoint backup path A-B-C-H-I-E.

Fig. 2.
Fig. 2.

Illustration of QMSP based on Dijkstra’s algorithm: (a) a primary path A-B-C-D-E; (b) two segment-backup paths A-F-G-D and C-H-I-E.

Fig. 3.
Fig. 3.

Backup resources for TASA and QMSP: (a) backup resources in TSAS ; (b) multiple segment-backup paths; (c) a solution for QMSP; (d) another solution for QMSP.

Fig. 4.
Fig. 4.

Test network topology: National network.

Fig. 5.
Fig. 5.

(a) Resource Consumed Ratio (RCR); (b) Blocking Probability (BR)

Tables (1)

Tables Icon

Table 1. Process of QMSP

Equations (2)

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

c j * = { + , If ( f w j = 0 ) c j ( W + 1 f w j ) W , Other
c j * = { + , If j p n or f w j + r w j < v j * c j ( v j * + 1 r w j ) W , Other

Metrics