王文博,汪斌強,王志明,陳飛宇,劉帥

(1.中國人民解放軍信息工程大學國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心, 450002, 鄭州;2.中國衛(wèi)星海上測控部, 214400, 江蘇江陰)

?

針對控制平面連通效能優(yōu)化的控制器布置方法

王文博1,汪斌強1,王志明1,陳飛宇1,劉帥2

(1.中國人民解放軍信息工程大學國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心, 450002, 鄭州;2.中國衛(wèi)星海上測控部, 214400, 江蘇江陰)

針對控制器間通信時延大、信息交互困難和全網(wǎng)視角難以維護的問題,提出了一種針對控制平面連通效能優(yōu)化的控制器布置方法。該方法在保證負載均衡和服務(wù)質(zhì)量的基礎(chǔ)上將控制器布置問題建模成為一個K-center問題,并對指標優(yōu)化下的控制器布置位置和個數(shù)進行了刻畫。為求解該模型,設(shè)計了相應(yīng)的基于連通效能的兩階段優(yōu)化算法:第一階段通過設(shè)置節(jié)點的優(yōu)先級別和搜索范圍參數(shù),在確保控制器準確布置的前提下縮小了解的搜索范圍,得到了線性松弛下的搜索半徑;第二階段輸入第一階段的結(jié)果,通過不斷調(diào)整指針最終確定控制器的布置位置。仿真結(jié)果表明:該方法實現(xiàn)了控制器的最優(yōu)化部署,減少了控制器間的平均時延,方便了控制層面的信息交互,與CCP方法相比,在保證時延和負載均衡的同時使運算復雜度和連通效能得到了明顯改善,在OS3E拓撲中的解搜索范圍減小了30%,不同拓撲中的平均連通效能最大減小了15%。

軟件定義網(wǎng)絡(luò);控制器布置;控制平面;連通效能

軟件定義網(wǎng)絡(luò)(software defined networks,SDN)[1]分離了轉(zhuǎn)發(fā)層與控制層,將原本束縛在轉(zhuǎn)發(fā)設(shè)備(交換機、路由器)之內(nèi)的智能環(huán)節(jié)抽離到上層,使網(wǎng)絡(luò)具備了協(xié)議標準開放、管理集中靈活和直接可編程等特點[2]。隨著網(wǎng)絡(luò)規(guī)模的不斷增大和業(yè)務(wù)需求的多元化,多控制器網(wǎng)絡(luò)中的控制平面設(shè)計[3]面臨著新的巨大挑戰(zhàn)。其中,控制平面的節(jié)點布置[4]關(guān)系到服務(wù)質(zhì)量和網(wǎng)絡(luò)的可擴展性,是控制平面設(shè)計的重要方面。

近年來,控制器節(jié)點的布置方法大致分為3類。第1類方法主要針對節(jié)點到控制器的傳播時延進行布置[4],例如針對平均時延優(yōu)化的K-median模型和針對最差時延優(yōu)化的K-center模型[4],這類方法將服務(wù)質(zhì)量作為布置的重要考慮因素,在邏輯上認為整個控制器集合的“角色”相同,實際上,大規(guī)模網(wǎng)絡(luò)通常分區(qū)域進行扁平控制,需要權(quán)衡其他因素進行綜合考慮。第2類方法通過對可靠性的刻畫,將控制器布置問題抽象成為一個NP-hard的最優(yōu)化問題。文獻[5-10]分別根據(jù)控制路徑損失[5-6]、網(wǎng)絡(luò)容錯性[7]、交換機節(jié)點的關(guān)聯(lián)性[8]和路徑失效性[9]對分布式網(wǎng)絡(luò)中控制平面的可靠性進行評估分析,設(shè)計并提出了相應(yīng)的數(shù)學模型和布置算法,例如l-w貪心算法[5]、基于模擬退火算法的布置算法[6]、K-Critical算法[10]等。第3類方法主要考慮了網(wǎng)絡(luò)中負載的分布情況[11-12],例如針對負載均衡的CCP模型[11]和針對級聯(lián)故障的布置模型[12]等。后兩類方法雖然在保證服務(wù)質(zhì)量的前提下,增強了控制平面的可靠性,但是未能對多控制器之間的連通性能進行有效的描述分析。

