计算机科学 ›› 2022, Vol. 49 ›› Issue (2): 329-335.doi: 10.11896/jsjkx.210100051
耿海军1,2, 王威1, 尹霞3
GENG Hai-jun1,2, WANG Wei1, YIN Xia3
摘要: 软件定义网络(Software Defined Network,SDN)是由美国斯坦福大学Clean Slate课题组提出的一种新型网络体系架构,该架构通过解耦控制平面和转发平面的功能来实现网络流量的灵活转发。但是,由于经济开销和技术条件的限制,互联网服务提供商的骨干网必定长期处于传统设备和SDN设备共存的混合SDN状态。因此,在混合SDN网络中研究应对单节点故障情形的路由保护方法是一个关键的科学问题。文中首先描述了混合SDN网络中应对单节点故障情形时需要解决的问题,然后通过两种启发式方法来解决该问题,最后在真实拓扑结构和模拟拓扑结构中对提出的启发式算法进行测试。实验结果表明,在传统骨干网中,仅需要将一小部分传统设备升级为SDN设备,所提算法就可以应对网络中所有可能的单节点故障情形。
中图分类号:
[1]GENG H J,ZHANG H,SHI X G,et al.Efficient computation of loop-free alternates[J].Journal of Network and Computer Applications,2020,151(5):1-12. [2]KUN Q,JIN Z,XIN W,et al.Efficient Recovery Path Computa-tion for Fast Reroute in Large-scale Software Defined Networks[J].IEEE Journal on Selected Areas in Communications,2019,37(8):1755-1768. [3]GENG H J,SHI X G,WANG Z L.Intra-domain Routing Protection Scheme Based on Minimum Intersection Paths[J].Journal of Software,2020,31(5):1536-1548. [4]DONG S.Survey on Software Defined Networks Security[J].Computer Science,2021,48(3):295-306. [5]ZHANG J,WANG H,LUO S T,et al.Hybrid Software Defined Network Energy Efficient Routing Algorithm Based on Genetic Algorithm[J].Computer Science,2020,47(6):236-241. [6]YANG Y,XU M,LI Q.Fast Rerouting Against Multi-LinkFailures Without Topology Constraint[J].IEEE/ACM Tran-sactions on Networking,2018,26(1):384-397. [7]GENG H,SHI X,WANG Z,et al.A hop-by-hop dynamic distributed multipath routing mechanism for link state network[J].Computer Communications,2018,116:225-239. [8]KWONG K W,GAO L,ZHANG Z L.On the feasibility and efficacy of protection routing in IP networks[J].IEEE/ACM Transactions on Networking,2011,19(5):1543-1556. [9]ATLAS A,ZININ A.RFC 5286,Basic specification for ip fast reroute:Loop-free alternates[S].IETF,2008. [10]ENYEDI G,RÉTVÑRI G,SZILÑGYI P,et al.IP Fast Re-Route:Lightweight Not-Via without Additional Addresses[C]//International Conference on Computer Communications (INFOCOM).IEEE Computer Society,2009:2771-2775. [11]ZHENG J,XU H,ZHU X,et al.We've Got You Covered:Fai-lure Recovery with Backup Tunnels in Traffic Engineering[C]//International Conference on Network Protocols (ICNP).IEEE Computer Society,2016:1-10. [12]RÉTVÑRI G,CSIKOR L,TAPOLCAI J,et al.Optimizing IGP link costs for improving IP-level resilience[C]//International Conference on the Design of Reliable Communication Networks (DRCN).IEEE Computer Society,2011:62-69. [13]RÉTVÑRI G,TAPOLCAI J,ENYEDI G,et al.Ip fast reroute:Loop free alternates revisited[C]//International Conference on Computer Communications (INFOCOM).IEEE Computer So-ciety,2011:2948-2956. [14]BRAUN W,MENTH M.Loop-Free Alternates with Loop Detection for Fast Reroute in Software-Defined Carrier and Data Center Networks[J].Journal of Network and Systems Management,2016,24(3):470-490. [15]HE L,LIN R,YU S,et al.Congestion-Aware Local Reroute for Fast Failure Recovery in Software-Defined Networks[J].IEEE/OSA Journal of Optical Communications & Networking,2017,9(11):934-944. [16]ZHANG X,CHENG Z,LIN R P,et al.Local Fast Reroute With Flow Aggregation in Software Defined Networks[J].IEEE Communications Letters,2017,21(4):785-788. [17]ZHU Z,LI Q,XIA S,et al.CAFFE:Congestion-Aware FastFailure Recovery in Software Defined Networks[C]//International Conference on Computer Communication and Networks (ICCCN).IEEE Computer Society,2018:1-9. [18]ZHENG J,XU H,ZHU X,et al.Sentinel:Failure Recovery in Centralized Traffic Engineering[J].IEEE/ACM Transactions on Networking,2019,27(5):1859-1872. [19]GENG H J,ZHANG W,YIN X.Routing Protection Algorithm Based on Hybrid Software Defined Network[J].Computer Engineering,2020,46(6):209-215. [20]GENG H J,SHI X G,WANG Z L,et al.Intra-domain Routing Protection Scheme Based on Minimum Intersection Paths[J].Journal of Software,2020,31(5):1536-1548. [21]YANG Z,YEUNG K L.SDN Candidate Selection in HybridIP/SDN Networks for Single Link Failure Protection[J].IEEE/ACM Transactions on Networking,2020,28(1):312-321. [22]NETWORK A B.Advanced networking for research and education[OL].http://abilene.internet2.edu,2003. [23]ANTONAKOPOULOS S,BEJERANO Y,KOPPOL P.FullProtection Made Easy:The DisPath IP Fast Reroute Scheme[J].IEEE/ACM Transactions on Networking,2015,23(4):1229-1242. [24]SPRING N,MAHAJAN R,WETHERALL D,et al.Measuring isp topologies with rocketfuel[J].IEEE/ACM Transactions on Networking,2004,12(1):2-16. |
[1] | 刘忠慧, 赵琦, 邹璐, 闵帆. 三元概念的启发式构建及其在社会化推荐中的应用 Heuristic Construction of Triadic Concept and Its Application in Social Recommendation 计算机科学, 2021, 48(6): 234-240. https://doi.org/10.11896/jsjkx.200500136 |
[2] | 郭启程, 杜晓玉, 张延宇, 周毅. 基于改进鲸鱼算法的无人机三维路径规划 Three-dimensional Path Planning of UAV Based on Improved Whale Optimization Algorithm 计算机科学, 2021, 48(12): 304-311. https://doi.org/10.11896/jsjkx.201000021 |
[3] | 郭飞雁, 唐兵. 基于用户延迟感知的移动边缘服务器放置方法 Mobile Edge Server Placement Method Based on User Latency-aware 计算机科学, 2021, 48(1): 103-110. https://doi.org/10.11896/jsjkx.200900146 |
[4] | 张举, 王浩, 罗舒婷, 耿海军, 尹霞. 基于遗传算法的混合软件定义网络路由节能算法 Hybrid Software Defined Network Energy Efficient Routing Algorithm Based on Genetic Algorithm 计算机科学, 2020, 47(6): 236-241. https://doi.org/10.11896/jsjkx.191000139 |
[5] | 张旭, 王莉莉, 杨博韬. 带有一刀切约束的二维非规则装箱算法 Heuristic Algorithms for Two-dimensional Irregular Bin Packing Problem with GuillotineConstraints 计算机科学, 2020, 47(5): 212-216. https://doi.org/10.11896/jsjkx.190400078 |
[6] | 杨婷, 罗飞, 丁炜超, 卢海峰. 一种自适应优化松弛量的装箱算法 Bin Packing Algorithm Based on Adaptive Optimization of Slack 计算机科学, 2020, 47(4): 211-216. https://doi.org/10.11896/jsjkx.190500132 |
[7] | 罗飞, 任强, 丁炜超, 卢海峰. 基于最小松弛量的启发式一维装箱算法 Heuristic One-dimensional Bin Packing Algorithm Based on Minimum Slack 计算机科学, 2019, 46(9): 315-320. https://doi.org/10.11896/j.issn.1002-137X.2019.09.048 |
[8] | 耿海军, 尹霞. 基于增量最短路径优先的域内高效路由保护算法 Efficient Intra-domain Routing Protection Algorithm Based on i-SPF 计算机科学, 2019, 46(8): 116-120. https://doi.org/10.11896/j.issn.1002-137X.2019.08.019 |
[9] | 张澍裕, 宫达, 谢兵, 刘开贵. 基于实时GPS的公交短时动态调度算法 Bus Short-term Dynamic Dispatch Algorithm Based on Real-time GPS 计算机科学, 2019, 46(6A): 497-501. |
[10] | 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法 Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading 计算机科学, 2018, 45(4): 94-99. https://doi.org/10.11896/j.issn.1002-137X.2018.04.014 |
[11] | 单天羽, 管煜旸. 基于种群多样性的可变种群缩减差分进化算法 Differential Evolution Algorithm with Adaptive Population Size Reduction Based on Population Diversity 计算机科学, 2018, 45(11A): 160-166. |
[12] | 李美争,李磊军,米据生,解滨. 概念格中基于粗糙熵的属性约简方法 Rough Entropy Based Algorithm for Attribute Reduction in Concept Lattice 计算机科学, 2018, 45(1): 84-89. https://doi.org/10.11896/j.issn.1002-137X.2018.01.013 |
[13] | 殷晓波,罗恩. 一种松弛的优化均衡流式图划分算法研究 Relaxed Optimal Balanced Streaming Graph Partitioning Algorithm 计算机科学, 2016, 43(4): 231-234. https://doi.org/10.11896/j.issn.1002-137X.2016.04.047 |
[14] | 陈小潘,孔云峰,郑泰皓,郑珊珊. 需求可拆分校车路径问题的元启发式算法 Metaheuristic Algorithm for Split Demand School Bus Routing Problem 计算机科学, 2016, 43(10): 234-241. https://doi.org/10.11896/j.issn.1002-137X.2016.10.045 |
[15] | 杨光,曾斌. 一种面向可靠传输的数据链中继策略研究 Research on Reliability-aware Relay Strategy in Data Link 计算机科学, 2015, 42(Z11): 253-257. |
|