skip to main content
article

Improved quasi-path restoration in mesh networks

Published: 01 February 2008 Publication History

Abstract

Restoration of disrupted traffic is critical in today's high-speed self-healing telecommunication networks. A restoration scheme dynamically discovers alternate paths bypassing the failed component. This paper presents an (online) improved quasi-path restoration (IQPR) scheme. IQPR is derived from the two-commodity max-flow algorithm. The running time complexity of IQPR is O(|V|3). Therefore, IQPR is computationally more efficient and more scalable than path restoration (PR). IQPR is faster (in restoration speed) and less complex than PR, and more economical (in spare capacity requirement) than link restoration (LR). Thus, it provides a good alternative to PR when quick restoration of disrupted traffic is desired.
The (offline) spare capacity planning problem deals with the allocation of spare capacity to each link in the network, such that the spare capacity requirement is minimized, while guaranteeing the desired level of restoration in the event of a link failure. The spare capacity allocation problems for LR, original quasi-path restoration (OQPR), IQPR, link-disjoint path restoration (LDPR) and PR are formulated as integer linear programming problems. Numerical results illustrate that the restoration schemes studied can be sorted from the least efficient to the most efficient (in the spare capacity requirement) in the following order: LR, OQPR, IQPR, LDPR and PR.
The experimental analysis shows that network topology and demand patterns have a significant impact on the spare capacity savings offered by one scheme over the other. Merits and demerits of these schemes are also discussed.

References

