SDN Reliability Evaluation Algorithm Based on Improved BDD

doi:10.3969/j.issn.1006-2475.2023.09.010

Abstract

Abstract: Aiming at the problem of insufficient reliability analysis of SDN data forwarding layer， this paper proposes an SDN reliability evaluation algorithm based on BDD， which can complete fast and accurate reliability analysis of SDN data forwarding layer. In view of the shortcomings of traditional BDD ranking methods that lead to large scale and long construction time for network reliability evaluation models， this paper proposes a new heuristic edge ranking algorithm， MP-BFS， to rank the variables of BDD. The experimental results show that compared with the traditional sorting algorithm， the proposed MP-BFS algorithm can significantly reduce the construction scale of BDD and complete the construction of BDD faster. The BDD-SDN algorithm can be used for rapid and accurate reliability analysis on the forwarding layer of SDN data.

Key words: SDN, reliability evaluation, binary decision diagram, breadth-first search

CLC Number:

TP393.2

JIANG Hou-hai, ZHUANG Yi, CAO Zi-ning. SDN Reliability Evaluation Algorithm Based on Improved BDD[J]. Computer and Modernization, 2023, 0(09): 64-69.

References

［1］ CASADO M， FREEDMAN M J， PETTIT J， et al. Ethane： Taking control of the enterprise［J］. ACM SIGCOMM Computer Communication Review， 2007，37（4）：1-12.
［2］ AL MTAWA Y， HAQUE A， LUTFIYYA H. Migrating from legacy to software defined networks： A network reliability perspective［J］. IEEE Transactions on Reliability， 2021，70（4）：1525-1541.
［3］ GERTSBAKH I， SHPUNGIN Y. Lomonosov’s turnip［M］// Network Reliability. 2020：71-80.
［4］ KARAKUS M， DURRESI A. Quality of service （QoS） in software defined networking （SDN）： A survey［J］. Journal of Network and Computer Applications， 2017， 80：200-218.
［5］ MOORE E F， SHANNON C E. Reliable circuits using less reliable relays［J］. Journal of the Franklin Institute， 1956，262（3）：191-208.
［6］ LIN P M， LEON B J， HUANG T C. A new algorithm for symbolic system reliability analysis［J］. IEEE Transactions on Reliability， 1976，25（1）：2-15.
［7］ FRATTA L， MONTANARI U. A boolean algebra method for computing the terminal reliability in a communication network［J］. IEEE Transactions on Circuit Theory， 1973，20（3）：203-211.
［8］ BALL M O. Complexity of network reliability computations［J］. Networks， 1980，10（2）：153-165.
［9］ SATITSATIAN S， KAPUR K C. An algorithm for lower
reliability bounds of multistate two-terminal networks［J］.
IEEE Transactions on Reliability， 2006，55（2）：199-206.
［10］冯海林. 网络系统中可靠性问题的研究［D］. 西安：西安电子科技大学， 2004.
［11］ MOSHNIKOV A S， KOLOMOITCEV V S. Reliability assessment of distributed control systems with network structure［C］// 2020 Wave Electronics and its Application in Information and Telecommunication Systems （WECONF）. 2020：1-4.
［12］陈永，陈耀. 基于随机Petri网的车车通信可靠性建模与分析［J］. 安全与环境学报， 2021，21（3）：984-989.
［13］高尚，杨静宇，吴小俊，等. 基于模拟退火算法思想的粒子群优化算法［J］. 计算机应用与软件， 2005（1）：103-104.
［14］ AKERS S B. Binary decision diagrams［J］. IEEE Transactions on Computers， 1978，27（6）：509-516.
［15］ COUDERT O， MADRE J C. A new method to compute prime and essential prime implicants of boolean functions［C］// Advanced Research in VLSI and Parallel systems. 1992：113-128.
［16］ ZANG X Y， SUN N R， TRIVEDI K S. A BDD-based algorithm for reliability analysis of phased-mission systems［J］. IEEE Transactions on Reliability， 1999，48（1）：50-60.
［17］ HARDY G， LUCET C， LIMNIOS N. K-terminal network reliability measures with binary decision diagrams［J］. IEEE Transactions on Reliability， 2007，56（3）：506-515.
［18］ YEH F M， LU S K， KUO S Y. OBDD-based evaluation of k-terminal network reliability［J］. IEEE Transactions on Reliability， 2002，51（4）：443-451.
［19］ FRIEDMAN S J， SUPOWIT K J. Finding the optimal variable ordering for binary decision diagrams［C］// The 24th ACM/IEEE Design Automation Conference. 1987：348-356.
［20］ LI J T， YANG Y， HUO G T， et al. New bidirectional fast BDD dynamic reordering algorithm［C］// 2020 IEEE 15th International Conference on Solid-state & Integrated Circuit Technology （ICSICT）. 2020：1-3.
［21］ KUMAR A， KUMAR A， CHOUDHARY S， et al. Optimization of binary decision diagram using genetic algorithm［C］// 2010 2nd International Conference on Reliability， Safety and Hazard-risk-based Technologies and Physics-of-failure Methods （ICRESH）. 2010：168-175.
［22］ AWAD A， HAWASH A， ABDALHAQ B. A genetic algorithm （GA） and swarm based binary decision diagram （BDD） reordering optimizer reinforced with recent operators［J］. IEEE Transactions on Evolutionary Computation， 2022.
［23］李闻白，潘竹生，林飞龙. BDD网络可靠性分析中启发式排序策略研究［J］. 计算机仿真， 2020，37（5）：165-172.
［24］ DU S G， SUN Y. A novel ordering method of binary decision diagram［C］// 2007 International Conference on Management Science and Engineering. 2007：299-304.
［25］潘竹生，莫毓昌. 边排序质量影响因素研究［J］. 计算机工程与科学， 2015，37（11）：2091-2098.
［26］ LÊ M， WEIDENDORFER J， WALTER M. A novel variable ordering heuristic for BDD-based K-terminal reliability［C］// 2014 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks. 2014：527-537.
［27］ SOMENZI F. CUDD： CU decision diagram package release 3.0. 0 （2015）［EB/OL］. ［2022-11-02］. http：//vlsi.colorado. edu/fabio/CUDD.
［28］ XING L. An efficient binary-decision-diagram-based approach for network reliability and sensitivity analysis［J］. IEEE Transactions on Systems， Man， and Cybernetics-Part A： Systems and Humans， 2007，38（1）：105-115.
［29］熊飞，乔迪，王宏祥，等. 一种基于有序二元决策图和布尔函数性质计算网络可靠性的算法［J］. 电子与信息学报， 2014，36（11）：2786-279.

