基于SDN的多控制器部署策略的研究

鮮永菊，朱　佳，魯昭男

(重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065)

基于SDN的多控制器部署策略的研究

鮮永菊，朱佳，魯昭男

(重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065)

摘要:隨著SDN在大型網(wǎng)絡(luò)以及廣域網(wǎng)中的需求，如何合理、高效地部署SDN控制器，從而以較低的部署成本，獲得較好的網(wǎng)絡(luò)性能，是當(dāng)前研究的熱點(diǎn)。針對(duì)控制器數(shù)量、部署位置問題以及交換機(jī)與控制器之間的映射關(guān)系的問題，首先給出一種分布式的控制器部署方式并設(shè)定了網(wǎng)絡(luò)相關(guān)參數(shù)，以流建立請(qǐng)求代價(jià)為優(yōu)化目標(biāo)，提出了一種基于貪心算法的控制器部署策略方案。最后通過仿真實(shí)驗(yàn)將所提出方案與ACL方案進(jìn)行對(duì)比，證明了所提方案在性能方面有一定的提升。

關(guān)鍵詞:SDN；控制器；貪心算法

SDN[1]由于其控制與轉(zhuǎn)發(fā)相分離的本質(zhì)，使數(shù)據(jù)的轉(zhuǎn)發(fā)更加簡單，網(wǎng)絡(luò)的控制更加靈活，并降低了網(wǎng)絡(luò)的管理成本，受到學(xué)術(shù)界和產(chǎn)業(yè)界的熱捧并成為其研究的熱點(diǎn)。隨著SDN在實(shí)際大型網(wǎng)絡(luò)拓?fù)湟约皬V域網(wǎng)中部署的需求，控制平面的可擴(kuò)展性成為亟待解決的問題[2]，目前國內(nèi)外已有解決SDN控制器可擴(kuò)展性的架構(gòu)方案，例如HyperFlow[3]、Onix[4]等。這些架構(gòu)方案通過把多個(gè)控制器劃分到不同的控制域中，形成分布式的控制器部署平面，這是未來解決SDN面向大規(guī)模網(wǎng)絡(luò)部署時(shí)的重要思路[5-8]。但是對(duì)于給定的網(wǎng)絡(luò)拓?fù)洌刂破鞯牟渴饐栴}還有待進(jìn)一步研究，比如，如何確定控制器的數(shù)量，以及每個(gè)控制器應(yīng)該控制哪些交換機(jī)，才能使各個(gè)轉(zhuǎn)發(fā)設(shè)備之間都能夠更加有效及時(shí)地獲得控制器的流表信息?？刂破鞑渴饐栴}可以根據(jù)不同的性能指標(biāo)如可靠性、時(shí)延、安全性、一致性等方面進(jìn)行研究。

1相關(guān)研究

國外已經(jīng)有在控制器部署相關(guān)方面的研究。文獻(xiàn)[9]提出了一種基于數(shù)學(xué)模型進(jìn)行求解的部署算法，其中以最小化網(wǎng)絡(luò)建設(shè)成本為目標(biāo)，考慮多個(gè)約束條件進(jìn)行求解，但該算法只適合小規(guī)模網(wǎng)絡(luò)，對(duì)大規(guī)模網(wǎng)絡(luò)來說，隨著節(jié)點(diǎn)規(guī)模的擴(kuò)大，計(jì)算復(fù)雜度急劇增大，求解時(shí)間過長，甚至無法求解。文獻(xiàn)[10]通過引入平均時(shí)延和最壞時(shí)延兩個(gè)衡量標(biāo)準(zhǔn)進(jìn)行大量試驗(yàn)，針對(duì)不同的拓?fù)浣Y(jié)構(gòu)來研究控制器數(shù)量和控制器在拓?fù)渲兴渴鹞恢脤?duì)時(shí)延的影響。但是在研究控制器部署策略時(shí)，沒有考慮到網(wǎng)絡(luò)的可靠性。無法保證控制器之間全局視圖的一致性，從而破壞了正常的數(shù)據(jù)轉(zhuǎn)發(fā)功能。

在以網(wǎng)絡(luò)可靠性為優(yōu)化目標(biāo)的研究工作中，文獻(xiàn)[11]提出了“受保護(hù)”交換機(jī)概念，使故障快速恢復(fù)的可能性達(dá)到最大，但文章所提的算法只適合于單控制器情況。文獻(xiàn)[12]提出了一種貪婪的控制器放置算法，它僅以兩點(diǎn)之間的可靠性作為判斷控制器放置位置的依據(jù)，其可靠性近似公式準(zhǔn)確性欠佳，無法代表實(shí)際的可靠性。文獻(xiàn)[13]提出了基于聚類的控制器放置算法和基于貪婪的控制器放置算法，分別實(shí)現(xiàn)了全局和局部的可靠性優(yōu)化效果。但在研究過程中沒有考慮通信時(shí)延帶來的影響，控制平面和數(shù)據(jù)平面可能存在的時(shí)延將難以保證控制邏輯更新的一致性，有可能造成網(wǎng)絡(luò)出現(xiàn)斷路、丟包、環(huán)路等現(xiàn)象，使網(wǎng)絡(luò)無法進(jìn)行正常通信。

