Enhancing Network Survivability Using Routing and Link Weight Assignment to Avoid Congestion

Enhancing Network Survivability Using Routing and Link Weight Assignment to Avoid Congestion

P.K. Tseng W.H. Chung C.F. Wu C.H. Wu

Research Center for Information Technology Innovation Academia Sinica, Taiwan

| |
| | Citation



The modern wired networks transport high data rates, where a single-network failure often causes enormous packet losses. To provide adequate protection for all source–destination pairs remains a critical issue in modern networks. In this article, a high survivability Internet Protocol (IP) fast-reroute scheme against single-link and single-node failures is first described, and then a Mixed Integer Non-linear Programming (MINP) is formulated to determine link weights so as to maximize the survivability of networks running the IP fast-reroute scheme. A simulated annealing-based routing and weight assignment scheme is proposed to approximate the optimal solution of the MINP. The simulations demonstrate that the proposed scheme can improve network survivability rate up to 83–100% for single-link failures, and 78–100% for single-node failures, and achieve reasonably good load balancing in five benchmark networks.


IP fast-reroute, load balance, loop-free, single-link and single-node failures, survivability


[1] Basu, A. & Riecke, J.G., Stability issues in OSPF routing. Proceedings of ACM SIGCOMM, pp. 225–236, August 2001. doi: http://dx.doi.org/10.1145/383059.383077

[2] Watson, D., Jahanian, F. & Labovitz, C., Experiences with monitoring OSPF on a regional service provider network. Proceedings of IEEE ICDCS, pp. 204–213, 2003.

[3] Moy, J., OSPF Version 2, IETF RFC 2328, April 1998. doi: http://dx.doi.org/10.1109/ icdcs.2003.1203467

[4] Goyal, M., Ramakrishnan, K.K. & Feng, W.-C., Achieving faster failure detection in OSPF networks. Proceedings of IEEE ICC, pp.296–300, May 2003. doi: http://dx.doi. org/10.1109/icc.2003.1204188

[5] Francois, P., Filsfils, C., Evans, J. & Bonaventure, O., Achieving sub-second IGP convergence in large IP networks. ACM SIGCOMM Computer Communication Review, 35(2), pp. 35–44, 2005. doi: http://dx.doi.org/10.1145/1070873.1070877

[6] Alattinoglu, C., Jacobson, V. & Yu, H., Towards milli-second IGP convergence, IETF Internet Draft, draft-alaettinoglu-ISISconvergence-00.txt, November 2000.

[7] Alattinoglu, C. & Casner, S., ISIS routing on the Qwest backbone: a recipe for subsecond ISIS convergence. Presented at the NANOG Meeting, Miami, FL, 2002.

[8] Eramo, V., Listanti, M. & Cianfrani, A., Design and evaluation of a new multi-path incremental routing algorithm on software routers. IEEE/ACM Transactions on Network and Service Management, 4(4), pp. 188–203, 2008. doi:http://dx.doi.org/10.1109/ tnsm.2009.041101

[9] Francois, P. & Bonaventure, O., Avoiding transient loops during the convergence of link-state routing protocols. IEEE/ACM Transactions on Networking, 15(6), pp. 1280–1292, 2007. doi: http://dx.doi.org/10.1109/tnet.2007.902686

[10] Fu, J., Sjödin, P. & Karlsson, G., Loop-free updates of forwarding tables. IEEE/ACM Transactions on Network and Service Management, 5(1), pp. 22–35, 2008. doi: http:// dx.doi.org/10.1109/tnsm.2008.080103

[11] Hopps, C. Analysis of an equal-cost multi-path algorithm. IETF RFC 2992, 2000.

[12] Atlas, A. & Zinin, A., Basic specification for IP fast reroute: loop-free alternates, IETF Internet Draft, draft-ietf-rtgwg-ipfrr-spec-base-04.txt, 2005.

[13] Atlas, A. U-turn alternates for IP/LDP fast-reroute, IETF Internet Draft, draft-atlas-iplocal-protect-uturn-03.txt, 2006.

[14] Raj, A. & Ibe, O.C. A survey of IP and multiprotocol label switching fast reroute schemes. Computer Networks, 51(8), pp. 1882–1907, 2007. doi: http://dx.doi.org/10.1016/j.comnet.2006.09.010

[15] Gjoka, M., Ram, V. & Yang, X., Evaluation of IP fast reroute proposals. Proceedings of COMSWARE, pp. 1–8, Jan. 2007. doi: http://dx.doi.org/10.1109/comswa.2007.382443

[16] Bryant, S., Filsfils, C., Previdi, S. & Shand, M., IP fast reroute using tunnels, IETF Internet Draft, draft-bryantipfrr-tunnels-02.txt, April 2005.

[17] Bryant, S., Shand, M. & Previdi, S., IP fast reroute using not-via addresses, IETF Internet Draft, draft-bryant-shand-IPFRR-notviaaddresses-01.txt, 2005.

[18] Kini, S., Ramasubramanian, S., Kvalbein, A. & Hansen, A.F., Fast recovery from duallink or single-node failures in IP networks using tunneling. IEEE/ACM Transactions on Networking, 18(6), pp. 1988–1999, December 2010. doi:http://dx.doi.org/10.1109/ tnet.2010.2055887

[19] Kvalbein, A., Hansen, A.F., Cˇicˇic´, T., Gjessing, S. & Lysne, O., Fast IP network recovery using multiple routing configurations. Proceedings of IEEE INFOCOM, April 2006. doi: http://dx.doi.org/10.1109/infocom.2006.227

[20] Kvalbein, A., Hansen, A.F., Cˇicˇic´, T., Gjessing, S. & Lysne, O., Multiple routing configurations for fast IP network recovery. IEEE/ACM Transactions on Networking, 17(2), pp. 473–486, April 2009. doi: http://dx.doi.org/10.1109/tnet.2008.926507