控制節(jié)點間的連通性[10]是連接SDN控制平面和數(shù)據(jù)平面的“紐帶”和“橋梁”,既連接交換機和控制器,又傳達了整個平面的控制信息,對方便域間信息交換、完成資源共享和保證邏輯集中的全局視角[3]很有意義,是提升服務(wù)質(zhì)量和控制平面可靠性的重要因素[10],而目前的布置方法對該問題的描述均相對欠缺。

本文在保證通信時延和負載均衡的前提下,提出了一種針對增強控制平面連通效能的控制器布置方法(connectivity optimized controller placement strategy, COCP strategy),并在此基礎(chǔ)上給出了一個基于連通效能的兩階段優(yōu)化算法(connectivity based 2-stage algorithm,CB2A),對指標優(yōu)化下的控制器布置位置和個數(shù)進行了研究。CB2A的第一階段通過事先設(shè)置候選控制器集合和搜索半徑縮小了問題的求解范圍,用線性松弛解給出搜索半徑的大致數(shù)值;第二階段通過不斷調(diào)整指針最終確定控制器的布置位置。通過在OS3E[13]和topology zoo[14]進行仿真,與capacitatedK-center算法[11]相比,CB2A算法在保證節(jié)點布置準確性的基礎(chǔ)上降低了算法的復雜度;與CCP方法[11]相比,連通效能明顯改善。就目前的文獻調(diào)查情況分析,根據(jù)控制平面的連通效能進行控制器布置是一種新的嘗試,可為控制平面設(shè)計提供新的數(shù)學模型和思路。

1 模型的建立

通過引入控制平面網(wǎng)絡(luò)的概念,給出控制平面連通效能的定義,繼而介紹目標優(yōu)化下的控制器布置模型。

1.1 控制平面的連通效能

軟件定義網(wǎng)絡(luò)在邏輯上類似于“client-server”網(wǎng)絡(luò),交換機完全依靠接收控制器的異步信息來實現(xiàn)數(shù)據(jù)的轉(zhuǎn)發(fā)。同時,在多控制器SDN架構(gòu)中,例如Onix、Hyperflow等,控制邏輯分布在各個控制器上,共同維護控制的一致性和唯一的全局視角。

本文提出軟件定義網(wǎng)絡(luò)控制平面連通效能的意義主要體現(xiàn)在以下幾個方面。①維護網(wǎng)絡(luò)的全局視角。優(yōu)化連通性能后控制器間能夠更好的協(xié)同合作,“透明的”管理和控制網(wǎng)絡(luò),方便各域內(nèi)的拓撲信息交換、流表安裝以及節(jié)點間的隸屬關(guān)系和角色的轉(zhuǎn)換。②保證控制的一致性。當不同控制器隸屬下的交換機需要相互通信時,控制器需要根據(jù)全網(wǎng)的拓撲信息進行流表安裝,但是由于控制器角色和下發(fā)順序的不同,流表到達交換機的時間可能會發(fā)生錯誤。優(yōu)化連通效能后,控制器間能夠更快地傳遞信息,保證了控制的一致性。③對控制平面的可靠性做了權(quán)衡。優(yōu)化控制器間連通性后,控制器布置方法將權(quán)衡交換機到控制器之間的時延和多控制器之間的時延,使得一旦某控制器發(fā)生故障,故障信息、交換機隸屬和遷移信息能夠更快地進行交換,促進快速恢復,減少交換機失聯(lián),以保證控制平面的可靠性。

1.2 模型的描述

假設(shè)將網(wǎng)絡(luò)建模成一個無向圖G=(V,E),其中V是無向圖中節(jié)點的集合,E是邊的集合。節(jié)點集合V={v1,v2,…,vn},控制器集合C={c1,c2,…,ck}。為較好地刻畫控制平面的連通效能,給出以下定義。

定義1 控制平面網(wǎng)絡(luò)即控制器及其間最短路徑組成的控制層網(wǎng)絡(luò),如圖1所示。

(1)

式中:Gc表示控制平面網(wǎng)絡(luò);E′表示控制器之間最短路徑集合。

圖1 控制器布置示意圖

定義2 連接狀態(tài)矩陣X=[xvc]n×n用于描述控制器布置位置、個數(shù)及openflow交換機的分配關(guān)系。其中,矩陣元素中c、v僅用于標識控制器與交換機;i、j用于標定節(jié)點位置。當(xvc)ij=1時,即控制器c布置在第j個位置上,且將第i個交換機v分配給該控制器。

