一種軟件定義網(wǎng)絡(luò)中的控制器熱備份及選舉算法

王文博，汪斌強(qiáng)，陳飛宇，王志明，宮陽陽

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

一種軟件定義網(wǎng)絡(luò)中的控制器熱備份及選舉算法

王文博，汪斌強(qiáng)，陳飛宇，王志明，宮陽陽

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

多控制器軟件定義網(wǎng)絡(luò)中交換機(jī)遷移策略計算空間大、考慮因素單一且無法立刻遷移出故障域內(nèi)交換機(jī).對此，本文將原交換機(jī)遷移問題優(yōu)化成為控制器的熱備份及選舉問題（Controller Hot Backup and Election Problem，CHBE Problem），對控制器進(jìn)行熱備份，并設(shè)計相應(yīng)的備份空間確定算法和主控制器選舉算法，通過權(quán)衡信息交互、失聯(lián)性、負(fù)載失衡和跨域通信四種代價實現(xiàn)合理的網(wǎng)絡(luò)構(gòu)建.實驗結(jié)果表明，與現(xiàn)有算法相比，負(fù)載均衡程度和跨域通信問題改善明顯，備份空間平均縮小了65%；在OS3E拓?fù)渲屑訖?quán)后的綜合評價最高提升了71%.

軟件定義網(wǎng)絡(luò)；多控制器；熱備份；控制器選舉；故障恢復(fù)

1 引言

目前，新型網(wǎng)絡(luò)體系結(jié)構(gòu)，如智慧協(xié)同網(wǎng)絡(luò)［1］，可重構(gòu)網(wǎng)絡(luò)［2］，軟件定義網(wǎng)絡(luò)，為解決傳統(tǒng)網(wǎng)絡(luò)的僵化問題提供了新的方案.其中，軟件定義網(wǎng)絡(luò)由于其易管理、可編程的特點，受到了廣泛關(guān)注.近年來，隨著業(yè)務(wù)需求和網(wǎng)絡(luò)規(guī)模的不斷增大，軟件定義網(wǎng)絡(luò)控制平面的擴(kuò)展性受到巨大挑戰(zhàn)［3，4］.其中，一個重要方面就是由于多控制器架構(gòu)“命運(yùn)共享”（fate sharing）所帶來的控制平面的脆弱性.

針對該問題的解決方法大致能夠分為兩類.第1類方法通過靜態(tài)布置控制器位置增強(qiáng)控制平面的可靠性［5～9］.這類方法單純改變節(jié)點分布，無法對網(wǎng)絡(luò)動態(tài)調(diào)節(jié)，使網(wǎng)絡(luò)處于一種“啞”的，“無法移動”的狀態(tài).第2類方法在控制器布局確定之后，通過遷移故障域或負(fù)載域內(nèi)的交換機(jī)，對網(wǎng)絡(luò)進(jìn)行彈性管控［10］.這類方法雖然能動態(tài)調(diào)整網(wǎng)絡(luò)，但往往考慮單一，僅關(guān)注片面的遷移代價［9～12］.導(dǎo)致遷移后某單一方面性能突出，其他方面性能較差.并且每一次完成遷移都需要對整個控制器集合進(jìn)行重新計算，復(fù)雜度高、時延較大，極易造成通信的不一致性.

針對上述問題，本文在動態(tài)調(diào)整的基礎(chǔ)上，提出一種對控制器進(jìn)行熱備份的遷移方法.先借助openflow1.4協(xié)議［13］定義了交換機(jī)的控制器備份空間，將原交換機(jī)遷移問題優(yōu)化成為控制器的熱備份及其相應(yīng)的master控制器選舉問題（Controller Hot Backup and Election Problem，CHBE Problem）.針對之前的遷移策略考慮因素單一，對信息交互代價、失聯(lián)性代價、負(fù)載失衡代價和跨域通信代價等四種代價進(jìn)行了描述.設(shè)計了兩個算法，分別確定控制器備份空間和完成主控制器選舉，使交換機(jī)每次遷移時的計算空間從整個控制器集合縮小到了控制器備份空間.就目前的文獻(xiàn)調(diào)查情況分析，通過為控制器找尋備份空間來實現(xiàn)遷移是一種新的嘗試，為遷移策略的實現(xiàn)和設(shè)計提供了新的數(shù)學(xué)模型和思路.

