復雜網絡生存遍歷算法的研究

張滿宇

[摘 ? ? ? ? ? 要] ?為應對大數據對網絡服務質量（QoS）的要求，復雜的軟件定義網絡得以部署。然而該網絡卻因缺乏高效的風險評估頻現安全問題。為此，構思一種生存遍歷算法，旨在提高復雜網絡體系風險的規避能力。算法通過為子網體系構建數學模型，并從全局角度建立目標遍歷策略來實施風險規避，同時對風險規避后的潛在風險再次建模開展評估以確保全網生存性。測試表明，生存遍歷算法各項指標表現較為顯著，具有良好的全局性。

[關 ? ?鍵 ? 詞] ?復雜網絡;失效;生存;計算;評估

[中圖分類號] ?TN915.07 ? ? ? ? [文獻標志碼] ?A ? ? ? ? ? ?[文章編號] ?2096-0603（2019）32-0001-03

目前關于軟件定義網絡體系穩健性的評估主要圍繞轉發層面的交換單元內部的流表項來開展。雖有部分研究也針對控制層面的穩健性來開展，但因缺乏全局性而收效甚微。以復雜網絡優化算法為例，該算法首先為每個子網體系內定義一個主用控制單元同時定義一個保護控制單元。當某一個子網體系內的主用控制單元失效，則該子網體系內的所有交換單元接入本子網體系內保護控制單元。如果某一個子網體系內的兩個控制單元均失效，則遍歷其他子網體系并將本子網體系內失效控制單元管轄下的交換單元接入該正常的子網體系。要是子網體系中的主用控制單元均失效，則遍歷出最輕載的那個備用控制單元實現交換單元接入。從應用角度分析，傳統的優化思想的確改善了應用層業務QoS，但這需以網絡開銷為代價。故本文從全局優化角度提出一種有效降低網絡開銷和資源消耗的生存策略。

一、復雜網絡體系下的生存思想

為避免傳統復雜網絡優化算法定義的冗余備用控制單元對全網開銷資源造成的浪費，本文提出的復雜網絡體系生存算法不再為每一個子網體系提供主備控制單元切換方案，改由將相鄰子網體系內的控制單元定義為異常子網體系失效控制單元的備用接入方案。在實施接入之前生存算法遍歷全局子網體系內的控制單元計算出待接入控制單元組的權值大小并排序。然后根據權值從大到小對異常子網體系內失效控制單元管轄下的交換單元組實施新的接入，并分析接入新控制單元后該新控制單元的數據流量載荷程度。若重載則遍歷權值低一級的子網體系內的新控制單元實施接入并再次分析新控制單元的數據流量載荷程度，以此類推直至接入到合適載荷程度的新控制單元。當失效控制單元管轄下的交換單元所接入的新控制單元并未出現超載，則將當前新控制單元視為本輪生存遍歷算法的解決方案。

根據生存算法的思路[1]，假設為一個復雜的軟件定義網絡定義1個異常子網體系和n個正常子網體系，其中將正常子網體系記作：SN={SN1，SN2，…，SNn}。整個復雜網絡體系下的每個SN內均存在一個唯一的控制單元記作C={C1，C2，…CL…Cn，Cn+1}。失效控制單元管轄下的交換單元組記作LE={LE1，LE2，…，LEF}。當復雜網絡體系在承載全業務時遭遇到數據流量載荷失效情形，此時交換單元將向其所屬控制單元提交規模為Nq的策略請求，控制單元須對此次提交的請求做出計算響應，并將策略計算結果通過南向接口下發給交換單元以便其內存流表及時執行更新操作。將第L個控制單元CL受理第F個交換單元LEF的計算請求所需的處理能力定義為Nq·■。其中■為LEF向CL提交請求的路由代價。同時定義除失效控制單元之外的所有正常控制單元受理全業務的平均載荷程度為（1/F）·■CL■，CL■為CL當前載荷程度。可求得控制單元未失效時的流量載荷承載因子：θB=（1/F）·■[CL■-（1/F）·■CL■，CL■]。進而求出控制單元失效后LEF接入CL之后，該CL的流量載荷承載因子：θA=（1/F）·■[Nq·■+CL■-（1/F）■CL■]。最后得到待選控制單元組中新控制單元被接入的權重：W=（Nq·■）-1·（θA-θB）。當待選控制單元組中某一個控制單元權值最大，則該控制單元首先作為接入的首選對象。