(2)

定義3 控制平面的連通效能定義在控制平面網(wǎng)絡(luò)上,即控制器間最短距離的倒數(shù)的平均值

(3)

d(v1,v2)是節(jié)點v1與v2之間的最短距離,引入定義2中的連接狀態(tài)矩陣后,式(3)可表示為

(4)

式中:集合J即是連接狀態(tài)矩陣描述下的控制器集合C。

用控制器節(jié)點之間連接跳數(shù)的平均距離來描述控制平面的連通效能,既能夠保證邏輯集中的全網(wǎng)視角,又能夠衡量控制器間信息傳遞。

當歸屬在不同控制器內(nèi)的某兩個交換機進行通信時,必需先通過控制平面的信息交互,再向各自的數(shù)據(jù)平面下發(fā)流表[8]。這一過程產(chǎn)生的通信開銷必然涉及到控制器節(jié)點對地理位置的描述。當衡量控制器布置對整個控制平面網(wǎng)絡(luò)帶來的通信開銷時,顯然定義3是合理的。

1.3 模型的建立

該模型在保證服務(wù)質(zhì)量和負載均衡的基礎(chǔ)上,優(yōu)化控制平面的連通效能。該模型旨在網(wǎng)絡(luò)搭建之初給出控制器的布置位置,不涉及具體的網(wǎng)絡(luò)通信細節(jié)與服務(wù)機制。模型中采用平均時延[4]對服務(wù)質(zhì)量進行刻畫。下面給出負載均衡中關(guān)于控制器負載的定義。

定義4 控制器負載即分配交換機向控制器流請求數(shù)的總和。該模型使用PACKET_IN消息的數(shù)量對控制器負載進行描述[11]。第j個控制器的負載可以表示為

(5)

式中:li是第i個交換機向控制器的流請求數(shù);xij用于描述控制器與交換機的分配關(guān)系。

為了保證交換機和其所屬控制器的傳播時延,模型對其間的跳數(shù)作了約束,要求控制器到其管轄的交換機的最大跳數(shù)不得超過ε。這樣能夠使控制器位于一簇交換機的中心,同時保證控制器盡量均勻地分布在拓撲以內(nèi)。ε的取值與拓撲的半徑和控制器布置個數(shù)有關(guān),這將在后續(xù)算法中給予進一步說明。

由式(5)可以看出,控制器交換機的分配關(guān)系雖然不能直接影響控制層面的連通效能(EGc由控制器布置位置直接影響),但是與時延和負載有關(guān),將影響控制器布置位置,進而對連通效能產(chǎn)生影響。

優(yōu)化控制平面連通效能下的模型為

隨著社會經(jīng)濟的轉(zhuǎn)變,人們越發(fā)關(guān)注護理質(zhì)量以及服務(wù)態(tài)度。熟練的操作,精準的技術(shù)能使患者治療效果更佳,為患者減輕痛苦。若護理人員自身技能較差,患者除了本身的痛苦外,還會對護理人員產(chǎn)生排斥心理,對治療效果以及醫(yī)患關(guān)系產(chǎn)生影響。通過綜合帶教法能夠使實習生快速掌握基礎(chǔ)知識,能夠增加患者信任度,改善醫(yī)患關(guān)系,提升患者滿意度。帶教教師在傳授知識過程中增加了交流,使實習生存在問題能夠盡快解決,使師生關(guān)系更加穩(wěn)固,建立和諧的教學氛圍,使工作能夠更好的開展。

(6)

(7)

(8)

(9)

式(6)是模型的優(yōu)化目標,即控制平面的連通效能最大值;式(7)～式(9)是模型的約束條件。式(7)保證了將全網(wǎng)內(nèi)的所有交換機分配給控制器;式(8)中Cj為第j臺控制器的容量,它保證了每臺控制器的負載均不超過其負載上限,以免引發(fā)控制器故障。同時,式(8)還隱含了定義4中的約束條件,使得交換機分配服從就近原則,以調(diào)整傳播時延來確保服務(wù)質(zhì)量。式(9)對連接狀態(tài)矩陣的元素進行了約束,保證元素的值非0即1。

至此,模型已經(jīng)描述完畢。本文將模型抽象成為一個復雜的0-1整數(shù)規(guī)劃問題。該問題在刻畫交換機分配的基礎(chǔ)上,對控制平面的連通效能進行描述。為了求解該問題,給出一個改進的兩階段算法。