2 相關(guān)研究

國內(nèi)外許多學(xué)者都對第1類方法給予了關(guān)注.文獻(xiàn)［5］定義了控制平面的可靠性并提出基于貪心算法的控制器布局算法；文獻(xiàn)［6］在研究可靠性的基礎(chǔ)上，關(guān)注了控制器個數(shù)的約束條件.此外，還有針對負(fù)載均衡的CCP布局方法［7］；針對故障恢復(fù)的FTCP布局方法［8］和針對多種因素的帕累托優(yōu)化布局方法［9］等等.上述布局方式雖然對改善控制平面的脆弱性意義重大，但是仍然無法從根本上解決“命運(yùn)共享”帶來的失效問題.

針對第1類方法中存在的問題，openflow1.4協(xié)議描述了一種動態(tài)調(diào)整的典型情況：每個交換機(jī)除了連接一個master控制器，還連接多個其余控制器作為slave控制器.當(dāng)該控制器發(fā)生故障或其域內(nèi)交換機(jī)在某時刻流請求激增時，需要對該域內(nèi)交換機(jī)實現(xiàn)向外遷移.文獻(xiàn)［9］將距離和時延作為遷移的首要衡量因素；ElastiCon［10］從彈性控制出發(fā)衡量了遷移前后負(fù)載均衡程度的改善；DCPP［11］通過添加監(jiān)視模塊，根據(jù)流量的實時變化對交換機(jī)進(jìn)行動態(tài)調(diào)整.這類動態(tài)調(diào)整策略極大的改善了第1類方法的固有缺陷，保證了網(wǎng)絡(luò)的通信暢通.但是遷移代價衡量單一，計算復(fù)雜度高、時延較大，難以滿足大型網(wǎng)絡(luò)的需要.

3 CHBE的建模與算法描述

本節(jié)對交換機(jī)遷移問題進(jìn)行了重述和建模，定義了備份空間和備份隸屬矩陣，將原問題建模成為一個考慮多種代價的整數(shù)規(guī)劃問題，繼而給出了相應(yīng)的CHBE算法并對其進(jìn)行了描述.

3.1問題的重述和建模

多控制器布局完成后，本文將此場景描述為openflow1.4協(xié)議中提出的，一個 master控制器、多個 slave控制器的應(yīng)用場景.

如圖1（a）所示，假設(shè)網(wǎng)絡(luò)被分為多個域，每個域內(nèi)均部署一個控制器.以s4為例（圖1（b）），若s4的備份控制器空間為（c1、c2、c3），當(dāng)c0發(fā)生不可逆故障或s4需要外遷時，可直接在其控制器備份空間內(nèi)完成master控制器的重新選舉.

本文所要研究的問題即是：

（1）為全網(wǎng)中的每一個openflow交換機(jī)確定備份控制器的個數(shù)及位置.

（2）控制器備份空間一旦確定，遷移時完成 master控制器的選舉.

介紹模型之前，完成兩個假設(shè)并作以說明：

假設(shè)（1） 同一時刻，最多只有一個網(wǎng)絡(luò)組件發(fā)生故障.

假設(shè)（2） 采用域內(nèi)不同組件故障相互獨(dú)立的研究模型.

本文采取了一種廣泛應(yīng)用的故障概率模型［14］，對于網(wǎng)絡(luò)內(nèi)不同組件的故障發(fā)生在統(tǒng)計學(xué)上認(rèn)為相互獨(dú)立.同時，根據(jù)文獻(xiàn)［6］，網(wǎng)絡(luò)中同時有兩個組件發(fā)生故障的概率很小，故假設(shè)同一時刻，最多只有一個網(wǎng)絡(luò)組件發(fā)生故障.