目前現(xiàn)有的SDN多個(gè)控制器部署方案中，大多是從交換機(jī)節(jié)點(diǎn)到控制器的傳輸時(shí)延角度或者可靠性角度來分析控制器的部署問題，這些研究都是僅考慮網(wǎng)絡(luò)中的鏈路因素，而沒有考慮到節(jié)點(diǎn)因素，因?yàn)樵诰W(wǎng)絡(luò)拓?fù)渲?，都是由?jié)點(diǎn)和鏈路組成的，節(jié)點(diǎn)的權(quán)重代表了經(jīng)過該節(jié)點(diǎn)以及由該節(jié)點(diǎn)產(chǎn)生的流數(shù)目，如果不考慮節(jié)點(diǎn)，則會(huì)忽略網(wǎng)絡(luò)中節(jié)點(diǎn)的負(fù)載，影響網(wǎng)絡(luò)的性能，節(jié)點(diǎn)因素同樣占據(jù)了很大一方面影響，所以在SDN控制器部署方案中，應(yīng)同時(shí)考慮節(jié)點(diǎn)和鏈路兩個(gè)方面因素來進(jìn)行研究。

2多控制器部署策略

本文在目前研究方案的基礎(chǔ)上對(duì)分布式多控制器的部署提出改進(jìn)方案，同時(shí)考慮節(jié)點(diǎn)和鏈路兩方面因素，以流建立請(qǐng)求代價(jià)為優(yōu)化目標(biāo)，研究了分布式控制平面中多控制器的部署問題，對(duì)于一個(gè)給定的拓?fù)洌紫冗M(jìn)行對(duì)區(qū)域劃分，然后提出一種基于貪心算法的控制器部署策略解決控制器部署位置優(yōu)化問題，從候選位置中選出最少數(shù)量的控制器集合，確定在哪些候選節(jié)點(diǎn)需要部署控制器，并計(jì)算出哪些控制器控制哪些交換機(jī)，即控制器與交換機(jī)的映射關(guān)系。

2.1控制器部署方式

控制器對(duì)交換機(jī)進(jìn)行控制和管理，從平面中的節(jié)點(diǎn)中找出若干節(jié)點(diǎn)作為控制器最佳部署節(jié)點(diǎn)，控制器和交換機(jī)分別視為平面E中的點(diǎn)。

在控制器部署時(shí)，主要存在兩種方式：帶內(nèi)部署和帶外部署[14]。帶內(nèi)部署即選取某個(gè)核心交換機(jī)(文中交換機(jī)節(jié)點(diǎn)均指核心交換機(jī)節(jié)點(diǎn))的位置作為控制器部署位置；帶外部署則選取交換機(jī)位置以外的地方作為控制器部署位置，并且每個(gè)交換機(jī)都與控制器建立一個(gè)單獨(dú)的安全通道以傳送消息信令。這兩種部署模式各有優(yōu)劣：帶內(nèi)部署可以避免控制器和交換機(jī)信息交互采用額外的接口和鏈路，減輕網(wǎng)絡(luò)設(shè)備的開銷；但這同時(shí)會(huì)帶來數(shù)據(jù)處理的開銷，控制器交換機(jī)在接收到新的數(shù)據(jù)時(shí)需要首先判斷其信息類型。而帶外模式則與此相反。在實(shí)際網(wǎng)絡(luò)部署中為了節(jié)省控制器的部署成本，大部分都采用帶內(nèi)部署方式，因此本文也采用帶內(nèi)部署方式。

2.2網(wǎng)絡(luò)區(qū)域劃分

隨著網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大，需要部署的控制器的數(shù)量也會(huì)逐漸增加，對(duì)整個(gè)區(qū)域進(jìn)行部署控制器時(shí)，由于節(jié)點(diǎn)數(shù)量太多，將會(huì)出現(xiàn)計(jì)算時(shí)間復(fù)雜度較高，這樣計(jì)算出來的部署位置更靠近網(wǎng)絡(luò)的中心，產(chǎn)生了熱點(diǎn)區(qū)域，不利于分散流量，不利于網(wǎng)絡(luò)流量均衡，最重要的是由于控制器性能的有限性，在區(qū)域邊界處的交換機(jī)有可能無法被所部署的控制器管理到，對(duì)整個(gè)區(qū)域劃分成小區(qū)域，再對(duì)每個(gè)小區(qū)域進(jìn)行控制器的部署，這樣使得在計(jì)算交換機(jī)和控制器映射關(guān)系時(shí)在較短時(shí)間內(nèi)收斂。

