基于模糊滿意度的軟件定義網(wǎng)絡(luò)交換機(jī)遷移策略

摘 要：針對(duì)軟件定義網(wǎng)絡(luò)中多控制器間負(fù)載均衡的遷移代價(jià)和遷移效率問題，提出一種基于模糊滿意度的交換機(jī)遷移策略。首先，構(gòu)建均衡判斷矩陣，監(jiān)測控制器負(fù)載狀態(tài)，且提出交換機(jī)組選擇度，劃分交換機(jī)組以選取遷移交換機(jī)；其次，考慮遷移代價(jià)和負(fù)載均衡率，構(gòu)建模糊滿意度遷移競爭模型，且提出改進(jìn)蟻群算法優(yōu)化求解，選擇最佳遷入控制器；最后，將遷移交換機(jī)遷往遷入控制器，實(shí)現(xiàn)交換機(jī)的快速遷移。實(shí)驗(yàn)結(jié)果表明，與現(xiàn)有交換機(jī)遷移策略相比，所提方法在保證較高負(fù)載均衡率的同時(shí)，進(jìn)一步優(yōu)化了網(wǎng)絡(luò)性能，遷移代價(jià)平均減少約26.8%，控制器平均響應(yīng)時(shí)間縮短約0.41 s，改善了交換機(jī)遷移過程。

關(guān)鍵詞：軟件定義網(wǎng)絡(luò)； 負(fù)載均衡； 交換機(jī)遷移； 遷移代價(jià)； 遷移效率

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2022）03-037-0857-06

doi：10.19734/j.issn.1001-3695.2021.07.0346

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目（61876131）；天津市科技計(jì)劃資助項(xiàng)目（19YFZCGX00130）；天津市科技特派員項(xiàng)目（20YDTPJC00460）

作者簡介：劉樹東（1965-），男，黑龍江哈爾濱人，教授，碩導(dǎo)，博士，主要研究方向?yàn)榫W(wǎng)絡(luò)通信與物聯(lián)網(wǎng)技術(shù)、嵌入式技術(shù)及應(yīng)用；崔文濤（1997-），男，河北邢臺(tái)人，碩士研究生，主要研究方向?yàn)檐浖x網(wǎng)絡(luò)；李國燕（1984-），女（通信作者），河北石家莊人，副教授，博士，主要研究方向?yàn)橄乱淮W(wǎng)絡(luò)技術(shù)（ligy@tcu.edu.cn）；趙偉豐（1978-），男，山東萊陽人，講師，博士，主要研究方向?yàn)榫W(wǎng)絡(luò)性能評(píng)價(jià)、無線網(wǎng)絡(luò).

Switch migration strategy based on fuzzy satisfaction in software defined network

Liu Shudong， Cui Wentao， Li Guoyan?， Zhao Weifeng

（College of Computer amp; Information Engineering， Tianjin Chengjian University， Tianjin 300384， China）

Abstract：To solve the problem of migration cost and efficiency of load balancing among multiple controllers in software defined networking， this paper proposed a switch migration strategy based on fuzzy satisfaction. Firstly， it constructed the balanced judgment matrix to monitor the load state of controllers， and divided switch groups by the proposed switch unit selection degree to select migration switches. Then， it constructed the migration competition model based on fuzzy satisfaction by considering the migration cost and load balance rate， and proposed an improved ant colony algorithm to select the best migration controller. Finally， it migrated migration switches to the migration controller to realize the rapid migration of switches. Experimental results show that compared with the existing switch migration strategies， this strategy not only ensures the high load balancing rate， but also further optimizes the network performance. In this strategy， the average migration cost decreases by about 26.8% and the average response time reduces by about 0.41 s， which improves the switch migration process.

Key words：software defined networking （SDN）; load balancing; switch migration; migration cost; migration efficiency

0 引言

隨著數(shù)據(jù)流量的與日俱增，傳統(tǒng)網(wǎng)絡(luò)架構(gòu)的網(wǎng)絡(luò)規(guī)模增大、更新維護(hù)業(yè)務(wù)困難，這使得時(shí)間成本和管理成本都急劇增長。軟件定義網(wǎng)絡(luò)（software defined networking，SDN）作為一種新型網(wǎng)絡(luò)架構(gòu)，最初應(yīng)用于校園網(wǎng)部署，將數(shù)據(jù)平面與控制平面分離，實(shí)現(xiàn)控制平面對(duì)全局網(wǎng)絡(luò)的集中管控，提高了網(wǎng)絡(luò)管理的可靠性和靈活性^[1]。SDN便于管理網(wǎng)絡(luò)的同時(shí)，控制平面的負(fù)載失衡風(fēng)險(xiǎn)也需要關(guān)注。控制器間負(fù)載失衡，會(huì)降低SDN網(wǎng)絡(luò)的穩(wěn)定性，并且會(huì)導(dǎo)致網(wǎng)絡(luò)無法正常運(yùn)行^[2]，因此研究交換機(jī)遷移實(shí)現(xiàn)控制器間負(fù)載均衡具有重要意義。

靜態(tài)部署方案^[3，4]無法隨網(wǎng)絡(luò)流量的動(dòng)態(tài)變化對(duì)控制器進(jìn)行相關(guān)調(diào)整，因此選用能夠改變控制器—交換機(jī)映射關(guān)系的動(dòng)態(tài)部署方案。Heller等人^[5]首次對(duì)控制器動(dòng)態(tài)部署進(jìn)行理論分析，為后續(xù)學(xué)者研究拓寬思路。Zhou等人^[6]提出一種動(dòng)態(tài)自適應(yīng)負(fù)載均衡框架，從一組欠載控制器中選擇最近的控制器接受負(fù)載轉(zhuǎn)移，減少了執(zhí)行時(shí)間和遷移成本。通過進(jìn)一步研究，Dixit等人^[7]在該框架的基礎(chǔ)上，提出一種包含負(fù)載調(diào)節(jié)模塊的ElastiCon架構(gòu)，根據(jù)就近遷移原則，設(shè)置雙閾值將交換機(jī)遷移至鄰居控制器。此外，Li等人^[8]為了對(duì)控制器負(fù)載狀態(tài)進(jìn)行更精確的判斷，擯棄傳統(tǒng)方案中使用交換機(jī)輸入指標(biāo)作為控制器的負(fù)載描述，而選用交換機(jī)帶給控制器的負(fù)載率性能指標(biāo)作為負(fù)載描述。