2 算法分析

模型是對經(jīng)典p-center問題的修正[11,15],是一個典型的NP-hard問題。其中,控制器布置個數(shù)和搜索半徑相互制約。文獻[15]給出了一般情況下(拓撲節(jié)點沒有重要性區(qū)分,即無控制器節(jié)點與交換機節(jié)點之分)的兩階段算法,并描述了p-center問題的兩個子問題;文獻[11]中的capacitatedK-center算法對p-center算法進行了改進,縮小了搜索半徑的變化范圍。本文在上述兩算法的基礎(chǔ)上提出CB2A算法,針對連通效能的優(yōu)化指標,對控制器集合的搜索范圍做了調(diào)整,相比之前算法進一步縮小了算法的復雜度,具體說明詳見仿真部分。

算法的第一階段根據(jù)拓撲的規(guī)模對ε進行限制。這一過程是一個典型的二分法求解過程,指針首先指向搜索范圍的中間點,然后通過不斷調(diào)整指針指向,對原問題進行松弛條件下的求解,確定ε的大概范圍。其中,線性松弛過程主要體現(xiàn)在對式(9)中的二進制取值松弛為小數(shù)?；诳刂破鞑贾脗€數(shù)K和ε的相互影響,當選定ε時,比較實際布置個數(shù)hnum與預計布置個數(shù)K之間的關(guān)系,如果hnum較大,說明ε束縛了交換機節(jié)點的“運動半徑”,應(yīng)將ε增大;反之,則減小ε。

算法的第二階段輸入第一階段得到的搜索起點,通過修正指針位置,最終確定控制器布置方法。算法的具體流程如下。

階段1有6個步驟。

步驟1 求出拓撲中所有源、目的節(jié)點的最短距離并按照降序排列,存入數(shù)組q;同時,找到搜索下限l=0,并取q的長度賦值給搜索上限ε。

步驟3 確定控制器布置的候選節(jié)點。先將控制器節(jié)點按照度降序排列,取集合的前w(w屬于0到1)個節(jié)點組成候選布置位置序列。

步驟4 代入候選控制器集合,使用線性規(guī)劃方法求解ε下最優(yōu)化問題的線性松弛解,得到此時的控制器布置個數(shù)hnum。如果hnum>K,l=m+1;否則,u=m。

步驟5 計算上限與下限的關(guān)系,如果u>l,轉(zhuǎn)到步驟2;否則,轉(zhuǎn)到步驟6。

步驟6 階段1得到距離ε的粗略取值,需要重新對搜索起點賦值,即將l的值賦給指針p。

階段2有2個步驟。

步驟7 求解此時控制器布置個數(shù)。根據(jù)p和候選控制器集合求解該條件下的線性解,也即控制器放置個數(shù)hnum。

步驟8 對指針進行調(diào)整。如果hnum>K,將指針加1,也即p=p+1。隨后跳轉(zhuǎn)至步驟7;否則結(jié)束階段2,得到最終的控制器布置方法。

值得注意的是,階段1的步驟3中,CB2A算法改進了原算法中的無差別搜索,將節(jié)點的度作為重要的考慮因素。先按照節(jié)點度的大小對所有節(jié)點進行降序排列,然后設(shè)計節(jié)點搜索范圍參數(shù)w,以控制算法計算的搜索范圍。其中,w是需要搜索的節(jié)點數(shù)占節(jié)點總數(shù)的百分比,按照度優(yōu)先原則選取,即步驟3。

使用度作為優(yōu)先級別劃分的原因是在考慮連通性能時,度越大的節(jié)點對連通各個節(jié)點的貢獻越大,能夠使控制節(jié)點更容易與其他節(jié)點通信,同時,度大的節(jié)點往往處在一簇節(jié)點的中心。這一特征在SDN中意義明顯,能夠?qū)粨Q機與控制器之間的連接跳數(shù)進行約束。明顯地,拓撲末端的葉子節(jié)點(度為1),不可能作為中心節(jié)點布置控制器。后續(xù)的仿真結(jié)果也證實了該想法,與沒有進行控制器節(jié)點約束的capacitatedK-center算法[11]相比,當選定合適的w和控制器布置個數(shù)K,兩者的控制器布置位置基本重合,說明度大的節(jié)點被選作控制器布置節(jié)點的可能性很大。