本文將進(jìn)一步研究對(duì)二維平面的區(qū)域劃分，按照六邊形原則將網(wǎng)絡(luò)劃分為i個(gè)區(qū)域，根據(jù)交換機(jī)節(jié)點(diǎn)數(shù)量和控制器容量，保證每個(gè)區(qū)域至少需要部署1個(gè)控制器，對(duì)每個(gè)區(qū)域由內(nèi)到外依次編號(hào)，再把六邊形區(qū)域平均劃分為6個(gè)子區(qū)域，每個(gè)子區(qū)也進(jìn)行編號(hào)A，B，C，D，E，F(xiàn)，二維平面的劃分如圖1所示。

圖1　網(wǎng)絡(luò)區(qū)域劃分圖

由于實(shí)際網(wǎng)絡(luò)中節(jié)點(diǎn)分布的密度不同，每個(gè)子區(qū)域?qū)?huì)包含有不同數(shù)量的節(jié)點(diǎn)，每個(gè)子區(qū)域?qū)?huì)部署一個(gè)或多個(gè)控制器，為了使部署方案更具靈活性，設(shè)定控制器的性能即容量不同，也就是一臺(tái)控制器所能控制的交換機(jī)數(shù)量不同，分為大容量控制器和小容量控制器，大容量控制器的容量U是小容量控制器容量V的ρ倍。首先根據(jù)子區(qū)域內(nèi)的交換機(jī)的數(shù)量w預(yù)估算出需要大容量控制器和小容量控制器的個(gè)數(shù)，他們之間的關(guān)系為

W=xU+yV+q

(1)

(2)

(3)

q=(WmodU)modV

(4)

式中：U,V,W,x,y,z,q均為整數(shù)，根據(jù)上式可以看出，在部署控制器時(shí)優(yōu)先部署大容量控制器，然后再部署小容量控制器，這樣是因?yàn)槿绻疾渴鸫笕萘靠刂破鲿?huì)浪費(fèi)資源，無法充分使用控制器的性能，最后剩余q個(gè)交換機(jī)根據(jù)鄰邊最近原則，交由相鄰子域內(nèi)的控制器進(jìn)行管理。當(dāng)下一個(gè)區(qū)域進(jìn)行控制器部署時(shí)，先將相鄰子域內(nèi)沒映射到的交換機(jī)節(jié)點(diǎn)“轉(zhuǎn)移”到本區(qū)域內(nèi)，然后再進(jìn)行本區(qū)域內(nèi)的控制器部署。

2.3SDN多控制器部署方案

當(dāng)數(shù)據(jù)在SDN網(wǎng)絡(luò)中，控制器的最主要功能之一是負(fù)責(zé)處理新流建立請(qǐng)求。在提出的控制器部署方案中，重點(diǎn)分析流請(qǐng)求的數(shù)量和流請(qǐng)求從交換機(jī)節(jié)點(diǎn)到控制器節(jié)點(diǎn)的傳輸代價(jià)來考慮控制器的最優(yōu)部署問題。

流請(qǐng)求消息的數(shù)量可以用交換機(jī)節(jié)點(diǎn)的權(quán)重w(s)衡量。節(jié)點(diǎn)的權(quán)重一方面體現(xiàn)節(jié)點(diǎn)的重要性，另一方面可代表經(jīng)過該節(jié)點(diǎn)以及由該節(jié)點(diǎn)產(chǎn)生的流數(shù)目。在本文中，以節(jié)點(diǎn)度ds來衡量節(jié)點(diǎn)的權(quán)重，節(jié)點(diǎn)的度是一個(gè)描述節(jié)點(diǎn)特征的重要參數(shù)，它是指和該節(jié)點(diǎn)相關(guān)聯(lián)的邊的條數(shù)。

節(jié)點(diǎn)權(quán)重w(s)表示為節(jié)點(diǎn)度ds

w(s)=ds

(5)

流請(qǐng)求消息從交換機(jī)節(jié)點(diǎn)到控制器節(jié)點(diǎn)的傳輸代價(jià)受多方面因素影響，如節(jié)點(diǎn)間距離(distance)、鏈路帶寬(bandwidth)、鏈路時(shí)延(delay)、鏈路負(fù)載(load)和交換機(jī)丟包率(loss)等相關(guān)因素。交換機(jī)節(jié)點(diǎn)到控制器節(jié)點(diǎn)的傳輸代價(jià)用f(s,c)來表示，流請(qǐng)求消息的轉(zhuǎn)發(fā)過程可看成是一類路由問題。在計(jì)算f(s,c)時(shí)，可以對(duì)各個(gè)影響因素歸一化后進(jìn)行加權(quán)，使用路由算法進(jìn)行求解。兩節(jié)點(diǎn)之間的傳輸代價(jià)f(i,j)可以用一種加權(quán)的表示方法為