對(duì)控制器動(dòng)態(tài)部署深入討論后發(fā)現(xiàn)由遷移產(chǎn)生的高通信開銷以及控制器決策時(shí)延問題，相關(guān)文獻(xiàn)[9～12]對(duì)此問題進(jìn)行了研究。史久根等人^[9]提出一種平衡負(fù)載的方案，主要用于降低數(shù)據(jù)傳輸時(shí)延。與之不同，在Li等人^[10]的進(jìn)一步研究中，用控制器靜態(tài)部署與動(dòng)態(tài)部署相結(jié)合的方式優(yōu)化控制器通信開銷，并利用寬度優(yōu)先搜索算法，實(shí)現(xiàn)對(duì)域內(nèi)交換機(jī)重新分配。Hu等人^[11]提出效率感知交換機(jī)遷移策略，引入負(fù)載差值矩陣和觸發(fā)因子來度量控制器上的負(fù)載均衡。Adekoya等人^[12]提出一種改進(jìn)交換機(jī)遷移決策算法，化解了輸入負(fù)載為大象流時(shí)的網(wǎng)絡(luò)危機(jī)。

雖然目前針對(duì)控制器動(dòng)態(tài)部署方案的研究已基本實(shí)現(xiàn)控制器間負(fù)載均衡，然而仍需要考慮并處理以下問題：a）選取遷出控制器的考慮因素單一，且遷移交換機(jī)與遷入控制器的選取僵化，易造成交換機(jī)頻繁遷移;b）交換機(jī)遷移的過程中，存在低遷移效率或控制器決策時(shí)延的降低經(jīng)常伴隨著高通信開銷的情況。

本文提出一種基于模糊滿意度的交換機(jī)遷移（fuzzy satisfaction-based switch migration，F(xiàn)SSM）策略，主要貢獻(xiàn)和創(chuàng)新工作總結(jié)如下：

a）遷出域的選取?；诳刂破髫?fù)載構(gòu)建了均衡判斷矩陣和均衡判斷閾值，以確定交換機(jī)遷移的觸發(fā)條件和遷出控制器。為了選取需要遷移的交換機(jī)，交換機(jī)選擇度被提出，它能夠減少控制器的決策時(shí)延，進(jìn)而縮短了交換機(jī)遷移的過程。

b）遷入域的選取。基于模糊滿意度的理論提出了遷移競爭模型。該模型通過設(shè)定負(fù)載均衡率閾值，劃分三種競爭狀況。依據(jù)此狀況動(dòng)態(tài)平衡了負(fù)載均衡率與遷移代價(jià)兩個(gè)指標(biāo)的優(yōu)化優(yōu)先權(quán)，保證了高負(fù)載均衡率與低遷移代價(jià)，這為靈活選取遷入域進(jìn)行交換機(jī)遷移提供了保障。

c）蟻群算法的改進(jìn)。一方面，對(duì)時(shí)延因子啟發(fā)函數(shù)進(jìn)行優(yōu)化，主要包括在迭代初期的搜索范圍進(jìn)行合理放大以及衰退系數(shù)的設(shè)定，從而降低在迭代后期時(shí)延因子的影響，以避免算法陷入局部最優(yōu)。另一方面，信息素更新方式被改變。首先為揮發(fā)系數(shù)增加調(diào)節(jié)系數(shù)參數(shù)，利用它增加各條路徑間的信息素濃度差異;然后，依據(jù)三種競爭狀況按比例調(diào)整每次更新信息素時(shí)的信息素增量，加快了算法收斂速度。

d）為FSSM策略設(shè)計(jì)了相應(yīng)的交換機(jī)遷移算法。在仿真實(shí)驗(yàn)中，綜合了多種性能評(píng)價(jià)指標(biāo)，將FSSM策略與現(xiàn)有的代表性遷移策略進(jìn)行比較，基于真實(shí)網(wǎng)絡(luò)拓?fù)潋?yàn)證FSSM策略性能。

1 分析與建模

本章描述交換機(jī)遷移實(shí)現(xiàn)控制器間負(fù)載均衡的過程，并定義相關(guān)參數(shù)，構(gòu)建SDN負(fù)載均衡網(wǎng)絡(luò)模型。

1.1 問題描述

SDN網(wǎng)絡(luò)管理系統(tǒng)的部署如圖1所示，系統(tǒng)架構(gòu)分為SDN控制層、數(shù)據(jù)轉(zhuǎn)發(fā)層和網(wǎng)絡(luò)流量層三層。SDN控制器層由多個(gè)包含負(fù)載均衡模塊的分布式控制器組成，是整個(gè)網(wǎng)絡(luò)的控制核心，獲取全局網(wǎng)絡(luò)視圖，通過控制交換機(jī)，從而實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)系統(tǒng)的管理和維護(hù)。數(shù)據(jù)轉(zhuǎn)發(fā)層是由多個(gè)OpenFlow交換機(jī)組成，實(shí)現(xiàn)數(shù)據(jù)包的轉(zhuǎn)發(fā)功能。網(wǎng)絡(luò)流量層由多個(gè)主機(jī)服務(wù)器構(gòu)成，負(fù)責(zé)產(chǎn)生網(wǎng)絡(luò)數(shù)據(jù)流量。