良好的生存機制除了考慮為失效控制單元管轄下的交換機計算出權值最大的新控制單元接入方案之外，還需對被接入的新控制單元展開數據流量處理能力展開分析，避免其重載。令CL數據流量載荷的峰值能力為HL■，則在實施[2]新控制單元接入前應先確保失效控制單元管轄下的交換單元，對被接入的新控制單元的載荷程度要求Nq·■等同或者低于該被接入的新控制單元的載荷余量HL■-CL■，方可執行接入方案。

二、復雜網絡體系下的生存機制

本文構思的生存思想旨在為復雜網絡體系內部的控制接入過程提供策略穩健性的優化評估。評估的過程從兩個方面來分布式實施。首先打破傳統優化算法在全網中的冗余定義，充分利用全局有限的控制資源為失效控制單元管轄下的交換單元提供快速修復策略，以降低數據流量載荷在局向時間成本上的代價。其次通過對被接入的新控制單元展開計算，分析其作為宿主節點在應對全業務數據流量載荷時的可用資源負載飽和度，以優化全局控制資源。基于生存思想所述，形成如下生存遍歷機制：將復雜網絡體系初始化為SN={SN1，SN2，…，SNn}、C={C1，C2，…CL…Cn，Cn+1}、LE={LE1，LE2，…，LEF}，并將失效控制單元相鄰子網體系和自身子網體系中的控制單元寫入，將失效控制單元管轄下的交換單元寫入LE。其次，遍歷SN={SN1，SN2，…，SNn}將控制單元寫入C={C1，C2，…CL…Cn，Cn+1}。然后讀出LEF并逐個求解出LEF到C={C1，C2，…CL…Cn，Cn+1}中的每一個權值W=（Nq·■）-1·（θA-θB）并按照大小排序。重新排序后再展開分析，確定其Nq·■值與HL■-CL■值之間的關系。如果前者等于或者小于后者，則說明LEF順利通過生存性評估可實施CL的接入。反之，則對重新排序后的C展開下一個待接入控制單元的生存性評估，直至實施接入。

三、生存機制評估

（一）評估模型

整個評估過程在Mininet環境中開展。將全局網絡分設為三個子網體系SN1、SN2、SN3。每個子網體系內均使用Floodlight[3]作為控制單元，記為C1、C2、C3。將OpenSwitch作為本次評估的交換單元，三個SN中的數據流量由Iperf隨機生成，規模分別為0.45、0.3、0.25。位于控制單元管轄下的交換單元規模分別為3個、6個、9個。節點網元間的路由局向速度設定為15Mb/s。結合生存思想所述原理，生存機制不僅為失效控制單元管轄下的交換單元提供快速接入方案，同時也包括對接入后的數據流量載荷開展時間代價評估以及接入后的新控制單元載荷處理能力展開測評，旨在優化整個復雜網絡的全業務處理能力。因此本次生存機制的效能評估應包含上述三項指標。

（二）評估結果

■

圖1 接入時間成本

根據前文所述，傳統的優化算法在開展復雜網絡穩健性評估時因失效子網體系的不同在策略上有所調整：（1）當在某個特定的子網體系中存在一個失效的控制單元，那么該子網體系中的交換單元便轉而接入該子網體系內唯一的備用控制單元;（2）當某個特定子網體系中的兩個主備控制單元均失效，則遍歷出一個正常的子網體系為異常子網體系中的交換單元實施接入;（3）若全局主用控制單元均失效，則鎖定路由代價最小的目標控制單元。相對于后面兩種情況，傳統優化算法在方案（1）中的實施效率最高。由于待選接入目標位于自身子網體系內，基本不消耗太多控制單元的計算資源也省去了比較分析的算法開銷，因此可在較短時間內直接實施目標接入。從接入目標所消耗的時間成本[4]上看，該方案占據絕對優勢，甚至優于本文構思的生存遍歷機制。這一現象在圖1所示的接入時間成本曲線圖中也得到了體現。由于整個接入過程位于本子網體系內部，因此實現備用目標接入后，全業務數據流量在交換單元和備用目標控制單元之間路由局向的時間代價也最小，優于本文討論的生存遍歷算法。這在圖2所示的數據流量載荷局向時間代價曲線中得到說明。但是傳統優化算法在實施后兩者方案需遍歷多個子網體系中的目標控制單元，這不僅增加篩選目標的時間成本，同時由于路由距離代價[5]的增加而直接導致接入目標與失效控制單元所在子網體系中的大量交換單元在實施全業務路由局向的時延變大。由于在方案（3）的情形下，這種遍歷操作貫穿了全局所有子網體系，相應的開銷代價最大。而本文所述生存算法旨在相鄰子網體系內開展目標控制單元的篩選。在順利實施目標接入后全業務的承載也局限在相鄰子網體系的目標控制單元和異常子網體系中的交換單元之間。故而路由局向的時間相對方案（2）和（3）較短。算法的這些特征在圖2和圖3所示的曲線中也同樣得到了驗證。

