SDN中基于雙向匹配的多控制器動(dòng)態(tài)部署算法

胡濤，張建輝，孔維功，楊森，曹路佳

?

SDN中基于雙向匹配的多控制器動(dòng)態(tài)部署算法

胡濤，張建輝，孔維功，楊森，曹路佳

（國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南 鄭州 450002）

針對(duì)分布式軟件定義網(wǎng)絡(luò)（SDN, software defined networking）中控制器負(fù)載不均衡問題，提出一種基于雙向匹配的多控制器動(dòng)態(tài)部署算法。首先，周期性收集網(wǎng)絡(luò)中跳數(shù)、時(shí)延和流量信息，分別構(gòu)建交換機(jī)和控制器的匹配列表。然后，按照優(yōu)化排序原則從2個(gè)列表中選取交換機(jī)和控制器實(shí)施雙向匹配，并通過模擬退火算法優(yōu)化匹配關(guān)系，實(shí)現(xiàn)分布式網(wǎng)絡(luò)中多控制器的動(dòng)態(tài)部署。仿真結(jié)果表明，與現(xiàn)有的方法相比，該算法能夠合理配屬交換機(jī)和控制器之間的連接關(guān)系，有效降低流請(qǐng)求排隊(duì)時(shí)延，同時(shí)控制器負(fù)載均衡率至少提高了17.9%。

軟件定義網(wǎng)絡(luò)；控制器；負(fù)載均衡；雙向匹配

1 引言

軟件定義網(wǎng)絡(luò)作為一種新型網(wǎng)絡(luò)體系架構(gòu)[1]，實(shí)現(xiàn)了控制平面和數(shù)據(jù)平面的完全解耦，將束縛在轉(zhuǎn)發(fā)設(shè)備內(nèi)的控制功能抽象到上層，能夠靈活地管理網(wǎng)絡(luò)且具有直接可編程[2]的特點(diǎn)，受到人們的廣泛關(guān)注，在域內(nèi)數(shù)據(jù)中心和域間數(shù)據(jù)中心[3]有著廣闊的應(yīng)用前景。

隨著應(yīng)用需求多元化和網(wǎng)絡(luò)流量的不斷增長(zhǎng)，同時(shí)為了提高控制器的可擴(kuò)展性，避免單點(diǎn)失效問題[4]，控制平面通常應(yīng)用于分布式系統(tǒng)，采用多控制器部署，如HyperFlow[5]、Kandoo[6]等。多控制器架構(gòu)將交換機(jī)靜態(tài)部署給控制器，由一個(gè)控制器管理多個(gè)交換機(jī)形成SDN子域?？刂破鏖g交互網(wǎng)絡(luò)狀態(tài)信息，共同完成流請(qǐng)求處理。

多控制器架構(gòu)的引入增強(qiáng)了網(wǎng)絡(luò)的靈活性和可靠性，然而由于控制器與交換機(jī)配屬失衡和SDN子域規(guī)劃不合理，一旦子域中出現(xiàn)控制器連接交換機(jī)數(shù)量過多，或流量突發(fā)造成控制器處理容量不足時(shí)，很容易導(dǎo)致各子域網(wǎng)絡(luò)中控制器負(fù)載差異較大，降低了網(wǎng)絡(luò)的通信性能。

近年來，關(guān)于控制器負(fù)載均衡的研究可以分為2種。1) 從控制器角度分析，優(yōu)化控制器的部署數(shù)量和位置[7~11]。此種方案主要通過合理部署控制器實(shí)現(xiàn)控制器負(fù)載均衡并提高控制平面可擴(kuò)展性，不足之處在于需要同時(shí)考慮多種度量因素，部署策略僵化、算法復(fù)雜度較高。2) 從交換機(jī)角度分析，改進(jìn)現(xiàn)有的交換機(jī)設(shè)計(jì)模式或調(diào)整交換機(jī)與控制器之間的連接關(guān)系[12~16]，保證控制器資源的合理利用。但交換機(jī)設(shè)計(jì)受限于已有的硬件條件，同時(shí)將交換機(jī)動(dòng)態(tài)調(diào)整作為一種彈性控制方式，很容易造成網(wǎng)絡(luò)架構(gòu)不穩(wěn)定，并且會(huì)產(chǎn)生大量的額外通信開銷，控制器邏輯一致性和狀態(tài)同步性較差。

針對(duì)上述研究中存在的問題，同時(shí)考慮交換機(jī)和控制器2個(gè)方面因素，以控制器負(fù)載均衡為目標(biāo)，應(yīng)用匹配思想[17]，提出了一種基于雙向匹配的多控制器動(dòng)態(tài)部署（MCDD, multi-controllers dynamic deployment）算法。本文的主要貢獻(xiàn)和創(chuàng)新工作總結(jié)如下。

1) 對(duì)SDN多控制器部署過程進(jìn)行建模研究，將交換機(jī)和控制器之間的流請(qǐng)求傳輸與處理刻化為排隊(duì)模型，分析發(fā)現(xiàn)網(wǎng)絡(luò)中時(shí)延和流量是影響控制器負(fù)載的2個(gè)因素。

