K-Backup: Load- and TCAM-Aware Multi-Backup Fast Failure Recovery in SDNs
Pages 3347 - 3360
Abstract
The Proactive Recovery (PR) mechanism in Software-Defined Networking (SDN) provides good failure recovery resilience for the Beyond Fifth-Generation/Sixth-Generation (B5G/6G) delay-sensitive applications. However, PR’s fixed single backup path policy for any flow and fine-grained backup forwarding rule configuration poses severe challenges for post-recovery congestion management and limited Ternary Content Addressable Memory (TCAM) space in SDN switches. To this end, we propose K-backup, a load- and TCAM-aware multi-backup fast failure recovery scheme for SDNs. Firstly, K-backup formulates and solves the congestion-aware multi-backup path planning problem for various failure scenarios, exploiting the inherent load diversity of multi-backup paths to minimize the post-recovery maximum link utilization. Secondly, K-backup aggregates flows sharing the same backup-path-weight pair on a link into a cascading table of Fast-Failover and SELECT groups. Meanwhile, each outputted backup path is labeled, and a corresponding label-matching flow table is configured for each intermediate switch to aggregate all flows on that path. Thirdly, K-backup dynamically adjusts the backup path update period based on the network load stabilization to reduce unnecessary controller overhead. Compared with state-of-the-art, K-backup achieves the lowest controller overhead, the best load balancing performance, the near-fewest TCAM space usage, and the near-shortest recovery time.
References
[1]
L. U. Khan, I. Yaqoob, M. Imran, Z. Han, and C. S. Hong, “6G wireless systems: A vision, architectural elements, and future directions,” IEEE Access, vol. 8, pp. 147029–147044, 2020.
[2]
M. Katz, P. Pirinen, and H. Posti, “Towards 6G: Getting ready for the next decade,” in Proc. 16th Int. Symp. Wireless Commun. Syst. (ISWCS), Aug. 2019, pp. 714–718.
[3]
M. Shokrnezhad and T. Taleb, “Near-optimal cloud-network integrated resource allocation for latency-sensitive B5G,” in Proc. IEEE Global Commun. Conf., Dec. 2022, pp. 4498–4503.
[4]
M. Alizadehet al., “Data center TCP (DCTCP),” in Proc. ACM SIGCOMM Conf., Aug. 2010, pp. 63–74.
[5]
G. DeCandia, “Dynamo: Amazon’s highly available key-value store,” ACM SIGOPS Operating Syst. Rev., vol. 41, no. 6, pp. 205–220, 2007.
[6]
D. C. Nguyenet al., “6G Internet of Things: A comprehensive survey,” IEEE Internet Things J., vol. 9, no. 1, pp. 359–383, Mar. 2021.
[7]
D. Kreutz, F. M. V. Ramos, P. E. Veríssimo, C. E. Rothenberg, S. Azodolmolky, and S. Uhlig, “Software-defined networking: A comprehensive survey,” Proc. IEEE, vol. 103, no. 1, pp. 14–76, Jan. 2015.
[8]
S. Sun, L. Gong, B. Rong, and K. Lu, “An intelligent SDN framework for 5G heterogeneous networks,” IEEE Commun. Mag., vol. 53, no. 11, pp. 142–147, Nov. 2015.
[9]
F. Z. Yousaf, M. Bredel, S. Schaller, and F. Schneider, “NFV and SDN—Key technology enablers for 5G networks,” IEEE J. Sel. Areas Commun., vol. 35, no. 11, pp. 2468–2478, Nov. 2017.
[10]
N. McKeownet al., “OpenFlow: Enabling innovation in campus networks,” ACM SIGCOMM Comput. Commun. Rev., vol. 38, no. 2, pp. 69–74, Mar. 2008.
[11]
J. Kempf, E. Bellagamba, A. Kern, D. Jocha, A. Takacs, and P. Sköldström, “Scalable fault management for OpenFlow,” in Proc. IEEE Int. Conf. Commun. (ICC), Jun. 2012, pp. 6606–6610.
[12]
A. X. Liu, C. R. Meiners, and E. Torng, “TCAM razor: A systematic approach towards minimizing packet classifiers in TCAMs,” IEEE/ACM Trans. Netw., vol. 18, no. 2, pp. 490–500, Apr. 2010.
[13]
Y.-D. Lin, H.-Y. Teng, C.-R. Hsu, C.-C. Liao, and Y.-C. Lai, “Fast failover and switchover for link failures and congestion in software defined networks,” in Proc. IEEE Int. Conf. Commun. (ICC), May 2016, pp. 1–6.
[14]
M. M. Tajiki, M. Shojafar, B. Akbari, S. Salsano, M. Conti, and M. Singhal, “Joint failure recovery, fault prevention, and energy-efficient resource management for real-time SFC in fog-supported SDN,” Comput. Netw., vol. 162, Oct. 2019, Art. no.
[15]
L. Zheng, H. Xu, S. Chen, and L. Huang, “Performance guaranteed single link failure recovery in SDN overlay networks,” in Proc. IEEE 26th Int. Conf. Parallel Distrib. Syst. (ICPADS), Dec. 2020, pp. 703–708.
[16]
Z. Yang and K. L. Yeung, “SDN candidate selection in hybrid IP/SDN networks for single link failure protection,” IEEE/ACM Trans. Netw., vol. 28, no. 1, pp. 312–321, Feb. 2020.
[17]
J. Chen, J. Chen, J. Ling, and W. Zhang, “Failure recovery using vlan-tag in SDN: High speed with low memory requirement,” in Proc. IEEE 35th Int. Perform. Comput. Commun. Conf. (IPCCC), Dec. 2016, pp. 1–9.
[18]
P. Murali Mohan, T. Truong-Huu, and M. Gurusamy, “Fault tolerance in TCAM-limited software defined networks,” Comput. Netw., vol. 116, pp. 47–62, Apr. 2017.
[19]
S. Feng, Y. Wang, X. Zhong, J. Zong, X. Qiu, and S. Guo, “A ring-based single-link failure recovery approach in SDN data plane,” in Proc. IEEE/IFIP Netw. Oper. Manage. Symp., Apr. 2018, pp. 1–7.
[20]
L. Wang, L. Yao, Z. Xu, G. Wu, and M. S. Obaidat, “CFR: A cooperative link failure recovery scheme in software-defined networks,” Int. J. Commun. Syst., vol. 31, no. 10, p. e3560, Jul. 2018.
[21]
S. Wang, H. Xu, L. Huang, X. Yang, and J. Liu, “Fast recovery for single link failure with segment routing in SDNs,” in Proc. IEEE 21st Int. Conf. High Perform. Comput. Commun.; IEEE 17th Int. Conf. Smart City; IEEE 5th Int. Conf. Data Sci. Syst. (HPCC/SmartCity/DSS), Aug. 2019, pp. 2013–2018.
[22]
C.-Y. Chu, K. Xi, M. Luo, and H. J. Chao, “Congestion-aware single link failure recovery in hybrid SDN networks,” in Proc. IEEE Conf. Comput. Commun. (INFOCOM), Oct. 2015, pp. 1086–1094.
[23]
S. Petale and J. Thangaraj, “Link failure recovery mechanism in software defined networks,” IEEE J. Sel. Areas Commun., vol. 38, no. 7, pp. 1285–1292, Jul. 2020.
[24]
T. Mori, M. Uchida, R. Kawahara, J. Pan, and S. Goto, “Identifying elephant flows through periodically sampled packets,” in Proc. 4th ACM SIGCOMM Conf. Internet Meas., 2004, pp. 115–120.
[25]
J. Goodman, A. G. Greenberg, N. Madras, and P. March, “Stability of binary exponential backoff,” J. ACM, vol. 35, no. 3, pp. 579–602, Jun. 1988.
[26]
R. L. S. De Oliveira, C. M. Schweitzer, A. A. Shinoda, and L. R. Prete, “Using mininet for emulation and prototyping software-defined networks,” in Proc. IEEE Colombian Conf. Commun. Comput. (COLCOM), May 2014, pp. 1–6.
[27]
M. R. Gary and D. S. Johnson, Computers and Intractability. San Francisco, CA, USA: Freeman, 1979.
[28]
J. W. Guck, A. Van Bemten, M. Reisslein, and W. Kellerer, “Unicast QoS routing algorithms for SDN: A comprehensive survey and performance evaluation,” IEEE Commun. Surveys Tuts., vol. 20, no. 1, pp. 388–415, 1st Quart., 2018.
[29]
N. Zadeh, “Theoretical efficiency of the Edmonds–Karp algorithm for computing maximal flows,” J. ACM, vol. 19, no. 1, pp. 184–192, Jan. 1972.
[30]
S. Q. Zhanget al., “TCAM space-efficient routing in a software defined network,” Comput. Netw., vol. 125, pp. 26–40, Oct. 2017.
[31]
Ryu Project Team. (2023). Ryu SDN Controller. [Online]. Available: https://ryu-sdn.org/
[32]
J. H. Kim and V. H. Vu, “Generating random regular graphs,” in Proc. 35th Annu. ACM Symp. Theory Comput., 2003, pp. 213–222.
[33]
W. Dobosiewicz and P. Gburzynski, “A bounded-hop-count deflection scheme for Manhattan-street networks,” in Proc. Conf. Comput. Commun., 1996, pp. 172–179.
[34]
A.-L. Barabási and E. Bonabeau, “Scale-free networks,” Sci. Amer., vol. 288, no. 5, pp. 60–69, May 2003.
[35]
S. Sharma, D. Staessens, D. Colle, M. Pickavet, and P. Demeester, “Enabling fast failure recovery in OpenFlow networks,” in Proc. 8th Int. Workshop Design Reliable Commun. Netw. (DRCN), Oct. 2011, pp. 164–171.
[36]
L. Shu, J. Hao, Y. Song, C. Li, and D. Wang, “Optimal many-to-many personalized concurrent communication in RapidIO-based fat-trees,” in Proc. 17th IEEE/ACIS Int. Conf. Softw. Eng., Artif. Intell., Netw. Parallel/Distributed Comput. (SNPD), May 2016, pp. 343–350.
[37]
SpaceX Starlink. (2023). Starlink. [Online]. Available: https://www.starlink.com/
[38]
B. Chappell. (2023). SpaceX Says Up to 40 of Its New Starlink Satellites Are Falling Out of Orbit. [Online]. Available: https://www.npr.org/2022/02/09/1079575679/spacex-40-starlink-satellites-destroyed
[39]
V. Liu, D. Halperin, A. Krishnamurthy, and T. Anderson, “F10: A fault-tolerant engineered network,” in Proc. 10th USENIX Symp. Networked Syst. Design Implement., 2013, pp. 399–412.
[40]
D. Wu, Y. Xia, X. S. Sun, X. S. Huang, S. Dzinamarira, and T. E. Ng, “Masking failures from application performance in data center networks with shareable backup,” in Proc. Conf. ACM Spec. Interest Group Data Commun., 2018, pp. 176–190.
[41]
R. N. Mysoreet al., “PortLand: A scalable fault-tolerant layer 2 data center network fabric,” in Proc. SIGCOMM, 2009, pp. 39–50.
[42]
Z. Jia, M. Sheng, J. Li, D. Zhou, and Z. Han, “VNF-based service provision in software defined LEO satellite networks,” IEEE Trans. Wireless Commun., vol. 20, no. 9, pp. 6139–6153, Sep. 2021.
[43]
M. Hu, M. Xiao, W. Xu, T. Deng, Y. Dong, and K. Peng, “Traffic engineering for software-defined LEO constellations,” IEEE Trans. Netw. Service Manage., vol. 19, no. 4, pp. 5090–5103, Dec. 2022.
[44]
X. Liet al., “Optimized controller provisioning in software-defined LEO satellite networks,” IEEE Trans. Mobile Comput., vol. 22, no. 8, pp. 4850–4864, Aug. 2023.
[45]
X. Ge, Z. Li, and S. Li, “5G software defined vehicular networks,” IEEE Commun. Mag., vol. 55, no. 7, pp. 87–93, Jul. 2017.
[46]
T. Han and N. Ansari, “A traffic load balancing framework for software-defined radio access networks powered by hybrid energy sources,” IEEE/ACM Trans. Netw., vol. 24, no. 2, pp. 1038–1051, Apr. 2016.
Index Terms
- K-Backup: Load- and TCAM-Aware Multi-Backup Fast Failure Recovery in SDNs
Index terms have been assigned to the content through auto-classification.
Recommendations
Backup Path Classification Based on Failure Risks for Efficient Backup Path Computation
NETWORKING '09: Proceedings of the 8th International IFIP-TC 6 Networking ConferenceWe propose a new approach exploiting the failure risk (node, link or Shared Risk Link Group) structures to enhance the backup path computation. Upon failure, our approach classifies the backup paths into two categories: operative backup paths and ...
Relaxed Failure Recovery Process for Reliable Quality-of-Service using Unreserved Backup Paths
AINA '07: Proceedings of the 21st International Conference on Advanced Networking and ApplicationsGuaranteed, high-quality service in the computer network often requires a single reserved path. However, a single path can easily suffer from single point failures. This paper provides a solution to handle flows when their reserved primary paths fail. ...
Load-Balanced IP Fast Failure Recovery
IPOM '08: Proceedings of the 8th IEEE international workshop on IP Operations and ManagementAs a promising approach to improve network reliability, Proactive Failure Recovery (PFR) re-routes data traffic to backup paths without waiting for the completion of routing convergence after a local link failure. However, the diverted traffic may ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
1063-6692 © 2024 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.
Publisher
IEEE Press
Publication History
Published: 16 April 2024
Published in TON Volume 32, Issue 4
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 10Total Downloads
- Downloads (Last 12 months)10
- Downloads (Last 6 weeks)0
Reflects downloads up to 26 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in