在該網(wǎng)絡(luò)架構(gòu)中，當(dāng)子域2接收到來自建筑云服務(wù)器的過多網(wǎng)絡(luò)流量時(shí)，域內(nèi)交換機(jī)會(huì)向控制器發(fā)送大量packet-in消息請(qǐng)求，導(dǎo)致控制器c₂與其他控制器間負(fù)載差異懸殊，嚴(yán)重影響網(wǎng)絡(luò)性能。因此，需要選取子域2中的交換機(jī)遷往子域1或3平衡控制器間負(fù)載，提高整體網(wǎng)絡(luò)流傳輸與處理能力。若控制平面的控制器間負(fù)載失衡，網(wǎng)絡(luò)吞吐量降低，會(huì)導(dǎo)致網(wǎng)絡(luò)系統(tǒng)產(chǎn)生傳輸信息延遲，最終整個(gè)系統(tǒng)崩潰。因此，進(jìn)行控制器間負(fù)載均衡研究具有十分重要的意義。

1.2 FSSM策略

基于模糊滿意度的交換機(jī)遷移策略（FSSM）主要分為兩個(gè)階段執(zhí)行：a）控制器負(fù)載監(jiān)測及選出遷出控制器和遷移交換機(jī)；b）構(gòu)建遷移競爭模型并求解遷入控制器，完成交換機(jī)遷移操作。

1.2.1 控制器負(fù)載和遷移觸發(fā)

根據(jù)圖論的相關(guān)知識(shí)，整個(gè)SDN用無向圖G（V，E）表示，V和E分別表示節(jié)點(diǎn)和鏈路的集合。m和n分別表示控制器和交換機(jī)的數(shù)量，C={c₁，c₂，…，cm}和S={s₁，s₂，…，sn}分別表示控制器和交換機(jī)的集合。交換機(jī)si與控制器cj的連接關(guān)系表示為xij為0或1，且最短距離用dij表示。主要參數(shù)說明如表1所示。

1.2.2 遷移競爭模型

隨著交換機(jī)動(dòng)態(tài)遷移過程的進(jìn)行，在控制器間負(fù)載均衡的同時(shí)，需要考慮隨之而來的遷移代價(jià)問題。

定義3 遷移代價(jià)。交換機(jī)遷移代價(jià)Pcost表示在交換機(jī)遷移生成的通信開銷，如式（3）～（5）所示，主要由遷移請(qǐng)求代價(jià)Prequest與負(fù)載變化代價(jià)Pchange組成。

定義4 負(fù)載均衡率。負(fù)載均衡率Φ是網(wǎng)絡(luò)中控制器負(fù)載分布狀態(tài)的直觀體現(xiàn)，如式（6）所示，其中μ是一個(gè)常數(shù)，保證隨負(fù)載均衡率數(shù)值增大，網(wǎng)絡(luò)負(fù)載越均衡。

定義5 遷移競爭模型?；谀：凉M意度的遷移競爭模型F如式（7）所示，用于解決遷移代價(jià)和負(fù)載均衡率兩個(gè)性能指標(biāo)之間的優(yōu)化問題，實(shí)質(zhì)上可轉(zhuǎn)換為多目標(biāo)決策問題^[13]。由于遷移代價(jià)和負(fù)載均衡率之間的優(yōu)化是[0，1]的定量評(píng)價(jià)，而不是“0或1”的定性評(píng)價(jià)，所以引入基于模糊數(shù)學(xué)的模糊滿意度，根據(jù)隸屬度理論進(jìn)行定性評(píng)價(jià)向定量評(píng)價(jià)轉(zhuǎn)換，用于綜合評(píng)價(jià)上述性能指標(biāo)。模糊滿意度是一種綜合評(píng)價(jià)方法，基于模糊數(shù)學(xué)對(duì)受到多種制約因素影響的對(duì)象或事物作出整體評(píng)價(jià)。它具有結(jié)果清晰、系統(tǒng)性強(qiáng)的特點(diǎn)，能較好地解決模糊和難以量化的問題，適用于解決各種不確定問題。

應(yīng)用基于模糊滿意度的多目標(biāo)決策方法實(shí)現(xiàn)遷移競爭模型中指標(biāo)的性能優(yōu)化。首先，設(shè)控制器的負(fù)載均衡率Φ為f1，交換機(jī)的遷移代價(jià)Pcost為f2，依據(jù)隸屬度函數(shù)對(duì)f1、f2的隸屬度進(jìn)行求解，并歸一化處理。隸屬度函數(shù)表示某元素屬于某模糊集合的真實(shí)程度，即一個(gè)集合中的元素是否屬于特定子集合，取值在[0，1]。隸屬度函數(shù)的選取具體有三種確定方法，包括模糊統(tǒng)計(jì)法、借助已有的客觀尺度和指派法。由于已知優(yōu)化目標(biāo)是保證負(fù)載均衡率f1高的同時(shí)遷移代價(jià)f2小，所以采用指派法中基于偏小型和偏大型模糊集合的梯形分布式隸屬度函數(shù)，如圖2、3所示，劃分f1、f2的三種優(yōu)化優(yōu)先權(quán)競爭狀態(tài)。

圖2是負(fù)載均衡率f1的隸屬度函數(shù)圖像，選擇偏小型，劃分f1的三種競爭狀況，隸屬度r1越小，f1優(yōu)先級(jí)越低。首先，當(dāng)f1大于0且小于最小閾值fmin1時(shí)，r1=1，則f1具有絕對(duì)優(yōu)化優(yōu)先權(quán)，即最低標(biāo)準(zhǔn)要保證負(fù)載均衡率維持正常水平；當(dāng)f1處于最小閾值fmin1和最大閾值fmax1區(qū)間時(shí)，r1單調(diào)遞減，則f1與其他指標(biāo)競爭優(yōu)化優(yōu)先權(quán)，本文是與f2競爭；當(dāng)f1大于最大閾值fmax1時(shí)，r1=0，則f1不參與競爭優(yōu)化優(yōu)先權(quán)，同時(shí)fmax1也是f1參與競爭的臨界值點(diǎn)。