2) 設(shè)計(jì)了基于雙向匹配的MCDD算法。根據(jù)網(wǎng)絡(luò)參數(shù)分別構(gòu)建交換機(jī)和控制器的匹配列表，交換機(jī)匹配具有輕流量負(fù)載的控制器，保證數(shù)據(jù)分組處理速率；控制器綜合考慮跳數(shù)、流請(qǐng)求速率和交換機(jī)歷史流量信息，匹配列表中最優(yōu)交換機(jī)，提升控制器資源利用率。同時(shí)，在雙向匹配過程中引入模擬退火算法提高匹配效率，并優(yōu)化匹配關(guān)系，實(shí)現(xiàn)多控制器負(fù)載均衡。

3) 在理論層面，通過數(shù)學(xué)推導(dǎo)論證，分析MCDD算法可行性。在實(shí)驗(yàn)層面，綜合多種負(fù)載均衡性能評(píng)價(jià)指標(biāo)，與現(xiàn)有的代表性算法進(jìn)行對(duì)比，開展相關(guān)實(shí)驗(yàn)研究，驗(yàn)證MCDD算法的性能優(yōu)勢(shì)。

2 相關(guān)工作

近年來，控制器負(fù)載均衡作為SDN領(lǐng)域的研究熱點(diǎn)，研究人員分別從控制器和交換機(jī)2個(gè)角度開展相關(guān)研究。

從控制器角度開展的研究主要考慮控制器部署狀態(tài)問題。Heller等[7]首次提出控制器部署和負(fù)載問題，注重網(wǎng)絡(luò)中平均時(shí)延和最大時(shí)延2類因素，將交換機(jī)和控制器之間的連接轉(zhuǎn)化為設(shè)備位置問題，構(gòu)建相應(yīng)數(shù)學(xué)模型，確定控制器最佳部署狀態(tài)。但在該文獻(xiàn)中并沒有考慮網(wǎng)絡(luò)流量的動(dòng)態(tài)傳輸。Hock等[8]將控制器部署轉(zhuǎn)化為Pareto彈性優(yōu)化問題，設(shè)定時(shí)延限制，失效容忍和負(fù)載均衡作為求解目標(biāo)，通過Pareto優(yōu)化去配置不同的性能度量，在時(shí)效性和算法準(zhǔn)確性之間進(jìn)行權(quán)衡。文獻(xiàn)[9]提出一種基于-means聚類劃分的控制器部署方案，初始化個(gè)聚類，并且基于節(jié)點(diǎn)距離為每個(gè)聚類分配一個(gè)中心，將該聚類中心作為控制器部署點(diǎn)。按照距離最短原則為控制器分配交換機(jī)，以迭代優(yōu)化的方式進(jìn)行聚類調(diào)整，優(yōu)化控制器部署位置和子域規(guī)模，有效地降低了控制器通信時(shí)延和負(fù)載開銷。文獻(xiàn)[10]提出使用博弈論解決SDN控制器最優(yōu)部署，在交換機(jī)到控制器時(shí)延、控制器間時(shí)延、控制器負(fù)載均衡3個(gè)目標(biāo)之間進(jìn)行博弈考慮，尋求一種均衡度量方法，確定控制器部署數(shù)量和位置。但由于算法復(fù)雜度較高，僅適應(yīng)于小規(guī)模網(wǎng)絡(luò)拓?fù)?。文獻(xiàn)[11]提出使用貪婪算法均衡控制器負(fù)載。通過對(duì)流請(qǐng)求的傳輸與處理進(jìn)行分析，計(jì)算數(shù)據(jù)收集代價(jià)，流表安裝代價(jià)和控制器同步代價(jià)，并建立相應(yīng)的開銷函數(shù)，求解負(fù)載均衡過程中控制器最小部署代價(jià)。

在SDN中，由于交換機(jī)的Packet-in請(qǐng)求是控制器負(fù)載的主要來源，因此，從交換機(jī)角度出發(fā)，相關(guān)學(xué)者提出優(yōu)化交換機(jī)自身性能和調(diào)整交換機(jī)與控制器連接關(guān)系，從而均衡控制器的負(fù)載分配。文獻(xiàn)[12]提出了DIFANE方案，其核心思想是設(shè)定網(wǎng)絡(luò)中部分交換機(jī)為權(quán)威交換機(jī)。根據(jù)預(yù)先定義的分區(qū)規(guī)則和權(quán)威規(guī)則，交換機(jī)不需要頻繁請(qǐng)求控制器，從而減輕了控制器負(fù)載。DevoFlow[13]采取規(guī)則復(fù)制和局部操作2種方式，減小了OpenFlow交換機(jī)和控制器的信息交互，從而有效地減輕和均衡了控制平面負(fù)載。文獻(xiàn)[14]對(duì)控制器進(jìn)行分層處理，構(gòu)建控制器集合，通過一個(gè)分層的超級(jí)控制器進(jìn)行協(xié)調(diào)。在不同的分組規(guī)則下基于單連接創(chuàng)建子網(wǎng)，每個(gè)控制器僅管理網(wǎng)絡(luò)的一部分。但不合理的子網(wǎng)規(guī)劃，容易導(dǎo)致交換機(jī)和控制器在局部網(wǎng)絡(luò)域中出現(xiàn)連接失衡。Chen等[15]提出了一種SDN彈性控制機(jī)制，將交換機(jī)從高負(fù)載控制器遷移至低負(fù)載控制器實(shí)現(xiàn)了負(fù)載在控制平面的重新分配。同時(shí)，文獻(xiàn)[15]還設(shè)計(jì)了相應(yīng)的分布式逐跳算法，使不同控制器可以獨(dú)立地運(yùn)行算法邏輯對(duì)交換機(jī)實(shí)施遷移。不足之處在于，交換機(jī)遷移作為一種動(dòng)態(tài)均衡方式會(huì)造成SDN不穩(wěn)定，并且控制器間需要進(jìn)行頻繁通信去保持SDN控制邏輯一致性。