f(i,j)=α·dis(i,j)+β·Band(i,j)+γ·del(i,j)+

λ·load(i,j)+μ·loss(s)

(6)

對(duì)所有影響鏈路傳輸代價(jià)的因素歸一化后，再使用路由算法進(jìn)行最優(yōu)路徑求解，以找到最小的路徑傳輸代價(jià)作為f(s,c)的度量

(7)

在SDN控制器部署問題中，優(yōu)化目標(biāo)是最小化流建立請(qǐng)求的平均代價(jià)，以此來衡量流建立請(qǐng)求傳輸時(shí)延。

網(wǎng)絡(luò)中并不是所有的交換機(jī)節(jié)點(diǎn)都可以作為控制器的候選位置節(jié)點(diǎn)，為了降低計(jì)算控制器最佳位置節(jié)點(diǎn)的復(fù)雜度，定義網(wǎng)絡(luò)中可部署控制器的候選節(jié)點(diǎn)集，從該節(jié)點(diǎn)集中找到流建立請(qǐng)求代價(jià)最小的節(jié)點(diǎn)，該節(jié)點(diǎn)即為控制器部署位置節(jié)點(diǎn)。其中控制器候選節(jié)點(diǎn)集的選擇原則是將節(jié)點(diǎn)權(quán)重大于或等于某固定值p的節(jié)點(diǎn)作為控制器候選位置節(jié)點(diǎn)集。

定義各區(qū)域內(nèi)交換機(jī)節(jié)點(diǎn)到控制器的流建立請(qǐng)求代價(jià)函數(shù)

cost(s,c)=w(s)·f(s,c)

(8)

區(qū)域內(nèi)各交換機(jī)節(jié)點(diǎn)到控制器的流建立請(qǐng)求的平均代價(jià)函數(shù)

(9)

式(9)說明流建立請(qǐng)求平均代價(jià)由交換機(jī)節(jié)點(diǎn)的權(quán)重w(v)和交換機(jī)向控制器發(fā)送的請(qǐng)求消息傳輸代價(jià)f(s,c)共同決定。

2.4基于貪心算法的多控制器部署策略(MultipleController Deployment Strategy，MCDS)步驟

基于貪心算法的MCDS步驟為：

1)初始化子域中控制器集合C′為空；

2)計(jì)算節(jié)點(diǎn)總數(shù)n，各節(jié)點(diǎn)的度deg，及相關(guān)的網(wǎng)絡(luò)影響因子如節(jié)點(diǎn)間距離(distance)、鏈路帶寬(bandwidth)、鏈路時(shí)延(delay)、鏈路負(fù)載(load)和交換機(jī)丟包率(loss)等；

4)根據(jù)步驟2中的網(wǎng)絡(luò)參數(shù)，對(duì)各個(gè)影響因素歸一化后進(jìn)行加權(quán)，使用路由算法計(jì)算各節(jié)點(diǎn)到控制器候選節(jié)點(diǎn)的最佳路徑，以找到最小的路徑代價(jià)作為得到路由代價(jià)f(s,c)的度量；

5)綜合考慮交換機(jī)節(jié)點(diǎn)的權(quán)重，計(jì)算交換機(jī)到控制器候選節(jié)點(diǎn)的流信息建立請(qǐng)求代價(jià)cost(s,c)，按遞增順序排列；

7)找出具有最小cost(c)的節(jié)點(diǎn)cm作為大容量控制器的部署節(jié)點(diǎn)，加入控制器集合中，控制器數(shù)量加1，并取出包括此控制器位置所在節(jié)點(diǎn)的交換機(jī)節(jié)點(diǎn)的前U個(gè)交換機(jī)節(jié)點(diǎn)作為此控制器映射的交換機(jī)，同時(shí)把cm和相映射的交換機(jī)從集合S中移除，此時(shí)本區(qū)域剩余數(shù)量為r=n-U；

8)判斷r是否大于u，如果r大于u，重復(fù)步驟5)～9)，如果r小于u，再判斷r是否大于v，如果r大于v，重復(fù)步驟5)～9)，步驟8)、9)中的U替換成V，如果r小于v，則剩余的r個(gè)節(jié)點(diǎn)暫時(shí)不進(jìn)行管理，進(jìn)行下一步；

9)計(jì)算剩余的各個(gè)節(jié)點(diǎn)與相鄰子域內(nèi)最近節(jié)點(diǎn)的距離，根據(jù)就近原則，把剩余的各個(gè)節(jié)點(diǎn)“移動(dòng)”到相應(yīng)的子域內(nèi)，按照順序A→B→C→D→E→F進(jìn)行部署，總能找到至少一個(gè)相鄰的未開始部署的子域，當(dāng)此相鄰子域進(jìn)行控制器部署時(shí)優(yōu)先考慮“被移動(dòng)”到本子域的節(jié)點(diǎn)，設(shè)節(jié)點(diǎn)數(shù)為b，此時(shí)步驟8)中的U變?yōu)閁′=U-b，然后再根據(jù)步驟5)～9)進(jìn)行控制器部署和交換機(jī)節(jié)點(diǎn)映射。