3 仿真與分析

首先說明仿真環(huán)境和仿真設(shè)置,然后分析仿真結(jié)果:①對比了CB2A算法和capacitatedK-center算法在同一優(yōu)化條件下的控制器布置位置的重合度,說明了模型中節(jié)點搜索范圍參數(shù)w設(shè)置的合理性;②在實驗拓撲中采用不同控制器布置方法,研究了控制平面連通效能的變化趨勢;③研究了控制器布置個數(shù)與連通效能之間的關(guān)系,發(fā)現(xiàn)了一些與想象不同但合乎情理的實驗結(jié)果。

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

(1)關(guān)于拓撲。為了使實驗更具說服性,實驗中的拓撲均取自O(shè)S3E和topology zoo。其中,OS3E網(wǎng)絡(luò)抽象自美國的實際骨干網(wǎng)絡(luò),來自Internet2項目,由美國120多所大學、研究機構(gòu)和公司為建設(shè)下一代互聯(lián)網(wǎng)共同推進。Topology zoo由澳大利亞政府和阿德雷德大學共同推進,抽象并收集了全球超過250個公共拓撲,在學界認可度高。

(2)關(guān)于仿真環(huán)境搭建和仿真步驟。為簡化實驗操作,本文類比文獻[11]中關(guān)于平均控制器負載的實驗設(shè)置。用PACKET_IN消息的數(shù)量作為衡量控制器負載的關(guān)鍵因素,平均流產(chǎn)生速率服從280 KB/s到320 KB/s的均勻分布。同時考慮到控制器掛載服務(wù)器之間的相互差異,對控制器容量做了差異化設(shè)置,即設(shè)為8～11 MB。由于問題中對負載均衡程度沒有衡量,仿真中只要不超過控制器容量即滿足網(wǎng)絡(luò)搭建要求。同時,實驗中使用跳數(shù)作為衡量網(wǎng)絡(luò)半徑的標準,式中的節(jié)點距離一律用跳數(shù)進行代替。

(3)CB2A中的線性規(guī)劃的求解采用IBM CPLEX Optimizer[16]進行求解。實驗環(huán)境為Intel Core i7 CPU 2.67 Hz,PC為RAM 8 GB,整個實驗平臺在C++語言下進行搭建。具體步驟是,通過C++進行拓撲搭建和輸入數(shù)據(jù)的設(shè)置,調(diào)用CPLEX中的Concert Techology進行模型建立,使用其內(nèi)核中的優(yōu)化算法求解式(6)中的優(yōu)化目標來完成整個實驗過程。

在上述設(shè)置下,實驗分別對算法性能、控制平面連通性能和控制器布置個數(shù)進行了研究分析。其中,控制平面連通性能采用式(4)進行計算,所得解經(jīng)驗證均能滿足第二階段的約束條件,保證了解的正確性。

3.2 實驗結(jié)果分析

實驗分別在OS3E網(wǎng)絡(luò)上運行CB2A和capacitatedK-center算法,此時保證優(yōu)化目標相同。調(diào)整節(jié)點搜索范圍參數(shù)w改變控制器布置個數(shù),統(tǒng)計不同情況下控制器布置位置的重合程度以說明CB2A算法設(shè)計流程的合理性。其中,布置位置的重合程度指在兩種算法下,布置在相同物理節(jié)點的控制器個數(shù)占控制器布置總個數(shù)的百分比,具體結(jié)果如圖2所示。維持w在較低值時,隨著控制器布置個數(shù)增多,重合度曲線呈現(xiàn)波動。這種現(xiàn)象出現(xiàn)的原因是,候選節(jié)點單純按照度的大小進行降序排列,對于度相同的節(jié)點僅隨機排列,并沒有進一步劃分優(yōu)先級別,導致某些重要節(jié)點始終無法進入搜索范圍。隨著控制器布置個數(shù)增多,對重合度造成的影響增大,所以重合度曲線波動下滑。隨著w值不斷增大,重合度曲線向上漂移,這是因為算法搜索范圍的增加帶來了布置位置重合度的增加。當w=0.7,兩種算法搜索結(jié)果完全相同,此時相當于設(shè)計算法的解搜索范圍減小了30%。

圖2 兩種算法下的控制器位置重合度