圖3是遷移代價(jià)f2的隸屬度函數(shù)圖像，選擇偏大型，劃分f2的三種競爭狀況，隸屬度r2越大，f2優(yōu)先級(jí)越高。首先，當(dāng)f2大于0且小于最小閾值fmin2時(shí)，r2=0，則f2不參與競爭優(yōu)化優(yōu)先權(quán)，同時(shí)fmin2也是f2參與競爭的臨界值點(diǎn)；當(dāng)f2處于最小閾值fmin2和最大閾值fmax2區(qū)間時(shí)，r2單調(diào)遞增，則f2與其他指標(biāo)競爭優(yōu)化優(yōu)先權(quán)，本文是與f1競爭；當(dāng)f2大于最大閾值fmax2時(shí)，r2=1，則f2具有絕對(duì)優(yōu)化優(yōu)先權(quán)。

其數(shù)學(xué)表達(dá)式為

1.2.3 遷移方案設(shè)定

a）交換機(jī)選取。提出交換機(jī)組選擇度，描述選擇待遷移交換機(jī)組的概率?？紤]控制器負(fù)載和時(shí)延，如式（10）（11）所示，φkj為交換機(jī)組選擇度，Lcj（t）′為遷出控制器遷出負(fù)載后與平均負(fù)載的差值。

在選取遷移交換機(jī)之前，為了減少計(jì)算時(shí)間，篩選出符合式（12）約束條件的交換機(jī)組Sgroup（j），再選擇具有max φkj的交換機(jī)組作為遷移對(duì)象。式（10）中k∈[1，2n－1]。

b）遷入控制器選取。選擇遷入控制器不僅要考慮控制器具有max Fsicg，還要考慮控制器剩余處理容量Lcg（t）rem，如式（14）。因此使用式（13）選擇遷入控制器cg。

2 算法設(shè)計(jì)

設(shè)計(jì)FSSM-1和FSSM-2算法以交換機(jī)遷移的方式完成多控制器間負(fù)載均衡。第一階段，構(gòu)造均衡判斷矩陣并劃分交換機(jī)組以完成遷出控制器與遷移交換機(jī)的選擇；第二階段，提出改進(jìn)的蟻群算法并對(duì)構(gòu)建的遷移競爭模型優(yōu)化求解以選擇遷入控制器來完成交換機(jī)遷移操作。

2.1 遷出控制器與遷移交換機(jī)的選擇

依據(jù)當(dāng)前網(wǎng)絡(luò)狀況，完成遷出控制器和遷移交換機(jī)的選取過程。首先，計(jì)算所有控制器的負(fù)載率，得到控制器間負(fù)載差異因子?cαcβ（行1）；從得到的差異因子中選出最大和最小差異因子，計(jì)算均衡判斷閾值δ，并構(gòu)建均衡判斷矩陣Bm×m（行2～4）;進(jìn)行負(fù)載均衡的判斷，若判斷負(fù)載不均衡，將差異因子對(duì)應(yīng)的兩個(gè)控制器中負(fù)載大的控制器加入遷出控制器集合，負(fù)載小的控制器加入遷入控制器集合;循環(huán)行5～11，得到所有控制器的遷出控制器集合₁和遷入控制器集合₂（行12）;在₁中選擇負(fù)載率最大的控制器作為遷出控制器（行13）;劃分交換機(jī)組，循環(huán)行15～21，得到所有符合[（1/2）L（t），L（t））約束條件的交換機(jī)組。其次，選擇這些交換機(jī)組中具有max φkj的交換機(jī)組作為遷移交換機(jī)，得到待遷出的交換機(jī)組Sgroup（j）（行22～24），算法結(jié)束。

對(duì)該選取過程的算法實(shí)現(xiàn)，如FSSM-1算法所示，通過構(gòu)造的均衡判斷矩陣和劃分的交換機(jī)組來完成遷出控制器與遷移交換機(jī)的選擇。

算法1 FSSM-1算法

輸入：網(wǎng)絡(luò)拓?fù)銰（V，E）。

輸出：遷出控制器集合₁；遷入控制器集合₂；遷移交換機(jī)Sgroup（j）Scj。

1 calculate Lcj（t） and ?cαcβ

2 get ?min（Bm×m） and" ?max（Bm×m）

3 calculate δ

4 construct matrix Bm×m

5 while （|?cαcβ－?cβcα|gt;δ）

6 if （Lcαgt;Lcβ）

7 then add cα to ₁ and add" cβ to ₂

8 else add cα to ₂ and add" cβ to ₁

9 end if

10 Bm×m=Bm×m－（?cαcβ，?cβcα）

11 end while

12 get ₁ and ₂

13 select the emigration controller with max Lcj（t）

14 calculate φkj based on Lcj（t），" dij and" L（t）

15 while （cj）

16 traverse the nums switches of the migration controller cj management

17 get the switch combinations Sgroup

18 if （12L（t）≤Lcj（t）－∑si∈Sgroup（k）Lsi（t）lt;L（t））

19 then select k switches that meet the constraint Sgroup（k）

20 end if

21 end while

22 select a switch combination with max φkj as the migrating switches

23 Scj=Scj－Sgroup（j）

24 get Sgroup（j）

算法復(fù)雜度是O（nums），nums表示遷出控制器所管理的交換機(jī)數(shù)目。相關(guān)運(yùn)算均為簡單的線性運(yùn)算，具有可行性和實(shí)時(shí)性。

2.2 選擇遷入控制器并完成交換機(jī)遷移

本文通過遷移代價(jià)和負(fù)載均衡率兩個(gè)性能指標(biāo)建立遷移競爭模型以選擇遷入控制器并完成交換機(jī)遷移。智能優(yōu)化算法是優(yōu)化求解該競爭模型中多目標(biāo)優(yōu)化問題的有效手段。常用優(yōu)化算法主要包括就近選擇算法^[7]、遺傳算法^[14]、蟻群算法^[15]等。全面考慮現(xiàn)有優(yōu)化算法和實(shí)際交換機(jī)遷移狀況，選擇在提高計(jì)算速度和降低復(fù)雜度方面具有優(yōu)勢(shì)的蟻群算法作為本文將要改進(jìn)的智能優(yōu)化算法。蟻群算法是一種啟發(fā)式算法，其基本思想來自于螞蟻覓食的最短路徑原理，螞蟻在其走過的路徑上釋放一種被稱為信息素的激素，使其被一定范圍的其他螞蟻發(fā)現(xiàn)。當(dāng)某些路徑上經(jīng)過的螞蟻越來越多，信息素濃度也越來越高，螞蟻選擇這些路徑的概率也就越高，結(jié)果導(dǎo)致這些路徑的信息素濃度又增高，螞蟻通過這些路徑的概率又上升，反復(fù)迭代，尋找最佳路徑。改進(jìn)蟻群算法的流程如圖4所示。