3 模型構(gòu)建

3.1 問題重述

本節(jié)主要對(duì)多控制器部署過程中控制器負(fù)載不均衡問題進(jìn)行重述。在現(xiàn)有的分布式SDN中，多控制器部署架構(gòu)如圖1所示。整個(gè)網(wǎng)絡(luò)被劃分為2個(gè)子域即Subdomain1和Subdomain2。在Subdomain1中，控制器1的剩余處理容量較小為5 MB，控制3個(gè)交換機(jī)。Subdomain2中控制器2的剩余處理容量較大為10 MB，僅控制2個(gè)交換機(jī)，則1和2處于負(fù)載不均衡狀態(tài)。因此，在多控制器部署架構(gòu)下所要解決的問題是，對(duì)于給定網(wǎng)絡(luò)拓?fù)洌跀?shù)據(jù)平面交換機(jī)連接已知，并且控制平面控制器狀態(tài)確定的情況下，如何配屬交換機(jī)和控制器的連接關(guān)系來構(gòu)建合理的分布式SDN子域，從而實(shí)現(xiàn)多控制器負(fù)載均衡。

圖1 交換機(jī)和控制器部署失衡狀態(tài)

3.2 網(wǎng)絡(luò)建模和參數(shù)設(shè)定

SDN多控制器架構(gòu)的核心思想是邏輯上集中但物理上分布，整個(gè)網(wǎng)絡(luò)被劃分為多個(gè)分布式子域，同時(shí)每個(gè)子域由特定的控制器進(jìn)行集中式控制。交換機(jī)通過向控制器發(fā)送Packet-in消息實(shí)現(xiàn)路由信息的查詢與獲取。本文將OpenFlow架構(gòu)下流量傳輸抽象為請(qǐng)求與服務(wù)的排隊(duì)過程?？紤]到現(xiàn)有的OpenFlow交換機(jī)均為多核交換機(jī)，支持多端口多VLAN背板上數(shù)據(jù)的并行處理[19]。同時(shí)，ONOS，OpenDaylight等主流控制器均采用多線程處理方式。因此，交換機(jī)和控制器之間的通信過程可以抽象為G/M/轉(zhuǎn)發(fā)隊(duì)列模型，其中，G表示交換機(jī)的Packet-in消息到達(dá)是一般過程，M為控制器對(duì)于流請(qǐng)求的處理是馬爾可夫型，控制器當(dāng)前線程數(shù)，表明控制器有能力同時(shí)連接多個(gè)交換機(jī)。當(dāng)交換機(jī)流請(qǐng)求到來時(shí)，控制器會(huì)在可用的線程空間內(nèi)對(duì)Packet-in消息進(jìn)行并行處理?；谠撏ㄐ拍Ｐ停瑢?duì)網(wǎng)絡(luò)中相關(guān)參數(shù)進(jìn)行計(jì)算，包括交換機(jī)到控制器的平均時(shí)延、控制器流量負(fù)載和控制器負(fù)載均衡。

1) 交換機(jī)到控制器的平均時(shí)延

因此，交換機(jī)到控制器的平均時(shí)延為

2) 控制器流量負(fù)載

3) 控制器負(fù)載均衡

目標(biāo)函數(shù)：

式(10)對(duì)網(wǎng)絡(luò)中所有設(shè)備的連接關(guān)系進(jìn)行限定。式(11)確保網(wǎng)絡(luò)中沒有控制器出現(xiàn)過載狀況。式(12)表示在給定時(shí)間內(nèi)所有交換機(jī)都能精確連接到主控制器。

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

4.1 匹配機(jī)制

匹配機(jī)制的總體思路是，對(duì)于給定的網(wǎng)絡(luò)拓?fù)?，通過構(gòu)建相應(yīng)設(shè)備的匹配列表，實(shí)現(xiàn)交換機(jī)和控制器的雙向匹配。

由于設(shè)備性質(zhì)不同，因此交換機(jī)和控制器在選擇匹配對(duì)象時(shí)考慮不同的約束條件。