事實上,與節(jié)點總數(shù)相比,控制器布置個數(shù)往往很少[6]。當控制器布置個數(shù)較少時,即使w取值較小,也能夠滿足控制器布置的準確性?？梢?CB2A算法的設(shè)計是合理有效的。同時,算法的復雜度主要體現(xiàn)在對線性規(guī)劃的求解上,原算法中該整數(shù)規(guī)劃問題的時間復雜度為O(2n),本文算法中由于w的引入使其復雜度下降為O(2wn)。

在OS3E和topology zoo中的若干拓撲上重做實驗,其拓撲信息見表1。

表1 實驗拓撲數(shù)據(jù)

在不同拓撲中,對相同條件下的CCP布置方法[11]和本文提出的COCP布置方法進行仿真,結(jié)果如圖3所示,橫軸是控制器個數(shù)k占拓撲中節(jié)點總數(shù)n的比例(k/n),縱軸是控制平面的連通效能E。實驗布置的控制器個數(shù)不超過節(jié)點總數(shù)的20%。

實驗結(jié)果顯示,COCP布置方法明顯提升了控制平面的連通效能,在4個不同拓撲中,其平均值最大提升了15%。在同一拓撲中,連通效能值的大小與控制器布置個數(shù)無明顯對應(yīng)關(guān)系。這一結(jié)果與事先的預測結(jié)論差距較大:憑借經(jīng)驗,控制器布置個數(shù)越多,連通性能越好。由于控制平面網(wǎng)絡(luò)(定義1)是原拓撲的一個子圖,其節(jié)點、鏈路的不確定性導致定義在該網(wǎng)絡(luò)上的連通效能與控制器布置個數(shù)并無直接聯(lián)系。同時,隨著控制器布置個數(shù)增多,兩種布置方法差異越來越不明顯。由于控制器布置個數(shù)增多,兩種布置方法的控制器位置重合概率增大。

(a)OS3E (b)Garr201104

(c)Columbus (d)Tw 圖3 不同拓撲中控制器布置方法比較

4 結(jié) 論

本文針對現(xiàn)存模型無法對控制平面連通性進行描述的不足,定義了SDN控制平面的連通效能指標,提出一種針對增強控制平面連通效能的控制器布置方法——COCP方法,對指標優(yōu)化下的控制器布置位置和個數(shù)進行了研究。該方法在保證連通性能和負載均衡的基礎(chǔ)上對控制器進行布置。設(shè)計了一種兩階段算法CB2A,通過調(diào)整節(jié)點搜索范圍參數(shù)改善了現(xiàn)有capacitatedK-center算法的運算復雜度。在OS3E和topology zoo中的公共拓撲上分別進行仿真實驗,證明了算法設(shè)計的合理性和COCP方法較CCP方法在提高控制平面連通效能方面的明顯優(yōu)勢。最后,研究了連通效能與控制器布置個數(shù)、拓撲差異之間的關(guān)系。本文對控制平面的連通性能進行描述,可為控制平面的設(shè)計和實現(xiàn)提供新的數(shù)學模型和努力方向。

[1] 左青云, 陳鳴, 趙廣松, 等. 基于OpenFlow的SDN技術(shù)研究 [J]. 軟件學報, 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] MCKEOWN N, ANDERSON T, BALAKRISHNAN H, et al. OpenFlow: enabling innovation in campus networks [J]. ACM SIGCOMM Computer Communication Review, 2008, 38(2): 69-74.

[3] LEVIN D, WUNDSAM A, HELLER B, et al. Logically centralized?: state distribution trade-offs in software defined networks [C]∥Proceedings of the First Workshop on Hot Topics in Software Defined Networks. New York, USA: ACM, 2012: 1-6.

[4] HELLER B, SHERWOOD R, MCKEOWN N. The controller placement problem [C]∥Proceedings of the First Workshop on Hot Topics in Software Defined Networks. New York, USA: ACM, 2012: 7-12.

[5] HU Yannan, WANG Wendong, GONG Xiangyang, et al. On the placement of controllers in software-defined networks [J]. The Journal of China Universities of Posts and Telecommunications, 2012, 19(S2): 92-97.

[6] YANNAN H, WENDONG W, GONG X, et al. Reliability-aware controller placement for software-defined networks [C]∥Proceedings of the 2013 IEEE International Symposium on Integrated Network Management. Piscataway, NJ, USA: IEEE, 2013: 672-675.