模型把網(wǎng)絡(luò)建模成為一個無向圖G=（S，E），其中S是無向圖中的節(jié)點的集合，E是邊的集合.G分成不同的域，每一個域部屬一個控制器.即G=｛D1，D2，…，Dk，…，Dn｝，且任意兩個域沒有重疊.控制器集合為V= ｛v1，v2，…，vj，…，vn｝，域Dk內(nèi)的控制器為vk.對于域Dk，域內(nèi)的openflow交換機(jī)集合為｛sk1，sk2，…，skmk｝，數(shù)量為mk個.同時定義了備份隸屬矩陣X=［xsv］|S|*|V|，當(dāng)xsv等于1時，說明控制器v為交換機(jī)s進(jìn)行備份，反之則為0.

為了解決備份控制器的布置位置和數(shù)量問題，本文考慮了以下四種代價：

（1）交換機(jī)與多控制器間的信息交互.以域Dk內(nèi)的控制器vk發(fā)生故障為例（描述其他三個代價時，此條件不變），剩余控制器集合為V*=V｛vk｝.當(dāng)用d（s，v）描述節(jié)點s和v之間的最短距離時，該域內(nèi)多控制器之間的信息交互的平均代價Ckr可以表示為：

（2）失聯(lián)性.本文認(rèn)為，當(dāng)openflow交換機(jī)再沒有可供選擇的備份控制器時，該openflow交換機(jī)失聯(lián)，即它將無法得到來自控制器的任何指示.文獻(xiàn)［12］中已經(jīng)做出了關(guān)于網(wǎng)絡(luò)穩(wěn)定性的研究工作.在這里，假設(shè)每條鏈路的故障概率為l，定義域Dk內(nèi)的openflow交換機(jī)的平均失聯(lián)性 Ckd為：

（3）負(fù)載均衡.雖然網(wǎng)絡(luò)流量時刻變化，但由于備份空間提供的是一族控制器，在考慮負(fù)載均衡時，可以用空間確定時的流量平均值，經(jīng)驗性的圈定這一族控制器的大概分布范圍.

本模型使用等概率的分配方法描述了交換機(jī)遷移為控制器帶來的負(fù)載貢獻(xiàn)，rvj表示網(wǎng)絡(luò)無故障時控制器vj所要處理的負(fù)載.本文使用其所需處理的PACKETIN消息的數(shù)量來近似的描述控制器負(fù)載［7］.rski表示域Dk中的openflow交換機(jī)ski向master控制器提出的平均流請求數(shù)，由于openflow交換機(jī)的遷移，控制器vj所需要處理的新的流請求數(shù)Rvj為：

用Lvj來表示控制器vj所能處理的流請求數(shù)的最大值，也即控制器vj的容量.此時用遷移完成之后剩余控制器容量使用率的方差來描述負(fù)載均衡代價Ckb：

（4）多域間通信.當(dāng)流經(jīng)過不同域時，交換機(jī)需要向所屬的控制器詢問路徑，將帶來由于多域產(chǎn)生的域間通信開銷［11］.用Pskivj表示openflow交換機(jī)ski到控制器vj的最短路徑中經(jīng)過的不同域所對應(yīng)控制器的集合.由此，多域間通信的平均開銷Ci可以表達(dá)為：

至此，所考慮的四種代價已經(jīng)描述完畢，式（6）中的綜合代價costk用于描述算法的性能.本模型的目標(biāo)即是使式（6）達(dá)到最小值.其中，α，β，γ，μ是用于權(quán)衡四種代價權(quán)重的常數(shù).

式（7）和式（8）是模型的約束條件.式（7）保證了備份隸屬矩陣中的元素是二進(jìn)制變量.式（8）保證了每個openflow交換機(jī)至少存在一個備份控制器.此時，即得到域Dk內(nèi)的openflow交換機(jī)的備份情況［xsv］|Dk|×|V*|.通過對整個網(wǎng)絡(luò)遍歷，將得到全網(wǎng)的備份隸屬矩陣.

3.2算法描述

本節(jié)介紹CHBE算法（CHBEA I和CBHEA II）.算法分為兩個部分：CHBEA I完成控制器備份空間確定，CHBEA II完成確定后的master控制器選舉.