此算法是一種局部最優(yōu)解算法，在每一次迭代計(jì)算中都能找到局部最優(yōu)解，算法復(fù)雜度較低，運(yùn)行時(shí)間也較短。避免了迭代計(jì)算陷入死循環(huán)，適用于節(jié)點(diǎn)數(shù)較多的大規(guī)模網(wǎng)絡(luò)。

3部署實(shí)例分析

本文首先要對(duì)一個(gè)給定的網(wǎng)絡(luò)拓?fù)溥M(jìn)行區(qū)域劃分，網(wǎng)絡(luò)拓?fù)淙鐖D2所示，對(duì)網(wǎng)絡(luò)拓?fù)鋭澐至?個(gè)區(qū)域并編號(hào)A，B，C，D，E，F(xiàn)，同時(shí)對(duì)各個(gè)子域內(nèi)的節(jié)點(diǎn)進(jìn)行編號(hào)，圖中的節(jié)點(diǎn)均為核心交換機(jī)所在位置的節(jié)點(diǎn)，大容量控制器可以控制6個(gè)交換機(jī)，小容量控制器可以控制4個(gè)交換機(jī)?？刂破鞑渴鸷蜻x節(jié)點(diǎn)選取節(jié)點(diǎn)度w(s)≥5的節(jié)點(diǎn)加入控制器候選節(jié)點(diǎn)集C中，在圖中用綠色表示候選節(jié)點(diǎn)(圖2原為彩圖，綠點(diǎn)在本圖中為顏色稍深一些的點(diǎn))，盡管網(wǎng)絡(luò)的規(guī)模并不是非常龐大，但足以說明本文所提的方案能提高系統(tǒng)。

圖2　區(qū)域劃分

在實(shí)例中，為了更直觀地說明流建立請(qǐng)求傳輸時(shí)延和網(wǎng)絡(luò)拓?fù)鋵?duì)于控制器部署位置的影響，本文在網(wǎng)絡(luò)拓?fù)鋮?shù)引入了節(jié)點(diǎn)間的路徑長度、鏈路帶寬。di,j表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的路徑長度，Bi,j表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的鏈路帶寬，且di,j=dj,i，Bi,j=Bj,i。

首先利用歸一化方法計(jì)算出節(jié)點(diǎn)間距離和鏈路帶寬的歸一化數(shù)值，并用加權(quán)公式得到兩節(jié)點(diǎn)間的鏈路傳輸代價(jià)加權(quán)值。然后利用Dijkstra算法找到各節(jié)點(diǎn)之間的最短路徑，然后根據(jù)現(xiàn)有的網(wǎng)絡(luò)參數(shù)及網(wǎng)絡(luò)拓?fù)淅肕ATLAB計(jì)算出各節(jié)點(diǎn)之間的路由代價(jià)，按照MCDS方案進(jìn)行部署，部署情況如圖3所示。

圖3　MCDS部署圖

在本區(qū)域中一共部署了11個(gè)控制器，其中9個(gè)大容量控制器和2個(gè)小容量控制器，圖3中紅色節(jié)點(diǎn)表示每個(gè)子域內(nèi)部署控制器所在位置(圖3原圖為彩圖，紅點(diǎn)在本圖中為顏色最深的點(diǎn))，在此控制器節(jié)點(diǎn)周圍的相同顏色的節(jié)點(diǎn)為此控制器所控制的交換機(jī)節(jié)點(diǎn)，

反映出了所部署的控制器與所管理的交換機(jī)之間的映射關(guān)系。

以A區(qū)域?yàn)槔M(jìn)行詳細(xì)說明，參數(shù)統(tǒng)計(jì)如下，鏈路帶寬單位是Mbit/s：d1,2=2.7,d1,4=1.7,d1,5=2.6,d1,9=2.2,d2,3=2.4,d2,6=1.1,d2,7=1.5,d3,8=0.9,d4,9=1.5；d4,12=2.4,d5,6=1.1,d5,9=0.5,d5,10=0.7,d6,7=1.0,d6,10=1.5,d7,8=0.8,d7,10=1.8；d7,11=1.1,d8,11=1.9,d9,12=1.1,d9,13=2.0,d10,11=0.9,d10,13=1.2,d11,13=2.0,d12,13=1.1，B1,2=2,B1,4=1,B1,5=2,B1,9=2,B2,3=2,B2,6=1,B2,7=2,B3,8=1,B4,9=1,B4,12=2；B5,6=1,B5,9=2,B5,10=1,B6,7=2,B6,10=2,B7,8=1,B7,10=2,B7,11=2,B8,11=2,B9,12=2；B9,13=2,B10,11=2,B10,13=2,B11,13=1,B12,13=1。