由于傳統(tǒng)蟻群算法具有隨機(jī)搜索和易陷入局部最優(yōu)的劣勢(shì)，所以本文提出蟻群算法的兩點(diǎn)改進(jìn)思路：

a）時(shí)延因子啟發(fā)函數(shù)的改進(jìn)。由于傳統(tǒng)蟻群算法在迭代初期的各路徑信息素濃度相同，表現(xiàn)為隨機(jī)搜索路徑，所以通過對(duì)距離進(jìn)行一定設(shè)置以合理放大搜索范圍。同時(shí)，由于蟻群算法在迭代后期的時(shí)延距離不再是選取路徑的主要影響因素，所以設(shè)置衰退系數(shù)以降低該啟發(fā)函數(shù)在算法迭代后期的影響力。時(shí)延因子啟發(fā)函數(shù)如式（15）所示，其中f₃_max、f₃_min和dig表示交換機(jī)si到遷入控制器cg距離的最大值、最小值和當(dāng)前值，Nmax、Nmin和Nc表示算法迭代次數(shù)的最大值、最小值和當(dāng)前值，ε₁和ε₂是衰退系數(shù)。

b）信息素更新公式的改進(jìn)。信息素濃度的更新由信息素?fù)]發(fā)和信息素增量一減一增兩部分組成，下一時(shí)刻的信息素濃度τij（t+1）如式（16）所示。

其中：Θij是揮發(fā)系數(shù);τij（t）是t時(shí)刻的當(dāng)前路徑信息素濃度; Δτij是信息素增量。

首先，對(duì)揮發(fā)系數(shù)Θij進(jìn)行改進(jìn)，如式（17）所示。傳統(tǒng)蟻群算法中的揮發(fā)系數(shù)是定值，算法易陷入局部最優(yōu)。因此，為了避免該問題，將揮發(fā)系數(shù)設(shè)置成動(dòng)態(tài)可變的。首先，計(jì)算當(dāng)前路徑信息素濃度τij與各路徑中最大信息素濃度τi-max的比值τij/τi-max。然后，使用調(diào)節(jié)系數(shù)ρ調(diào)整揮發(fā)系數(shù)Θij與當(dāng)前路徑信息素濃度τij的關(guān)系為負(fù)相關(guān)，保證信息素濃度大的路徑，信息素?fù)]發(fā)得慢，而信息素濃度小的路徑，信息素?fù)]發(fā)得快。這種動(dòng)態(tài)可變的揮發(fā)系數(shù)有效增大了路徑之間的信息素濃度差異，避免算法陷入局部最優(yōu)。

然后，對(duì)信息素增量Δτij進(jìn)行改進(jìn)，如式（18）所示?；谶w移競爭模型中f₁與f₂的優(yōu)化優(yōu)先權(quán)的三種競爭狀態(tài)，對(duì)信息素增量進(jìn)行相應(yīng)設(shè)置。當(dāng)f₁具有絕對(duì)優(yōu)先權(quán)時(shí)，只釋放f₁的信息素；當(dāng)f₂具有絕對(duì)優(yōu)先權(quán)時(shí)，只釋放f₂的信息素；當(dāng)f₁與f₂存在競爭時(shí)，基于f₁、f₂的隸屬度比值r₁/r₂按比例釋放兩種信息素。這種分情況釋放信息素的方式，可以加快算法收斂速度且不易陷入局部最優(yōu)。

其中：Q、Δτ^f₁ ^{or f}₂ij和Δτ^f₁^.2ij是定值;Len是螞蟻?zhàn)哌^總距離長度。

利用改進(jìn)蟻群算法對(duì)遷移競爭模型進(jìn)行求解以選擇遷入控制器并完成交換機(jī)遷移的優(yōu)化過程：

a）初始化參數(shù)。包括信息素濃度τij、時(shí)延因子啟發(fā)函數(shù)D，最小、最大迭代次數(shù)Nmin和Nmax（行1）。

b）隨機(jī)放置螞蟻。根據(jù)D計(jì)算每個(gè)螞蟻的下一個(gè)訪問節(jié)點(diǎn)，直至所更新信息素表有螞蟻訪問完所有節(jié)點(diǎn)（行2）。

c）計(jì)算各個(gè)螞蟻經(jīng)過的路徑長度Len，記錄當(dāng)前迭代次數(shù)中的最優(yōu)解（行3）。

d）構(gòu)建遷移競爭模型。得到遷移代價(jià)和負(fù)載均衡率兩個(gè)性能指標(biāo)的隸屬度函數(shù)比值r₁/r₂，用于之后更新信息素增量（行4）。

e）基于遷移競爭模型的三種優(yōu)化優(yōu)先權(quán)競爭狀態(tài)，對(duì)各個(gè)節(jié)點(diǎn)連接路徑上的下一時(shí)刻信息素濃度τij（t+1）進(jìn)行更新（行5～17）。在三種競爭關(guān)系中，當(dāng)f₁與f₂存在競爭時(shí)，依據(jù)f₁與f₂的隸屬度比值釋放兩種信息素（行6～9）；當(dāng)f₁的優(yōu)化有絕對(duì)的優(yōu)先權(quán)時(shí)，只釋放f₁信息素；當(dāng)f₂的優(yōu)化有絕對(duì)的優(yōu)先權(quán)時(shí)，只釋放f₂信息素（行11～14）。

f）判斷是否達(dá)到最大迭代次數(shù)Nmax，若未達(dá)到，則返回步驟b），否則退出循環(huán)（行20～22）。