CHBEAⅠ是基于模擬退火算法（Simulated Annealing）的一種啟發(fā)式算法.算法的流程主要是，每次計算一個域內(nèi)的備份隸屬矩陣，然后遍歷全網(wǎng)內(nèi)的其他域，最終將所得到的子備份隸屬矩陣進(jìn)行整合，得到優(yōu)化后的最終解（行14）.算法首先需要一個初始值作為計算的起點，在這里選擇了全1矩陣.通過隨機(jī)改變備份隸屬矩陣中的元素向最優(yōu)解進(jìn)行靠近.每次迭代時，如果新獲得的costk值向優(yōu)化目標(biāo)靠近，就接受新的備份隸屬矩陣（行7）；否則，僅以一定概率接受新的備份隸屬矩陣（行9）.當(dāng)計算完成域Dk的子備份隸屬矩陣nowk后，再計算其他域，直到得到子備份隸屬矩陣的向量｛now1，now2，…，nown｝，進(jìn)行整合（行14）.

CHBEAⅠ：

控制器備份空間確定算法

CHBEAⅡ中，首先定義了master控制器分配矩陣Y=［ysv］|S|*|V|.當(dāng)yskivj=1時，意為將控制器vj作為交換機(jī)ski的master控制器.算法二輸入算法一的結(jié)果，從交換機(jī)ski的備份控制器空間中選舉master控制器，即vj∈｛~V|?vm?~V，xskivm=1｝（行4）.在選舉過程中，由于之前確定備份空間時已經(jīng)考慮了信息交互代價和失聯(lián)性代價，這兩個指標(biāo)對于已經(jīng)選定備份空間的同一個交換機(jī)來講，在控制器的選舉上并不構(gòu)成影響因素.這里，按照式（4）和式（5）計算控制器vi作為交換機(jī)ski的master控制器的代價（行6），此時式中計算的流量值是當(dāng)時流量的真實值，并非確定備份空間時的流量數(shù)據(jù).直到找到產(chǎn)生最小代價的控制器節(jié)點vj作為master控制器.迭代的順序取決于故障域內(nèi)的交換機(jī)節(jié)點距非故障域邊緣的距離（行3）.這樣做的目的是為了盡量杜絕交換機(jī)分配時的跨域問題.每次迭代結(jié)束后，需要更新非故障域和控制器已接受的流請求數(shù)集合（行10，行11），以便進(jìn)入下一次迭代.直到將故障域中的所有交換機(jī)都分配到新的控制器上，得到最終的 master控制器分配 矩陣 ［ysv］|S|*|V|.

CHBEAⅡ：主控制器選舉算法

4 仿真分析

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

關(guān)于環(huán)境搭建和參數(shù)設(shè)置，本文做出幾點說明：

（1）關(guān)于拓?fù)涞倪x擇和控制器放置位置.本文首先使用OS3E［15］完成算法驗證，然后在 topology zoo［16］中提供的公共拓?fù)渖现匦伦隽藢嶒?在控制器的放置上，均采取文獻(xiàn)［3］中提到的平均通信開銷最小的方法.使用topology zoo進(jìn)行試驗時，本文一律按照控制器數(shù)量占交換機(jī)節(jié)點總數(shù)的17%的比例進(jìn)行布置.這樣做的原因是，當(dāng)布置過少控制器時，由于備份空間縮小帶來的計算增益將不再明顯，文獻(xiàn)［6］中提出，當(dāng)布置控制器所占交換機(jī)節(jié)點總數(shù)比例為20%左右時，帶來的控制路徑損失（control path loss）最小.

（2）交換機(jī)負(fù)載和控制器容量的設(shè)置.為了更好的搭建仿真環(huán)境，本文借鑒了文獻(xiàn)［7］中的部分設(shè)置，但是作了一些修改.平均流產(chǎn)生速率設(shè)為300K/s.由于控制器所搭載服務(wù)器存在單個和集群的差異，本文為其容量作了差異化設(shè)置，也即將 PACKET-IN消息的平均流量設(shè)為8M～11M.同時，本模型還為控制器設(shè)計了負(fù)載上限，當(dāng)控制器的負(fù)載超過這個上限時，認(rèn)為此刻已經(jīng)發(fā)生故障.在仿真的初刻，保證負(fù)載均衡和控制器完好，仿真過程中通過調(diào)節(jié)負(fù)載上限，能夠使控制器處理更多的流和消息.