[21] Cˇicˇic´, T., Hansen, A.F., Kvalbein, A., Hartmann, M., Martin, R., Menth, M., Gjessing, S. & Lysne, O., Relaxed multiple routing configurations: IP fast reroute for single and correlated failures. IEEE/ACM Transactions on Network and Service Management, 6(1), pp. 1–14, 2009. doi: http://dx.doi.org/10.1109/tnsm.2009.090301

[22] Nelakuditi, S., Lee, S., Yu, Y., Zhang, Z.-L. & Chuah, C.-N., Fast local rerouting for handling transient link failures. IEEE/ACM Transactions on Networking, 15(2), pp. 359–372, April 2007. doi: http://dx.doi.org/10.1109/tnet.2007.892851

[23] Menth, M. & Martin, R., Network resilience through multi-topology routing. Proceedings of the 5th International Workshop on Design of Reliable Communication Networks (DRCN), October 2005. doi: http://dx.doi.org/10.1109/drcn.2005.1563878

[24] Kvalbein, A., Cˇicˇic´, T. & Gjessing, S., Post-failure routing performance with multiple routing configurations. Proceedings of IEEE INFOCOM, April 2007. doi: http://dx.doi. org/10.1109/infcom.2007.20

[25] Nelakuditi, S., Lee, S., Yu, Y. & Zhang, Z.-L., Failure insensitive routing for ensuring service availability. Proceedings of the International Workshop Quality Service (IWQoS), pp. 287–304, 2003. doi: http://dx.doi.org/10.1007/3-540-44884-5_16

[26] Lee, S., Yu, Y., Nelakuditi, S., Zhang, Z.-L. & Chuah, C.-N., Proactive versus reactive approaches to failure resilient routing. Proceedings of IEEE INFOCOM, pp. 176–186, 2004. doi: http://dx.doi.org/10.1109/infcom.2004.1354492

[27] Zhong, Z., Nelakuditi, S., Yu, Y., Lee, S., Wang, J. & Chuah, C.-N., Failure inferencing based fast rerouting for handling transient link and node failures. Proceedings of IEEE INFOCOM, pp. 1–5, April 2006. doi: http://dx.doi.org/10.1109/infcom.2005.1498576

[28] Oran, D., OSI IS-IS intra-domain routing protocol, IETF Request for Comments 1142. [29] Psenak, P., Mirtorabi, S., Roy, A., Nguen, L. & Pillay-Esnault, P., MTOSPF: Multi topology (MT) routing in OSPF, IETF, RFC4915, June 2007.

[30] Przygienda, T., Shen, N. & Sheth, N., M-ISIS: Multi topology (MT) routing in IS-IS, IETF RFC 5120, February 2008.

[31] Kwong, K.-W., Guérin, R., Shaikh, A. & Tao, S., Balancing performance, robustness and flexibility in routing systems. IEEE/ACM Transactions on Network and Service Management, 7(3), pp. 186–199, September 2010. doi: http://dx.doi.org/10.1145/1544012.1544022

[32] Xi, K. & Chao, H. J., IP fast rerouting for single-link/node failure recovery. Fourth International Conference on Broadband Communications, Networks and Systems (BROADNETS), pp. 142–151, September 2007. doi:http://dx.doi.org/10.1109/broadnets.2007.4550418

[33] Bejerano, Y., Breitbart, Y., Orda, A., Rastogi, R. & Sprintson, A., Algorithms for computing QoS paths with restoration. Proceedings of IEEE INFOCOM, pp. 1435–1445, 2003. doi: http://dx.doi.org/10.1109/infcom.2003.1208979

[34] Wei, C.-Y. & Naraghi-Pour, M., Path restoration with QoS and label constraints in MPLS networks. Proceedings of IEEE ICC, pp. 1278–1282, 2004. doi: http://dx.doi.org/10.1109/icc.2004.1312705

[35] Wang, D. & Li, G., Efficient distributed bandwidth management for MPLS fast reroute. IEEE/ACM Transactions on Networking, 16(2), pp. 486–495, 2008. doi: http://dx.doi. org/10.1109/tnet.2007.900411

[36] Sharma, V., Framework for MPLS-based recovery, IETF Internet Draft, draft-ietf-mplsrecovery-frmwrk-03.txt, January 2002.

[37] Fortz, B. & Thorup, M., Internet traffic engineering by optimizing OSPF weights. Proceedings of IEEE INFOCOM, pp. 519–528, 2000. doi: http://dx.doi.org/10.1109/infcom.2000.832225

[38] Kirkpatrick, S., Gelatt, C.D., Jr. & Vecchi, M.P. Optimization by simulated annealing Science, 220(4598), pp. 671–680, May 1983.

[39] Iannaccone, G., Chuah, C., Mortier, R., Bhattacharyya, S. & Diot, C., Analysis of link failures in an IP backbone. Proceedings of ACM SIGCOMM Internet Measurement Workshop, November 2002. doi: http://dx.doi.org/10.1145/637235.637238

[40] Markopoulou, A., Iannaccone, G., Bhattacharyya, S., Chuah, C.-N. & Diot, C., Characterization of failures in an IP backbone network. Proceedings of IEEE INFOCOM, March 2004. doi: http://dx.doi.org/10.1109/infcom.2004.1354653

[41] Tseng, P., Chung, W., Lin, K.C., Shih, C. & Chen, L., Physical-layer communication recovery for heterogeneous network. Disaster Management and Human Health Risk III: Reducing Risk, Improving Outcomes, WIT Press: A Coruña, Spain, 2013. doi:http:// dx.doi.org/10.2495/dman130181