[1]
{1} E. C. Chow, J. Bicknell, S. McCaughey, and S. Syed, "A fast distributed network restoration algorithm," in Proc. Computers and Communications , Tempe, AZ, Mar. 1993, pp. 261-267.
[2]
{2} H. Komine, T. Chujo, T. Ogura, K. Miyazaki, and T. Soejima, "A distributed restoration algorithm for multiple-link and node failures of transport networks," in Proc. IEEE GLOBECOM, San Diego, CA, Dec. 1990, vol. 1, pp. 459-463.
[3]
{3} R. R. Iraschko, W. Grover, and M. MacGregor, "A distributed real time path restoration protocol with performance close to centralized multi-commodity max flow," in Proc. 1st Int. Conf. Design of Reliable Communication Networks, Brugge, Belgium, May 1998, paper O9.
[4]
{4} B. T. Doshi, S. Dravida, P. Harshavardhana, O. Hauser, and Y. Wang, "Optical network design and restoration," Bell Labs. Tech. J., vol. 4, no. 1, pp. 58-84, Jan./Mar. 1999.
[5]
{5} J. Anderson, B. Doshi, S. Dravida, and P. Harshavardhana, "Fast restoration of ATM networks," IEEE J. Sel. Areas Commun., vol. 12, no. 1, pp. 128-138, Jan. 1994.
[6]
{6} S. S. Lumetta, M. Médard, and Y.-C. Tseng, "Capacity versus robustness: A tradeoff for link restoration in mesh networks," J. Lightw. Technol., vol. 18, no. 12, pp. 1765-1775, Dec. 2000.
[7]
{7} S. Venkatesan, M. Patel, and N. Mittal, "A distributed algorithm for path restoration in circuit switched communication networks," in Proc. IEEE Symp. Reliable Distrib. Syst., Orlando, FL, Oct. 2005, pp. 226-236.
[8]
{8} Y. Xiong and L. G. Mason, "Restoration strategies and spare capacity requirements in self-healing ATM networks," IEEE/ACM Trans. Networking , vol. 7, no. 1, pp. 98-110, Feb. 1999.
[9]
{9} P. Demeester, M. Gryseels, A. Autenrieth, C. Brianza, L. Castagna, G. Signorelli, R. Clemente, M. Ravera, A. Jajszczyk, D. Janukowicz, K. V. Doorselaere, and Y. Harada, "Resilience in multilayer networks," IEEE Commun. Mag., vol. 37, no. 8, pp. 70-76, Aug. 1999.
[10]
{10} W. Lai and D. McDysan, "Network hierarchy and multilayer survivability," RFC 3386, Nov. 2002.
[11]
{11} L. Shen, X. Yang, and B. Ramamurthy, "Shared risk link group (SRLG)-diverse path provisioning under hybrid service level agreements in wavelength-routed optical mesh networks," IEEE/ACM Trans. Networking, vol. 13, no. 4, pp. 918-931, Aug. 2005.
[12]
{12} D. Xu, Y. Xiong, C. Qiao, and G. Li, "Failure protection in layered networks with shared risk link groups," IEEE Network, vol. 18, no. 3, pp. 36-41, May/Jun. 2004.
[13]
{13} V. Jain, S. Alagar, S. I. Baig, and S. Venkatesan, "Optimal quasi-path restoration in telecom backbone networks," in Proc. 13th Int. Conf. Systems Engineering, Las Vegas, NV, Aug. 1999, pp. CS-175-CS-180.
[14]
{14} R. R. Iraschko, M. H. MacGregor, and W. D. Grover, "Optimal capacity placement for path restoration in mesh survivable network," in Proc. IEEE Int. Conf. Communications (ICC), Dallas, TX, Jun. 1996, vol. 3, pp. 1568-1574.
[15]
{15} K. Murakami and H. S. Kim, "Joint optimization of capacity and flow assignment for self-healing ATM networks," in Proc. IEEE Int. Conf. Communications (ICC), Seattle, WA, Jun. 1995, vol. 1, pp. 216-220.
[16]
{16} A. V. Goldberg and R. E. Tarjan, "A new approach to the maximum-flow problem," J. Assoc. Comput. Machin., vol. 35, no. 4, pp. 921-940, Oct. 1988.
[17]
{17} S. Even, A. Itai, and A. Shamir, "On the complexity of timetable and multi-commodity flow problems," SIAM J. Comput., vol. 5, no. 4, pp. 691-703, 1976.
[18]
{18} D. A. Dunn, W. D. Grover, and M. H. MacGregor, "Comparison of k-shortest paths and maximum flow routing for network facility restoration," IEEE J. Sel. Areas Commun., vol. 12, no. 1, pp. 88-99, Jan. 1994.
[19]
{19} G. Shen and W. D. Grover, "Segment-based approaches to survivable translucent network design under various ultra-long-haul system reach capabilities," OSA J. Opt. Netw., vol. 3, no. 1, pp. 1-24, Jan. 2004.
[20]
{20} K. P. Gummadi, M. J. Pradeep, and C. S. R. Murthy, "An efficient primary-segmented backup scheme for dependent real-time communication in multihop networks," IEEE/ACM Trans. Networking, vol. 11, no. 1, pp. 81-94, Feb. 2003.
[21]
{21} P.-H. Ho, J. Tapolcai, and T. Cinkler, "Segment shared protection in mesh communications networks with bandwidth guaranteed tunnels," IEEE/ACM Trans. Networking, vol. 12, no. 6, pp. 1105-1118, Dec. 2004.
[22]
{22} D. Xu, Y. Xiong, and C. Qiao, "Novel algorithms for shared segment protection," IEEE J. Sel. Areas Commun., vol. 21, no. 8, pp. 1320-1331, Oct. 2003.
[23]
{23} M. Herzberg, S. J. Bye, and A. Utano, "The hop-limit approach for spare-capacity assignment in survivable networks," IEEE/ACM Trans. Networking, vol. 3, no. 6, pp. 775-784, Dec. 1995.
[24]
{24} M. Herzberg, D. Wells, and A. Herschtal, "Optimal resource allocation for path restoration in mesh-type self-healing networks," in Proc. 15th Int. Teletraffic Congr., Washington, DC, Jun. 1997, vol. 15, pp. 351-360.
[25]
{25} R. R. Iraschko, M. H. MacGregor, and W. D. Grover, "Optimal capacity placement for path restoration in STM or ATM mesh survivable networks," IEEE/ACM Trans. Networking, vol. 6, no. 3, pp. 325-336, Jun. 1998.
[26]
{26} T. H. Oh, T. M. Chen, and J. L. Kennington, "Fault restoration and spare capacity allocation with QoS constraints for MPLS networks," in Proc. IEEE Global Communications Conf., San Francisco, CA, Nov. 2000, pp. 1731-1735.
[27]
{27} D. Medhi and D. Tipper, "Some approaches to solving a multihour broadband network capacity design problem with single-path routing," Telecommun. Syst., vol. 13, no. 2, pp. 269-291, 2000.
[28]
{28} B. V. Caenegem, W. V. Parys, F. D. Turck, and P. M. Demeester, "Dimensioning of survivable WDM networks," IEEE J. Sel. Areas Commun., vol. 16, no. 7, pp. 1146-1157, Sep. 1998.
[29]
{29} Y. Liu, D. Tipper, and P. Siripongwutikorn, "Approximating optimal spare capacity allocation by successive survivable routing," in Proc. IEEE INFOCOM, Anchorage, AK, Apr. 2001, vol. 2, pp. 699-708.
[30]
{30} S. Orlowski and R. Wessly, "Comparing restoration concepts using optimal network configurations with integrated hardware and routing decisions," J. Netw. Syst. Manag., vol. 13, no. 1, pp. 99-118, Mar. 2005.
[31]
{31} T. C. Hu, "Multi-commodity network flows," Oper. Res., vol. 11, pp. 344-360, May/Jun. 1963.
[32]
{32} A. Itai, "Two-commodity flow," J. ACM, vol. 25, no. 4, pp. 596-611, Oct. 1978.
[33]
{33} B. Awerbuch, "Reducing complexities of the distributed max-flow and breadth-first-search algorithms by means of network synchronization," Networks, vol. 15, no. 4, pp. 425-437, 1985.
[34]
{34} Digital cross-connect systems in transport network survivability Bellcore, Special Report SR-NWT-002514, Jan. 1993, Issue 1.
[35]
{35} Using the CPLEX Callable Library. Incline Village, NV: ILOG Inc., 1997.

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 16, Issue 1
February 2008
245 pages

Publisher

IEEE Press

Publication History

Published: 01 February 2008
Published in TON Volume 16, Issue 1

Author Tags

  1. integer linear programming
  2. link restoration
  3. network survivability
  4. path restoration
  5. quasi-path restoration
  6. selfhealing networks
  7. spare capacity allocation

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 236
    Total Downloads
  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 27 Jan 2025

Other Metrics

Citations

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