g）輸出程序結(jié)果，并根據(jù)需要輸出遷入控制器cg，然后將遷移交換機(jī)Sgroup（j）從cj遷移到cg上，完成交換機(jī)遷移操作，最后更新控制器—交換機(jī)連接關(guān)系xij（行23～25）。

對(duì)優(yōu)化過程進(jìn)行算法實(shí)現(xiàn)，如FSSM-2算法所示，通過改進(jìn)的蟻群算法對(duì)遷移競爭模型函數(shù)F進(jìn)行優(yōu)化求解，算法迭代得到遷入控制器cg，然后完成交換機(jī)遷移操作。

算法2 FSSM-2算法

輸入：網(wǎng)絡(luò)拓?fù)銰（V，E）；遷出控制器cj；遷移交換機(jī)Sgroup（j）Scj；遷入控制器集合₂。

輸出：遷入控制器cg；控制器—交換機(jī)連接關(guān)系xij。

1 initialization τij， D and iterations Nmin and Nmax

2 place the ants according D

3 calculate Len and record the optimal solution in the current iteration number

4 build the migration competition model F=r₁r₂

5 start updating pheromones by three competing states of the migration competition model

6 if （Rminlt;f₁lt;Rmax） then

7 competition between f₁ and f₂

8 Θij= Θ×（τij/τi-max）^ρ

9 Δτij=QLen+Δτ^f₁^.2ijr₁r₂

10 else

11 if （f₁≤Rmin or f₁≥Rmax） then

12 no competition between f₁ and f₂

13 Θij= Θ×（τij/τi-max）^ρ

14 Δτij=QLen+Δτ^f₁^orf₂ij

15 end if

16 end if

17 τij（t+1）=Θij×τij（t）+Δτij，Θij∈（0，1）

18 complete an iterative process

19 set counter Nc=Nc+1

20 while （Nminlt;Nclt;Nmax）

21 turn to line 2

22 end while

23 get the immigration controller cg

24 migrate Sgroup（j） from cj to cg

25 get the connection relationship xij

對(duì)FSSM-2算法進(jìn)行必要的收斂性和復(fù)雜度說明。

1）算法收斂性

首先，改進(jìn)時(shí)延因子啟發(fā)函數(shù)對(duì)搜索初期的搜索范圍進(jìn)行合理放大，不再是盲目搜索，前期收斂性得到提高。其次，在信息素更新時(shí)，傳統(tǒng)方式是釋放信息素濃度等量，收斂較緩慢，本文將基于模糊滿意度的遷移競爭模型與信息素更新公式結(jié)合，在不同競爭狀態(tài)下，釋放的信息素濃度不同，能夠更快找到最優(yōu)路徑，收斂性得到進(jìn)一步提高。因此，算法收斂性得到保證。

2）算法復(fù)雜度

算法復(fù)雜度是O（m²g ），與遷入控制器集合中控制器個(gè)數(shù)mg有關(guān)。每次算法迭代都選擇最優(yōu)路徑進(jìn)行信息素更新，涉及到的公式均為加減乘除的線性運(yùn)算，算法具有有效性和實(shí)時(shí)性。

3 性能評(píng)估

為了驗(yàn)證本文FSSM策略的有效性與可行性，本章將FSSM策略與具有代表性的單控制器部署（single controller deployment，SCD）策略、就近遷移（nearest migration，NM）策略^[7]、在線動(dòng)態(tài)調(diào)整（algorithm of dynamic online adjustment，ADO-A）策略^[9]、控制域調(diào)整（control domain adjustment algorithm，CDAA）策略^[10]進(jìn)行比較。各種策略性能描述如表2所示。

3.1 仿真環(huán)境搭建

1）實(shí)驗(yàn)平臺(tái)和物理設(shè)備

本文選用RYU^[16]控制器，并基于Mininet仿真工具。共選取八臺(tái)具有相同配置的服務(wù)器設(shè)備，Intel Core i7 3.2 GHz 8 GB RAM，裝載Ubuntu 16.04 LTS系統(tǒng)。六臺(tái)機(jī)器運(yùn)行基于FSSM的RYU控制器，一臺(tái)機(jī)器上僅安裝RYU控制器模擬集中式控制器，另一臺(tái)機(jī)器上運(yùn)行Mininet。iperf用于生成網(wǎng)絡(luò)流量，以及用Cbench模擬packet-in流請(qǐng)求。

2）拓?fù)溥x擇

為了模擬真實(shí)的網(wǎng)絡(luò)環(huán)境，實(shí)驗(yàn)中的拓?fù)涫褂肙S3E^[17]，驗(yàn)證FSSM策略的有效性。此外為了驗(yàn)證FSSM策略的拓?fù)溥m用性，使用Internet Topology Zoo^[18]中的拓?fù)銲nterllifiber，具有較OS3E更大的網(wǎng)絡(luò)規(guī)模，有73個(gè)節(jié)點(diǎn)和93條鏈路。此外，每個(gè)交換機(jī)與兩個(gè)主機(jī)連接。

3）參數(shù)設(shè)定

為了模擬真實(shí)的網(wǎng)絡(luò)流量狀況，參照文獻(xiàn)[19]的流量特征，使用iperf工具模擬網(wǎng)絡(luò)流量分布狀況。為了有效評(píng)估方案的可行性，設(shè)定數(shù)據(jù)流具有不同的到達(dá)速率，為5 000～15 000 K/s。此外設(shè)定每個(gè)交換機(jī)每秒隨機(jī)產(chǎn)生流請(qǐng)求及請(qǐng)求路徑，這樣能夠更好地模擬出真實(shí)的網(wǎng)絡(luò)環(huán)境。設(shè)定所有控制器具有相同的性能，處理容量的上限為10 000 K，設(shè)packet-in流請(qǐng)求數(shù)目為30 Byte。

3.2 仿真結(jié)果分析

1）遷移代價(jià)與控制器吞吐量