A區(qū)中一共有13個(gè)節(jié)點(diǎn)，選取節(jié)點(diǎn)度大于等于5的節(jié)點(diǎn)為控制器部署候選節(jié)點(diǎn)，圖中節(jié)點(diǎn)為{1，2，7，9，10，11，13}。根據(jù)式(7)算出各節(jié)點(diǎn)到候選控制器節(jié)點(diǎn)的最小路徑傳輸代價(jià)，然后根據(jù)式(8)計(jì)算出各節(jié)點(diǎn)到候選控制器節(jié)點(diǎn)的流建立請(qǐng)求，代價(jià)，按遞增順序排列得到前5個(gè)交換機(jī)節(jié)點(diǎn)到候選控制器節(jié)點(diǎn)的平均流建立請(qǐng)求，代價(jià)最小的是節(jié)點(diǎn)7，即當(dāng)前控制器最佳部署位置，所映射的交換機(jī)節(jié)點(diǎn)為{2，6，8，10，11}。到節(jié)點(diǎn)7的最小路徑傳輸代價(jià)分別為：f(2,7)=0.53,f(6,7)=0.44,f(7,8)=0.65,f(7,10)=0.58,f(7,11)=0.45。

移除節(jié)點(diǎn){2，6，7，8，10，11}再進(jìn)行剩余節(jié)點(diǎn)的部署，得到節(jié)點(diǎn)9為當(dāng)前控制器最佳部署位置，所映射的交換機(jī)節(jié)點(diǎn)為{1，4，5，12，13}。到節(jié)點(diǎn)9的最小路徑傳輸代價(jià)分別為：f(1,9)=0.66,f(4,9)=0.78,f(5,9)=0.34,f(9,12)=0.45,f(9,13)=0.62。

移除{1，4，5，12，13}后A區(qū)域剩余一個(gè)節(jié)點(diǎn)3，暫時(shí)不進(jìn)行對(duì)節(jié)點(diǎn)3管理，在B區(qū)域進(jìn)行部署時(shí)優(yōu)先考慮節(jié)點(diǎn)3進(jìn)行部署。最終選定了節(jié)點(diǎn)7和節(jié)點(diǎn)9作為A區(qū)域的最佳部署位置。

4方案比較與仿真結(jié)果分析

4.1方案比較

本文在上述網(wǎng)絡(luò)拓?fù)湎屡c其他算法進(jìn)行比較，并仿真驗(yàn)證其有效性。以最小化平均時(shí)延參數(shù)下的控制器位置部署方案ACL(Average-Case Latency)為例進(jìn)行比較，其從最可能的控制器部署位置中找到最佳位置使得平均時(shí)延最小。

(10)

在ACL方案下的控制器位置部署節(jié)點(diǎn)為9和10，如圖4所示。

圖4　ACL方案部署圖

節(jié)點(diǎn)9所映射的節(jié)點(diǎn)為{1，2，3，4，12}，到節(jié)點(diǎn)9的最小路徑傳輸代價(jià)分別為：f(1,9)=0.66,f(2,9)=1.41,f(3,9)=2.1,f(4,9)=0.78,f(9,12)=0.45。

到節(jié)點(diǎn)10的最小路徑傳輸代價(jià)分別為：f(5,10)=0.63,f(6,10)=0.53,f(7,10)=0.58,f(10,11)=0.41,f(10,13)=0.47。

對(duì)比兩種方案：

在MCDS方案下的流建立請(qǐng)求總代價(jià)為

5costMCDS(7)+5costMCDS(9)=25.47

(11)

在ACL方案下的流建立請(qǐng)求總代價(jià)為

5costACL(9)+5costACL(10)=35.17

(12)

由結(jié)果可以看出，在MCDS方案下區(qū)域A的流建立請(qǐng)求代價(jià)小于在ACL方案下的流建立請(qǐng)求代價(jià)。

從圖4中可以直觀地發(fā)現(xiàn)，在ACL方案下的控制器部署位置更靠近于網(wǎng)絡(luò)拓?fù)渲泄?jié)點(diǎn)更密集的位置，因?yàn)樵诓渴饡r(shí)只考慮了網(wǎng)絡(luò)鏈路延時(shí)參數(shù)，也就是節(jié)點(diǎn)之間的鏈路距離。在兩種方案下進(jìn)行控制器部署，統(tǒng)計(jì)每個(gè)子區(qū)域的流信息建立請(qǐng)求傳輸總代價(jià)進(jìn)行對(duì)比，如圖5所示。

圖5　不同區(qū)域中流信息建立傳輸總代價(jià)對(duì)比圖

