一种基于改进BDD的SDN可靠性评估算法

doi:10.3969/j.issn.1006-2475.2023.09.010

摘要/Abstract

摘要： 针对SDN数据转发层面可靠性分析不足的问题，本文提出一种基于BDD的SDN可靠性评估算法BDD-SDN，可以完成快速、精确的SDN数据转发层可靠性分析。针对传统BDD排序方法会导致网络可靠性评估模型构建规模大和构建时间长的缺点，本文提出一种新的启发式边排序算法MP-BFS，对BDD的变量进行排序。实验结果表明，与传统的排序算法相比，本文提出的MP-BFS算法可以明显缩小BDD的构建规模，更快地完成BDD的构建，使用BDD-SDN算法可对SDN数据转发层进行快速、精确的可靠性分析。

关键词: 软件定义网络, 可靠性评估, 二元决策图, 广度优先搜索

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

中图分类号:

TP393.2

姜厚海, 庄毅, 曹子宁. 一种基于改进BDD的SDN可靠性评估算法[J]. 计算机与现代化, 2023, 0(09): 64-69.

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.

参考文献

［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]	肖军弼, 邱艺. 基于状态感知数据平面的SDN故障检测与恢复方案[J]. 计算机与现代化, 2024, 0(12): 116-123.
[2]	王重阳, 庄毅. 基于SDN和改进CSA算法的多作业集群的负载均衡算法[J]. 计算机与现代化, 2023, 0(11): 28-35.
[3]	陈晨, 庄毅, 高增. QoE驱动的SDN网络高可用传输框架[J]. 计算机与现代化, 2023, 0(11): 62-68.
[4]	姜厚海, 庄毅, 曹子宁. 一种基于流聚合与拥塞避免的SDN快速故障恢复方案[J]. 计算机与现代化, 2023, 0(10): 77-83.
[5]	雷依翰, 曹利峰, 韩孟达, 韩雪. 软件定义天地一体化网络安全切换架构与方法[J]. 计算机与现代化, 2023, 0(08): 119-126.
[6]	高枫, 庄毅, 刘骁. 一种基于路径跟踪反馈的SDN网络可信传输方案[J]. 计算机与现代化, 2022, 0(12): 102-110.
[7]	王颖颖, 庄毅, 孙逸帆. 基于粒子群优化BP神经网络的可靠性评估模型[J]. 计算机与现代化, 2022, 0(12): 42-49.
[8]	包春晖, 庄毅, 郭黎烨. 面向服务传输的SDN移动网络脆弱性评估模型[J]. 计算机与现代化, 2022, 0(11): 43-51.
[9]	凌致远, 陈晓, 宋磊, . 基于匹配动作表模型的可编程数据平面流表归并[J]. 计算机与现代化, 2022, 0(07): 74-78.
[10]	王文蔚, 肖军弼, 程鹏, 张悦. 基于SDN的DDoS攻击防御系统[J]. 计算机与现代化, 2021, 0(02): 117-121.
[11]	戴松, 孙延涛, 刘强, 贾泽群, . 基于多模电台的SDMANET网络组网方法[J]. 计算机与现代化, 2020, 0(08): 82-88.
[12]	肖军弼, 程鹏, 谭立状, 孟祥泽. 基于SDN的数据中心动态优先级多路径调度算法[J]. 计算机与现代化, 2020, 0(07): 21-26.
[13]	耿岚岚1，孙延涛2，戴松1. 一种面向软件定义移动自组网的拓扑发现方法[J]. 计算机与现代化, 2019, 0(09): 53-.
[14]	詹晗. 基于OpenStack的分布式SDN控制器Dragonflow研究[J]. 计算机与现代化, 2017, 0(7): 91-94.
[15]	印苏凯1,刘光杰1,刘伟伟1,翟江涛2,戴跃伟1,2. 软件定义网络中的多流时间式隐信道设计[J]. 计算机与现代化, 2017, 0(4): 94-98,104.