本實(shí)驗(yàn)對(duì)比兩種規(guī)模網(wǎng)絡(luò)中，遷移代價(jià)及控制器吞吐量狀況。實(shí)驗(yàn)結(jié)果如圖5、6所示，在遷移代價(jià)方面，ADOA最高，NM次之，CDAA、FSSM較前兩者更低且相差不大，SCD則為0；在控制器吞吐量方面，F(xiàn)SSM最高，ADOA、CDAA相差不大，NM降低比較明顯，SCD最低。SCD只有一個(gè)控制器，發(fā)生過載無法遷移，遷移代價(jià)為0，而控制器與交換機(jī)的信息傳輸則會(huì)產(chǎn)生吞吐量。雖然NM能夠就近遷移交換機(jī)到鄰居控制器，有效減少遷移代價(jià)，然而這種方式極易造成鄰居控制器也過載的情況。ADOA通過控制器域內(nèi)、域間的頻繁信息傳輸動(dòng)態(tài)調(diào)整控制器負(fù)載，降低傳播時(shí)延和排隊(duì)時(shí)延，然而會(huì)產(chǎn)生大量遷移代價(jià)以及降低控制器吞吐量。CDAA考慮到域內(nèi)及域間通信代價(jià)，通過BFS算法有效降低遷移成本，吞吐量較ADOA也有些許增加。本文FSSM通過建立遷移模糊競爭模型，遷移過程始終保持遷移代價(jià)與負(fù)載均衡率之間的當(dāng)前最優(yōu)狀態(tài)，從全局角度出發(fā)亦提高了控制器吞吐量。在OS3E網(wǎng)絡(luò)中，F(xiàn)SSM相比近年來的ADOA、CDAA交換機(jī)遷移策略，遷移代價(jià)分別降低了38.3%、13.8%，吞吐量分別提高了15.6%、12.4%。在更大規(guī)模的Interllifiber網(wǎng)絡(luò)中，F(xiàn)SSM優(yōu)勢(shì)更明顯，遷移代價(jià)分別降低了43.7%、11.6%，吞吐量分別提高了35.7%、23.9%。總體來說，F(xiàn)SSM與ADOA、CDAA相比，遷移代價(jià)平均降低了26.8%，吞吐量平均提高了20.8%。

2）控制器響應(yīng)時(shí)間

如圖7、8所示，SCD的控制器響應(yīng)時(shí)間波動(dòng)較小，基本不會(huì)隨著網(wǎng)絡(luò)環(huán)境的變化而出現(xiàn)較大波動(dòng)，一直維持在最高值0.9 s附近。NM具有高響應(yīng)時(shí)間峰值0.693 s和較大波動(dòng)，ADOA、CDAA、FSSM的響應(yīng)時(shí)間短且波動(dòng)較小，在40 min后趨于穩(wěn)定，并且在OS3E網(wǎng)絡(luò)中，前30 min三者響應(yīng)時(shí)間相差不大。NM就近遷移交換機(jī)到鄰居控制器，然而當(dāng)鄰近控制器也發(fā)生過載時(shí)，會(huì)發(fā)生二次遷移，網(wǎng)絡(luò)波動(dòng)較大，同時(shí)也增加了控制器響應(yīng)時(shí)間。OS3E網(wǎng)絡(luò)中，在0～40 min階段，由于ADOA、CDAA和FSSM都是動(dòng)態(tài)調(diào)整控制器負(fù)載，所以三者響應(yīng)時(shí)間不相上下，在0.3～0.4 s附近。然而隨著時(shí)間的推移以及網(wǎng)絡(luò)規(guī)模的擴(kuò)大，在Interllifiber中，F(xiàn)SSM始終比ADOA、CDAA的響應(yīng)時(shí)間短，差值基本維持在0.1 s左右，這是因?yàn)镕SSM通過負(fù)載差異矩陣對(duì)控制器負(fù)載監(jiān)測以及使用交換機(jī)組遷移，進(jìn)行多交換機(jī)任務(wù)。實(shí)驗(yàn)證明，F(xiàn)SSM在控制器響應(yīng)時(shí)間方面優(yōu)于上述四種策略。

對(duì)上述兩幅圖的實(shí)驗(yàn)結(jié)果進(jìn)行求平均值數(shù)據(jù)處理，得到圖9所示兩種網(wǎng)絡(luò)中五種策略的控制器平均響應(yīng)時(shí)間。OS3E網(wǎng)絡(luò)中，F(xiàn)SSM的控制器平均響應(yīng)時(shí)間相較于SCD、NM、ADOA、CDAA，分別下降了67.3%、44.5%、6.9%、8.3%，平均縮短0.32 s。而在更大規(guī)模的Interllifiber網(wǎng)絡(luò)中，F(xiàn)SSM的控制器平均響應(yīng)時(shí)間相較于SCD、NM、ADOA、CDAA，分別下降了66.5%、51.7%、22.5%、24.0%，平均縮短0.41 s。

3）負(fù)載均衡率

本實(shí)驗(yàn)對(duì)負(fù)載均衡性能評(píng)估，如圖10、11所示。隨著packet-in消息數(shù)目的增加，所有遷移策略（NM、ADOA、CDAA及FSSM）的負(fù)載均衡率都呈現(xiàn)下降趨勢(shì)，這是因?yàn)楫a(chǎn)生的過載控制器數(shù)量會(huì)提升，觸發(fā)交換機(jī)遷移，保持控制器間負(fù)載均衡變得愈加困難。初始狀態(tài)沒有packet-in請(qǐng)求，控制器負(fù)載均衡率均在0.8以上。當(dāng)開始發(fā)送流請(qǐng)求之后，packet-in消息數(shù)目在0～20 Byte時(shí)，各遷移策略亦保持著高負(fù)載均衡率。然而，隨著控制器接收越來越多的packet-in流請(qǐng)求，NM發(fā)生明顯下降，這是由于NM只能將負(fù)載轉(zhuǎn)移到鄰居控制器，然而鄰居控制器負(fù)載可能也高，不能成為最佳選擇對(duì)象。ADOA、CDAA及FSSM都是從全局出發(fā)平衡負(fù)載，能夠得到及時(shí)的負(fù)載轉(zhuǎn)移，因此負(fù)載均衡率相對(duì)平穩(wěn)下降。此外，F(xiàn)SSM通過改進(jìn)的蟻群算法提高遷移速度以及使用遷移競爭模型，全程考慮控制器間負(fù)載均衡率，保障發(fā)生負(fù)載失衡后盡快實(shí)施交換機(jī)遷移。因此，較其他三種策略，F(xiàn)SSM的負(fù)載均衡率始終維持最高水平。OS3E網(wǎng)絡(luò)中，F(xiàn)SSM相比NM的負(fù)載均衡率提高了25.6%，相比ADOA、CDAA的負(fù)載均衡率平均提高了15.3%。Interllifiber網(wǎng)絡(luò)中，F(xiàn)SSM相比NM的負(fù)載均衡率提高了41.7%，相比ADOA、CDAA的負(fù)載均衡率平均提高了9.0%。總體來說，F(xiàn)SSM相較其他三種策略，負(fù)載均衡率全程下降緩慢，維持在最高水平，表現(xiàn)出良好的負(fù)載均衡率性能。