交換機(jī)目標(biāo)。交換機(jī)更愿意選擇具有大處理容量的控制器，以避免在數(shù)據(jù)分組傳輸過程中產(chǎn)生流請(qǐng)求擁塞。交換機(jī)匹配列表定義如下。

圖2 交換機(jī)和控制器實(shí)施雙向匹配

因此，交換機(jī)和控制器完成雙向匹配需要滿足以下條件。

4.2 MCDD算法

算法1 多控制器動(dòng)態(tài)部署（MCDD）

控制器冗余因子β

輸出 交換機(jī)和控制器連接關(guān)系()

15) end if

17) end while

20) end while

23) end if

4.3 算法可行性證明

4.3.1 穩(wěn)定的連接關(guān)系

首先，證明通過算法1可以產(chǎn)生一個(gè)穩(wěn)定的連接關(guān)系。

綜上，整個(gè)匹配進(jìn)程將不會(huì)遺漏任何交換機(jī)和控制器，二者之間連接是穩(wěn)定且可靠的，因此，原命題得到證明。

4.3.2 算法優(yōu)化性能分析

為了驗(yàn)證MCDD算法的可行性，下面進(jìn)行數(shù)學(xué)推導(dǎo)論證，同理想情況下的最優(yōu)解進(jìn)行對(duì)比分析。

理想狀態(tài)下，當(dāng)輸入請(qǐng)求在所有交換機(jī)中都是等值分布時(shí)，此時(shí)控制器負(fù)載最小，如式(16)所示。

下面，計(jì)算MCDD算法同理想狀態(tài)（如式(16)所示）的差距。

因此，MCDD算法與理想狀況的性能比值為

5 仿真分析

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

關(guān)于仿真環(huán)境和實(shí)驗(yàn)參數(shù)，本文做出如下說明。

1) 實(shí)驗(yàn)平臺(tái)

在控制器選取方面，本文采用OpenDaylight作為實(shí)驗(yàn)控制器，同時(shí)在斯坦福大學(xué)研發(fā)的Mininet平臺(tái)上進(jìn)行測(cè)試。OpenDaylight控制器基于Java語言編寫，運(yùn)行于JVM 上，支持多種版本的OpenFlow協(xié)議。為了保證實(shí)驗(yàn)效率，將Mininet和OpenDaylight以虛擬機(jī)的形式部署在2個(gè)不同的物理設(shè)備。實(shí)驗(yàn)機(jī)器的配置為Intel Corei7 3.4 GHz 8 GB RAM，并配屬一個(gè)2 Gbit/s的網(wǎng)卡。

2) 拓?fù)溥x擇和算法實(shí)現(xiàn)

實(shí)驗(yàn)拓?fù)洳捎镁哂休^高認(rèn)可度的Internet2 OS3E網(wǎng)絡(luò)拓?fù)洹S3E拓?fù)淇偣舶?4個(gè)節(jié)點(diǎn)和42條鏈路，網(wǎng)絡(luò)中所有節(jié)點(diǎn)都具備部署交換機(jī)或控制器的能力，且各節(jié)點(diǎn)之間的統(tǒng)計(jì)相互獨(dú)立。本文算法采用Java語言在OpenDaylight應(yīng)用層進(jìn)行實(shí)現(xiàn)，并借助Matlab工具對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析。

3) 仿真參數(shù)設(shè)定

5.2 仿真驗(yàn)證與分析

為了驗(yàn)證MCDD算法的控制器負(fù)載均衡性能，在這里同文獻(xiàn)[9]中-means控制器均衡部署算法和文獻(xiàn)[15]中控制器彈性控制方法（ECA, elastic control approach）進(jìn)行對(duì)比。-means方法依據(jù)距離原則對(duì)節(jié)點(diǎn)進(jìn)行聚類操作，選取聚類中心作為控制器部署點(diǎn)，通過聚類分割均衡控制器負(fù)載。ECA將交換機(jī)動(dòng)態(tài)分配作為算法核心，按照負(fù)載自適應(yīng)方式選取交換機(jī)實(shí)施遷移，從而調(diào)整控制器負(fù)載分布。

5.2.1 實(shí)驗(yàn)1

本實(shí)驗(yàn)主要驗(yàn)證不同算法在SDN子域規(guī)劃方面性能。子域規(guī)劃作為判定控制器負(fù)載均衡的重要指標(biāo)，在SDN中，控制器管理的交換機(jī)數(shù)量越均衡，則子域規(guī)劃越合理，控制器負(fù)載均衡性能越好?；贠S3E網(wǎng)絡(luò)拓?fù)?，類比文獻(xiàn)[7]中拓?fù)湓O(shè)定，在整個(gè)網(wǎng)絡(luò)中共部署5個(gè)具有相同條件的控制器，但交換機(jī)與控制器之間的匹配關(guān)系并未確定，對(duì)比3種算法在交換機(jī)分配和子域規(guī)劃方面的性能，實(shí)驗(yàn)結(jié)果如圖3所示。從宏觀拓?fù)浣嵌冗M(jìn)行分析，-means對(duì)于子域的規(guī)劃效果不夠理想，各子域中交換機(jī)數(shù)量差異較大。ECA和MCDD雖然都能夠?qū)崿F(xiàn)交換機(jī)在各子域的均衡部署，但ECA中存在跨域節(jié)點(diǎn)，會(huì)導(dǎo)致嚴(yán)重的跨域通信問題。

