Improved quasi-path restoration in mesh networks

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|³). 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: S. Venkatesan , Maulin Patel , Neeraj Mittal, A Distributed Algorithm for Path Restoration in Circuit Switched Communication Networks, Proceedings of the 24th IEEE Symposium on Reliable Distributed Systems, p.226-236, October 26-28, 2005 [doi>10.1109/RELDIS.2005.5]
• 8: Yijun Xiong , Lorne G. Mason, Restoration strategies and spare capacity requirements in self-healing ATM networks, IEEE/ACM Transactions on Networking (TON), v.7 n.1, p.98-110, Feb. 1999 [doi>10.1109/90.759330]
• 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: W. Lai , D. McDysan, Network Hierarchy and Multilayer Survivability, RFC Editor, 2002
• 11: Lu Shen , Xi Yang , Byrav Ramamurthy, Shared risk link group (SRLG)-diverse path provisioning under hybrid service level agreements in wavelength-routed optical mesh networks, IEEE/ACM Transactions on Networking (TON), v.13 n.4, p.918-931, August 2005 [doi>10.1109/TNET.2005.852879]
• 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: Andrew V. Goldberg , Robert E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM (JACM), v.35 n.4, p.921-940, Oct. 1988 [doi>10.1145/48014.61051]
• 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: Krishna Phani Gummadi , Madhavarapu Jnana Pradeep , C. Siva Ram Murthy, An efficient primary-segmented backup scheme for dependable real-time communication in multihop networks, IEEE/ACM Transactions on Networking (TON), v.11 n.1, p.81-94, February 2003 [doi>10.1109/TNET.2002.808405]
• 21: Pin-Han Ho , János Tapolcai , Tibor Cinkler, Segment shared protection in mesh communications networks with bandwidth guaranteed tunnels, IEEE/ACM Transactions on Networking (TON), v.12 n.6, p.1105-1118, December 2004 [doi>10.1109/TNET.2004.838592]
• 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: Meir Herzberg , Stephen J. Bye , Anthony Utano, The hop-limit approach for spare-capacity assignment in survivable networks, IEEE/ACM Transactions on Networking (TON), v.3 n.6, p.775-784, Dec. 1995 [doi>10.1109/90.477723]
• 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: Rainer R. Iraschko , M. H. MacGregor , Wayne D. Grover, Optimal capacity placement for path restoration in STM or ATM mesh-survivable networks, IEEE/ACM Transactions on Networking (TON), v.6 n.3, p.325-336, June 1998 [doi>10.1109/90.700896]
• 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: Sebastian Orlowski , Roland Wessäly, Comparing Restoration Concepts Using Optimal Network Configurations with Integrated Hardware and Routing Decisions, Journal of Network and Systems Management, v.13 n.1, p.99-118, March 2005 [doi>10.1007/s10922-005-1864-3]
• 31: [31] T. C. Hu, "Multi-commodity network flows," Oper. Res., vol. 11, pp. 344-360, May/Jun. 1963.
• 32: Alon Itai, Two-Commodity Flow, Journal of the ACM (JACM), v.25 n.4, p.596-611, Oct. 1978 [doi>10.1145/322092.322100]
• 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.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming; Integer programming
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Design

Keywords:
integer linear programming, link restoration, network survivability, path restoration, quasi-path restoration, selfhealing networks, spare capacity allocation