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

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

?

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

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

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

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

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

1 引言

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

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

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

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

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

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

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

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

2 相關工作

近年來，控制器負載均衡作為SDN領域的研究熱點，研究人員分別從控制器和交換機2個角度開展相關研究。

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

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

3 模型構建

3.1 問題重述

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

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

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

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

1) 交換機到控制器的平均時延

因此，交換機到控制器的平均時延為

2) 控制器流量負載

3) 控制器負載均衡

目標函數(shù)：

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

4 算法設計

4.1 匹配機制

匹配機制的總體思路是，對于給定的網(wǎng)絡拓撲，通過構建相應設備的匹配列表，實現(xiàn)交換機和控制器的雙向匹配。

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

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

圖2 交換機和控制器實施雙向匹配

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

4.2 MCDD算法

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

控制器冗余因子β

輸出 交換機和控制器連接關系()

15) end if

17) end while

20) end while

23) end if

4.3 算法可行性證明

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

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

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

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

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

理想狀態(tài)下，當輸入請求在所有交換機中都是等值分布時，此時控制器負載最小，如式(16)所示。

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

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

5 仿真分析

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

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

1) 實驗平臺

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

2) 拓撲選擇和算法實現(xiàn)

實驗拓撲采用具有較高認可度的Internet2 OS3E網(wǎng)絡拓撲。OS3E拓撲總共包含34個節(jié)點和42條鏈路，網(wǎng)絡中所有節(jié)點都具備部署交換機或控制器的能力，且各節(jié)點之間的統(tǒng)計相互獨立。本文算法采用Java語言在OpenDaylight應用層進行實現(xiàn)，并借助Matlab工具對實驗結果進行分析。

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

5.2 仿真驗證與分析

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

5.2.1 實驗1

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

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

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

圖4 3種算法得到的交換機部署結果對比

5.2.2 實驗2

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

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

圖5 3種算法得到的流請求排隊時延對比

5.2.3 實驗3

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

圖6 OS3E網(wǎng)絡交換機流請求速率

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

圖7 控制器負載均衡率

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

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

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

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

6 結束語

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

[1] 左青云, 陳鳴, 趙廣松, 等. 基于OpenFlow的SDN技術研究[J]. 軟件學報, 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-），男，陜西武功人，國家數(shù)字交換系統(tǒng)工程技術研究中心碩士生，主要研究方向為寬帶信息網(wǎng)、軟件定義網(wǎng)絡。

張建輝（1977-），男，河南平頂山人，國家數(shù)字交換系統(tǒng)工程技術研究中心副研究員，主要研究方向為寬帶信息網(wǎng)、網(wǎng)絡安全。

孔維功（1980-），男，河南封丘人，國家數(shù)字交換系統(tǒng)工程技術研究中心博士生，主要研究方向為寬帶信息網(wǎng)。

楊森（1985-），男，遼寧蓋州人，國家數(shù)字交換系統(tǒng)工程技術研究中心助理研究員，主要研究方向為通信與信息網(wǎng)絡。

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

2017-02-13；

2017-06-12

國家自然科學基金資助項目（No.61521003, No.61372121）；國家科技支撐計劃基金資助項目（No.2014BAH30B01）；國家高技術研究發(fā)展計劃（“863”計劃）基金資助項目（No.2015AA016102）；河南省科技攻關計劃基金資助項目（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)