為了更加清楚地對(duì)比不同算法的子域規(guī)劃效果，對(duì)圖3中實(shí)驗(yàn)數(shù)據(jù)進(jìn)行統(tǒng)計(jì)匯總與分析，結(jié)果如圖4所示。在相同的控制器部署條件下，-means中控制器管理的交換機(jī)個(gè)數(shù)相差最大，其中，控制器1管理的交換機(jī)數(shù)量是控制器2和4結(jié)果的2倍。這是因?yàn)?means在規(guī)劃過程中，只根據(jù)設(shè)備間距離進(jìn)行節(jié)點(diǎn)聚合，當(dāng)節(jié)點(diǎn)間距離差異較大時(shí)，聚類操作容易陷入局部最優(yōu)，造成交換機(jī)區(qū)域性聚集，子域規(guī)劃效果差。ECA和MCDD都較好地實(shí)現(xiàn)了交換機(jī)和控制器的均衡連接。但由于ECA在動(dòng)態(tài)分配時(shí)，將交換機(jī)分配給剩余處理容量最大的控制器，雖然可以在一定程度上均衡控制器負(fù)載，但忽略了子域間節(jié)點(diǎn)連通性，在交換機(jī)和控制器之間產(chǎn)生跨域通信問題。相比較而言，MCDD從交換機(jī)和控制器2個(gè)角度進(jìn)行分析，基于模擬退火算法對(duì)雙向匹配關(guān)系進(jìn)行優(yōu)化，保證了子域規(guī)劃的合理性，同時(shí)控制器匹配列表考慮設(shè)備間距離、流請(qǐng)求速率和交換機(jī)歷史流量信息，避免了僅考慮單一網(wǎng)絡(luò)度量產(chǎn)生的節(jié)點(diǎn)孤立和跨域交互問題。根據(jù)交換機(jī)部署數(shù)量標(biāo)準(zhǔn)差對(duì)分布式子域的節(jié)點(diǎn)均衡率進(jìn)行量化，經(jīng)過歸一化處理后，MCDD的節(jié)點(diǎn)均衡率達(dá)到了0.872，相較于-means（節(jié)點(diǎn)均衡率0.517）和ECA（節(jié)點(diǎn)均衡率0.743），具有明顯的部署優(yōu)勢(shì)。

圖3 OS3E網(wǎng)絡(luò)子域規(guī)劃結(jié)果

圖4 3種算法得到的交換機(jī)部署結(jié)果對(duì)比

5.2.2 實(shí)驗(yàn)2

在實(shí)驗(yàn)1拓?fù)湟?guī)劃的基礎(chǔ)上，本實(shí)驗(yàn)對(duì)于3種算法的流請(qǐng)求排隊(duì)時(shí)延進(jìn)行評(píng)估。假設(shè)數(shù)據(jù)分組在光纖電纜中傳輸時(shí)，傳輸速率可靠穩(wěn)定，無分組丟失現(xiàn)象。為了消除實(shí)驗(yàn)隨機(jī)誤差，3種算法均在相同的實(shí)驗(yàn)條件下運(yùn)行30次，記錄仿真數(shù)據(jù)，以測(cè)量平均值作為實(shí)驗(yàn)結(jié)果，如圖5所示。

圖5中Subdomain1~Subdomain5分別表示控制器1~5所在的SDN子域。從整體來看，-means中各子域的流請(qǐng)求排隊(duì)時(shí)延較高；ECA在Subdomain2的流請(qǐng)求排隊(duì)時(shí)延達(dá)到了近45 ms，而在其他子域的排隊(duì)時(shí)延基本上都小于20 ms；MCDD各子域的流請(qǐng)求排隊(duì)時(shí)延相差不大，且均處于較低值（最大時(shí)延23 ms）。這是因?yàn)?means方案雖然優(yōu)化了控制器的位置選擇，但對(duì)子域內(nèi)交換機(jī)數(shù)量缺乏規(guī)劃，在控制器處理性能相同的條件下，交換機(jī)的過量部署會(huì)導(dǎo)致子域中流請(qǐng)求處于高排隊(duì)時(shí)延狀態(tài)。ECA作為一種彈性控制方式，雖然能夠快速轉(zhuǎn)地移控制器負(fù)載，保證控制器高處理性能，但很容易在交換機(jī)遷移過程中產(chǎn)生跨域通信問題，網(wǎng)絡(luò)狀態(tài)的不穩(wěn)定反而導(dǎo)致流請(qǐng)求排隊(duì)時(shí)延急劇增加。MCDD對(duì)交換機(jī)和控制器進(jìn)行雙向匹配，考慮流請(qǐng)求速率和跳數(shù)因素，使交換機(jī)自適應(yīng)地連接剩余處理容量最大的控制器，流請(qǐng)求被快速處理，各子域排隊(duì)時(shí)延較低。