（3）在綜合考慮各方面代價時，關(guān)于權(quán)重系數(shù)的說明.該權(quán)重值只是為了平衡四方面因素的影響，改變之后，各因素的相對關(guān)系變化不大.在這里，模型在對各因素進(jìn)行歸一化之后，選取了1∶1∶1∶1的比重，實際工程中，可以按照需要再作調(diào)整.同時，本文使用式（6）中的加權(quán)后的綜合代價作為算法性能的綜合評價.

4.2仿真分析

為了說明算法的性能，本文將CHBE算法與若干算法進(jìn)行了比較說明.由于該方向文獻(xiàn)較少，本文借鑒了以往研究中的控制器布置算法，將某些布置算法的思想作為控制器備份空間確定的一個因素.其中，距控制器跳數(shù)最小算法（Shortest Path Algorithm，SPA）和距離域最短算法（Nearest Domain Algorithm，NDA）參看文獻(xiàn)［9］，考慮控制器布置的負(fù)載均衡算法（Load Balancing Algorithm，LBA）在文獻(xiàn)［7］中有所提及.上述三種算法均只考慮了交換機(jī)遷移或控制器布置的單一因素，其中，SP算法是將故障域內(nèi)的交換機(jī)分配給離它最近的控制器，ND算法是將故障域內(nèi)的交換機(jī)分配給距離非故障域邊緣最近的對應(yīng)控制器，而LB算法是每次分配都選擇剩余控制器容量使用率最低的控制器.本文在具體仿真中還做了細(xì)微調(diào)整，保證了實驗場景相同.例如，將備份空間引入上述三種算法并設(shè)置為整個控制器集合.

本文首先使用了OS3E網(wǎng)絡(luò)對CHBE算法進(jìn)行了驗證.具體仿真所使用的網(wǎng)絡(luò)拓?fù)淝闆r如圖2（a）所示情況.圖2（b）、圖2（c）是分別在圖2（a）的基礎(chǔ)上運(yùn)行CHBE算法和SP算法的情況示意.可以明顯看出，CHBE算法能較好的重新布置交換機(jī)，而SP算法造成了跨域問題（圖2（c）），這將嚴(yán)重阻礙網(wǎng)絡(luò)的正常通信.

接著，研究拓展了OS3E中控制器的數(shù)量，仿真算法對各個因素的影響.實驗關(guān)注點設(shè)置為單域內(nèi)控制器發(fā)生故障（域的劃分按照距離控制器節(jié)點的遠(yuǎn)近進(jìn)行，開始時保證網(wǎng)絡(luò)負(fù)載均衡［11］），完成master控制器選舉之后的時刻.

圖3（a）和圖3（b）說明了隨著控制器數(shù)量的增加，算法為交換機(jī)找尋的備份個數(shù)的平均值和多控制器信息交互代價也相應(yīng)增加.但是相較于其他三種算法，CHBE算法選取了較小的備份空間并花費(fèi)了較少的通信代價.根本原因在于CHBE算法找到的備份空間只是整個控制器集合的一個子集.

圖3（c）～（f）分別對比了算法在失聯(lián)性、負(fù)載方差、跨域通信和綜合代價上的不同表現(xiàn)：

（1）失聯(lián)性代價和信息交互代價相互矛盾，即控制器數(shù)量越多，失聯(lián)性越小.這是由于備份空間越大，失聯(lián)的可能性越低，但是多控制器造成的通信開銷也相應(yīng)增加.

（2）在負(fù)載方差方面，控制器數(shù)量越多，負(fù)載越均衡.對比不同算法，CHBE算法僅劣于LB算法，這是由于LB算法僅考慮負(fù)載均衡，沒有其他因素的約束.

（3）由于考慮了跨域通信開銷，四種算法中僅有CHBE算法始終沒有出現(xiàn)跨域問題.整體看來，控制器布置數(shù)量越多，故障域內(nèi)的交換機(jī)個數(shù)越少，跨域問題越不明顯.LB算法的性能最差，這是由于當(dāng)流請求數(shù)占控制器容量比例不大時，LB算法為交換機(jī)提供的可選控制器空間增大.