[1]	XIAO Junbi, QIU Yi. SDN Failure Detection and Recovery Scheme Based on State-aware Data Plane [J]. Computer and Modernization, 2024, 0(12): 116-123.
[2]	JIANG Hou-hai, ZHUANG Yi, CAO Zi-ning. A Fast Failure Recovery Scheme for SDN Based on Flow Aggregation and Congestion Avoidance [J]. Computer and Modernization, 2023, 0(10): 77-83.
[3]	LEI Yi-han, CAO Li-feng, HAN Meng-da, HAN Xue. Security Handover Architecture and Method for Software Defined Space-ground#br# Integration Network [J]. Computer and Modernization, 2023, 0(08): 119-126.
[4]	WANG Ying-ying, ZHUANG Yi, SUN Yi-fan. Reliability Evaluation Model of BP Neural Network Based on Particle Swarm Optimization [J]. Computer and Modernization, 2022, 0(12): 42-49.
[5]	BAO Chun-hui, ZHUANG Yi, GUO Li-ye. Vulnerability Assessment Model of SDN Mobile Network for Service Transmission [J]. Computer and Modernization, 2022, 0(11): 43-51.
[6]	CHU Su-hong, LIU Lei, . POF Protocol Parser [J]. Computer and Modernization, 2022, 0(09): 93-98.
[7]	LING Zhi-yuan, CHEN Xiao, SONG Lei, . Flow Table Merging on Programmable Data Planes Based on MAT Model [J]. Computer and Modernization, 2022, 0(07): 74-78.
[8]	WANG Wen-wei, XIAO Jun-bi, CHENG Peng, ZHANG Yue. SDN-based DDoS Attack Defense System [J]. Computer and Modernization, 2021, 0(02): 117-121.
[9]	DAI Song, SUN Yan-tao, LIU Qiang, JIA Ze-qun, . Networking Method for SDMANET Based on Multi-mode Radio [J]. Computer and Modernization, 2020, 0(08): 82-88.
[10]	YUAN Jie， ZHANG Min-lei. Research on Fault Recovery Mechanism of Power Information System Based on SDN [J]. Computer and Modernization, 2018, 0(11): 7-.
[11]	TIAN Ye1， SUN Yan-tao1,2， XIONG Ke1,2. A Semi-centralized SDN Routing Strategy in Data Center Network [J]. Computer and Modernization, 2018, 0(01): 95-101.
[12]	ZHAN Han. Research on Distributed SDN Controller Dragonflow Based on OpenStack [J]. Computer and Modernization, 2017, 0(7): 91-94.
[13]	ZHUANG Huai-dong, DU Qing-wei. A Method of Data Center Network Dynamic Traffic Scheduling Based on SDN [J]. Computer and Modernization, 2016, 251(07): 80-86.
[14]	MA Chao1,2, CHENG Li1, KONG Ling-ling3. Performance Analysis of Traffic Anomaly Detection in Cloud-based Software-defined Network [J]. Computer and Modernization, 2015, 0(10): 92-97+102.
[15]	SHEN Qingguo， HUANG Liaoruo， LUO Jian. Analyses of Softwaredefined Network and Its Application [J]. Computer and Modernization, 2014, 0(4): 133-137.