圖5 3種算法得到的流請(qǐng)求排隊(duì)時(shí)延對(duì)比

5.2.3 實(shí)驗(yàn)3

本實(shí)驗(yàn)對(duì)比3種算法在不同流請(qǐng)求狀況下控制器負(fù)載均衡率及相應(yīng)的網(wǎng)絡(luò)開銷變化情況。同樣基于OS3E網(wǎng)絡(luò)拓?fù)?，利用流量生成器在交換機(jī)中產(chǎn)生持續(xù)不斷的流請(qǐng)求，如圖6所示。整個(gè)過程可以劃分為2個(gè)階段。階段1（0~6 h）：所有交換機(jī)的流請(qǐng)求速率均小于200 kB/s，流量分布具有自相似性。階段2（7~12 h）：在交換機(jī)中產(chǎn)生大量流請(qǐng)求，模擬流量突發(fā)狀況，直至網(wǎng)絡(luò)中所有交換機(jī)的流請(qǐng)求速率均達(dá)到峰值。經(jīng)過多次重復(fù)實(shí)驗(yàn)，記錄實(shí)驗(yàn)數(shù)據(jù)。參考仿真參數(shù)設(shè)定，以各控制器經(jīng)過歸一化處理后的負(fù)載標(biāo)準(zhǔn)差作為依據(jù)，計(jì)算控制器負(fù)載均衡率，并且得到3種算法在均衡控制器負(fù)載過程中產(chǎn)生的轉(zhuǎn)發(fā)開銷P和狀態(tài)同步開銷P。實(shí)驗(yàn)結(jié)果如圖7~圖9所示。

圖6 OS3E網(wǎng)絡(luò)交換機(jī)流請(qǐng)求速率

在圖7中，當(dāng)所有交換機(jī)的流請(qǐng)求速率都較低且具有自相似特性時(shí)（0~6 h），3種算法的控制器負(fù)載均衡率基本保持平穩(wěn)狀態(tài)，其中，MCDD的控制器負(fù)載均衡率最高，-means次之，ECA最低。這說明MCDD通過雙向匹配可以有效實(shí)現(xiàn)穩(wěn)定網(wǎng)絡(luò)狀態(tài)下交換機(jī)和控制器之間的合理連接，保證了控制器負(fù)載的均衡分布。雖然-means根據(jù)節(jié)點(diǎn)間距離最短原則進(jìn)行聚類劃分，已經(jīng)具有一定的均衡效果，但它僅考慮控制器如何部署而忽略了交換機(jī)的合理配置，對(duì)于控制器負(fù)載均衡率的提升仍然不夠顯著。ECA的負(fù)載自適應(yīng)調(diào)節(jié)方式在低流請(qǐng)求速率狀況下難以體現(xiàn)出動(dòng)態(tài)調(diào)整的優(yōu)勢(shì)，控制器負(fù)載均衡率較低。當(dāng)網(wǎng)絡(luò)中交換機(jī)逐漸出現(xiàn)流量突發(fā)狀況時(shí)（7~10 h），部分控制器出現(xiàn)負(fù)載溢出。-means基于聚類分割得到的單個(gè)網(wǎng)絡(luò)子域規(guī)模較小，僅能預(yù)防少數(shù)流請(qǐng)求突發(fā)狀況，一旦突發(fā)流數(shù)量增長(zhǎng)過快，控制器負(fù)載狀況更加惡化，負(fù)載均衡率快速下降。雖然ECA通過遷移交換機(jī)能有效消除控制器過載問題，但無法實(shí)現(xiàn)控制器負(fù)載的細(xì)粒度調(diào)整，整體效果優(yōu)于-means，和MCDD相比仍然較差。MCDD在實(shí)施雙向匹配連接時(shí)就已經(jīng)預(yù)先設(shè)置冗余因子和轉(zhuǎn)發(fā)因子，保證控制器預(yù)留出部分冗余容量處理突發(fā)流請(qǐng)求，同時(shí)，根據(jù)交換機(jī)轉(zhuǎn)發(fā)數(shù)據(jù)分組的歷史信息，將有流請(qǐng)求突發(fā)傾向的交換機(jī)預(yù)先連接至具有較大剩余處理容量的控制器。因此，MCDD能夠有效應(yīng)對(duì)較多數(shù)量的突發(fā)流請(qǐng)求，將控制器負(fù)載均衡率維持在較高水平，相比于其他2種算法，控制器負(fù)載均衡率至少提高了17.9%。當(dāng)所有交換機(jī)都產(chǎn)生流量突發(fā)問題時(shí)（11~12 h），3種算法全部失效，盡管此時(shí)負(fù)載均衡率接近1，但控制器均處于高負(fù)載狀態(tài)，網(wǎng)絡(luò)發(fā)生癱瘓，必須增加新控制器或提高控制器性能來改善網(wǎng)絡(luò)通信質(zhì)量。

圖7 控制器負(fù)載均衡率

