復(fù)雜網(wǎng)絡(luò)生存遍歷算法的研究

張滿宇

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

[關(guān) ? ?鍵 ? 詞] ?復(fù)雜網(wǎng)絡(luò);失效;生存;計算;評估

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

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

一、復(fù)雜網(wǎng)絡(luò)體系下的生存思想

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

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

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

二、復(fù)雜網(wǎng)絡(luò)體系下的生存機制

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

三、生存機制評估

（一）評估模型

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

（二）評估結(jié)果

■

圖1 接入時間成本

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

■

圖2 數(shù)據(jù)流量載荷局向時間代價

■

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

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

四、結(jié)論

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

參考文獻：

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

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

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

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

[5]許訓，李鑒.基于SDN和離線計算的QoS路由方法[J].信息技術(shù)，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