從圖5中可以看出，對(duì)于區(qū)域A，B，E，F(xiàn)的流建立傳輸時(shí)延都得到了一定程度的減少，只有區(qū)域C，D保持一致，是因?yàn)镃，D區(qū)域在兩種方案下部署的位置相同，在區(qū)域A，B，E，F(xiàn)的部署位置更能有利于流建立傳輸。從而說明了MCDS方案中控制器位置部署具有一定的合理性。

4.2仿真環(huán)境設(shè)置

MCDS性能分析基于Opnet平臺(tái)，它模擬了一個(gè)開放式虛擬交換網(wǎng)絡(luò)，通過對(duì)數(shù)據(jù)包、節(jié)點(diǎn)、鏈路、網(wǎng)絡(luò)拓?fù)浞謩e進(jìn)行配置，使其執(zhí)行SDN網(wǎng)絡(luò)中數(shù)據(jù)層和控制層的進(jìn)程。在Opnet上模擬數(shù)據(jù)包流，在不同的交換機(jī)節(jié)點(diǎn)間建立了安全通道來模擬SDN的網(wǎng)絡(luò)連接，數(shù)據(jù)包流的產(chǎn)生服從λ=100的泊松分布為基準(zhǔn)，數(shù)據(jù)包流從交換機(jī)節(jié)點(diǎn)出發(fā)到達(dá)控制器，通過對(duì)各節(jié)點(diǎn)端口進(jìn)行配置來分配控制器管理所對(duì)應(yīng)的交換機(jī)。根據(jù)控制器節(jié)點(diǎn)的權(quán)重的不同配置相應(yīng)流請(qǐng)求速率，控制器處理單個(gè)數(shù)據(jù)包時(shí)間為0.7 ms，處理速率為數(shù)據(jù)包發(fā)送速率的兩倍才能使系統(tǒng)趨于穩(wěn)定，在該仿真過程中，設(shè)定了3 min為一次仿真運(yùn)行周期，在對(duì)控制器部署評(píng)估中，主要從流信息到控制器的時(shí)延和丟包率來進(jìn)行分析。

4.3仿真性能分析

對(duì)兩種部署方案進(jìn)行網(wǎng)絡(luò)拓?fù)浯罱?，利用ETE Delay統(tǒng)計(jì)了全網(wǎng)的交換機(jī)到控制器的時(shí)延和丟包率。

圖6表示在MCDS和ACL兩種部署方案下的網(wǎng)絡(luò)時(shí)延對(duì)比，橫坐標(biāo)表示仿真時(shí)間，單位是秒；縱坐標(biāo)表示所有交換機(jī)到控制器的流信息傳輸平均時(shí)延，單位是毫秒，圖7表示在兩種方案下的丟包率對(duì)比圖，橫坐標(biāo)表示仿真時(shí)間，單位是秒，縱坐標(biāo)表示流信息在傳輸時(shí)的丟包率，1表示100%。通過仿真可以看出MCDS的時(shí)延低于ACL的時(shí)延，這是由于在MCDS中，部署位置在節(jié)點(diǎn)7和節(jié)點(diǎn)9，不在最密集的位置，分散了網(wǎng)絡(luò)流量，均衡了節(jié)點(diǎn)的負(fù)載，避免了網(wǎng)絡(luò)產(chǎn)生熱點(diǎn)區(qū)域。而在ACL中，部署位置在節(jié)點(diǎn)9和節(jié)點(diǎn)10，控制器1管理的是1，2，3，4，12交換機(jī)節(jié)點(diǎn)，增加了鏈路距離，導(dǎo)致了傳輸時(shí)延的增加。從丟包率來看，ACL也高于MCDS，主要是因?yàn)樵贛CDS中，節(jié)點(diǎn)7的負(fù)載要大于節(jié)點(diǎn)10的負(fù)載，減少了丟包率，由此得出MCDS方案對(duì)系統(tǒng)提高了一定的性能。

圖6　時(shí)延對(duì)比圖(截圖)

圖7　丟包率對(duì)比圖(截圖)

5小結(jié)

本文在目前研究方案的基礎(chǔ)上對(duì)分布式多控制器的部署提出改進(jìn)方案，同時(shí)考慮節(jié)點(diǎn)和鏈路兩方面因素，以流建立請(qǐng)求代價(jià)為優(yōu)化目標(biāo)，研究了分布式控制平面中多控制器的部署問題，對(duì)于一個(gè)給定的拓?fù)?，首先進(jìn)行對(duì)區(qū)域劃分，然后提出一種基于貪心算法的控制器部署策略解決控制器部署位置優(yōu)化問題，并用部署實(shí)例進(jìn)行詳細(xì)說明，最后通過仿真實(shí)驗(yàn)將所提出方案與現(xiàn)有研究方案進(jìn)行對(duì)比，證明了所提方案對(duì)流建立請(qǐng)求時(shí)延和丟包率都有一定的性能提升。

參考文獻(xiàn)：