在圖8和圖9中分別顯示了3種算法的轉(zhuǎn)發(fā)開銷和狀態(tài)同步開銷對(duì)比情況。在流量自相似狀況下，網(wǎng)絡(luò)狀態(tài)相對(duì)穩(wěn)定，無過載控制器產(chǎn)生，因此，3種算法的狀態(tài)同步開銷相差不大。由于MCDD中控制器需要收集交換機(jī)的歷史轉(zhuǎn)發(fā)信息，所以轉(zhuǎn)發(fā)開銷略高于-means和ECA。當(dāng)網(wǎng)絡(luò)中出現(xiàn)流量突發(fā)狀況時(shí)，轉(zhuǎn)發(fā)開銷和狀態(tài)同步開銷都有所上升。ECA的2類開銷上升幅度最大，這是因?yàn)榻粨Q機(jī)遷移需要在網(wǎng)絡(luò)中交互和同步大量設(shè)備狀態(tài)信息。MCDD和-means都采用先驗(yàn)式網(wǎng)絡(luò)構(gòu)建方式，子域中交換機(jī)和控制器連接關(guān)系基本保持穩(wěn)定，當(dāng)流請(qǐng)求速率增加時(shí)，轉(zhuǎn)發(fā)開銷和狀態(tài)同步開銷也會(huì)有所提高，但與ECA相比，仍處于較低水平。

圖8 轉(zhuǎn)發(fā)開銷

圖9 狀態(tài)同步開銷

綜合比較圖7~圖9的實(shí)驗(yàn)結(jié)果可以得出，相比于-means和ECA，MCDD具有較好的控制器負(fù)載均衡性能，并且在應(yīng)對(duì)網(wǎng)絡(luò)中流量突發(fā)狀況時(shí)，產(chǎn)生的轉(zhuǎn)發(fā)開銷和狀態(tài)同步開銷均在可接受范圍之內(nèi)。

6 結(jié)束語

本文針對(duì)分布式軟件定義網(wǎng)絡(luò)中存在的多控制器負(fù)載不均衡問題，提出了一種基于雙向匹配的多控制器動(dòng)態(tài)部署算法。通過對(duì)SDN多控制器網(wǎng)絡(luò)實(shí)施建模，分析時(shí)延和控制流量對(duì)于控制器負(fù)載均衡性能的影響，并分別構(gòu)建交換機(jī)和控制器的匹配列表。根據(jù)設(shè)定的匹配規(guī)則選擇列表中元素進(jìn)行雙向匹配，借助模擬退火算法提升匹配效率，優(yōu)化了網(wǎng)絡(luò)中設(shè)備間連接關(guān)系，實(shí)現(xiàn)多控制器的動(dòng)態(tài)部署。通過數(shù)學(xué)推導(dǎo)與分析，論證了算法可行性。同時(shí)，基于多種評(píng)估度量，設(shè)置一系列的仿真對(duì)比實(shí)驗(yàn)，結(jié)果表明，MCDD算法在子域規(guī)劃，流請(qǐng)求排隊(duì)時(shí)延和控制器負(fù)載均衡率方面相比其他算法具有明顯優(yōu)勢(shì)。未來的研究工作將圍繞以下2個(gè)方面內(nèi)容展開：1) 在進(jìn)行多控制器部署時(shí)，加入鏈路失效和交換機(jī)失效模型；2) 將時(shí)延問題進(jìn)一步拓展到交換機(jī)間時(shí)延和控制器間時(shí)延，實(shí)施多目標(biāo)優(yōu)化。

[1] 左青云, 陳鳴, 趙廣松, 等. 基于OpenFlow的SDN技術(shù)研究[J]. 軟件學(xué)報(bào), 2013, 24(5): 1078-1097.

ZUO Q Y, CHEN M, ZHAO G S, et al. Research on OpenFlow-based SDN technologies[J]. Journal of Software, 2013, 24(5): 1078-1097.

[2] MCKEOWN N, ANDERSON T, BALAKRISHAN H, et al. OpenFlow: enabling innovation in campus network[J]. ACM SIGCOMM Computer Communication Review, 2008, 38(2): 69-74.

[3] FARES M A, RADHAKRISHNAN S, et al. Hedera: dynamic flow scheduling for data center networks[C]//USENIX NSDI. 2010: 71-78.

[4] TOOTOONCHIAN A, GORBUNOV S, GANJALI Y, et al. On controller performance in software-defined networks[C]//USENIX HotICE. 2012: 1-6.

[5] TOOTOONCHIAN A, GANJALI Y. Hyperflow: a distributed control plane for OpenFlow[C]//2010 Internet Network Management Conference on Research on Enterprise Networking. 2010.

[6] HASSAS Y S. Kandoo: a framework for efficient and scalable offloading of control applications[C]//First Workshop on Hot Topics in Software Defined Networks. ACM, 2012: 19-24.

[7] HELLER B, SHERWOOD R, MCKEOWN N. The controller placement problem[C]//First Workshop on Hot Topics in Software Defined Networks. 2012: 7-12.