4 結(jié)束語

本文討論了分布式SDN中的多控制器間負(fù)載均衡問題，以遷移代價(jià)和負(fù)載均衡率為優(yōu)化目標(biāo)，利用模糊滿意度模型和蟻群算法快速求解，提出了分階段式的遷移算法FSSM。通過實(shí)驗(yàn)仿真發(fā)現(xiàn)，F(xiàn)SSM能夠以較少的時(shí)間均衡控制器間負(fù)載，且能夠有效降低交換機(jī)遷移帶來的額外遷移開銷。下一步計(jì)劃將研究重心放在網(wǎng)絡(luò)設(shè)備發(fā)生故障的特殊情況上以進(jìn)一步提高分布式SDN網(wǎng)絡(luò)的健壯性。

參考文獻(xiàn)：

[1]左青云，陳鳴，趙廣松，等.基于OpenFlow的SDN技術(shù)研究[J].軟件學(xué)報(bào)，2013，24（5）：1078-1097.（Zuo Qingyun， Chen Ming， Zhao Guangsong， et al. Research on OpenFlow-based SDN technologies[J].Journal of Software，2013，24（5）：1078-1097.）

[2]Semong T， Maupong T， Anokye S， et al. Intelligent load balancing techniques in software defined networks： a survey[J].Electronics，2020，9（7）：1091.

[3]Killi B P R， Rao S V. Capacitated next controller placement in software defined networks[J].IEEE Trans on Network and Service Management，2017，14（3）：514-527.

[4]賈吾財(cái)，呂光宏，王桂芝，等.SDN多控制器放置問題研究綜述[J].計(jì)算機(jī)科學(xué)，2020，47（7）：206-212.（Jia Wucai， Lyu Guanghong， Wang Guizhi， et al. Review on placement of multiple controllers in SDN[J].Computer Science，2020，47（7）：206-212.）

[5]Heller B， Sherwood R， McKeown N. The controller placement problem[J].ACM SIGCOMM Computer Communication Review，2012，42（4）：473-478.

[6]Zhou Yuanhao， Zhu Mingfa， Xiao Limin， et al. A load balancing strategy of SDN controller based on distributed decision[C]//Proc of the 13th IEEE International Conference on Trust， Security and Privacy in Computing and Communications.Washington DC：IEEE Compu-ter Society，2014：851-856.

[7]Dixit A， Hao F， Mukherjee S， et al. Towards an elastic distributed SDN controller[J].ACM SIGCOMM Computer Communication Review，2013，43（4）：7-12.

[8]Li Jiaqi， Sun Enchang， Zhang Yanhua. Multi-threshold SDN controllers load balancing algorithm based on controller load[C]//Proc of International Conference on Computer，Communications and Network.2018：145-154.

[9]史久根，謝熠君，孫立，等.軟件定義網(wǎng)絡(luò)中面向時(shí)延和負(fù)載的多控制器放置策略[J].電子與信息學(xué)報(bào)，2019，41（8）：1869-1876.（Shi Jiugen， Xie Yijun， Sun Li， et al. Multi-controller placement strategy based on latency and load in software defined network[J].Journal of Electronics amp; Information Technology，2019，41（8）：1869-1876.）

[10]Li Guoyan， Wang Xinqiang， Zhang Zhigang. SDN-based load balancing scheme for multi-controller deployment[J].IEEE Access，2019，7：39612-39622.

[11]Hu Tao， Lan Julong， Zhang Jianhui， et al. EASM： efficiency-aware switch migration for balancing controller loads in software-defined networking[J].Peer-to-Peer Networking and Applications，2019，12（2）：452-464.

[12]Adekoya O， Aneiba A， Patwary M. An improved switch migration decision algorithm for SDN load balancing[J].IEEE Open Journal of the Communications Society，2020（1）：1602-1613.

[13]Chen Yuanlin. An interactive fuzzy-norm satisfying method for multi-objective reactive power sources planning[J].IEEE Trans on Power Systems，2000，15（3）：1154-1160.

[14]Xue Hai， Kim K T， Youn H Y. Dynamic load balancing of software-defined networking based on genetic-ant colony optimization[J].Sensors，2019，19（2）：311.

[15]Dorigo M， Maniezzo V. Ant system： optimization by a colony of coo-perating agents[J].IEEE Trans on Systems， Man， and Cybernetics： Part B，1996，26（1）：29-41.

[16]Morita K， Yamahata I， Linux V， et al. Ryu： network operating system[EB/OL].（2012）[2020-09-10].https：//ryu-sdn.org/.

[17]Wood G. Internet2 open science， scholarship and services exchange[EB/OL].（1996）[2020-09-05].http：//www.internet2.edu/network/ose/.

[18]Knight S， Nguyen H X， Falkner N， et al. The Internet topology zoo[EB/OL].（2011）[2020-09-10].http：//www.topology-zoo.org/.

[19]Hu Tao， Yi Peng， Guo Zehua， et al. Bidirectional matching strategy for multi-controller deployment in distributed software defined net-working[J].IEEE Access，2018，6：14946-14953.