[1]GREENE K. Software-defined networking [EB/OL]. [2009-01-04]. http://www.technologyreview.com/read_article.aspx?ch=specialsections&sc=tr10&id=22120.

[2]PENNA M C，JAMHOUR E，MIGUEL M L F. A clustered SDN architecture for large scale WSON.[C]//Proc. IEEE 28th International Conference on Advanced Information Networking and Applications (AINA).[S.l]：IEEE，2014：374-381.

[3]TOOTOONCHIAN A，GANJALI Y. HyperFlow: a distributed control plane for OpenFlow[C]//Proc. the 2010 Internet Network Management Conference on Research on Enterprise Networking. San Jose：USENIX Association，2010：3.

[4]KOPONEN T，CASADO M，GUDE N，et al. Onix: a distributed control platform for large-scale production networks [C]//Proc. 9th USENIX Conf. on Operating Systems Design and Implementation (OSDI). Vancouver：USENIX Association，2010：1-6.

[5]JARRAYA Y，MADI T，DEBBABI M. A survey and a layered taxonomy of software-defined networking [J]. IEEE communications surveys & tutorials，2014，16(4)：1955-1980.

[6]SU W，LIU C，LAGOA C M，et al. Integrated，distributed traffic control in multidomain networks [J]. IEEE transactions on control systems technology，2014，23(4)：1-1.

[7]LANGE S，GEBERT S，SPOERHASE J，et al. Specialized heuristics for the controller placement problem in large scale SDN networks[C]// 2015 27th International. IEEE Teletraffic Congress (ITC 27).[S.l.]：IEEE，2015：210-218.

[8]XIAO P，QU W，QI H，et al. The SDN controller placement problem for WAN[C]//Proc. IEEE/CIC International Conference on Communications in China. [S.l.]：IEEE，2014：220-224.

[9]SALLAHI A，ST-HILAIRE M. Optimal model for the controller placement problem in software defined networks [J]. IEEE communications letters，2015，19(1)：30-33.

[10]HELLER B，SHERWOOD R，MCKEOWN N. The controller placement problem [J].ACM sigcomm computer communication review，2012，42(4)：7-12.

[11]ZHANG Y，BEHESHTI N. Fast failover for control traffic in software-defined networks[C]//Proc. IEEE Global Communications Conference (GLOBECOM). CA，USA：IEEE，2012：2665-2670.

[12]ZHANG Y，BEHESHTI N，TATIPAMULA M. On resilience of split-architecture networks [C]//Proc. Global Telecommunications Conference，[S.l.]：IEEE，2011：1-6.

[13]劉娟，黃韜，魏亮 SDN中基于可靠性優(yōu)化的控制器放置算法研究[EB/OL].[2015-03-12]. http://www.paper.edu.cn/releasepaper/content/201312-161.

[14]AHMED R，BOUTABA R. Design considerations for managing wide area software defined networks [J]. IEEE communications magazine，2014，52(7)：116-123.

鮮永菊(1973— )，女，博士，副教授，主要研究方向?yàn)檎J(rèn)知無線電關(guān)鍵技術(shù)、LTE 與未來網(wǎng)絡(luò)關(guān)鍵技術(shù)；

朱佳(1989— )，碩士生，主研軟件定義網(wǎng)絡(luò)；

魯昭男(1990— )，碩士生，主研軟件定義網(wǎng)絡(luò)。

責(zé)任編輯：許盈

Research on multiple controllers deployment strategy of SDN

XIAN Yongju, ZHU Jia,LU Zhaonan

(DepartmentofCommunicationandInformationEngineering,ChongqingUniversityofPostsandTelecommunications，Chongqing400065，China)

Abstract:With the demand for large-scale network and wide area networks on SDN, how to deploy SDN controllers properly and efficiently to lower deployment costs and get better network performance, is the current research focus. For the issues on number of controllers, the deployment location, and the mapping relations between switch and controller, the paper gives a distributed controller deployment model and sets network-related parameters firstly, in order to optimize the flow setup request, a controller deployment strategy program based on greedy algorithm has been proposed. Finally, comparing with the existing research programs though the simulation experiments, it shows that the proposed scheme promoting some performance.

Key words:SDN; controller; greedy algorithm

中圖分類號(hào):TN915.04

文獻(xiàn)標(biāo)志碼:A

DOI：10.16280/j.videoe.2016.06.015

基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目(61301124)；重慶郵電大學(xué)科研基金項(xiàng)目(A2012-16)

作者簡介：

收稿日期：2016-01-15

文獻(xiàn)引用格式：鮮永菊，朱佳，魯昭男. 基于SDN的多控制器部署策略的研究[J].電視技術(shù)，2016，40(6)：78-84.

XIAN Y J，ZHU J，LU Z N. Research on multiple controllers deployment strategy of SDN [J].Video engineering，2016，40(6)：78-84.

專題SDN技術(shù)與應(yīng)用