[7] ROS F J, RUIZ P M. Five nines of southbound reliability in software-defined networks [C]∥Proceedings of the Third Workshop on Hot Topics in Software Defined Networks. New York, USA: ACM, 2014: 1-6.

[8] HOCK D, GEBERT S, HARTMANN M H, et al. POCO-framework for Pareto-optimal resilient controller placement in SDN-based core networks [C]∥Proceedings of the 2014 IEEE Network Operations and Management Symposium. Piscataway, NJ, USA: IEEE, 2014: 1-2.

[9] ZHANG Ying, BEHESHTI N, TATIPAMULA M. On resilience of split-architecture networks [C]∥Proceedings of the 2011 IEEE Global Telecommunications Conference. Piscataway, NJ, USA: IEEE, 2001: 1-6.

[10]YURY J, CRISTINA C, AURELIO J G. On the controller placement for designing a distributed SDN control plane [C]∥Proceedings of the 2014 IFTP Networking Conference. Piscataway, NJ, USA: IEEE, 2014: 1-9.

[11]YAO Guang, BI Jun, LI Yuliang, et al. On the capacitated controller placement problem in software defined networks [J]. IEEE Communications Letters, 2014, 18(8):1339-1342.

[12]GAO Guang, BI Jun, GUO Luyi. On the cascading failures of multi-controllers in software defined networks [C]∥Proceedings of the 21st IEEE International Conference on Network Protocols. Piscataway, NJ, USA: IEEE, 2013: 1-2.

[13]The Internet2 Community. Internet2 open science, scholarship and services exchange [EB/OL]. (2012-01-01) [2015-03-02]. http:∥www.internet2.edu/network/ose/.

[14]KNIGHT S, NGUYEN H X, FALKNER N, et al.The internet topology zoo [J]. IEEE Selected Areas in Communications, 2011, 29(9): 1765-1775.

[15]AYKUT ?ZSOY F, PINAR M C. An exact algorithm for the capacitated vertex p-center problem[J]. Computers and Operations Research, 2006, 33(5): 1420-1436.

[16]IBM. CPLEX-Optimizer [EB/OL](2012-01-01)[2005-03-02]. http:∥www-01.ibm.com/software/integration/optimization/cplex-optimizer.

(編輯 武紅江)

A Placement Strategy of Controllers for Optimizing the Connectivity of Control Plane

WANG Wenbo1,WANG Binqiang1,WANG Zhiming1,CHEN Feiyu1,LIU Shuai2

(1. China National Digital Switching System Engineering and Technological R&D Center, The PLA Information Engineering University, Zhengzhou 450002, China; 2. China Satellite Maritime Tracking and Control Department, Jiangyin, Jiangsu 214400, China)

A placement strategy of controllers for optimizing the connectivity of control plan is proposed to decrease communication latency among controllers, to improve the message communication and to remain a global view of the whole network. The controller placement problem is formulated as aK-center problem based on the load balance and QoS. The number of controllers and their placements are also studied with optimization. A 2-stage optimization algorithm based on connectivity is designed to solve the model. In the first stage of the algorithm, the node priority and the search variables are set to reduce the search scope and to ensure the accurate placement, until a search diameter is achieved under linear relaxation. The results of the first stage are used as the inputs of the second stage, and the final placement of controllers is obtained through the pointer adjustment. Simulation results show that the proposed strategy realizes the optimization of controller placement, reduces the average inner-controller latency and improves the communication in the control plane. A comparison with the CCP strategy shows that the strategy decreases the algorithm complexity and improves the connectivity of control plane with the consideration of the latency and load balance. The search scope of the solution space reduces by 30% in OS3E, and the average connectivity for different topologies increases about 15%.

software defined networks; controller placement; control plane; connectivity

2015-04-16。

王文博(1991—),男,碩士生;汪斌強(通信作者),男,教授。

國家重點基礎(chǔ)研究發(fā)展計劃資助項目(2012CB315901,2013CB329104);國家自然科學基金資助項目(61372121,61309019);國家高技術(shù)研究發(fā)展計劃資助項目(2015AA016102,2013AA013505)。

時間:2015-11-18

10.7652/xjtuxb201512013

TP393

A

0253-987X(2015)12-0077-06

網(wǎng)絡(luò)出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20151118.1615.004.html