[8] HOCK D, GEBERT S, HARTMANN M, et al. POCO-framework for Pareto-optimal resilient controller placement in SDN-based core networks[C]//Network Operations and Management Symposium (NOMS). 2014: 1-2.

[9] WANG G, ZHAO Y, HUANG J, et al. A-means-based network partition algorithm for controller placement in software defined network[C]//IEEE International Conference on Communications (ICC). 2016: 1-6.

[10] KSENTINI A, BAGAA M, TALEB T. On using bargaining game for optimal placement of SDN controllers[C]//2016 IEEE International Conference on Communications (ICC). 2016: 1-6.

[11] OBADIA M, BOUET M, ROUGIER J L. A greedy approach for minimizing SDN control overhead[C]//The 2015 1st IEEE Conference on Network Softwarization (NetSoft). 2015: 1-5.

[12] YU M, REXFORD J, FREEDMAN M J, et al. Scalable flow-based networking with DIFANE[C]//In Proc ACM SIGCOMM, 2010: 1-6.

[13] CURTIS A R, MOGUL J C, TOURRILHES J, et al. DevoFlow: scaling flow management for highperformance networks[C]//SIGCOMM Toronto. 2011: 254-265.

[14] ZHANG H L, GUO X. SDN-based load balancing strategy for server cluster[C]//2014 IEEE 3rd International Conference on Cloud Computing and Intelligence Systems. 2014: 662-667.

[15] CHEN H C, CHENG G Z, WANG Z M. A game-theoretic approach to elastic control in software-defined networking[J]. China Communication, 2016 (5):103-109.

[16] MüLLER L F, OLIVEIRA R R. Survivor: an enhanced controller placement strategy for improving SDN survivability[C]//2014 IEEE Global Communications Conference. 2014:1909-1915.

[17] ROTH A E, SOTOMAYOR M A O. Two-sided matching: a study in game-theoretic modeling and analysis[M]. Cambrideg: Cambridge University Press,1992.

[18] VAUGHAN J, STOEV S. Network-wide statistical modeling, prediction, and monitoring of computer traffic[J]. Technometrics, 2013, 55(1): 79-93.

[19] OGASAWARA S, TAKAHASHI Y. Performance analysis of traffic classification in an OpenFlow switch[C]//2016 Cloudification of the Internet of Things (CIoT). 2016: 1-6.

[20] GARCíA-MARTíNEZ C, LOZANO M, RODRíGUEZ-DíAZ F J. A simulated annealing method based on a specialised evolutionary algorithm[J]. Applied Soft Computing Journal, 2012, 12(12): 573-588.

Dynamic deployment algorithm for multi-controllers based on bidirectional matching in software defined networking

HU Tao, ZHANG Jianhui, KONG Weigong, YANG Sen, CAO Lujia

National Digital Switching System Engineering R&D Center, Zhengzhou 450002, China

Aiming at the controller load imbalance problem in distributed SDN, a multi-controller dynamic deployment algorithm based on bidirectional matching was proposed. Through collecting hop counts, delay and flow information in the network periodically, match lists of switch and controller was built respectively. According to the principle of optimal queuing, switches and controllers were selected from two match lists for implementing bidirectional matching, and the relationship of matching with the help of simulated annealing algorithm was optimized, which achieved dynamic deployment for multi-controller in distributed network. Results show that, compared with the existing approaches, this algorithm can match the connections between switches and controllers reasonably, and reduce the queue delay of flow request effectively. Moreover, and the controller load balancing rate has increased by 17.9% at least.

software defined network, controller, load balancing, bidirectional matching

TP393

A

10.11959/j.issn.1000-436x.2018015

胡濤（1993-），男，陜西武功人，國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心碩士生，主要研究方向?yàn)閷拵畔⒕W(wǎng)、軟件定義網(wǎng)絡(luò)。

張建輝（1977-），男，河南平頂山人，國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心副研究員，主要研究方向?yàn)閷拵畔⒕W(wǎng)、網(wǎng)絡(luò)安全。

孔維功（1980-），男，河南封丘人，國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心博士生，主要研究方向?yàn)閷拵畔⒕W(wǎng)。

楊森（1985-），男，遼寧蓋州人，國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心助理研究員，主要研究方向?yàn)橥ㄐ排c信息網(wǎng)絡(luò)。

曹路佳（1983-），男，河北撫寧人，國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心助教，主要研究方向?yàn)榫W(wǎng)絡(luò)安全。

2017-02-13；

2017-06-12

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61521003, No.61372121）；國(guó)家科技支撐計(jì)劃基金資助項(xiàng)目（No.2014BAH30B01）；國(guó)家高技術(shù)研究發(fā)展計(jì)劃（“863”計(jì)劃）基金資助項(xiàng)目（No.2015AA016102）；河南省科技攻關(guān)計(jì)劃基金資助項(xiàng)目（No.162102210034）

: The National Natural Science Foundation of China (No.61521003, No.61372121), The National Key Technology R&D Program (No.2014BAH30B01), The National High Technology Research and Development Program of China (863 Program) (No.2015AA016102), The Key Scientific and Technological Project of Henan Province (No.162102210034)