（4）CHBE算法在個別單項因素上稍有欠缺，但是綜合評價優(yōu)于其他算法.當(dāng)k/n=0.12時（表1），CHBE算法較其他三種算法，在信息交互和跨域通信兩個方面有明顯優(yōu)勢，負(fù)載均衡性能僅次于LB算法，綜合評價最大提高了68%.當(dāng)k/n=0.088時，綜合評價提升最大，達(dá)到71%.

表1　四種算法的性能比較

最后，本文在topology zoo提供的261個公共拓?fù)渲刑暨x了27個拓?fù)渲刈鰧嶒?如圖4，橫軸是拓?fù)涿Q，縱軸是節(jié)點個數(shù).這些拓?fù)涞墓?jié)點數(shù)在60～90之間.本文在這些拓?fù)渲惺褂昧薈HBE算法進(jìn)行仿真分析，說明了算法在不同拓?fù)渖系倪m用性.實驗發(fā)現(xiàn)，CHBE算法將交換機(jī)的備份控制器數(shù)量平均縮小了65%，大大縮小了備份空間，達(dá)到了四種代價權(quán)衡下的綜合結(jié)果.

5 結(jié)論

針對多控制器軟件定義網(wǎng)絡(luò)中交換機(jī)遷移策略計算空間大、考慮因素單一且遷移時延較大等問題，本文優(yōu)化并回答了CHBE問題：（1）為全網(wǎng)中的每一個openflow交換機(jī)確定備份控制器的個數(shù)及位置；（2）控制器備份空間一旦確定，遷移時完成master控制器的重新選舉.

本文首次采用熱備份的方法完成了對交換機(jī)遷移策略的設(shè)計.將上述問題建模成一個考慮信息交互，失聯(lián)性，負(fù)載失衡和跨域通信等多種代價的整數(shù)規(guī)劃問題.通過基于模擬退火算法的CHBEAⅠ確定了控制器備份空間，通過CHBEAⅡ完成了master控制器選舉. 與SP、ND、LB算法相比，所提算法雖然在個別單項因素的考量上稍有欠缺，但在負(fù)載均衡和跨域通信兩個方面改善明顯，綜合評價最大提升了71%，并將控制器備份空間平均減小了65%.通過引入熱備份的方法，為遷移策略的實現(xiàn)和設(shè)計提供了新的數(shù)學(xué)模型和努力方向.本文關(guān)注了單個控制器故障的一般場景，多點同時故障時通過調(diào)整控制器的流請求情況、更新非故障域，CHBE算法依然能夠給出此應(yīng)用場景下的交換機(jī)遷移方法.對于更復(fù)雜的多點故障和級聯(lián)故障情景，將在下一步的工作中繼續(xù)研究.

［1］張宏科，羅洪斌.智慧協(xié)同網(wǎng)絡(luò)體系基礎(chǔ)研究［J］.電子學(xué)報，2013，41（7）：1249-1254. Zhang Hong-ke，Luo Hong-bin.Fundamental research on theories of smart and cooperative networks［J］.Acta Electronica Sinica，2013，41（7）：1249-1254.（in Chinese）

［2］蘭巨龍，程東年，胡宇翔.可重構(gòu)信息通信基礎(chǔ)網(wǎng)絡(luò)體系研究［J］.通信學(xué)報，2014，35（1）：128-139. Lan Ju-long，Cheng Dong-nian，Hu Yu-xiang.Research on reconfigurable information communication basal network architecture［J］.Journal on Communications，2014，35（1）：128-139.（in Chinese）

［3］B Heller，R Sherwood，N McKeown.The controller placement problem［A］.Proceedings of the First Workshop on Hot Topics in Software Defined Networks［C］.Helsinki，F(xiàn)inland：IEEE，2012.7-12.

［4］D Levin，A Wundsam，B Heller，N Handigol，A Feldmann. Logically centralized？：State distribution trade-offs in software defined networks［A］.Proceedings of the First Workshop on Hot Topics in Software Defined Networks［C］. Helsinki，F(xiàn)inland：IEEE，2012.1-6.

［5］Y Hu，W Wendong，X Gong，X Que，S Cheng.On the placement of controllers in software-defined networks［J］. The Journal of China Universities of Posts and Telecommunications，2012，19（2）：92-171.

［6］Hu Y，Wang W，Gong X，et al.On reliability-optimizedcontroller placement for software-defined networks［J］. Communications China，2014，11（2）：38-54.