■

圖2 數據流量載荷局向時間代價

■

圖3 被接入目標載荷承重度

有別于傳統優化算法，本文描述的生存機制不僅考慮了目標的優化選擇，也兼顧了實施接入以后目標的載荷承重度。此舉主要從全網優化角度來考慮，進一步加強了復雜網絡的生存性。而傳統優化算法目標僅僅只是為失效子網體系實施風險轉移，并未長遠地考慮到風險轉移之后目標承載度是否處于重載狀態。本質上看，該行為實際上是將潛在的風險嫁接到了目標控制單元，這勢必降低整個復雜網絡的QoS，也不利于軟件定義網絡架構優勢的發揮。算法的這些性能通過圖3所示的接入目標承重度來接受測評。圖3示可見，當SN1中的C1出現失效后其承載能力急劇下降至零，SN2和SN3中的C2、C3作為目標接受接入。由于目標控制單元需要對新增的交換單元做出載荷響應，因此無論傳統算法還是本文闡述的生存機制，其載荷程度均有所增加。圖中曲線的遞增走勢說明了此問題。從圖中曲線不難觀測到，在實施接入之前C2的承載度輕于C3的承載度，本著全局均衡優化原則，實施目標接入后C2的承載度保持增重趨勢的前提下應該保持相對重載。C3的承載度在保持增重趨勢的前提下應該保持相對輕載。從圖中可見，這樣的均衡優化特征在本文的生存算法得到了發揮。相比之下傳統優化算法因缺乏全局性使接入在實施之后出現潛在的重載風險。

四、結論

本文圍繞軟件定義網絡架構的優勢展開討論了復雜網絡在應用中存在的風險，并提出相應的解決方案。方案的實施有效地突破了傳統優化算法在穩健性評估方面存在的局限性。評估結果表明，該方案不僅有效地提高了復雜網絡風險轉移的效能性，同時也有效地避免了二次風險潛伏的可能性，具有良好的全局性。

參考文獻：

[1]王帥，金華敏.基于SDN的安全分析及關鍵技術研究[J].電信科學，2018，34（2）：45-49.

[2]楊耀通.基于蝙蝠算法的SDN多控制器部署[J].重慶大學學報，2018，41（9）：57-65.

[3]周環，劉慧.基于Floodlight的SDN控制器研究[J].計算機工程與應用，2016，52（24）：137-146.

[4]陳鳴，代飛，許博，等.主動測量SDN性能的機制[J].通信學報，2018，38（6）：35-44.

[5]許訓，李鑒.基于SDN和離線計算的QoS路由方法[J].信息技術，2018，41（11）：91-96.

◎編輯 趙瑞峰

Research on Survival Traversal Algorithm of Complex Networks

ZHANG Man-yu

Abstract：Although in response to big dataundefineds（QoS） requirements for network quality of service，complex software-defined networks can be deployed. However，security problems frequently arise because of the lack of efficient risk assessment.In this paper，a survival ergodic algorithm is proposed to improve the risk aversion ability of complex network systems.The algorithm builds a mathematical model for the subnet system and sets up a target traversal strategy from the global point of view to implement risk avoidance.At the same time，it evaluates the potential risk modeling after risk avoidance to ensure the survivability of the whole network. The test results show that the survival ergodic algorithm performs significantly and has a good global performance.

Key words：complex network;failure;survival;computation;evaluation