［7］G Yao，J Bi，Y Li，L Guo.On the capacitated controller placement problem in software defined networks［J］.IEEE Communications Letters，2014，18（8）：1339-1342.

［8］Ros F J，Ruiz P M.Five nines of southbound reliability in software-defined networks［A］.ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking （HotSDN）［C］.Chicago，USA：IEEE，2014.1-6.

［9］D Hock，S Gebert，M Hartmann，T Zinner，Tran-Gia.POCO-framework for pareto-optimal resilient controller placement in SDN-based core networks［A］.Network Operations and Management Symposium［C］.Krakow，Poland：IEEE，2014.1-2.

［10］A Dixit，F(xiàn) Hao，S Mukherjee，T V Lakshman，R Kompella.Towards an elastic distributed SDN controller［A］. Proceedings of the Second ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking［C］.Hong Kong，China：IEEE，2013.7-12.

［11］M F Bari，A R Roy，S R Chowdhury，Q Zhang，M F Zhani，R Ahmed，R Boutaba.Dynamic controller provisioning in software defined networks［A］.Proceedings of 9th International Conference on Network and Service Management［C］.Zürich，Switzerland：IEEE，2013.18-25.

［12］Y Zhang，N Beheshti，M Tatipamula.On resilience of split-architecture networks［A］.Global Telecommunications Conference（GLOBECOM）［C］.Houston，USA：IEEE，2011.1-6.

［13］Open Flow Switch Specification，Version 1.4.0［OL］.https：//www.opennetworking.org/images/stories/downloads/sdn-resources/onf-specifications/openflow/openflow-spec-v1.4.0.pdf.

［14］K Le，V Li.Modeling and analysis of systems with multimode components and dependent failures［J］.IEEE Transactions on Reliability，1989，38（1）：68-75.

［15］Internet2 Open Science，Scholarship and Services Exchange ［OL］.http：//www.internet2.edu/network/ose/.

［16］Knight S，Nguyen H X，F(xiàn)alkner N，et al.The internet topology zoo［J］.IEEE Journal on Selected Areas in Communications，2011，29（9）：1765-1775.

王文博 男，1991年1月出生，河南信陽人.國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心碩士研究生，主要研究方向為軟件定義網(wǎng)絡(luò).

E-mail：jameschenmu@outlook.com

汪斌強(qiáng) 男，1963年2月生，安徽安慶人.國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心教授、博士生導(dǎo)師，主要研究方向為寬帶信息網(wǎng)絡(luò)，網(wǎng)絡(luò)安全.

E-mail：wbq6301@163.com

陳飛宇 男，1990年8月出生，河南周口人.國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心碩士研究生，主要研究方向為寬帶信息網(wǎng)絡(luò).

The Controller Hot Backup and Election Algorithms in Software Defined Networks

WANG Wen-bo，WANG Bin-qiang，CHEN Fei-yu，WANG Zhi-ming，GONG Yang-yang

（National Digital Switching System Engineering R&D Center，Zhengzhou，Henan 450002，China）

In multi-domain software defined networks，the existed switch migration strategies always have big computation space and only consider single migration factor.Once the controller gets broken，the switches cannot be migrated immediately.This paper presents the controller hot backup and election problem and designs the corresponding algorithms to find the backup space and complete the master controller election.To reasonably build the network，this paper considers the message exchange cost，the disconnectivity cost，load imbalance cost and cross domain cost.Results show that，compared with the existed algorithms，the proposed algorithms reduce the controller backup space by an average of 65%，and increase the weighted comprehensive evaluation up to 71%in OS3E topology.

software defined networks；multi-controller；hot backup；controller election；failover

TP393

A

0372-2112（2016）04-0913-07

電子學(xué)報URL：http：//www.ejournal.org.cn 10.3969/j.issn.0372-2112.2016.04.023

2014-11-02；

2014-12-12；責(zé)任編輯：孫瑤

國家973重點基礎(chǔ)研究發(fā)展計劃（No.2012CB315901，No.2013CB329104）；國家自然科學(xué)基金（No.61372121）；國家863高技術(shù)研究發(fā)展計劃（No.2013AA013505）