分布式SDN控制器放置問題研究

蔡 寧 ,韓言妮 ,安 偉徐 震

1中國科學(xué)院 信息工程研究所 北京 中國100093

2中國科學(xué)院大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院 北京 中國100049

1 引言

計(jì)算機(jī)網(wǎng)絡(luò)通常包含大量的交換機(jī)、路由器以及防火墻、網(wǎng)絡(luò)地址轉(zhuǎn)換器和負(fù)載均衡器等多種類型的網(wǎng)絡(luò)中間件。隨著近年來互聯(lián)網(wǎng)技術(shù)的快速發(fā)展和互聯(lián)網(wǎng)業(yè)務(wù)需求日益增長,網(wǎng)絡(luò)規(guī)模和數(shù)據(jù)流量的不斷增長使得網(wǎng)絡(luò)的管理和控制越來越復(fù)雜。特別是,隨著網(wǎng)絡(luò)虛擬化和云計(jì)算的廣泛部署以及移動(dòng)計(jì)算趨勢的興起,網(wǎng)絡(luò)環(huán)境變得更加動(dòng)態(tài),從而使流量模式和網(wǎng)絡(luò)狀況以更快速和顯著的方式發(fā)生變化。

在傳統(tǒng)網(wǎng)絡(luò)架構(gòu)中,每個(gè)網(wǎng)絡(luò)設(shè)備不僅轉(zhuǎn)發(fā)數(shù)據(jù)包,還要計(jì)算和維護(hù)其操作所需的狀態(tài); 網(wǎng)絡(luò)運(yùn)營商需在命令行界面環(huán)境中使用有限的一組低級設(shè)備配置命令來執(zhí)行日益復(fù)雜的管理策略和任務(wù)?，F(xiàn)有傳統(tǒng)網(wǎng)絡(luò)架構(gòu)采用控制與轉(zhuǎn)發(fā)緊耦合的網(wǎng)絡(luò)管理方式,已經(jīng)難以適應(yīng)計(jì)算機(jī)網(wǎng)絡(luò)的復(fù)雜性和動(dòng)態(tài)性發(fā)展需要,具體面臨如下4個(gè)問題:

(1) 異構(gòu)設(shè)備增加了網(wǎng)絡(luò)管理的復(fù)雜性:為了執(zhí)行各種網(wǎng)絡(luò)管理策略,并響應(yīng)可能發(fā)生的各種網(wǎng)絡(luò)事件(例如流量突變、網(wǎng)絡(luò)攻擊等),網(wǎng)絡(luò)運(yùn)營商需要為網(wǎng)絡(luò)中大量的異構(gòu)網(wǎng)絡(luò)設(shè)備進(jìn)行配置。每種設(shè)備都使用各自專用的配置工具和配置命令,并根據(jù)特定協(xié)議運(yùn)行,因此增加了網(wǎng)絡(luò)管理的復(fù)雜性。

(2) 頻繁地人為配置增加了網(wǎng)絡(luò)管理的復(fù)雜性:由于網(wǎng)絡(luò)規(guī)模的快速增長和網(wǎng)絡(luò)狀態(tài)的不斷變化,運(yùn)營商需要不斷地人工調(diào)整網(wǎng)絡(luò)配置以響應(yīng)不斷變化的網(wǎng)絡(luò)狀況。為此,運(yùn)營商借助外部工具或構(gòu)建臨時(shí)腳本以在事件發(fā)生時(shí)動(dòng)態(tài)地重新配置網(wǎng)絡(luò)設(shè)備。這種人為的頻繁配置加劇了配置的復(fù)雜性,且容易引入配置錯(cuò)誤[1]。

(3) 分布式的低級配置方式增加了網(wǎng)絡(luò)管理的復(fù)雜性:每個(gè)網(wǎng)絡(luò)設(shè)備的控制平面與其數(shù)據(jù)平面緊耦合,且控制平面使用低級的配置命令進(jìn)行設(shè)備配置,這種分布式的網(wǎng)絡(luò)管理方式使得運(yùn)營商需要將網(wǎng)絡(luò)范圍的高級管理策略轉(zhuǎn)化為分布式的低級設(shè)備配置命令,隨著日益復(fù)雜的網(wǎng)絡(luò)策略的不斷增加,網(wǎng)絡(luò)管理也越來越復(fù)雜。

(4) 網(wǎng)絡(luò)設(shè)備的專用配置方式和封閉式開發(fā)阻礙了網(wǎng)絡(luò)的發(fā)展與創(chuàng)新:網(wǎng)絡(luò)設(shè)備使用專用的配置工具和封閉式的開發(fā)環(huán)境,設(shè)備配置方法和命令的更新通常由設(shè)備供應(yīng)商單方面決定,導(dǎo)致新協(xié)議和新技術(shù)的引入與部署變得極為困難,阻礙了網(wǎng)絡(luò)的發(fā)展與創(chuàng)新。

由于傳統(tǒng)網(wǎng)絡(luò)專用的、分布式的、低級的、封閉的網(wǎng)絡(luò)管理方式難以適應(yīng)日益復(fù)雜和變化的網(wǎng)絡(luò)發(fā)展趨勢,網(wǎng)絡(luò)的管理、發(fā)展和創(chuàng)新變得越來越困難。

1.1 軟件定義網(wǎng)絡(luò)

為了解決上述問題,研究人員提出了一種新型網(wǎng)絡(luò)范式——軟件定義網(wǎng)絡(luò)(Software-Defined Networking,SDN)。SDN將控制平面功能從各個(gè)網(wǎng)絡(luò)設(shè)備移動(dòng)到集中的控制器軟件,網(wǎng)絡(luò)設(shè)備只保留簡單的分組轉(zhuǎn)發(fā)功能。圖 1是由開放網(wǎng)絡(luò)基金會(huì)(Open Networking Foundation,ONF)提出的SDN經(jīng)典三層架構(gòu),包括數(shù)據(jù)平面、控制平面和應(yīng)用平面。

圖1 SDN架構(gòu)Figure 1 SDN architecture

(1) 數(shù)據(jù)平面也被稱為轉(zhuǎn)發(fā)平面,由支持 SDN南向接口的網(wǎng)絡(luò)設(shè)備組成,用于轉(zhuǎn)發(fā)數(shù)據(jù)包。網(wǎng)絡(luò)設(shè)備可以是SDN硬件交換機(jī)、SDN虛擬交換機(jī)或支持SDN的路由器等,后文統(tǒng)稱為交換機(jī)。數(shù)據(jù)平面設(shè)備通過南向接口接收控制平面的控制器下發(fā)的控制策略,并以流表項(xiàng)的形式存儲(chǔ)于本地。當(dāng)數(shù)據(jù)平面的數(shù)據(jù)包到達(dá)時(shí),網(wǎng)絡(luò)設(shè)備根據(jù)本地存儲(chǔ)的流表項(xiàng)對數(shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā)與處理,當(dāng)找不到匹配的流表項(xiàng)時(shí),網(wǎng)絡(luò)設(shè)備會(huì)向控制器發(fā)送請求消息,由控制器決定如何處理該數(shù)據(jù)包并將處理指令下發(fā)給相關(guān)網(wǎng)絡(luò)設(shè)備。數(shù)據(jù)平面設(shè)備還通過南向接口向控制平面的控制器主動(dòng)上報(bào)設(shè)備狀態(tài)和網(wǎng)絡(luò)狀態(tài)等信息。南向接口為上層提供統(tǒng)一的網(wǎng)絡(luò)資源控制接口以簡化網(wǎng)絡(luò)資源控制工作,在多種南向接口協(xié)議中,OpenFlow[2]受到了最為廣泛的關(guān)注與使用,因此本文也主要關(guān)注基于OpenFlow的SDN解決方案。

(2) 控制平面由集中的控制器軟件組成,負(fù)責(zé)維護(hù)全網(wǎng)信息,為應(yīng)用層提供全局網(wǎng)絡(luò)抽象視圖,同時(shí)將應(yīng)用層的要求轉(zhuǎn)換并下發(fā)至數(shù)據(jù)平面設(shè)備?？刂破矫嫱ǔＪ褂脝蝹€(gè)控制器,這種控制平面被稱為集中式SDN控制平面。由于可擴(kuò)展性和可靠性等方面的需要,開發(fā)了分布式 SDN控制平面,即使用多個(gè)控制器共同管理整個(gè)網(wǎng)絡(luò),控制器之間通過東西向接口進(jìn)行通信以維持全網(wǎng)視圖?？刂破髦袃?nèi)置了多種網(wǎng)絡(luò)服務(wù)模塊用于執(zhí)行基本的網(wǎng)絡(luò)資源管控。控制平面通過北向接口與應(yīng)用平面中的應(yīng)用程序進(jìn)行通信,向應(yīng)用層程序開放對底層網(wǎng)絡(luò)資源的控制能力。

(3) 應(yīng)用平面包含使用SDN控制器北向接口實(shí)現(xiàn)的應(yīng)用程序,這些應(yīng)用程序通過組合調(diào)用北向接口,實(shí)現(xiàn)比控制器內(nèi)置網(wǎng)絡(luò)服務(wù)更加復(fù)雜和自動(dòng)化的網(wǎng)絡(luò)服務(wù),包括路由、流量工程、負(fù)載均衡、防火墻和網(wǎng)絡(luò)狀態(tài)監(jiān)測等。應(yīng)用程序依據(jù)控制平面提供的全網(wǎng)視圖,不需依賴于底層網(wǎng)絡(luò)基礎(chǔ)設(shè)施的執(zhí)行細(xì)節(jié),以集中的方式直接表達(dá)所需的目標(biāo)和策略,由控制器接收并轉(zhuǎn)化為南向特定的命令和指示各數(shù)據(jù)平面設(shè)備行為的轉(zhuǎn)發(fā)規(guī)則。

SDN控制器具有網(wǎng)絡(luò)的全局視圖,能夠根據(jù)當(dāng)前的網(wǎng)絡(luò)狀態(tài)(例如鏈路利用率、網(wǎng)絡(luò)故障等)快速地做出恰當(dāng)?shù)穆酚蓻Q策,提高網(wǎng)絡(luò)資源利用率,實(shí)現(xiàn)更高效的網(wǎng)絡(luò)控制和管理; SDN使用集中式的網(wǎng)絡(luò)配置方式,繞過底層網(wǎng)絡(luò)細(xì)節(jié)的復(fù)雜性,無需單獨(dú)配置所有設(shè)備,簡化并加快了網(wǎng)絡(luò)的配置; SDN通過開放可編程接口,提供自動(dòng)化的網(wǎng)絡(luò)管理能力,降低網(wǎng)絡(luò)設(shè)計(jì)、部署、管理及擴(kuò)展開銷,減少運(yùn)維耗時(shí)以及人工失誤,從而降低網(wǎng)絡(luò)運(yùn)維成本; 開發(fā)人員還可通過可編程接口快速部署各種新協(xié)議和應(yīng)用程序,加速網(wǎng)絡(luò)的發(fā)展與創(chuàng)新。

1.2 集中式SDN控制平面

集中式 SDN控制平面使用單個(gè)控制器(例如NOX[3]、Floodlight[4]、Ryu[5]和 Beacon[6]等),是 SDN早期的部署方式,主要應(yīng)用于校園網(wǎng)和小型企業(yè)網(wǎng),因此集中式控制平面能夠滿足需求。但當(dāng)SDN推廣到數(shù)據(jù)中心和廣域網(wǎng)(Wide Area Network,WAN)等大規(guī)模網(wǎng)絡(luò)時(shí),集中式SDN控制平面在性能、可擴(kuò)展性和可靠性等方面遇到如下挑戰(zhàn):

(1) 性能:SDN中控制平面與數(shù)據(jù)平面相分離,交換機(jī)不再具有對新流做出決策的能力,需要與控制器建立通信以接收關(guān)于新流的處理決定。此外,控制器也會(huì)根據(jù)當(dāng)前的網(wǎng)絡(luò)狀態(tài)以及上層應(yīng)用程序制定的控制策略主動(dòng)地下發(fā)轉(zhuǎn)發(fā)規(guī)則?？刂破髋c距離較遠(yuǎn)的交換機(jī)之間通信可能需要過多的時(shí)延,這在地理分布的WAN中尤為嚴(yán)重?？刂破矫媾c數(shù)據(jù)平面之間較高的通信時(shí)延會(huì)降低控制平面的決策速度和數(shù)據(jù)平面的響應(yīng)速度[7],也限制了期望的故障恢復(fù)能力以及橫向的擴(kuò)展[8]。

(2) 可擴(kuò)展性:隨著網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大和業(yè)務(wù)需求的不斷增多,控制器需要應(yīng)對越來越多的網(wǎng)絡(luò)事件和流請求,這可能會(huì)使控制器由于其計(jì)算、內(nèi)存和帶寬等資源的限制成為瓶頸,出現(xiàn)控制器過載的情況,這在數(shù)據(jù)中心和大型企業(yè)網(wǎng)等大規(guī)模網(wǎng)絡(luò)中尤為嚴(yán)重[9]。例如,NOX控制器[3]每秒可處理3萬個(gè)流請求[7],而具有 1500臺(tái)服務(wù)器的數(shù)據(jù)中心每秒平均產(chǎn)生10萬條流[10],具有100個(gè)交換機(jī)的網(wǎng)絡(luò)每秒最多可以產(chǎn)生1000萬個(gè)流請求[6],遠(yuǎn)遠(yuǎn)超過了NOX控制器的處理能力。控制器的負(fù)載過高會(huì)增加控制器的處理時(shí)延,影響網(wǎng)絡(luò)的性能。為了解決該問題,研究人員試圖限制向SDN控制器發(fā)送流請求的數(shù)量,例如,將部分控制功能返還給交換機(jī)[11-12],這種方式雖然可以一定程度上提高網(wǎng)絡(luò)的可擴(kuò)展性,但需要修改交換機(jī)的硬件且較為復(fù)雜,并且該方式違背了SDN控制與轉(zhuǎn)發(fā)分離的設(shè)計(jì)初衷。

(3) 可靠性:單個(gè)控制器本質(zhì)上具有單點(diǎn)故障問題,且易受拒絕服務(wù)攻擊的影響。當(dāng)控制平面失效時(shí),交換機(jī)將失去轉(zhuǎn)發(fā)新流和應(yīng)對網(wǎng)絡(luò)其他動(dòng)態(tài)變化的能力,降低服務(wù)質(zhì)量,最終可能導(dǎo)致網(wǎng)絡(luò)癱瘓。值得注意的是,即使控制器正常運(yùn)行,由于鏈路或交換機(jī)的故障,某些網(wǎng)絡(luò)設(shè)備還是會(huì)與控制器發(fā)生斷連。因此,單控制器與轉(zhuǎn)發(fā)平面的分層架構(gòu)對網(wǎng)絡(luò)的可靠性產(chǎn)生了重大影響。

集中式SDN控制平面不能保證大規(guī)模網(wǎng)絡(luò)在性能、可擴(kuò)展性和可靠性等方面的需求。

1.3 分布式SDN控制平面

為了增強(qiáng)在大規(guī)模網(wǎng)絡(luò)部署時(shí)SDN的性能、可擴(kuò)展性和可靠性,研究人員提出了分布式SDN控制平面,它使用多個(gè)物理分布、邏輯集中的控制器共同管理整個(gè)網(wǎng)絡(luò)。邏輯集中是指全部或部分控制器具有全局的網(wǎng)絡(luò)視圖,從而保證做出全局最優(yōu)的控制決策。

在分布式SDN控制平面中,控制器之間使用東西向接口進(jìn)行通信。東西向接口(1)用于控制器之間共享本地網(wǎng)絡(luò)狀態(tài)信息從而構(gòu)建全局網(wǎng)絡(luò)視圖; (2)用于控制器故障轉(zhuǎn)移機(jī)制,實(shí)時(shí)檢測控制器的存活情況并做好數(shù)據(jù)備份; (3)用于控制器之間的負(fù)載均衡機(jī)制,平均分配網(wǎng)絡(luò)負(fù)載,使網(wǎng)絡(luò)獲得最佳性能和效率。東西向接口若使用專用的鏈路傳遞消息則稱為帶外連接方式; 若使用網(wǎng)絡(luò)中已有的鏈路傳輸消息則稱為帶內(nèi)連接方式。

根據(jù)控制平面的物理組織結(jié)構(gòu),分布式SDN控制平面大體分為扁平模型和分層模型兩種類型,如圖2所示。

圖2 分布式SDN控制平面Figure 2 Distributed SDN control plane

(1) 扁平模型:該模型將網(wǎng)絡(luò)水平劃分為多個(gè)區(qū)域,每個(gè)區(qū)域由一個(gè)控制器負(fù)責(zé)管理,該域稱為該控制器的管理域。為了實(shí)現(xiàn)邏輯集中的控制,控制器之間通過東西向接口進(jìn)行通信,交換各自管理域的狀態(tài)信息,從而維護(hù)全局的網(wǎng)絡(luò)視圖。典型的扁平 SDN 控制平臺(tái)有 Onix[13]、HyperFlow[14]和ONOS[15]等。

(2) 分層模型:該模型將控制平面根據(jù)所需服務(wù)垂直劃分為多個(gè)層次。底層由本地控制器組成,本地控制器之間不相互連接,且只處理本地應(yīng)用程序的需求。上層由通常稱為“根”的控制器構(gòu)成,根控制器與底層控制器相連,處理非本地應(yīng)用的需求。與扁平模型不同的是,分層模型的底層控制器僅具有本地網(wǎng)絡(luò)視圖,只有上層控制器才具有網(wǎng)絡(luò)的全局視圖。典型的分層SDN控制平臺(tái)有Kandoo[16]、谷歌的B4[17]和Espresso[18]等。

以上兩種模型以及各種SDN控制平臺(tái)的詳細(xì)介紹可參考相應(yīng)的綜述文獻(xiàn)[19-20]。

分布式SDN控制平面相比集中式SDN控制平面具有如下優(yōu)勢: (1)地理位置分布的控制平面可以降低控制器與交換機(jī)間的通信時(shí)延,提高網(wǎng)絡(luò)性能;(2)多控制器可以解決單控制器的處理瓶頸,提高可擴(kuò)展性; (3)多控制器可以解決單點(diǎn)故障問題,并可通過執(zhí)行各種故障檢測和恢復(fù)機(jī)制進(jìn)一步提高網(wǎng)絡(luò)的可靠性。例如,HyperFlow[14]使用分布式存儲(chǔ)系統(tǒng)WheelFS[21]提供的故障檢測機(jī)制檢測控制器故障,當(dāng)某個(gè)控制器發(fā)生故障后將受影響的交換機(jī)重分配到臨近的控制器; ONOS[15]在網(wǎng)絡(luò)構(gòu)建時(shí)就將每個(gè)交換機(jī)連接到多個(gè)控制器來應(yīng)對控制器故障。

1.4 控制器放置問題

分布式SDN控制平面在過去幾年受到廣泛關(guān)注并發(fā)展迅速,研究人員開發(fā)了多種分布式SDN控制平臺(tái)[13-18]解決了分布式SDN控制平面的設(shè)計(jì)與實(shí)現(xiàn)問題,但是分布式控制平面在實(shí)際部署時(shí)還需要考慮以下幾個(gè)問題: (1)使用多少個(gè)控制器實(shí)例; (2)控制器實(shí)例的放置位置; (3)每個(gè)控制器管理哪些交換機(jī)。這些問題統(tǒng)稱為控制器放置問題(Controller Placement Problem,CPP)。

控制器的放置對SDN的性能、可靠性和成本等方面產(chǎn)生重要影響。例如,控制器的放置位置和交換機(jī)到控制器的分配會(huì)影響控制平面與數(shù)據(jù)平面之間的時(shí)延; 控制器與交換機(jī)之間的連接以及備用路徑和備用控制器的選取也會(huì)影響網(wǎng)絡(luò)的可靠性; 控制器的數(shù)量以及交換機(jī)到控制器的分配和連接也會(huì)影響網(wǎng)絡(luò)的成本與能耗。

控制器放置問題由 Heller等人[22]首次提出,他們研究了 WAN中控制器的數(shù)量和位置對控制器與交換機(jī)之間傳播時(shí)延的影響,目標(biāo)是最小化傳播時(shí)延,并通過將該問題等同于選址問題[23],證明了CPP是NP難問題。WAN是使用分布式SDN控制平面的一個(gè)重要場景,并且WAN的網(wǎng)絡(luò)拓?fù)湎啾葦?shù)據(jù)中心等網(wǎng)絡(luò)的拓?fù)涓訌?fù)雜和多樣,研究人員提出了多種WAN中的控制器放置方案。因此,本文主要關(guān)注WAN中的控制器放置問題,具體模型如下:

WAN拓?fù)溆梢粋€(gè)無向圖G(V,E)表示,其中,V表示節(jié)點(diǎn)(即交換機(jī))集合,E表示邊(即鏈路)集合。距離矩陣D,dv,u∈D表示節(jié)點(diǎn)v和u(v,u∈V)之間的最短距離,通常使用最短路徑時(shí)延或者最小跳數(shù)表示。k表示控制器數(shù)量,P表示k個(gè)控制器的放置位置集合,所以,控制器的放置位置滿足P?V,即放置于網(wǎng)絡(luò)中的節(jié)點(diǎn)位置?？刂破鞣胖脝栴}是在給定的網(wǎng)絡(luò)G中,確定控制器的數(shù)量k、控制器的放置位置P以及交換機(jī)到控制器的分配A:V→P,從而使得預(yù)定義的目標(biāo)函數(shù)fi(i∈ {i,… ,J})達(dá)到最優(yōu)。

本文對控制器放置問題進(jìn)行深入調(diào)研,主要貢獻(xiàn)總結(jié)如下:

(1) 介紹了SDN以及分布式SDN控制平面的優(yōu)勢及面臨的挑戰(zhàn),并闡述控制器放置問題的重要性;

(2) 歸納總結(jié)了控制器放置問題的優(yōu)化指標(biāo),并從含義、重要性、分類、計(jì)算方法和影響因素等方面對各指標(biāo)進(jìn)行詳細(xì)分析;

(3) 根據(jù)多目標(biāo)的權(quán)衡方式對已有研究提出的控制器放置方案進(jìn)行歸類、分析與總結(jié);

(4) 總結(jié)了控制器放置問題中仍然存在的問題,為該領(lǐng)域的后續(xù)研究提供參考。

其余部分的組織結(jié)構(gòu)如下: 第 2節(jié)介紹了控制器放置問題的優(yōu)化指標(biāo); 第 3節(jié)對已有的控制器放置方案進(jìn)行分類和詳細(xì)介紹; 第 4節(jié)給出未來的研究展望; 第5節(jié)總結(jié)全文。

2 優(yōu)化指標(biāo)

控制器放置問題的優(yōu)化目標(biāo)包括最大化性能(主要指最小化時(shí)延,包括制器與交換機(jī)間時(shí)延和控制器間時(shí)延)、優(yōu)化控制器負(fù)載、最大化可靠性以及最小化成本與能耗(包括部署成本、管理成本和能量消耗)等多個(gè)方面。本節(jié)從定義、重要性、分類、計(jì)算方法和影響因素等方面對相關(guān)指標(biāo)進(jìn)行詳細(xì)介紹。

2.1 時(shí)延

網(wǎng)絡(luò)信息的收集和指令的下發(fā)等多種SDN網(wǎng)絡(luò)管控功能的執(zhí)行都需要控制器與交換機(jī)之間頻繁的通信,控制器之間也需要經(jīng)常通信以進(jìn)行狀態(tài)同步和管理協(xié)調(diào)。控制器與交換機(jī)間時(shí)延和控制器間時(shí)延對SDN網(wǎng)絡(luò)的性能有重要影響。時(shí)延主要包括以下四部分:

(1) 傳輸時(shí)延是指發(fā)送端將數(shù)據(jù)包發(fā)送到鏈路上的時(shí)間,通常表示為數(shù)據(jù)包的長度與鏈路帶寬的比值,其中,鏈路帶寬由最小傳輸速率的網(wǎng)絡(luò)接口決定。

(2) 傳播時(shí)延是指數(shù)據(jù)從鏈路的源端傳播到目的端的時(shí)間,可表示為鏈路的長度與鏈路中信號的傳播速度的比值。

(3) 排隊(duì)時(shí)延包括交換機(jī)的排隊(duì)時(shí)延和控制器的排隊(duì)時(shí)延。交換機(jī)的排隊(duì)時(shí)延是指數(shù)據(jù)包進(jìn)入交換機(jī)之后在輸入隊(duì)列中等待處理以及在確定轉(zhuǎn)發(fā)端口之后在輸出隊(duì)列中排隊(duì)等待轉(zhuǎn)發(fā)的時(shí)間。控制器的排隊(duì)時(shí)延是指數(shù)據(jù)包進(jìn)入控制器后等待處理的時(shí)間。排隊(duì)時(shí)延與設(shè)備的負(fù)載和處理性能有關(guān)。

(4) 處理時(shí)延包括控制器處理時(shí)延和交換機(jī)處理時(shí)延,指設(shè)備收到數(shù)據(jù)包后進(jìn)行分析頭部、提取數(shù)據(jù)和查找適當(dāng)路由等操作的時(shí)間,由設(shè)備的負(fù)載與性能決定。

以上四類時(shí)延在不同類型的網(wǎng)絡(luò)中具有不同的權(quán)重。在地理位置集中且?guī)捿^小的局域網(wǎng)中,傳輸時(shí)延占主導(dǎo)地位,而傳播時(shí)延可以忽略不計(jì)。在WAN中,網(wǎng)絡(luò)跨越較廣的地理范圍,并使用具有高性能線速轉(zhuǎn)發(fā)能力的交換機(jī)和高帶寬容量的鏈路,且流路徑請求消息的長度相對較小,因此傳輸時(shí)延、排隊(duì)時(shí)延和處理時(shí)延可以忽略不計(jì),傳播時(shí)延是主要因素,通常使用傳播時(shí)延作為控制器與交換機(jī)間時(shí)延以及控制器間時(shí)延的度量。

2.1.1 控制器與交換機(jī)間時(shí)延

控制器與交換機(jī)間時(shí)延會(huì)影響控制平面的決策速度和數(shù)據(jù)平面的響應(yīng)速度,進(jìn)而影響業(yè)務(wù),尤其是實(shí)時(shí)業(yè)務(wù)(例如鏈路故障的發(fā)現(xiàn)與恢復(fù)),因此需要最小化控制器與交換機(jī)間時(shí)延?？刂破髋c交換機(jī)間時(shí)延包括以下5個(gè)指標(biāo):

(1) 無故障時(shí)平均傳播時(shí)延

無故障時(shí)控制器與交換機(jī)間平均傳播時(shí)延是指控制器與交換機(jī)間傳播時(shí)延的均值,如式(1)所示[22,24-25],該式隱含地假設(shè)交換機(jī)到控制器的分配基于最近分配。若明確指定了交換機(jī)到控制器的特定分配,平均傳播時(shí)延需要按照式(2)[25]進(jìn)行計(jì)算,其中A(v)表示為交換機(jī)v分配的控制器。優(yōu)化目標(biāo)是從所有可能的放置方案中尋找最優(yōu)的放置使平均傳播時(shí)延最小。平均時(shí)延隱藏了最大時(shí)延,可能出現(xiàn)某些交換機(jī)與控制器間時(shí)延過大的情況。

(2) 無故障時(shí)最大傳播時(shí)延

無故障時(shí)控制器與交換機(jī)間最大傳播時(shí)延是指控制器與交換機(jī)間傳播時(shí)延的最大值。與平均傳播時(shí)延的計(jì)算類似,式(3)[22,24,26-28]基于最近分配,而式(4)[29]是更為一般的計(jì)算公式。最大傳播時(shí)延反映了時(shí)延的最差情況,能夠保證所有時(shí)延不超過該最大值。因此最大傳播時(shí)延常用來作為優(yōu)化指標(biāo)(即最小化最大傳播時(shí)延)或作為其他優(yōu)化目標(biāo)的約束條件(例如在滿足最大傳播時(shí)延約束下最小化成本)。

(3) 控制器故障時(shí)平均傳播時(shí)延

當(dāng)控制器發(fā)生故障時(shí),可以使用故障轉(zhuǎn)移機(jī)制,例如基于正常最短路徑路由的備份分配,將之前連接到該故障控制器的所有交換機(jī)重新分配到距這些交換機(jī)第二近的控制器。但是將交換機(jī)分配到新的控制器可能會(huì)導(dǎo)致更高的時(shí)延,因此在控制器放置還應(yīng)考慮控制器發(fā)生故障時(shí)的時(shí)延情況?？紤]最多k-1個(gè)控制器故障的所有可能場景(包括無故障場景),X表示這些場景中無故障控制器的放置,則控制器故障時(shí)控制器與交換機(jī)間平均傳播時(shí)延如式(5)所示[24]。

(4) 控制器故障時(shí)最大傳播時(shí)延

與無故障時(shí)的平均傳播時(shí)延類似,控制器故障時(shí)的平均傳播時(shí)延反映的是整體情況,會(huì)掩蓋時(shí)延的最差情況,因此需要考慮控制器故障時(shí)的最大傳播時(shí)延,如式(6)所示[24,27]。

(5) 交換機(jī)或鏈路故障時(shí)最大傳播時(shí)延

不同的交換機(jī)或鏈路故障構(gòu)成不同的故障場景,所有故障場景與無故障場景組成了網(wǎng)絡(luò)場景集合,由T表示。網(wǎng)絡(luò)場景t發(fā)生的概率為rt,交換機(jī)或鏈路故障時(shí)控制器與交換機(jī)間最大傳播時(shí)延如式(7)所示[30]。由于交換機(jī)或鏈路故障可能會(huì)導(dǎo)致某些交換機(jī)與所有控制器發(fā)生斷連,這些交換機(jī)與控制器間的時(shí)延可視為無限大,為了便于分析,為該情況增加一個(gè)懲罰性的時(shí)延值[30]。

2.1.2 控制器間時(shí)延

在分布式 SDN控制平面中,控制器之間: (1)需要經(jīng)常通信來獲得全局一致的網(wǎng)絡(luò)狀態(tài)信息,確保做出正確的管理決策; (2)需要進(jìn)行協(xié)調(diào)以進(jìn)行跨域的操作; (3)需要狀態(tài)同步和協(xié)調(diào),用于網(wǎng)絡(luò)故障的發(fā)現(xiàn)與恢復(fù)。因此,需要最小化控制器間的時(shí)延以提高網(wǎng)絡(luò)管理效率?？刂破鏖g的平均傳播時(shí)延和最大傳播時(shí)延分別如式(8)[24]和(9)[24,27]所示。

2.2 控制器負(fù)載

控制器的負(fù)載主要包括四部分[29]: (1)處理交換機(jī)的流路徑請求事件(簡稱流路徑請求負(fù)載); (2)維護(hù)本地網(wǎng)絡(luò)視圖; (3)與其他控制器通信獲得全網(wǎng)視圖;(4)將應(yīng)用程序生成的策略轉(zhuǎn)換成流表規(guī)則并下發(fā)至交換機(jī)。流路徑請求負(fù)載通常被認(rèn)為是總負(fù)載中最重要的部分,其使用交換機(jī)的流路徑請求率進(jìn)行度量。

控制器的負(fù)載過大將顯著增加控制器的處理時(shí)延[7],進(jìn)而增加控制器與交換機(jī)之間的總通信時(shí)延。高負(fù)載的控制器由于缺少處理故障的資源,更加可能遭受攻擊,因此具有更高的故障概率,甚至可能導(dǎo)致其他控制器的級聯(lián)故障[31]。在控制器放置時(shí)要合理地為控制器分配負(fù)載,相關(guān)指標(biāo)包括控制器能力約束和控制器負(fù)載均衡兩大類。

2.2.1 控制器能力約束

受處理器、內(nèi)存和帶寬等資源的限制,控制器的處理能力是有限的?？刂破鞯呢?fù)載不應(yīng)超過其能力[29,32-34],即交換機(jī)到控制器的分配應(yīng)滿足控制器能力約束,如式(10)所示[29],其中l(wèi)v表示交換機(jī)的流路徑請求率,D(p)表示控制器p所管理的所有交換機(jī)。為了與考慮備用的控制器能力約束相區(qū)分,該約束也被稱為不考慮備用的控制器能力約束。

為了應(yīng)對突發(fā)流量或由于故障轉(zhuǎn)移機(jī)制導(dǎo)致的負(fù)載增加,可以為控制器預(yù)留一部分能力作為備用[35]。預(yù)留比例由βp表示,則考慮備用的控制器能力約束如式(11)所示。

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

控制器放置時(shí),不但要避免控制器負(fù)載超過其能力,還應(yīng)該很好地平衡控制器間的負(fù)載分配,保證控制平面高效地運(yùn)行。與控制器負(fù)載均衡相關(guān)的指標(biāo)包括以下四個(gè)。

(1) 考慮負(fù)載均衡的控制器負(fù)載約束

控制器負(fù)載分配最理想的情形是每個(gè)控制器都分配數(shù)量相同的負(fù)載,但由于交換機(jī)可能具有不同的流路徑請求率,且控制器的負(fù)載通常是以交換機(jī)為單位進(jìn)行分配,很難使得各控制器間的負(fù)載完全均衡。因此,可以利用考慮負(fù)載均衡的控制器負(fù)載約束來限制控制器的負(fù)載分配,如式(12)所示[36],τ作為調(diào)節(jié)因子對約束進(jìn)行微調(diào)。

(2) 無故障時(shí)控制器間負(fù)載最大差值

考慮負(fù)載均衡的控制器負(fù)載約束只設(shè)置了控制器負(fù)載的上界。在控制器放置過程中,不僅要避免出現(xiàn)一部分控制器負(fù)載過大的情況,還要避免一部分控制器負(fù)載過低,以提高控制平面的資源利用率。控制器負(fù)載的不均衡情況使用控制器的最大負(fù)載與最小負(fù)載的差值來描述,如式(13)所示[24-25,27],這里的目標(biāo)是最小化控制器間負(fù)載最大差值。

(3) 控制器故障時(shí)控制器間負(fù)載最大差值

當(dāng)控制器發(fā)生故障時(shí),故障控制器管理的交換機(jī)會(huì)通過故障轉(zhuǎn)移機(jī)制分配到其他正常運(yùn)行的控制器。交換機(jī)到控制器的重新分配會(huì)影響控制器的負(fù)載?？刂破鞴收蠒r(shí)控制器間的負(fù)載情況也由負(fù)載最大差值反映,如式(14)所示[24,27]。其中,Y表示最多k-2個(gè)控制器發(fā)生故障時(shí)的無故障控制器。優(yōu)化目標(biāo)是最小化正常運(yùn)行的控制器間的負(fù)載最大差值。

(4) 控制器負(fù)載率方差

控制器間負(fù)載最大差值反映的是控制器負(fù)載均衡情況,但卻沒有考慮控制器的能力約束。將控制器負(fù)載與控制器能力的比值定義為控制器利用率,也即控制器負(fù)載率[37],用來反映控制器的負(fù)載占用情況并設(shè)置其最大約束為1。使用所有控制器負(fù)載率的方差來表示考慮控制器能力的控制器的負(fù)載均衡情況,如式(15)所示。

2.3 可靠性

在SDN中,交換機(jī)與控制器通過標(biāo)準(zhǔn)的傳輸層安全協(xié)議(TLS)或傳輸控制協(xié)議(TCP)連接進(jìn)行通信,控制器之間也需要連接通信以進(jìn)行控制平面的協(xié)調(diào)。交換機(jī)與控制器以及控制器之間的連接路徑統(tǒng)稱為控制路徑,所有控制路徑構(gòu)成 SDN的控制網(wǎng)絡(luò)[13]。

網(wǎng)絡(luò)運(yùn)行過程中,由于軟件缺陷、惡意攻擊、配置錯(cuò)誤、硬件故障和斷電等原因會(huì)導(dǎo)致網(wǎng)絡(luò)組件發(fā)生故障,可能會(huì)使部分控制器路徑發(fā)生故障?？刂坡窂焦收峡赡軙?huì)造成控制平面與數(shù)據(jù)平面的斷連,從而使控制平面失去對部分?jǐn)?shù)據(jù)平面的管控能力,可能會(huì)導(dǎo)致數(shù)據(jù)平面嚴(yán)重的丟包和性能下降。此外,控制路徑故障也可能會(huì)導(dǎo)致控制平面中控制器之間的斷連,從而影響控制器之間的協(xié)同。因此,在控制器放置時(shí)應(yīng)該最大化控制網(wǎng)絡(luò)的可靠性,進(jìn)而提高整個(gè)SDN的可靠性和性能。

網(wǎng)絡(luò)組件故障主要分為兩種類型:(1)數(shù)據(jù)平面故障包括鏈路故障和交換機(jī)故障。鏈路故障表示經(jīng)過故障鏈路的流量不能再通過該鏈路進(jìn)行傳輸,交換機(jī)故障表示該交換節(jié)點(diǎn)無法發(fā)送、響應(yīng)或轉(zhuǎn)發(fā)任何數(shù)據(jù)包。(2)控制平面故障是指控制器實(shí)例不再具有任何控制功能。

網(wǎng)絡(luò)組件發(fā)生故障后,可以通過故障轉(zhuǎn)移機(jī)制避免或減小故障對控制網(wǎng)絡(luò)造成的影響。故障轉(zhuǎn)移機(jī)制主要包括以下兩種:(1)備用路徑:交換機(jī)與分配的控制器之間使用多條路徑進(jìn)行連接,在主控制路徑發(fā)生故障后(由數(shù)據(jù)平面故障導(dǎo)致),交換機(jī)可以通過備用路徑與控制器進(jìn)行連接,從而維持控制平面與數(shù)據(jù)平面的正常通信,提高控制網(wǎng)絡(luò)的可靠性?？梢允褂玫竭_(dá)控制器的任何路徑作為備用路徑(例如節(jié)點(diǎn)不相交路徑、最短路徑或最寬路徑)。(2)備用控制器:OpenFlow 1.2提出多控制器方案,為控制器賦予了不同角色,使交換機(jī)可以通過主/從連接的方式連接到多個(gè)控制器。當(dāng)交換機(jī)與主控制器失去連接時(shí)(主控制器發(fā)生故障或備用路徑全部失效),備用(從)控制器可以接管該交換機(jī),保證對網(wǎng)絡(luò)的正常管控。備用控制器可以是多個(gè)控制器,備用控制器構(gòu)成的備用控制器列表指定了交換機(jī)連接到這些控制器實(shí)例的順序。

根據(jù)是否使用故障轉(zhuǎn)移機(jī)制,控制網(wǎng)絡(luò)的可靠性分為無故障轉(zhuǎn)移機(jī)制的可靠性和有故障轉(zhuǎn)移機(jī)制的可靠性兩類。

2.3.1 無故障轉(zhuǎn)移機(jī)制的可靠性

無故障轉(zhuǎn)移機(jī)制的可靠性指不考慮故障轉(zhuǎn)移機(jī)制時(shí)控制網(wǎng)絡(luò)正常運(yùn)行的能力。在網(wǎng)絡(luò)中,交換機(jī)、鏈路或控制器都有一定的故障概率,進(jìn)而會(huì)導(dǎo)致控制路徑故障。故障的控制路徑越多,對控制網(wǎng)絡(luò)的影響越嚴(yán)重。因此在控制器放置時(shí)需要最小化控制路徑的故障比例或概率,從而提高控制網(wǎng)絡(luò)的可靠性。無故障轉(zhuǎn)移機(jī)制的可靠性包括以下5個(gè)指標(biāo):

(1) 故障控制路徑預(yù)期比例

在物理網(wǎng)絡(luò)中,故障場景多種多樣,故障場景之間彼此獨(dú)立,每個(gè)故障場景都可能影響控制網(wǎng)絡(luò)中部分控制路徑的狀態(tài),可以采用基于原因的可靠性分析模型[38]進(jìn)行可靠性分析。網(wǎng)絡(luò)場景集合(包括無故障場景和所有故障場景)由S表示,場景s發(fā)生的概率為rs,且會(huì)導(dǎo)致qs條控制路徑中斷。使用故障控制路徑的預(yù)期比例來描述控制網(wǎng)絡(luò)的可靠性,如式(16)所示[39],目標(biāo)是最小化故障控制路徑預(yù)期比例,其中m表示控制路徑的總數(shù)。

(2) 有效控制路徑預(yù)期比例

有效控制路徑預(yù)期比例是指在所有網(wǎng)絡(luò)場景中無故障控制路徑的平均比例,如式(17)所示[40],優(yōu)化目標(biāo)是最大化有效控制路徑預(yù)期比例,與式(16)的關(guān)系是ε(P) = 1 -δ(P)。

(3) 控制路徑故障概率

與前兩個(gè)指標(biāo)基于原因的分析不同,Zhang等人[41]分析單條控制路徑的故障概率,控制路徑的故障概率與該路徑中節(jié)點(diǎn)和鏈路的故障概率有關(guān)。Zei表示鏈路ei的故障概率,Zvj表示節(jié)點(diǎn)vj的故障概率,節(jié)點(diǎn)a到b之間控制路徑Ra,b的故障概率Za,b如式(18)所示[41]。優(yōu)化目標(biāo)是最小化控制路徑平均故障概率或最小化控制路徑最大故障概率。

(4) 控制網(wǎng)絡(luò)有效概率

控制路徑故障概率反映的是單條控制路徑的可靠性,將所有控制路徑正常運(yùn)行概率的乘積定義為控制網(wǎng)絡(luò)有效概率,來評價(jià)整個(gè)網(wǎng)絡(luò)的可靠性,如式(19)[37]所示,目標(biāo)是最大化控制網(wǎng)絡(luò)有效概率。

(5) 斷連交換機(jī)數(shù)

交換機(jī)與控制器間的控制路徑故障會(huì)使交換機(jī)與控制器之間發(fā)生斷連,交換機(jī)將不再受控制器的管控,使用斷連的交換機(jī)數(shù)來反映控制網(wǎng)絡(luò)的可靠性。在所有網(wǎng)絡(luò)場景S中,平均斷連交換機(jī)數(shù)和最大斷連交換機(jī)數(shù)分別如式(20)和(21)所示。其中,表示在場景s中,交換機(jī)v是否與控制器A(v)發(fā)生斷連,若是則為 1,否則為 0,目標(biāo)是最小化平均或最大斷連交換機(jī)數(shù)。

2.3.2 有故障轉(zhuǎn)移機(jī)制的可靠性

有故障轉(zhuǎn)移機(jī)制的可靠性是指使用故障轉(zhuǎn)移機(jī)制時(shí)控制網(wǎng)絡(luò)面對故障仍能維持正常運(yùn)行的能力,即維持交換機(jī)與控制器以及控制器之間連接的能力,也被稱為彈性、恢復(fù)性或生存性。有故障轉(zhuǎn)移機(jī)制的可靠性的度量指標(biāo)包括以下4種:

(1) 交換機(jī)與控制器間的連通性

交換機(jī)與控制器間的連通性是指交換機(jī)與控制器間不相交路徑數(shù),這些路徑均可以作為交換機(jī)與控制器間的備用路徑。wp,v表示控制器p與交換機(jī)v之間不相交路徑的數(shù)量,若交換機(jī)v不屬于控制器p的管理域,則該值為0。交換機(jī)與其分配的控制器間不相交路徑數(shù)的平均值如式(22)所示[35]。交換機(jī)與控制器間的連通性越大,表示可用的備用路徑數(shù)越多,從多種故障場景中維持交換機(jī)與控制平面連通的可能性越大,因此在控制器放置時(shí)要最大化交換機(jī)與控制器間的連通性。

(2) 控制路徑平均長度

為了減少故障轉(zhuǎn)移機(jī)制的執(zhí)行時(shí)間,備用路徑需要提前進(jìn)行配置,且主控制路徑和備用控制路徑的選擇需要同時(shí)優(yōu)化,控制路徑(包括主控制路徑和備用控制路徑)的平均長度如式(23)所示[42],其中uv,A(v)表示交換機(jī)v與其分配的控制器之間的主控制路徑的長度,mv,A(v)表示交換機(jī)v與其分配的控制器之間的備用控制路徑的長度。目標(biāo)是最小化控制路徑平均長度?？紤]到傳播時(shí)延與鏈路長度是線性關(guān)系,最小化控制路徑長度等同于最小化控制器與交換機(jī)間時(shí)延。鏈路的故障概率通常也與鏈路長度成正比,因此最小化控制路徑長度也可視為最小化控制路徑的故障概率。

(3) 故障控制路徑預(yù)期比例

當(dāng)網(wǎng)絡(luò)發(fā)生故障時(shí),即使使用故障轉(zhuǎn)移機(jī)制,還是可能出現(xiàn)交換機(jī)與控制器或控制器之間沒有可用連接的情況,將這種情況稱為廣義的控制路徑故障?？紤]所有網(wǎng)絡(luò)場景S,ps表示受場景s中的網(wǎng)絡(luò)故障影響的控制路徑的條件故障概率,與使用的故障轉(zhuǎn)移機(jī)制有關(guān),θs表示以故障節(jié)點(diǎn)為端點(diǎn)的控制路徑數(shù)量,φs表示包含故障節(jié)點(diǎn)(非端點(diǎn))的控制路徑數(shù)量,使用故障轉(zhuǎn)移機(jī)制時(shí)故障控制路徑的預(yù)期比例如式(24)所示[43]。目標(biāo)是最小化故障控制路徑預(yù)期比例。

(4) 無控制器節(jié)點(diǎn)數(shù)

控制器故障時(shí),受影響的交換機(jī)會(huì)連接到備用控制器,只要存在至少一個(gè)正常運(yùn)行的控制器,數(shù)據(jù)平面都可以維持與控制平面之間的連接。當(dāng)數(shù)據(jù)平面發(fā)生故障時(shí),網(wǎng)絡(luò)拓?fù)浒l(fā)生改變,可能導(dǎo)致某些交換機(jī)與控制平面發(fā)生斷連。這些斷連的交換機(jī)(至少與另一個(gè)斷連交換機(jī)相連)雖仍然可以繼續(xù)轉(zhuǎn)發(fā)網(wǎng)絡(luò)中已有的流量,但是不能再轉(zhuǎn)發(fā)新的流量或接收控制器的其他指令,這種交換機(jī)被稱為無控制器節(jié)點(diǎn)。對于特定的控制器放置P,考慮所有網(wǎng)絡(luò)場景S,最大無控制器節(jié)點(diǎn)數(shù)如式(25)所示[24,27],其中,Es為連通性矩陣。在場景s中,若交換機(jī)v能到達(dá)控制器p,則矩陣Es的項(xiàng)為0,否則為1。優(yōu)化目標(biāo)是最小化最大無控制器節(jié)點(diǎn)數(shù)。

2.4 成本與能耗

在控制器放置時(shí)還需要考慮部署成本、管理成本和能量消耗等指標(biāo),這些對于分布式SDN的實(shí)際部署和商用非常重要。

2.4.1 部署成本

控制器的數(shù)量影響資本支出(CAPEX)與運(yùn)營支出(OPEX),因此大多數(shù)研究考慮的是使用較少的控制器實(shí)現(xiàn)特定的優(yōu)化目標(biāo)。對于采用帶外連接方式的控制網(wǎng)絡(luò),還需要考慮鏈路的成本。控制器與鏈路的部署成本根據(jù)使用場景分為以下兩類:

(1) 靜態(tài)部署成本

靜態(tài)部署成本C指控制網(wǎng)絡(luò)構(gòu)建初期的成本,包括控制器的安裝成本Cc、控制器與交換機(jī)之間鏈路的安裝成本Cl以及控制器之間鏈路的安裝成本Ct,如式(26)所示[32]。其中,控制器的安裝成本與控制器的價(jià)格有關(guān),鏈路的安裝成本與鏈路的單價(jià)和鏈路的長度有關(guān)。優(yōu)化目標(biāo)是最小化靜態(tài)部署成本。

(2) 網(wǎng)絡(luò)擴(kuò)張成本

為了滿足用戶和業(yè)務(wù)增長的需要,網(wǎng)絡(luò)需要不斷擴(kuò)張,即為數(shù)據(jù)平面添加更多的網(wǎng)絡(luò)設(shè)備。為此,控制網(wǎng)絡(luò)也需要進(jìn)行調(diào)整以滿足網(wǎng)絡(luò)控制在性能和可靠性等方面的需求。控制網(wǎng)絡(luò)變化的成本定義為網(wǎng)絡(luò)擴(kuò)張成本C′,包括控制器的安裝和移除成本、控制器與交換機(jī)間鏈路的安裝或移除成本Cl′以及控制器之間鏈路的安裝或移除成本Ct′,如式(27)所示[34]。目標(biāo)是最小化網(wǎng)絡(luò)擴(kuò)張成本。

2.4.2 管理成本

管理成本主要是指網(wǎng)絡(luò)管理的通信成本,包括靜態(tài)管理成本和動(dòng)態(tài)管理成本兩類。

(1) 靜態(tài)管理成本

靜態(tài)管理成本是指控制網(wǎng)絡(luò)不發(fā)生改變時(shí)網(wǎng)絡(luò)管理的通信成本,主要包括以下三部分:

統(tǒng)計(jì)信息收集成本 Cv:控制器需要定期地收集其管理域內(nèi)交換機(jī)的端口、流表等統(tǒng)計(jì)信息。收集成本與交換機(jī)和控制器間的距離(通常由時(shí)延或跳數(shù)表示)以及查詢交換機(jī)信息的比特率有關(guān)。

流路徑設(shè)置成本 Cq:當(dāng)新流進(jìn)入交換機(jī)時(shí),由于沒有匹配的轉(zhuǎn)發(fā)規(guī)則,交換機(jī)會(huì)向控制器發(fā)送路徑設(shè)置請求消息,控制器計(jì)算該流的轉(zhuǎn)發(fā)路徑并將相應(yīng)的轉(zhuǎn)發(fā)規(guī)則下發(fā)至相關(guān)交換機(jī)。因此,流路徑設(shè)置成本包括初始路徑設(shè)置請求成本和規(guī)則安裝成本。若該流進(jìn)入其他控制器的管理域,還需要再次執(zhí)行路徑設(shè)置請求,將該成本稱為中間路徑設(shè)置請求成本。則流路徑設(shè)置成本是以上三個(gè)成本之和,與交換機(jī)的流路徑請求率、請求消息、流表安裝消息以及交換機(jī)與控制器間的距離有關(guān)。

控制器同步成本 Cs:指控制器之間信息同步的成本,與控制器之間的距離、同步數(shù)據(jù)量以及同步策略有關(guān)。

靜態(tài)管理成本CO是上述三類成本的加權(quán)和,如式(28)所示[44]。權(quán)重由運(yùn)營商根據(jù)需求來決定,優(yōu)化目標(biāo)是最小化靜態(tài)管理成本。

(2) 動(dòng)態(tài)管理成本

動(dòng)態(tài)管理成本是指控制網(wǎng)絡(luò)發(fā)生變動(dòng)時(shí)的通信成本。由于網(wǎng)絡(luò)流量變化等原因需要實(shí)時(shí)調(diào)整交換機(jī)到控制器之間的分配。交換機(jī)到控制器的重分配成本由Cr表示,與交換機(jī)到新分配的控制器之間的距離有關(guān)。動(dòng)態(tài)管理成本CO′是靜態(tài)管理成本與重分配成本的加權(quán)和,如式(29)所示[33],優(yōu)化目標(biāo)是最小化動(dòng)態(tài)管理成本。

2.4.3 能量消耗

降低控制網(wǎng)絡(luò)的能耗不僅有利于減少運(yùn)營成本支出,而且還能減少碳排放有助于環(huán)境保護(hù)?？刂凭W(wǎng)絡(luò)的能耗主要包括控制器能耗和控制鏈路能耗。

(1) 控制器能耗

控制器的能耗與控制器的數(shù)量有關(guān),在控制器放置時(shí)應(yīng)盡可能減少控制器的數(shù)量從而降低控制器能耗。此外,可以根據(jù)網(wǎng)絡(luò)中流量負(fù)載的實(shí)時(shí)變化動(dòng)態(tài)地調(diào)整控制器的數(shù)量[45],在流量負(fù)載降低時(shí)減少運(yùn)行控制器的數(shù)量從而降低控制器能耗。

(2) 控制鏈路能耗

控制鏈路能耗與控制網(wǎng)絡(luò)中使用的鏈路數(shù)有關(guān),如式(30)所示[46],優(yōu)化目標(biāo)是最小化控制鏈路的能耗,其中,二元變量χe表示鏈路e是否屬于控制鏈路,若是則為1,否則為0,ρe表示鏈路e的能量消耗。

為了進(jìn)一步減少控制鏈路能耗,在網(wǎng)絡(luò)運(yùn)行的非高峰時(shí)期,可以將某些交換機(jī)端口置為睡眠模式以使對應(yīng)的鏈路進(jìn)入睡眠狀態(tài)[47]。

2.5 小結(jié)

SDN控制器放置問題的優(yōu)化指標(biāo)及其主要影響因素如表1所示,所有優(yōu)化指標(biāo)均與網(wǎng)絡(luò)的拓?fù)溆忻芮械年P(guān)系?？刂破髋c交換機(jī)間時(shí)延以及控制器間時(shí)延的指標(biāo)包括平均時(shí)延和最大時(shí)延兩大類。平均時(shí)延反映時(shí)延的整體情況,但隱藏了最差的情況,而最大時(shí)延可以保證每個(gè)控制器與交換機(jī)間的時(shí)延或控制器間的時(shí)延符合預(yù)期的需求。WAN中的時(shí)延通常只考慮傳播時(shí)延,在后文中如果不做特別說明,時(shí)延泛指傳播時(shí)延,且指無故障時(shí)的傳播時(shí)延。并且控制器能力約束泛指不考慮備用的控制器能力約束。接下來,首先分析這些優(yōu)化指標(biāo)之間的內(nèi)在關(guān)系,然后對已有的SDN控制器放置方案進(jìn)行歸類并詳細(xì)介紹。

3 控制器放置方案

SDN控制器放置問題通常是一個(gè)多目標(biāo)優(yōu)化問題,且大多數(shù)目標(biāo)之間具有競爭關(guān)系。競爭關(guān)系是指對一個(gè)目標(biāo)進(jìn)行優(yōu)化時(shí),優(yōu)化過程會(huì)對另一個(gè)目標(biāo)產(chǎn)生負(fù)面影響。由于競爭關(guān)系的存在,不存在對所有目標(biāo)均為最優(yōu)的控制器放置方案,決策者需要對這些目標(biāo)進(jìn)行權(quán)衡。以下是 5個(gè)典型的競爭關(guān)系和三類權(quán)衡方式。

表1 SDN控制放置問題的優(yōu)化指標(biāo)及其主要影響因素Table 1 Optimization indexes and main influencing factors of SDN controller placement problem

(1) 優(yōu)化目標(biāo)的競爭關(guān)系

最小化無故障時(shí)控制器與交換機(jī)間時(shí)延,最小化控制器故障時(shí)控制器與交換機(jī)間時(shí)延:為了最小化無故障時(shí)控制器與交換機(jī)間時(shí)延,控制器需要分散地放置在網(wǎng)絡(luò)中。為了最小化控制器故障時(shí)控制器與交換機(jī)間時(shí)延,所有控制器都趨向于放置在網(wǎng)絡(luò)中心的位置,當(dāng)大部分控制器發(fā)生故障后,無故障控制器可以接管相應(yīng)的交換機(jī)并使控制器與交換機(jī)間時(shí)延盡可能小。

最小化控制器與交換機(jī)間時(shí)延,最小化控制器間時(shí)延:將控制器分散地放置在網(wǎng)絡(luò)中會(huì)降低控制器與交換機(jī)間時(shí)延,但是會(huì)導(dǎo)致控制器間時(shí)延增加。為了最小化控制器間時(shí)延而將控制器聚集在一起的放置會(huì)導(dǎo)致控制器與交換機(jī)間時(shí)延的增加。

最小化控制器與交換機(jī)間時(shí)延,最大化控制器負(fù)載均衡:由于網(wǎng)絡(luò)具有不規(guī)則的拓?fù)?將交換機(jī)連接到距離最近的控制器以最小化控制器與交換機(jī)間時(shí)延的方案難以保證控制器的負(fù)載均衡。為了最大化控制器的負(fù)載均衡,可能需要將交換機(jī)連接到距離較遠(yuǎn)的控制器,從而導(dǎo)致控制器與交換機(jī)間時(shí)延增加。

最大化可靠性,最小化時(shí)延:為了提高可靠性,控制器放置時(shí)主要考慮網(wǎng)絡(luò)組件的故障概率和控制路徑的故障概率,可能會(huì)導(dǎo)致控制器與交換機(jī)以及控制器間的時(shí)延增加。此外,為了進(jìn)一步提高可靠性,在故障發(fā)生時(shí)利用故障轉(zhuǎn)移機(jī)制將交換機(jī)通過當(dāng)前可用的路徑連接到可用的控制器,可能會(huì)進(jìn)一步增加控制器與交換機(jī)間的時(shí)延。

最小化成本與能耗,最小化時(shí)延(或最大化可靠性):為了最小化成本與能耗,需要盡量減少放置控制器的數(shù)量以及控制路徑中使用的鏈路數(shù)量。但是為了降低時(shí)延或提高可靠性,趨向于在網(wǎng)絡(luò)中部署大量的控制器并使用大量的控制路徑來實(shí)現(xiàn)性能或可靠性的最優(yōu)化。

(2) 優(yōu)化目標(biāo)的權(quán)衡方式

權(quán)衡方式1: 設(shè)置約束。通常側(cè)重于對其中一個(gè)目標(biāo)進(jìn)行優(yōu)化,而對其他指標(biāo)設(shè)置約束,例如設(shè)置最大時(shí)延約束、控制器可以管理的交換機(jī)個(gè)數(shù)、控制器間負(fù)載最大差值約束或故障容忍率等。這種權(quán)衡方式的缺點(diǎn)是需要大量的網(wǎng)絡(luò)知識來提前設(shè)置約束值,約束值的設(shè)置不當(dāng)也會(huì)影響其他目標(biāo)的優(yōu)化結(jié)果。

權(quán)衡方式2: 設(shè)置權(quán)重。根據(jù)優(yōu)化目標(biāo)的重要程度設(shè)置對應(yīng)的權(quán)重,將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為帶權(quán)重的單目標(biāo)優(yōu)化問題。與權(quán)衡方式1類似,權(quán)重的設(shè)置需要大量的先驗(yàn)知識,并對結(jié)果產(chǎn)生重要影響。

權(quán)衡方式3: Pareto最優(yōu)。計(jì)算所有Pareto最優(yōu)結(jié)果,構(gòu)成Pareto邊界,之后,網(wǎng)絡(luò)運(yùn)營商可以根據(jù)需求選擇合適的方案。通常,稱放置方案P1是Pareto最優(yōu)的,當(dāng)且僅當(dāng)不存在放置方案P2使得對于所有的目標(biāo)函數(shù)fi(i∈ {i,… ,J})有fi(P2) 不亞于fi(P1)且至少有一個(gè)i使得fi(P2) 優(yōu)于fi(P1)。這種權(quán)衡方式的優(yōu)點(diǎn)包括: 避免先驗(yàn)地對一些指標(biāo)設(shè)置約束,這些約束可能導(dǎo)致沒有可行的放置方案; 能清晰地展示優(yōu)化目標(biāo)之間的權(quán)衡; 決策者可根據(jù)不同需求選擇適合的方案。但是該方式由于需要返回 Pareto邊界,相比權(quán)衡方式1和2更加耗時(shí)。

在已有的控制器放置問題的解決方案中,若采用權(quán)衡方式1,則可根據(jù)優(yōu)化目標(biāo)的側(cè)重將這些放置方案分為以性能為主要優(yōu)化目標(biāo)、以可靠性為主要優(yōu)化目標(biāo)和以成本與能耗為主要優(yōu)化目標(biāo)的三類放置方案。其中,性能優(yōu)化主要是指最小化時(shí)延,且根據(jù)是否考慮控制器能力約束可進(jìn)一步分為最小化無能力約束的時(shí)延和最小化有能力約束的時(shí)延這兩類方案。若放置方案使用權(quán)衡方式2或3,則這些方案統(tǒng)稱為多目標(biāo)優(yōu)化的控制器放置方案,根據(jù)使用的權(quán)衡方式,可進(jìn)一步分為帶權(quán)重和 Pareto最優(yōu)兩類多目標(biāo)放置方案。圖 3展示了控制器放置方案的分類,下面對各類方案的已有研究進(jìn)行詳細(xì)介紹。

圖3 SDN控制器放置方案分類Figure 3 Classification of SDN controller placement schemes

3.1 性能優(yōu)化

首先,介紹以性能為主要優(yōu)化目標(biāo)的控制器放置方案,包括最小化無能力約束的時(shí)延和最小化有能力約束的時(shí)延兩類,從時(shí)延、控制器負(fù)載、可靠性、成本與能耗以及算法等方面對已有方案進(jìn)行分析,如表2和3所示。

3.1.1 最小化無能力約束的時(shí)延

Heller等人[22]首次提出控制器放置問題,分別以最小化控制器與交換機(jī)間平均時(shí)延和最小化控制器與交換機(jī)間最大時(shí)延為優(yōu)化目標(biāo),研究控制器的放置對控制器與交換機(jī)間時(shí)延的影響。最小化平均時(shí)延對應(yīng)的優(yōu)化問題是最小 k-median問題[48],最小化最大時(shí)延對應(yīng)的優(yōu)化問題是最小k-center問題。他們采用窮舉法搜尋最優(yōu)的控制器放置方案,研究結(jié)果表明最小化平均時(shí)延的放置方案傾向于將控制器放置在交換機(jī)密度較高的位置,而最小化最大時(shí)延的控制器放置傾向于地理分布較為中心的位置。

Wang等人[28]提出使用網(wǎng)絡(luò)劃分的方法解決控制器放置問題,目標(biāo)是最小化控制器與交換機(jī)間最大時(shí)延。他們基于標(biāo)準(zhǔn)的 k-means聚類算法和Katsavounidis等人[54]提出的初始化方法,提出一個(gè)優(yōu)化的k-means算法,將網(wǎng)絡(luò)劃分為k個(gè)子網(wǎng),并使每個(gè)子網(wǎng)內(nèi)的控制器與其管理的交換機(jī)間的最大時(shí)延最小。仿真結(jié)果表明,相比標(biāo)準(zhǔn)的 k-means算法,所提的優(yōu)化算法可以顯著減小控制器與交換機(jī)間的最大時(shí)延。

表2 最小化無能力約束的時(shí)延的控制器放置方案Table 2 Controller placement schemes of minimizing the latency without capacity constraint

表3 最小化有能力約束的時(shí)延的控制器放置方案Table 3 Controller placement schemes of minimizing the latency with capacity constraint

Wang等人[49]在之前研究的基礎(chǔ)上,提出最小化控制器與交換機(jī)間最大傳播時(shí)延和控制器排隊(duì)時(shí)延的控制器放置方案。分布式控制平面的模型基于ONOS控制平臺(tái)[15],即交換機(jī)通過調(diào)度器與多個(gè)控制器連接,調(diào)度器用于將交換機(jī)負(fù)載分布到不同的控制器,交換機(jī)的流路徑請求在到達(dá)調(diào)度器之前需要暫存在調(diào)度器前的隊(duì)列中,暫存的時(shí)間被稱為控制器排隊(duì)時(shí)延,與控制器的處理能力和負(fù)載有關(guān)。在WAN中,相比控制器排隊(duì)時(shí)延,傳播時(shí)延在總時(shí)延中占主導(dǎo)地位,因此需要分別處理這兩種時(shí)延: 首先,使用優(yōu)化的 k-means算法[28]進(jìn)行網(wǎng)絡(luò)劃分以減小每個(gè)子網(wǎng)內(nèi)控制器到交換機(jī)間的最大傳播時(shí)延;之后,在具有大量交換機(jī)的子網(wǎng)內(nèi)放置多個(gè)控制器以減小控制器排隊(duì)時(shí)延,最終使控制器與交換機(jī)間時(shí)延滿足最大時(shí)延約束。研究結(jié)果表明所提方案相比傳統(tǒng)的k-means和k-center算法可以更有效地減小控制器與交換機(jī)間的時(shí)延。

Guo等人[30]提出兩個(gè)控制器放置模型,即考慮所有鏈路故障場景的控制器放置以及只考慮單鏈路故障的控制器放置。在鏈路故障發(fā)生后將受影響的交換機(jī)通過當(dāng)前可用路徑連接到控制器,最小化交換機(jī)與控制器間的最大傳播時(shí)延。他們提出一個(gè)貪心算法對單鏈故障的控制器放置進(jìn)行求解,該算法每次迭代選擇一個(gè)控制器放置位置,使得當(dāng)前的放置方案產(chǎn)生最小的鏈路故障時(shí)控制器與交換機(jī)間最大傳播時(shí)延。在Internet2 OS3E拓?fù)鋄55]和Cernet2拓?fù)鋄56]上的仿真結(jié)果顯示所提算法與最優(yōu)解之間的誤差不盡相同,且最大誤差達(dá)到 17.6%,但隨著放置控制器數(shù)量的增加,所提算法的誤差在兩個(gè)拓?fù)渖暇尸F(xiàn)減小的趨勢。

Alshamrani等人[50]在控制器放置時(shí)為每個(gè)交換機(jī)分配3個(gè)距離最近的控制器以應(yīng)對最多2個(gè)控制器故障的場景。目標(biāo)是最小化控制器故障時(shí)控制器與交換機(jī)間最大時(shí)延和平均時(shí)延。實(shí)驗(yàn)結(jié)果表明,當(dāng)控制器數(shù)量較少時(shí),為每個(gè)交換機(jī)分配多個(gè)控制器的方式會(huì)導(dǎo)致控制器與交換機(jī)間時(shí)延顯著增加,隨著放置控制器數(shù)量的增加,增加的時(shí)延逐漸減小,可以在可靠性和性能之間取得平衡。

Heller等人[22]和 Alshamrani等人[50]都同時(shí)研究了不同性能優(yōu)化目標(biāo)的控制器放置: 由于網(wǎng)絡(luò)拓?fù)涞牟灰?guī)則性,最小化平均時(shí)延和最小化最大時(shí)延的控制器放置結(jié)果通常是不同的。Guo等人[30]和Alshamrani等人[50]分別考慮了鏈路故障和控制器故障場景: 相比于不考慮故障場景的控制器放置,考慮故障場景的控制器放置在提高可靠性的同時(shí)會(huì)明顯增加控制器與交換機(jī)間的時(shí)延; 隨著控制器數(shù)量的增加,增加的時(shí)延會(huì)不斷減小,因此為了滿足可靠性約束,需放置盡可能多的控制器以減小控制器與交換機(jī)間時(shí)延的增加。

3.1.2 最小化有能力約束的時(shí)延

考慮控制器能力約束時(shí),最小化控制器與交換機(jī)間最大時(shí)延對應(yīng)的優(yōu)化問題是能力約束的k-center問題[57]。Yao等人[29]將該問題描述為整數(shù)規(guī)劃模型,在二分查找法中通過解決整數(shù)規(guī)劃的線性松弛確定控制器與交換機(jī)間距離的下界,之后使用整數(shù)規(guī)劃的方法進(jìn)行求解,并通過遍歷k值尋找滿足控制器能力約束的最小控制器數(shù)。在仿真中使用隨機(jī)(交換機(jī)的流請求率服從均勻分布)和熱點(diǎn)(20%的交換機(jī)為熱點(diǎn)交換機(jī))等兩種不同的流模型來模擬不同的負(fù)載場景。研究結(jié)果表明,使控制器不發(fā)生過載所需的最少控制器數(shù)在不同的負(fù)載場景中略有不同; 相比不考慮控制器能力約束的放置,考慮控制器能力約束的放置可以使用較少的控制器保證控制器不發(fā)生過載,并且產(chǎn)生較小的控制器與交換機(jī)間時(shí)延。

Hu等人[36]在考慮控制器負(fù)載均衡時(shí)分別最小化控制器與交換機(jī)間平均時(shí)延和最小化控制器與交換機(jī)間最大時(shí)延。他們使用考慮負(fù)載均衡的控制器負(fù)載約束調(diào)整控制器間的負(fù)載均衡情況,并評估考慮負(fù)載均衡時(shí)所付出的時(shí)延代價(jià),在SDN-lib[58]中的拓?fù)渖线M(jìn)行大量仿真。研究結(jié)果表明,對于只考慮最小化時(shí)延的控制器放置方案,只需增加較小的時(shí)延即可實(shí)現(xiàn)控制器之間良好的負(fù)載均衡,特別地,在Abilene拓?fù)浜虲ost266拓?fù)渖戏謩e使用5個(gè)和2個(gè)控制器進(jìn)行放置時(shí),可以在不增加時(shí)延的情況下實(shí)現(xiàn)控制器間的負(fù)載均衡。

Killi等人[51]在控制器放置時(shí)為每個(gè)交換機(jī)分配距離最近的N個(gè)控制器。當(dāng)最多N-1個(gè)控制器發(fā)生故障時(shí),故障控制器管理的交換機(jī)可以重新分配至距其最近的一個(gè)備用控制器,避免交換機(jī)與控制平面發(fā)生斷連。優(yōu)化目標(biāo)是最小化交換機(jī)與距離最近的第N個(gè)控制器間的最大時(shí)延,同時(shí)使控制器的負(fù)載滿足其能力約束。研究結(jié)果顯示,控制器發(fā)生故障后,將受影響的交換機(jī)連接到當(dāng)前可用的控制器雖然可以保證交換機(jī)到控制平面的持續(xù)連接,但是可能會(huì)導(dǎo)致交換機(jī)與控制平面間的時(shí)延過大; 在控制器放置時(shí)提前考慮可能的故障場景并為交換機(jī)分配備用控制器,可以避免故障發(fā)生之后交換機(jī)與控制平面間時(shí)延的急劇增長。

Killi等人[52]研究單控制器故障場景的控制器放置,為每個(gè)交換機(jī)分配一個(gè)距離最近的控制器作為該交換機(jī)的主控制器,選擇距離該主控制器最近的控制器作為該交換機(jī)的一個(gè)備用控制器。優(yōu)化目標(biāo)是最小化交換機(jī)與主控制器以及主控制器與備用控制器間的最大時(shí)延,并使主控制器與備用控制器均滿足能力約束。他們將該問題建模為混合整數(shù)線性規(guī)劃問題,使用模擬退火算[59]法進(jìn)行求解。模擬退火算法是基于蒙特卡洛方法的啟發(fā)式算法,將當(dāng)前解以一定的接受概率移動(dòng)到更差解,從而避免陷入局部最優(yōu),接受概率在算法迭代初期時(shí)設(shè)置較大以允許更廣泛的搜索空間,隨著迭代次數(shù)的增加,接受概率逐漸減小,有助于算法的收斂。通過經(jīng)驗(yàn)以及大量的仿真實(shí)驗(yàn)為模擬退火算法針對特定的問題模型設(shè)置合適的相關(guān)參數(shù)。研究結(jié)果表明,由于同時(shí)考慮了無故障和控制器故障場景,所提方案會(huì)略微增加交換機(jī)與主控制器間時(shí)延,但會(huì)顯著降低交換機(jī)與備用控制器間時(shí)延; 與通過CPLEX優(yōu)化器[60]獲得的最優(yōu)解相比,模擬退火算法可以使用少于一半的時(shí)間獲取近優(yōu)解。

Killi等人[53]在控制器放置時(shí)還考慮單鏈路故障場景,將受影響的交換機(jī)通過備用路徑連接到控制器,目標(biāo)是最小化鏈路故障時(shí)控制器與交換機(jī)間最大時(shí)延,并使控制器的負(fù)載滿足控制器能力約束。優(yōu)化目標(biāo)中單鏈路故障場景的最大時(shí)延和無故障場景的最大時(shí)延的權(quán)重由網(wǎng)絡(luò)運(yùn)營商決定。仿真結(jié)果表明: 無故障場景的最大時(shí)延和故障場景的最大時(shí)延具有競爭關(guān)系; 在控制器放置時(shí)為交換機(jī)設(shè)置備用路徑的方式可以降低鏈路故障發(fā)生后控制器與交換機(jī)間的最大時(shí)延,同時(shí)也降低了控制器間平均時(shí)延和最大時(shí)延。

由于控制器的處理能力有限,保證控制器負(fù)載不超過其能力的控制器放置更加符合實(shí)際場景。Killi等人[51-53]在控制器放置時(shí)還分別考慮了控制器故障場景和鏈路故障場景。提前設(shè)計(jì)備用控制器和備用路徑的方案會(huì)顯著減小網(wǎng)絡(luò)組件故障帶來的控制器與交換機(jī)間時(shí)延急劇增大,但也需要使無故障場景中的時(shí)延不受過多影響。通常使用網(wǎng)絡(luò)場景的發(fā)生概率作為同時(shí)優(yōu)化不同網(wǎng)絡(luò)場景時(shí)延的權(quán)重。

3.2 可靠性優(yōu)化

按照是否采用故障轉(zhuǎn)移機(jī)制,以可靠性為主要優(yōu)化目標(biāo)的控制器放置方案分為最大化無故障轉(zhuǎn)移機(jī)制的可靠性和最大化有故障轉(zhuǎn)移機(jī)制的可靠性兩類。

3.2.1 最大化無故障轉(zhuǎn)移機(jī)制的可靠性

從故障場景、可靠性、時(shí)延、控制器負(fù)載、成本與能耗以及算法等方面對最大化無故障轉(zhuǎn)移機(jī)制的可靠性的已有控制器放置方案進(jìn)行分析,如表4所示。

表4 最大化無故障轉(zhuǎn)移機(jī)制的可靠性的控制器放置方案Table 4 Controller placement schemes of maximizing the reliability without failover mechanism

Zhang等人[41]研究分離架構(gòu)的可靠性,考慮交換機(jī)或鏈路故障導(dǎo)致控制器與交換機(jī)間控制路徑故障的場景,目標(biāo)是在控制器放置時(shí)最小化控制器與交換機(jī)間控制路徑平均故障概率。他們首先使用基于最小割的方法將網(wǎng)絡(luò)劃分為k個(gè)子網(wǎng),目標(biāo)是最小化每個(gè)子網(wǎng)內(nèi)交換機(jī)到圖心的距離,同時(shí)最小化子網(wǎng)之間邊的數(shù)目,以提高子網(wǎng)內(nèi)交換機(jī)間的路徑多樣性。之后,將控制器放置在每個(gè)子網(wǎng)的中心交換機(jī)位置,并將子網(wǎng)內(nèi)的交換機(jī)通過最短路徑與該控制器相連。他們在環(huán)型、星型和胖樹等不同類型和規(guī)模的網(wǎng)絡(luò)拓?fù)渖线M(jìn)行大量的仿真,以尋找可靠性指標(biāo)與網(wǎng)絡(luò)拓?fù)渲g的關(guān)系,并提出一個(gè)貪心放置方案用于算法的性能對比。仿真結(jié)果表明: 基于最小割的控制器放置方案相比隨機(jī)放置和貪心放置方案具有更低的控制路徑故障概率; 控制器與交換機(jī)間控制路徑的長度越長,控制器與交換機(jī)間連接丟失的概率越高。

Hu等人[39-40]采用基于原因的可靠性分析模型分析控制網(wǎng)絡(luò)的可靠性,考慮單個(gè)交換機(jī)或單條鏈路故障導(dǎo)致的控制器與交換機(jī)或控制器間控制路徑故障的場景,目標(biāo)是最小化故障控制路徑的預(yù)期比例。他們提出兩個(gè)啟發(fā)式算法: (1)貪心算法: 基于交換機(jī)故障率選出控制器放置的候選位置,每次從候選位置中選擇一個(gè)可以產(chǎn)生最小故障控制路徑預(yù)期比例的位置放置一個(gè)控制器,設(shè)置回溯步長進(jìn)行回溯來尋找比當(dāng)前放置更優(yōu)的放置位置以避免陷入局部最優(yōu); (2)模擬退火算法: 是一個(gè)通用算法,通過大量仿真確定該算法對可靠控制器放置問題的優(yōu)化配置參數(shù)。仿真結(jié)果證實(shí)了以下結(jié)論: (1)模擬退火算法的結(jié)果優(yōu)于貪心算法; (2)若放置的控制器數(shù)量過少,較多的交換機(jī)將通過相同的鏈路與控制器相連,單個(gè)網(wǎng)絡(luò)組件(交換機(jī)或鏈路)故障會(huì)導(dǎo)致較多的控制路徑故障; 若放置的控制器數(shù)量過多,會(huì)產(chǎn)生大量的控制器間的控制路徑,組件故障也很有可能會(huì)導(dǎo)致多條控制路徑故障; (3)最大化控制網(wǎng)絡(luò)可靠性的控制器放置具有較高的控制器與交換機(jī)間時(shí)延,但滿足Heller等人[22]提出的時(shí)延上限。

Guo等人[61]按照網(wǎng)絡(luò)功能將SDN分為兩個(gè)相互依賴的網(wǎng)絡(luò): 數(shù)據(jù)轉(zhuǎn)發(fā)網(wǎng)絡(luò)(交換機(jī)與交換機(jī)之間構(gòu)成的網(wǎng)絡(luò))和控制網(wǎng)絡(luò),并使用級聯(lián)故障分析的方法分析控制器放置對控制網(wǎng)絡(luò)可靠性的影響。研究鏈路或節(jié)點(diǎn)(控制器或交換機(jī))故障導(dǎo)致控制器與交換機(jī)之間斷連的情況,目標(biāo)是在網(wǎng)絡(luò)組件故障時(shí)使控制器連接盡可能多的交換機(jī)。他們使用基于貪心的社區(qū)發(fā)現(xiàn)算法[62]將網(wǎng)絡(luò)劃分為k個(gè)子網(wǎng),在每個(gè)子網(wǎng)內(nèi)選擇到其他節(jié)點(diǎn)具有最大接近中心性的節(jié)點(diǎn)放置控制器。實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)網(wǎng)絡(luò)的可靠性與網(wǎng)絡(luò)拓?fù)涞钠骄窂介L度成反比,因此,環(huán)型網(wǎng)絡(luò)拓?fù)渚哂休^低的可靠性,而隨機(jī)網(wǎng)絡(luò)由于其平均路徑長度較短而具有較高的可靠性。

Jiménez等人[26]將控制器與交換機(jī)間控制路徑構(gòu)成的網(wǎng)絡(luò)視為一組以控制器為根的樹,在控制器放置時(shí)考慮如何構(gòu)建一組健壯樹,使所需的控制器數(shù)量最小,并最小化交換機(jī)或鏈路故障導(dǎo)致的控制器與交換機(jī)間故障控制路徑的數(shù)量,同時(shí)滿足控制器與交換機(jī)間時(shí)延約束和控制器間時(shí)延約束。他們提出名為 k-Critical的聚類算法,將具有較大節(jié)點(diǎn)度且周圍一定跳數(shù)范圍內(nèi)的節(jié)點(diǎn)數(shù)較多的節(jié)點(diǎn)作為控制器的候選節(jié)點(diǎn),構(gòu)建以控制器候選節(jié)點(diǎn)為根的樹,最小化該樹的深度以降低網(wǎng)絡(luò)故障對控制路徑造成的影響,同時(shí)使控制器與交換機(jī)間時(shí)延滿足最大時(shí)延約束。之后,對于與其他控制器時(shí)延超過時(shí)延約束的控制器,在其管理域內(nèi)添加一個(gè)控制器使控制器間時(shí)延滿足約束。研究結(jié)果表明: 使用多個(gè)控制器進(jìn)行放置可以減小控制器與交換機(jī)間時(shí)延,但是過多的控制器是不劃算的,因?yàn)闀r(shí)延的減少是微不足道的; k-Critical算法以增加控制器與交換機(jī)間的時(shí)延為代價(jià)提高了網(wǎng)絡(luò)的可靠性,由于時(shí)延滿足最大時(shí)延約束,因此該代價(jià)可以接受; 相比同規(guī)模的稀疏型網(wǎng)絡(luò),密集型網(wǎng)絡(luò)的路徑長度較短,因此具有更小的控制器與交換機(jī)間時(shí)延。

Zhang等人[41]和Jiménez等人[26]在控制器放置時(shí)考慮交換機(jī)或鏈路故障對控制器與交換機(jī)間控制路徑的影響。Hu等人[39-40]研究了交換機(jī)或鏈路故障對整個(gè)控制網(wǎng)絡(luò)的影響。Guo等人[61]還考慮了控制器故障場景?？刂坡窂降拈L度越短,控制路徑的故障概率越低。最大化可靠性的控制器放置方案通常具有較高的控制器與交換機(jī)間時(shí)延,可以通過設(shè)置最大時(shí)延約束進(jìn)行限制。

3.2.2 最大化有故障轉(zhuǎn)移機(jī)制的可靠性

從故障場景、故障轉(zhuǎn)移機(jī)制、可靠性、時(shí)延、控制器負(fù)載、成本與能耗以及算法等方面對最大化有故障轉(zhuǎn)移機(jī)制的可靠性的控制器放置方案進(jìn)行分析,如表5所示。

表5 最大化有故障轉(zhuǎn)移機(jī)制的可靠性的控制器放置方案Table 5 Controller placement schemes of maximizing the reliability with failover mechanism

Hock等人[27]考慮最多兩個(gè)交換機(jī)或兩條鏈路同時(shí)發(fā)生故障的場景,給定控制器的數(shù)量,通過窮舉法尋找最小化最大無控制器節(jié)點(diǎn)數(shù)的放置方案。無控制器節(jié)點(diǎn)數(shù)通常會(huì)隨著控制器數(shù)量的增加而減少,因此還需要尋找不出現(xiàn)無控制器節(jié)點(diǎn)的最少控制器數(shù)的放置,搜尋方法基于以下假設(shè): 在兩個(gè)相鄰的無控制器節(jié)點(diǎn)位置至少放置一個(gè)控制器以保證在故障發(fā)生時(shí)這兩個(gè)交換機(jī)節(jié)點(diǎn)不會(huì)成為無控制器節(jié)點(diǎn)。仿真結(jié)果表明: 避免出現(xiàn)無控制器節(jié)點(diǎn)的控制器放置會(huì)導(dǎo)致控制器與交換機(jī)間時(shí)延增加; 在Topology Zoo[56]的大多數(shù)拓?fù)渲?超過 20%的交換機(jī)位置需要放置控制器從而在任何雙交換機(jī)或鏈路故障時(shí)保證所有交換機(jī)與控制平面的持續(xù)連接。

Hu等人[43]研究單個(gè)交換機(jī)或單條鏈路故障導(dǎo)致的控制器與交換機(jī)或控制器間控制路徑故障的場景。不同的故障轉(zhuǎn)移機(jī)制可能會(huì)導(dǎo)致不同的可靠性結(jié)果,使用條件故障概率表示由不同的網(wǎng)絡(luò)組件故障和故障轉(zhuǎn)移機(jī)制使控制路徑發(fā)生故障的概率。他們證明了可靠的控制器放置問題是NP難問題,為了便于分析,假定所有控制路徑的條件故障概率均相同,并使用之前研究[39]提出的貪心算法和模擬退火算法進(jìn)行求解。大量的仿真表明: 模擬退火算法最接近最優(yōu)解,平均誤差為0.02%; 放置過多或過少的控制器都會(huì)降低控制網(wǎng)絡(luò)的可靠性; 可靠性和平均時(shí)延以及可靠性和最大時(shí)延之間通常不可能同時(shí)達(dá)到最優(yōu),但最大化可靠性的放置結(jié)果所增加的時(shí)延是可以接受的。

Müller等人[35]在控制器放置時(shí)考慮交換機(jī)與控制器間路徑的多樣性(即連通性)以及備用控制器,提出一種彈性的控制器放置策略,具體分為兩步: (1)為了最大化交換機(jī)與控制器間的連通性,選擇使交換機(jī)與控制器之間節(jié)點(diǎn)不相交路徑數(shù)最多的位置作為控制器的放置位置。同時(shí)使控制器的負(fù)載滿足其能力約束,并為控制器預(yù)留部分能力以應(yīng)對故障轉(zhuǎn)移機(jī)制造成的負(fù)載增大的情況。使用整數(shù)線性規(guī)劃方法尋找最優(yōu)的放置結(jié)果。(2)為每個(gè)交換機(jī)選擇一組備用控制器: 可以使用基于鄰近的方式選擇距離交換機(jī)最近的一組控制器作為其備用控制器,或者使用基于剩余能力的方法選擇剩余能力最多的一組控制器作為備用控制器。仿真結(jié)果表明: 在控制器放置時(shí)考慮交換機(jī)與控制器間路徑的多樣性有助于降低交換機(jī)與控制平面之間斷連的概率; 故障發(fā)生后,基于剩余能力的備用控制器選擇方法可以保證控制器不發(fā)生過載,而基于鄰近的備用控制器選擇方法雖然在第一步為每個(gè)控制器的部分能力進(jìn)行預(yù)留,但還是會(huì)出現(xiàn)某些控制器過載的情況。

Vizarreta等人[42]提出兩個(gè)控制器放置方案: 方案一將交換機(jī)通過兩條不相交的控制路徑連接到同一個(gè)控制器; 方案二將交換機(jī)通過兩條不相交的控制路徑分別連接到兩個(gè)不同的控制器?？紤]到鏈路故障概率與鏈路長度成正比,因此放置目標(biāo)是最小化控制器與交換機(jī)間控制路徑(包括主控制路徑和備用控制路徑)的平均長度。由于傳播時(shí)延與路徑的長度是線性關(guān)系,因此控制路徑長度的優(yōu)化也等同于控制器與交換機(jī)間時(shí)延的優(yōu)化。他們將兩個(gè)放置方案建模為混合整數(shù)線性規(guī)劃問題,使用 Gurobi求解器[63]進(jìn)行求解。仿真結(jié)果表明,相比無故障轉(zhuǎn)移機(jī)制且最小化控制器與交換機(jī)間平均控制路徑長度的方案,所提方案以增加較小的控制器與交換機(jī)間時(shí)延為代價(jià),顯著提高了控制路徑在不同故障場景中的恢復(fù)性: (1)在單鏈路或雙鏈路故障場景中,故障控制路徑預(yù)期比例降低了三個(gè)數(shù)量級; (2)當(dāng)節(jié)點(diǎn)(交換機(jī)或控制器)故障是主要故障時(shí),控制路徑平均可用性也有明顯改善,由于方案二提供了對控制器故障的保護(hù),因此具有更優(yōu)的結(jié)果。

Hock等人[27]提出不出現(xiàn)無控制器節(jié)點(diǎn)的控制器放置方案,由于無控制器節(jié)點(diǎn)不能通過任何故障轉(zhuǎn)移機(jī)制與控制平面進(jìn)行通信,因此是網(wǎng)絡(luò)故障導(dǎo)致的最嚴(yán)重的后果之一。Hu等人[43]在控制器放置時(shí)最小化故障控制路徑預(yù)期比例,但沒有指明采用的具體故障轉(zhuǎn)移機(jī)制。Müller等人[35]在控制器放置時(shí)考慮控制器能力約束,并最大化交換機(jī)與控制器間的連通性,但沒能確保對每條控制路徑的保護(hù)。Vizarreta等人[42]對控制路徑的保護(hù)進(jìn)行了明確的規(guī)劃,但提出的兩個(gè)放置方案適用于不同類型的故障場景,并不能很好地同時(shí)應(yīng)對所有故障場景。

3.3 成本與能耗優(yōu)化

以成本與能耗為主要優(yōu)化目標(biāo)的控制器放置方案分為最小化部署成本、最小化管理成本和最小化能量消耗三類。從成本與能耗、時(shí)延、控制器負(fù)載、可靠性以及算法等方面對不同的放置方案進(jìn)行分析。

3.3.1 最小化部署成本

最小化部署成本的控制器放置方案如表6所示。

表6 最小化部署成本的控制器放置方案Table 6 Controller placement schemes of minimizing the deployment cost

Rath等人[64]根據(jù)網(wǎng)絡(luò)中控制器負(fù)載的實(shí)時(shí)變化動(dòng)態(tài)地調(diào)整控制器的數(shù)量以及交換機(jī)與控制器之間的分配,使控制器與交換機(jī)間時(shí)延滿足給定時(shí)延約束、控制器利用率處于給定范圍,最終目標(biāo)是最小化控制器數(shù)量,即最小化控制器成本。他們使用分布式解決方案,在每個(gè)控制器上執(zhí)行非零和博弈來解決該優(yōu)化問題。每個(gè)控制器試圖最大化其利用率并最小化控制器與交換機(jī)間時(shí)延,與相鄰控制器進(jìn)行交互以執(zhí)行調(diào)整交換機(jī)分配、增加或刪除控制器等操作,具體邏輯如下: 當(dāng)控制器利用率低于最低閾值時(shí),將該控制器管理域內(nèi)的所有交換機(jī)分配給其相鄰控制器,然后將該控制器刪除或關(guān)閉; 當(dāng)控制器利用率高于最大閾值時(shí),將該控制器的部分交換機(jī)分配給其相鄰控制器以降低該控制器的負(fù)載; 當(dāng)控制器利用率高于最大閾值,但所有相鄰控制器均不能在滿足時(shí)延和控制器利用率約束條件下接收該控制器的負(fù)載時(shí),需增加一個(gè)新的控制器來分擔(dān)過多的負(fù)載。

Ros等人[65-66]將交換機(jī)連接到多個(gè)控制器以提高控制網(wǎng)絡(luò)的可靠性,目標(biāo)是在滿足可靠性約束的條件下最小化每個(gè)交換機(jī)連接的控制器的數(shù)量以及最小化控制器的總數(shù),即最小化控制器的成本(包括控制器的部署成本和為交換機(jī)提供服務(wù)的成本)。可靠性約束是指交換機(jī)通過不相交路徑與多個(gè)控制器進(jìn)行連接時(shí),交換機(jī)連接到控制平面的概率不小于給定門限值。他們提出一個(gè)啟發(fā)式算法進(jìn)行求解: 根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的度數(shù)對節(jié)點(diǎn)進(jìn)行由大到小排名,排名較高的節(jié)點(diǎn)作為控制器的候選節(jié)點(diǎn),其余節(jié)點(diǎn)通過不相交路徑連接到排名較高的候選節(jié)點(diǎn)以減少控制器的數(shù)量,不斷增加控制器數(shù)量直至達(dá)到可靠性約束。研究結(jié)果發(fā)現(xiàn): 所需的控制器數(shù)量與網(wǎng)絡(luò)中度為 1的節(jié)點(diǎn)的數(shù)量呈正相關(guān); 在Topology Zoo[56]的75%的拓?fù)渲?使用8個(gè)控制器即可滿足5個(gè)9的可靠性約束,每個(gè)交換機(jī)也只需連接2個(gè)控制器。

Sallahi等人[32]旨在設(shè)計(jì)全新的 SDN控制網(wǎng)絡(luò),且控制路徑使用帶外的連接方式。他們不僅考慮控制器的數(shù)量、位置以及控制器與交換機(jī)之間的連接,還考慮控制器的類型(具有不同的端口數(shù)、處理速度和價(jià)格)、控制器與交換機(jī)以及控制器間鏈路的類型(具有不同的帶寬和價(jià)格),并限制了控制器的放置位置(但不限定于交換機(jī)位置)。最終目標(biāo)是最小化SDN控制網(wǎng)絡(luò)的部署成本,包括控制器的安裝成本、控制器與交換機(jī)間鏈路成本以及控制器間的鏈路成本,同時(shí)滿足控制器能力約束和流路徑設(shè)置時(shí)延約束,流路徑設(shè)置時(shí)延包括傳輸時(shí)延、傳播時(shí)延和控制器處理時(shí)延。此外還需要滿足一些其他約束條件,例如,控制器所使用的鏈路數(shù)不能大于控制器的端口數(shù),控制器與交換機(jī)之間的鏈路要滿足交換機(jī)的帶寬需求。他們將控制器放置模型建模為線性規(guī)劃模型,并使用CPLEX優(yōu)化器[60]進(jìn)行求解。仿真結(jié)果顯示: 當(dāng)控制器放置位置數(shù)量固定時(shí),成本隨著交換機(jī)數(shù)量的增加呈線性增加; 當(dāng)交換機(jī)數(shù)量固定時(shí),成本隨著控制器放置位置數(shù)量的增加而略微下降,因?yàn)橛懈嗟目赡苓x擇成本更低的放置位置。

Sallahi等人[34]還提出網(wǎng)絡(luò)擴(kuò)張模型,即在已有的 SDN網(wǎng)絡(luò)中,隨著用戶或業(yè)務(wù)需求的增長,需要在數(shù)據(jù)平面新增一組交換機(jī)時(shí),如何重新設(shè)計(jì)控制網(wǎng)絡(luò)(例如新增控制器或調(diào)整交換機(jī)與控制器間的分配),在滿足控制器與交換機(jī)間時(shí)延約束和控制器能力約束的條件下,最小化網(wǎng)絡(luò)擴(kuò)張成本。網(wǎng)絡(luò)擴(kuò)張成本包括控制器的安裝和移除成本、控制器與交換機(jī)間鏈路的安裝或移除成本以及控制器之間鏈路的安裝或移除成本。他們基于之前研究[32]提出的數(shù)學(xué)模型,加以修改以考慮網(wǎng)絡(luò)擴(kuò)張場景,并采用CPLEX[60]求解該線性規(guī)劃問題。實(shí)驗(yàn)結(jié)果顯示,向不同規(guī)模的初始網(wǎng)絡(luò)新增相同數(shù)量的交換機(jī)時(shí),初始規(guī)模較小的網(wǎng)絡(luò)需要新增更多的控制器并安裝和移除更多的鏈路,從而導(dǎo)致更高的網(wǎng)絡(luò)擴(kuò)張成本。

Ros等人[65-66]提出的控制器放置方案在滿足可靠性約束的條件下最小化控制器成本,會(huì)導(dǎo)致控制器與交換機(jī)間時(shí)延過長,適用于時(shí)延不敏感的網(wǎng)絡(luò)場景。Rath等人[64]和Sallahi等人[32,34]在控制器放置時(shí)考慮控制器能力和時(shí)延約束,并考慮了動(dòng)態(tài)放置場景,通過調(diào)整控制器的數(shù)量和交換機(jī)與控制器間的分配以實(shí)現(xiàn)成本最優(yōu)。Sallahi等人[32,34]的方案適用于使用帶外連接的控制網(wǎng)絡(luò)的設(shè)計(jì),且由于計(jì)算復(fù)雜度的原因只適用于小規(guī)模網(wǎng)絡(luò)場景。

3.3.2 最小化管理成本

最小化管理成本的控制器放置方案如表7所示。

Obadia等人[44]在控制器放置時(shí)最小化靜態(tài)管理成本,同時(shí)滿足控制器與交換機(jī)間時(shí)延約束?？刂破髦g使用全連接的方式進(jìn)行連接,在控制網(wǎng)絡(luò)中的生成樹上進(jìn)行數(shù)據(jù)共享。他們提出一個(gè)貪心算法進(jìn)行求解,大致邏輯如下: 首先在每個(gè)控制器的可能放置位置放置一個(gè)控制器,交換機(jī)連接到最近的控制器; 每次迭代時(shí)嘗試關(guān)閉其中一個(gè)控制器,使交換機(jī)與控制器間時(shí)延滿足約束; 計(jì)算當(dāng)前管理成本,若小于之前的管理成本,則進(jìn)行下一輪迭代,直至成本最低。實(shí)驗(yàn)結(jié)果顯示: 若統(tǒng)計(jì)信息收集成本在管理成本中占比較大,則控制器與交換機(jī)間的距離對管理成本具有重要影響,控制器需要靠近交換機(jī)放置,導(dǎo)致所需控制器的數(shù)量增加; 若流路徑設(shè)置成本占比較大,控制器與交換機(jī)間的距離需減小以減小管理成本,同樣也會(huì)導(dǎo)致控制器數(shù)量的增加; 若控制器同步成本占比較大,則控制器的數(shù)量需要減小以最小化管理成本; 所提算法與最優(yōu)解之間的誤差小于3%。

Bari等人[33]提出動(dòng)態(tài)控制器放置的管理框架,根據(jù)網(wǎng)絡(luò)中流路徑請求率的變化動(dòng)態(tài)地調(diào)整交換機(jī)到控制器的分配,最終目標(biāo)是在滿足控制器能力約束和控制器與交換機(jī)間時(shí)延約束的條件下,最小化動(dòng)態(tài)管理成本。若某個(gè)控制器連接的交換機(jī)都被分配到其他控制器,則該控制器置為閑置狀態(tài),閑置狀態(tài)的控制器只監(jiān)聽特定端口以等待交換機(jī)的連接。他們將動(dòng)態(tài)控制器放置問題建模為整數(shù)線性規(guī)劃問題,并提出兩個(gè)啟發(fā)式算法進(jìn)行求解: (1)基于背包問題的貪心算法: 每次迭代時(shí)選擇到所有未分配的交換機(jī)距離之和最短的控制器,然后使用貪心背包算法將交換機(jī)分配給該控制器; (2)模擬退火算法: 針對之前交換機(jī)到控制器的分配,首先調(diào)整不滿足當(dāng)前流量變化的分配,然后使用模擬退火算法進(jìn)一步優(yōu)化分配。實(shí)驗(yàn)結(jié)果顯示: 網(wǎng)絡(luò)中的流量變化時(shí),兩個(gè)啟發(fā)式算法均可保證流路徑設(shè)置時(shí)延不會(huì)產(chǎn)生較大波動(dòng); 模擬退火算法相比基于背包問題的貪心算法可以產(chǎn)生更加平穩(wěn)和更低的流路徑設(shè)置時(shí)延以及更小的動(dòng)態(tài)管理成本,且使用的控制器數(shù)量也更少,但卻產(chǎn)生更長的收斂時(shí)間。

表7 最小化管理成本的控制器放置方案Table 7 Controller placement schemes of minimizing the management cost

Yao等人[67]在控制器放置時(shí)考慮交換機(jī)的權(quán)重,目標(biāo)是最小化流路徑設(shè)置請求成本。交換機(jī)的權(quán)重由交換機(jī)的流請求率表示,流路徑設(shè)置請求成本表示為交換機(jī)的權(quán)重和交換機(jī)與控制器之間最短距離的乘積。在控制器放置時(shí),首先使用聚類算法[69]將網(wǎng)絡(luò)劃分為k個(gè)子網(wǎng),k由控制器的能力和總負(fù)載決定,然后在每個(gè)子網(wǎng)內(nèi)選擇流路徑設(shè)置請求成本最低的節(jié)點(diǎn)放置控制器。控制器放置后,由于網(wǎng)絡(luò)中流量的變化可能會(huì)導(dǎo)致控制器發(fā)生過載,此時(shí)需要將過載控制器管理的部分交換機(jī)遷移到相鄰控制器以緩解過載問題并實(shí)現(xiàn)控制器間的負(fù)載均衡。遷移時(shí)選擇流請求率較大的邊界交換機(jī),目標(biāo)是在保證新分配的控制器不發(fā)生過載的情況下,最小化遷移的交換機(jī)到新分配的控制器的流路徑設(shè)置請求成本,即最小化交換機(jī)到控制器的重分配成本。

Ksentini等人[68]在控制器放置時(shí)考慮兩個(gè)優(yōu)化目標(biāo): (1)最小化控制器與交換機(jī)間的通信成本,該成本與控制器到交換機(jī)間占用鏈路的總帶寬和交換機(jī)的流路徑請求率有關(guān); (2)最小化控制器間的通信成本,即最小化控制器間占用鏈路的總帶寬。他們提出兩個(gè)單目標(biāo)的解決方案: 方案一對目標(biāo)(2)進(jìn)行優(yōu)化,對目標(biāo)(1)設(shè)置控制器與交換機(jī)間通信成本的最大接受值進(jìn)行約束; 方案二對目標(biāo)(1)進(jìn)行優(yōu)化并設(shè)置對目標(biāo)(2)的約束值。兩個(gè)方案均設(shè)置控制器間負(fù)載最大差值約束來保證控制器間的負(fù)載均衡,并使用線性規(guī)劃模型進(jìn)行求解。仿真結(jié)果顯示: 控制器與交換機(jī)間通信成本約束值的增大會(huì)導(dǎo)致控制器與交換機(jī)間通信成本的增加,并且還會(huì)導(dǎo)致控制器與交換機(jī)之間以及控制器之間總的通信成本增加; 同樣,控制器之間通信成本約束值的增大也會(huì)導(dǎo)致控制器間的通信成本以及總的通信成本的增加。

Obadia等人[44]提出的最小化靜態(tài)管理成本的控制器放置方案適用于流量波動(dòng)不大的網(wǎng)絡(luò)場景。Bari等人[33]和Yao等人[67]提出的動(dòng)態(tài)控制器放置方案適用于網(wǎng)絡(luò)中流量變化較大的場景。Bari等人[33]提出的兩個(gè)放置算法中,雖然模擬退火算法的結(jié)果更優(yōu),但是運(yùn)行時(shí)間也更長,因此模擬退火算法適用于需要近似最優(yōu)結(jié)果的場景,而基于背包問題的啟發(fā)式算法更適合需要快速得出解決方案的場景。Obadia等人[44]和 Ksentini等人[68]的研究結(jié)果表明總成本中不同成本的權(quán)重的選擇以及約束值的設(shè)置對最終的放置結(jié)果會(huì)產(chǎn)生重要影響,因此需要針對特定的場景來合理確定相關(guān)參數(shù)的設(shè)置。

3.3.3 最小化能量消耗

最小化能量消耗的控制器放置方案如表8所示。

表8 最小化能量消耗的控制器放置方案Table 8 Controller placement schemes of minimizing the energy consumption

Huque等人[45]提出放置一組控制器模塊來管理整個(gè)網(wǎng)絡(luò),每個(gè)控制器模塊包含一定數(shù)量的控制器。根據(jù)交換機(jī)流路徑請求率的實(shí)時(shí)變化,動(dòng)態(tài)調(diào)整控制器模塊中激活的控制器的數(shù)目,在保證控制器不發(fā)生過載的情況下最小化控制器模塊中控制器的數(shù)量,從而最小化控制器的能耗。在控制器模塊放置時(shí),首先將網(wǎng)絡(luò)劃分為多個(gè)子網(wǎng),使每個(gè)子網(wǎng)內(nèi)任意兩個(gè)交換機(jī)間的時(shí)延滿足控制器與交換機(jī)間時(shí)延約束。然后在每個(gè)子網(wǎng)內(nèi)選擇使控制器與交換機(jī)間最大時(shí)延最小的位置放置控制器模塊,該位置可以是地理平面內(nèi)的任意位置。仿真結(jié)果顯示,在網(wǎng)絡(luò)的非高峰時(shí)期,所提方案可以通過關(guān)閉部分控制器來降低控制器能耗; 相比稀疏型網(wǎng)絡(luò),在密集型網(wǎng)絡(luò)中關(guān)閉的控制器比例更高。

Ruiz-Rivera等人[47]對已有的控制器放置方案進(jìn)行優(yōu)化。在網(wǎng)絡(luò)的非高峰時(shí)期,盡可能關(guān)閉交換機(jī)與控制器間的鏈路,從而最小化控制鏈路的能耗。假設(shè)所有鏈路具有相同的能耗,優(yōu)化目標(biāo)可簡化為最小化交換機(jī)與控制器間使用的鏈路數(shù)。關(guān)閉鏈路前,控制器與交換機(jī)間受影響的通信路徑需要進(jìn)行調(diào)整。為了避免調(diào)整后過長的通信時(shí)延,他們設(shè)置控制器與交換機(jī)間最大時(shí)延約束進(jìn)行限制,并且還設(shè)置控制器能力約束避免出現(xiàn)過載,設(shè)置鏈路最大利用率約束防止發(fā)生擁塞。他們將該問題建模為0-1整數(shù)規(guī)劃問題,提出一個(gè)名為 GreCo的啟發(fā)式算法進(jìn)行快速求解。實(shí)驗(yàn)結(jié)果表明,在網(wǎng)絡(luò)非高峰時(shí)期通過關(guān)閉鏈路的方式可以節(jié)省高達(dá) 55%的能耗,所提啟發(fā)式算法需要使用比最優(yōu)解多20%的鏈路。

受Ruiz-Rivera等人[47]的啟發(fā),Hu等人[46]從能耗的角度來考慮控制器的初始放置,將具有能耗意識的控制器放置問題建模為0-1整數(shù)規(guī)劃問題,目標(biāo)是最小化控制器與交換機(jī)間控制鏈路的能量消耗,同時(shí)滿足于控制器與交換機(jī)間時(shí)延約束和控制器能力約束。他們基于GreCo算法[47]提出一個(gè)啟發(fā)式算法進(jìn)行求解。仿真結(jié)果表明,為了節(jié)省鏈路的能耗,需要減少控制路徑中使用的鏈路數(shù)量,會(huì)導(dǎo)致控制器與交換機(jī)間時(shí)延增大,但滿足最大時(shí)延約束; 相比最優(yōu)解,所提啟發(fā)式算法使用的額外鏈路數(shù)不會(huì)超過4%。

Huque等人[45]提出控制器模塊的概念,并將控制器模塊放置于地理平面的任意位置,適用于地理不受限的放置場景。Ruiz-Rivera等人[47]和Hu等人[46]旨在通過減少控制器與交換機(jī)間控制鏈路的數(shù)量從而減小鏈路的能耗,但由于采用帶內(nèi)連接方式,關(guān)閉控制鏈路的方法會(huì)影響到數(shù)據(jù)平面流的轉(zhuǎn)發(fā)。

3.4 多目標(biāo)優(yōu)化

多目標(biāo)優(yōu)化的控制器放置方案分為帶權(quán)重和Pareto最優(yōu)兩類,從時(shí)延、控制器負(fù)載、可靠性、成本與能耗以及算法等方面對不同的放置方案進(jìn)行分析。

3.4.1 帶權(quán)重的多目標(biāo)優(yōu)化

帶權(quán)重的多目標(biāo)優(yōu)化的控制器放置方案如表9所示。

Ksentini等人[68]在控制器放置時(shí)考慮兩個(gè)優(yōu)化目標(biāo): (1)最小化控制器與交換機(jī)之間的通信成本; (2)最小化控制器之間的通信成本。這兩個(gè)優(yōu)化目標(biāo)之間是競爭關(guān)系,使用Nash討價(jià)還價(jià)博弈在兩個(gè)優(yōu)化目標(biāo)之間進(jìn)行權(quán)衡,使總的通信成本最小,同時(shí)使控制器之間滿足負(fù)載最大差值約束,建模為線性規(guī)劃模型。仿真結(jié)果顯示,相比優(yōu)化單個(gè)目標(biāo)并對另一個(gè)目標(biāo)設(shè)置約束的方案,所提的多目標(biāo)解決方案可以在兩個(gè)優(yōu)化目標(biāo)之間實(shí)現(xiàn)更好的權(quán)衡,并取得最低的總通信成本。

Tanha等人[70]在控制器放置時(shí)為了應(yīng)對控制器故障為交換機(jī)分配多個(gè)備用控制器,備用控制器的不同數(shù)量表示不同的彈性等級,目標(biāo)是在滿足控制器能力約束下,最小化控制器的部署成本以及最小化流路徑設(shè)置請求成本。假設(shè)控制器的部署成本與控制器放置位置的屬性相關(guān),放置位置的節(jié)點(diǎn)度越大,部署成本越低,所以在控制器放置時(shí)傾向于將控制器放置在節(jié)點(diǎn)度大的位置,使控制器與交換機(jī)間具有較高的連通性。流路徑設(shè)置請求成本包括交換機(jī)到主控制器和所有備用控制器的流路徑設(shè)置請求成本,與交換機(jī)的流請求率和交換機(jī)與控制器間的時(shí)延有關(guān)。他們將以上兩個(gè)成本的加權(quán)和作為最終的優(yōu)化目標(biāo),并使用線性規(guī)劃方法進(jìn)行求解,根據(jù)交換機(jī)的流請求率是否相同以及控制器的能力是否一致,考慮三種不同的網(wǎng)絡(luò)場景。仿真結(jié)果顯示,所需的控制器數(shù)量不僅與彈性等級有關(guān),并且還依賴于網(wǎng)絡(luò)拓?fù)浜途W(wǎng)絡(luò)場景; 在大多數(shù)網(wǎng)絡(luò)場景中,交換機(jī)與控制器間的時(shí)延隨著彈性等級的增加而增大; 隨著彈性等級的增加,控制器間的負(fù)載均衡情況在某些拓?fù)渲袝?huì)不斷惡化,而在其余拓?fù)渲袆t會(huì)不斷改善,再次體現(xiàn)了放置結(jié)果對網(wǎng)絡(luò)拓?fù)涞囊蕾嚒?/p>

表9 帶權(quán)重的多目標(biāo)優(yōu)化的控制器放置方案Table 9 Weighted multi-objective optimized controller placement schemes

Zhang等人[37]在控制器放置時(shí)考慮三個(gè)優(yōu)化目標(biāo): (1)最大化可靠性,即最小化控制路徑故障概率;(2)最大化控制器間負(fù)載均衡狀況,即最小化控制器負(fù)載率方差; (3)最小化控制器與交換機(jī)間最大時(shí)延,包括控制器處理時(shí)延、交換機(jī)處理時(shí)延以及控制器與交換機(jī)間傳播時(shí)延。在交換機(jī)到控制器的分配時(shí)考慮將交換機(jī)同時(shí)連接到多個(gè)控制器并將流路徑請求分配到多個(gè)控制器。在建模時(shí)為多個(gè)目標(biāo)分配權(quán)重從而將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題,使用自適應(yīng)細(xì)菌覓食優(yōu)化算法[71]進(jìn)行求解。仿真結(jié)果顯示,所提方案可以獲得近優(yōu)解,在優(yōu)化目標(biāo)之間取得權(quán)衡,在提高網(wǎng)絡(luò)可靠性的同時(shí),實(shí)現(xiàn)控制器間的負(fù)載均衡并減少控制器與交換機(jī)間時(shí)延。

Ksentini等人[68]的研究結(jié)果表明設(shè)置權(quán)重的權(quán)衡方式相比只優(yōu)化單個(gè)目標(biāo)而對其他目標(biāo)設(shè)置約束的方式可以取得更優(yōu)的放置結(jié)果。Tanha等人[70]和Zhang等人[37]提出的方案均適用于可靠的控制器放置,Zhang等人[37]的方案考慮了更多的優(yōu)化目標(biāo)并且算法更為高效,適合大規(guī)模網(wǎng)絡(luò)場景的放置。

3.4.2 Pareto最優(yōu)的多目標(biāo)優(yōu)化

Pareto最優(yōu)的多目標(biāo)優(yōu)化的控制器放置方案如表10所示。

Heller等人[22]不僅分別研究了最小化控制器與交換機(jī)間平均時(shí)延和最小化控制器與交換機(jī)間最大時(shí)延的控制器放置,還研究了同時(shí)考慮平均時(shí)延和最大時(shí)延時(shí)的 Pareto最優(yōu)解,分析了兩個(gè)指標(biāo)之間的關(guān)系。實(shí)驗(yàn)結(jié)果表明,最小化平均時(shí)延和最小化最大時(shí)延這兩個(gè)優(yōu)化目標(biāo)在現(xiàn)實(shí)網(wǎng)絡(luò)拓?fù)渲泻茈y同時(shí)達(dá)到最優(yōu)。

Hock等人[27]權(quán)衡最小化無故障時(shí)控制器與交換機(jī)間最大時(shí)延以及最小化控制器故障時(shí)控制器與交換機(jī)間最大時(shí)延,通過窮舉法找出所有 Pareto最優(yōu)放置,由運(yùn)營商選擇滿足其需求的放置方案。此外,他們還考慮最小化控制器與交換機(jī)間最大時(shí)延和最小化控制器間負(fù)載最大差值,使用 Topology Zoo[56]的拓?fù)溥M(jìn)行大量仿真,展示這兩個(gè)指標(biāo)的 Pareto最優(yōu)放置,結(jié)果表明: 在20%的拓?fù)渲?存在這兩個(gè)指標(biāo)同時(shí)最優(yōu)的放置,而在80%的拓?fù)渲?一個(gè)指標(biāo)的最優(yōu)會(huì)顯著惡化另一個(gè)指標(biāo)。之后,他們又加入控制器故障時(shí)控制器與交換機(jī)間最大時(shí)延和控制器故障時(shí)控制器間負(fù)載最大差值兩個(gè)指標(biāo),展示了無故障時(shí)的 Pareto最優(yōu)放置對控制器故障時(shí)的時(shí)延和負(fù)載均衡都會(huì)產(chǎn)生負(fù)面影響。最后,他們研究最小化控制器與交換機(jī)間最大時(shí)延和最小化控制器間最大時(shí)延的 Pareto最優(yōu)放置,結(jié)果表明這兩個(gè)優(yōu)化目標(biāo)不可能同時(shí)達(dá)到最優(yōu),基于這兩個(gè)指標(biāo)對控制器放置位置特征的影響,對兩個(gè)指標(biāo)的不同側(cè)重將影響控制器放置位置在整個(gè)網(wǎng)絡(luò)中的分散程度。

Lange等人[24]使用 Czyz?ak 等人[72]提出的 Pareto模擬退火算法來解決多目標(biāo)優(yōu)化的控制器放置問題。Pareto模擬退火算法是一個(gè)通用、多目標(biāo)的啟發(fā)式算法,可以將任意目標(biāo)加入到評估中,且不限制優(yōu)化目標(biāo)的數(shù)量。在仿真中,對控制器與交換機(jī)間平均時(shí)延、控制器與交換機(jī)間最大時(shí)延、控制器間平均時(shí)延、控制器間最大時(shí)延以及控制器間負(fù)載最大差值等五個(gè)指標(biāo)進(jìn)行優(yōu)化,評估 Pareto模擬退火算法的運(yùn)行時(shí)間以及與最優(yōu)解之間的誤差。結(jié)果顯示,對于窮舉搜索算法需要幾十分鐘才能得出結(jié)果的問題實(shí)例,Pareto模擬退火算法在幾十秒內(nèi)即可得出結(jié)果,且與最優(yōu)解之間的平均誤差為2%。

表10 Pareto最優(yōu)的多目標(biāo)優(yōu)化的控制器放置方案Table 10 Pareto-optimal multi-objective optimized controller placement schemes

Lange等人[25]還研究專用的算法對控制器放置問題的適用性,考慮控制器與交換機(jī)間平均時(shí)延和控制器間負(fù)載最大差值兩個(gè)優(yōu)化指標(biāo)。他們基于k-medoids聚類算法[73],提出 Pareto能力約束的k-medoids算法,通過設(shè)置控制器能力約束來限制每個(gè)控制器分配的交換機(jī)個(gè)數(shù),控制器能力約束隱式地影響了控制器間負(fù)載最大差值,通過不斷增加控制器能力約束值,最優(yōu)化控制器與交換機(jī)間平均時(shí)延,從而得出時(shí)延與控制器負(fù)載均衡在控制器放置時(shí)的不同權(quán)衡。仿真結(jié)果表明,專用的啟發(fā)式算法(即Pareto能力約束的k-medoids算法)的結(jié)果準(zhǔn)確性優(yōu)于通用方法(即Pareto模擬退火算法[72]),但當(dāng)考慮更多的優(yōu)化目標(biāo)時(shí)(例如最小化控制器與交換機(jī)間最大時(shí)延、最小化控制器間平均時(shí)延和最小化控制器間最大時(shí)延),由于通用算法可以搜索更多的空間,因此可以獲取更優(yōu)解。

Jalili等人[74]使用NSGA-Ⅱ算法[78]來解決多目標(biāo)的控制器放置問題,目標(biāo)包括最小化控制器間最大時(shí)延和最小化控制器間負(fù)載最大差值。NSGA-Ⅱ算法是一種有效的多目標(biāo)遺傳算法,用于尋找 Pareto最優(yōu)解,它采用快速非支配排序算法降低計(jì)算復(fù)雜度,采用擁擠度和擁擠度比較算子保留種群多樣性,并使用精英機(jī)制提高優(yōu)化結(jié)果。在Internet2 OS3E拓?fù)鋄55]上的仿真結(jié)果驗(yàn)證了所提算法可獲得近似Pareto邊界的解。

Ahmadi等人[75]基于 NSGA-Ⅱ算法提出一種混合的 NSGA-Ⅱ算法來解決控制器放置問題,最小化控制器間最大時(shí)延并最小化控制器間負(fù)載最大差值。通過應(yīng)用兩次三重錦標(biāo)賽選擇策略,在混合交叉過程中獲得兩個(gè)父代種群,在每次錦標(biāo)賽選擇中,從種群中選擇三個(gè)隨機(jī)的方案,并通過擁擠度比較算子返回最優(yōu)的方案,父代確定后,通過基于路徑重連策略[79]的交叉產(chǎn)生子代種群,這種修改允許生成更具多樣性的子代種群。通過仿真發(fā)現(xiàn),所提算法在運(yùn)行過程中不斷提高結(jié)果準(zhǔn)確性的同時(shí),展示了結(jié)果的多樣性,避免陷入局部最優(yōu)或聚集在少數(shù)幾個(gè)最優(yōu)解當(dāng)中,最終取得至少一半的Pareto最優(yōu)解。

Ahmadi等人[76]基于兩個(gè)有效的遺傳算法NSGA-Ⅱ[78]和NSGA-Ⅲ[80]提出一種稱為多起點(diǎn)的混合非支配排序遺傳算法來解決控制器放置問題。該算法使用貪心的啟發(fā)式產(chǎn)生高質(zhì)量的初始種群,還加入了強(qiáng)化機(jī)制、本地搜索機(jī)制以及分散機(jī)制,所有機(jī)制在多起點(diǎn)的步驟中進(jìn)行協(xié)作,構(gòu)成一個(gè)有效的進(jìn)化算法。實(shí)驗(yàn)評估了算法在控制器與交換機(jī)間最大時(shí)延、控制器間最大時(shí)延和控制器間負(fù)載最大差值等優(yōu)化指標(biāo)之間的權(quán)衡。結(jié)果顯示所提算法可以使用較少的計(jì)算時(shí)間和內(nèi)存資源生成靠近 Pareto邊界并具有良好分布的近優(yōu)解。

Liao等人[77]提出基于密度的控制器放置方案,首先使用基于密度的聚類算法將網(wǎng)絡(luò)劃分為k個(gè)子網(wǎng),使每個(gè)子網(wǎng)內(nèi)的交換機(jī)具有緊密的連接,而子網(wǎng)之間的交換機(jī)具有相對較少的連接。之后,根據(jù)不同的優(yōu)化目標(biāo),通過窮舉法在每個(gè)子網(wǎng)內(nèi)找出一個(gè)最優(yōu)的放置或一組 Pareto最優(yōu)放置,從而實(shí)現(xiàn)全網(wǎng)的近似最優(yōu)放置。實(shí)驗(yàn)評估了所提方案在控制器與交換機(jī)間平均時(shí)延、控制器與交換機(jī)間最大時(shí)延和控制器間平均時(shí)延等優(yōu)化指標(biāo)的 Pareto最優(yōu)解,并與 Zhang等人[41]提出的基于最小割的放置方案和Lange等人[24]提出的Pareto模擬退火算法進(jìn)行比較。實(shí)驗(yàn)結(jié)果顯示: 相比Pareto模擬退火算法,所提方案與基于最小割的方案均可以取得更小的控制器與交換機(jī)間時(shí)延,且所提方案的結(jié)果優(yōu)于基于最小割的方案; Pareto模擬退火算法可以取得更小的控制器間時(shí)延,這是因?yàn)樗岱桨概c基于最小割的方案都是在每個(gè)子網(wǎng)內(nèi)放置一個(gè)控制器,控制器間的距離受到了子網(wǎng)劃分的影響; 所提方案在鏈路故障時(shí)還可取得較高的可靠性,所有放置方案在一個(gè)規(guī)模較小的網(wǎng)絡(luò)拓?fù)渲芯a(chǎn)生了非常低的可靠性,說明網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)對網(wǎng)絡(luò)的可靠性也有重要影響。他們還提出了考慮控制器能力約束的基于密度的聚類算法,相比能力約束的k-center算法[29],該算法放置更少的控制器使每個(gè)控制器不發(fā)生過載。

Pareto最優(yōu)的多目標(biāo)優(yōu)化方案可以清楚地展示優(yōu)化目標(biāo)之間的權(quán)衡。窮舉法[22,27]遍歷所有搜索空間可以獲得最優(yōu)解,適用于小規(guī)模網(wǎng)絡(luò)的放置。通用的多目標(biāo)算法(例如Pareto模擬退火算法和NSGA-Ⅱ遺傳算法)可以有效地解決控制器放置問題,但針對控制器放置問題的專用算法(例如聚類算法[25,77])通?？梢匀〉酶鼉?yōu)解。隨著優(yōu)化目標(biāo)數(shù)量的增多,通用算法具有更高的準(zhǔn)確性。因此,專用算法更適合解決優(yōu)化目標(biāo)數(shù)量較少的控制器放置問題,而通用算法適用于優(yōu)化目標(biāo)數(shù)量較多的控制器放置。

3.5 小結(jié)

由于在地理分布廣泛的 WAN中搭建專用的控制鏈路是成本不劃算的,大多數(shù)方案使用帶內(nèi)連接的方式構(gòu)建控制路徑。分布式控制平面大多使用扁平模型,且控制器之間使用全網(wǎng)狀互連的方式進(jìn)行連接。時(shí)延作為最重要的指標(biāo)之一成為很多方案的優(yōu)化指標(biāo)或考慮因素,且主要考慮傳播時(shí)延?；舅械目刂破鞣胖梅桨付际褂米疃搪窂阶鳛榭刂坡窂揭詼p小時(shí)延。由于控制器的處理能力有限,使用控制器能力約束對控制器的負(fù)載進(jìn)行限制。此外,控制器的負(fù)載也會(huì)影響控制器的性能以及可靠性,因此控制器間負(fù)載的分布情況也被加以考慮。隨后,可靠性、成本與能耗等多種指標(biāo)加入到控制器放置問題的考慮因素,控制器放置問題成為了多目標(biāo)的優(yōu)化問題。已有研究根據(jù)不同的優(yōu)化目標(biāo)和不同的問題實(shí)例規(guī)模,使用不同的權(quán)衡方式以及不同的算法來解決控制器放置問題。設(shè)置約束的權(quán)衡方式適用于優(yōu)化單個(gè)目標(biāo)的放置場景,其他指標(biāo)約束值的設(shè)定需要相關(guān)的網(wǎng)絡(luò)知識,可以根據(jù)運(yùn)營商的需求預(yù)先指定,例如,運(yùn)營商可能希望部署的 SDN控制網(wǎng)絡(luò)能夠在滿足控制器與交換機(jī)間特定的時(shí)延約束下最大化網(wǎng)絡(luò)的可靠性。當(dāng)需要同時(shí)優(yōu)化多個(gè)目標(biāo)時(shí),由于同類指標(biāo)可以較為合理地分配權(quán)重,因此設(shè)置權(quán)重的權(quán)衡方式更加適用于優(yōu)化多個(gè)同類指標(biāo)的放置場景,例如同時(shí)優(yōu)化多種管理成本。Pareto最優(yōu)的權(quán)衡方式可以展示多個(gè)優(yōu)化目標(biāo)之間的權(quán)衡關(guān)系,使運(yùn)營商可以根據(jù)需求從中選擇合適的放置方案,更加適用于優(yōu)化非同類指標(biāo)的放置場景。

4 研究展望

已有研究工作主要從性能、可靠性、成本與能耗等方面解決SDN控制器放置問題。然而,SDN控制器放置仍然存在很多問題有待進(jìn)一步研究,簡要介紹如下:

(1) 控制器數(shù)量的確定

控制器數(shù)量的不同會(huì)導(dǎo)致不同的控制器放置位置以及交換機(jī)與控制器之間的分配,因此合適的控制器數(shù)量對控制器的放置非常重要。文獻(xiàn)[22,24,27,41,49,61]提前設(shè)置控制器數(shù)量,然后尋找該控制器數(shù)量下的最優(yōu)放置位置和分配。然而,根據(jù)經(jīng)驗(yàn)設(shè)置的控制器數(shù)量并不一定產(chǎn)生最優(yōu)的放置結(jié)果。文獻(xiàn)[29]采用逐漸增加控制器數(shù)量的方式尋找滿足控制器能力約束的最小控制器數(shù)量。文獻(xiàn)[77]選擇使時(shí)延收益遞減的控制器數(shù)作為放置的控制器數(shù)。文獻(xiàn)[28]基于控制器與交換機(jī)間時(shí)延約束將網(wǎng)絡(luò)分成k個(gè)子網(wǎng)并在每個(gè)子網(wǎng)放置一個(gè)控制器。文獻(xiàn)[26]通過控制器間時(shí)延約束確定控制器的數(shù)量。這些方案在確定控制器數(shù)量時(shí)只考慮單一的優(yōu)化指標(biāo)并且通常比較耗時(shí)?？刂破鞯臄?shù)量不僅決定了控制器的部署成本與能耗,還對時(shí)延和可靠性等方面產(chǎn)生重要影響。因此,控制器數(shù)量的確定需要綜合考慮多個(gè)優(yōu)化指標(biāo)并尋找快速、準(zhǔn)確的算法。

(2) 控制器負(fù)載對控制器性能和可靠性的影響

受處理器、內(nèi)存和帶寬等資源的限制,控制器具有有限的處理能力,只能管理有限數(shù)量的交換機(jī)?？刂破鞯呢?fù)載也會(huì)影響控制器的處理能力,并最終影響控制器的處理時(shí)延。文獻(xiàn)[81]提出了一個(gè)控制器處理時(shí)延與控制器能力和負(fù)載之間關(guān)系的模型,由排隊(duì)模型和路由計(jì)算的時(shí)間復(fù)雜度兩部分組成。但是該模型沒有考慮控制器的并行處理能力以及不同類型控制器的處理邏輯。此外,控制器的負(fù)載還會(huì)影響控制器的可靠性,可靠性會(huì)隨著負(fù)載的升高而降低。目前還沒有對控制器負(fù)載與其可靠性之間關(guān)系的定量研究?？刂破鞯呢?fù)載、性能和可靠性是控制器放置時(shí)需要考慮的重要指標(biāo),它們之間的相互影響有待進(jìn)一步研究。

(3) 控制器同步方案

控制器之間需要經(jīng)常通信以同步網(wǎng)絡(luò)狀態(tài),已有文獻(xiàn)提出多種狀態(tài)同步方案,例如,使用網(wǎng)絡(luò)信息庫(NIB)的同步方案[13]、基于定期同步的方案[82]、基于負(fù)載方差的同步方案[83]和基于 Paxos的快速同步方法[84]。不同方案具有不同的同步效率并產(chǎn)生不同的同步開銷。因此,在控制器放置時(shí),當(dāng)考慮控制器間時(shí)延或管理成本等相關(guān)指標(biāo)時(shí),需要指定控制器放置場景中使用的控制器同步方案,以便得出準(zhǔn)確的放置結(jié)果,或者設(shè)計(jì)更優(yōu)的同步方案以減小控制器間同步時(shí)延和管理成本。

(4) 控制路徑的分配

控制器放置時(shí),交換機(jī)通常分配到距離最近的控制器,并使用最短路徑與控制器進(jìn)行通信。這種分配方式可以最大程度減小控制器與交換機(jī)間的時(shí)延,但是對某些指標(biāo)可能會(huì)產(chǎn)生負(fù)面影響,例如分配到距離最近的控制器可能會(huì)導(dǎo)致控制器間負(fù)載不均衡甚至出現(xiàn)控制器過載,某些最短路徑可能具有較大的故障概率或產(chǎn)生較高的成本。因此需要綜合考慮多個(gè)目標(biāo)恰當(dāng)?shù)剡M(jìn)行控制器與交換機(jī)間的分配并選擇合適的控制路徑。此外,很少有文獻(xiàn)在控制器放置時(shí)考慮控制路徑中鏈路的負(fù)載狀況。過高的鏈路負(fù)載會(huì)導(dǎo)致鏈路傳輸性能下降和可靠性降低。在選擇控制路徑時(shí)需要考慮鏈路的利用率,使控制流量均衡地分布在整個(gè)控制網(wǎng)絡(luò)中。

(5) 交換機(jī)遷移的觸發(fā)條件及遷移選擇

由于網(wǎng)絡(luò)中流量的變化,需要?jiǎng)討B(tài)地調(diào)整交換機(jī)與控制器之間的分配(即交換機(jī)遷移)以實(shí)現(xiàn)控制器之間的負(fù)載均衡,進(jìn)而提高控制平面的性能。交換機(jī)遷移通常發(fā)生在以下三個(gè)場景中: (1)當(dāng)網(wǎng)絡(luò)中的總流量過大甚至超過所有控制器的能力時(shí),需要加入新的控制器并將一些交換機(jī)遷移到該控制器以分擔(dān)部分負(fù)載; (2)當(dāng)網(wǎng)絡(luò)中的總流量過低時(shí),需要將部分控制器關(guān)閉或置為睡眠狀態(tài)并將這些控制器管理的交換機(jī)遷移到其他控制器,從而減小控制器能耗和控制器間通信成本; (3)當(dāng)網(wǎng)絡(luò)中總流量沒有超過控制器能力但卻出現(xiàn)控制器負(fù)載不均衡時(shí),需要將負(fù)載過大的控制器管理的部分交換機(jī)遷移到其他控制器以實(shí)現(xiàn)控制器間負(fù)載均衡。在上述三個(gè)場景中,負(fù)載的“過大”和“過低”目前還沒有明確的定量表示,通常是在控制器過載時(shí)才進(jìn)行交換機(jī)的遷移。因此需要合理地考慮交換機(jī)遷移的觸發(fā)條件。當(dāng)執(zhí)行遷移操作時(shí),也需要合理地選擇遷移交換機(jī)和遷移目的控制器,不僅要在控制器負(fù)載均衡、控制路徑時(shí)延、控制路徑可靠性和管理成本等方面進(jìn)行權(quán)衡,還需要考慮遷移操作的成本。

(6) 高效的算法

隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大和網(wǎng)絡(luò)狀態(tài)的不斷變化,網(wǎng)絡(luò)管理員需要實(shí)時(shí)調(diào)整控制器的數(shù)量、位置以及交換機(jī)到控制器的分配,以實(shí)現(xiàn)網(wǎng)絡(luò)高效、可靠和經(jīng)濟(jì)地運(yùn)行。然而,控制器放置問題通常是NP難問題,尋找最優(yōu)的放置方案是耗時(shí)的。此外,控制器放置問題通常是多目標(biāo)的聯(lián)合優(yōu)化問題,且目標(biāo)之間具有競爭關(guān)系,增加了問題的復(fù)雜性。因此,在建模時(shí)需要綜合考慮多個(gè)優(yōu)化目標(biāo)并設(shè)計(jì)更高效的算法快速、準(zhǔn)確地解決控制器放置問題。

表11 不同類型網(wǎng)絡(luò)的控制器放置問題研究Table 11 Survey of controller placement problem for different types of networks

(7) 不同類型網(wǎng)絡(luò)的控制器放置

大多數(shù)已有研究關(guān)注的都是 WAN中的控制器放置問題。近年來,隨著SDN應(yīng)用場景的擴(kuò)展和多控制器需求的增加,研究人員對數(shù)據(jù)中心網(wǎng)絡(luò)和無線網(wǎng)絡(luò)中的控制器放置問題也展開了研究,代表性成果如表11所示。在數(shù)據(jù)中心網(wǎng)絡(luò)中,控制器放置于接入層交換機(jī)連接的服務(wù)器上,可采用帶外的連接方式,主要考慮控制器處理時(shí)延。在無線網(wǎng)中,控制器與被控制元素之間通常通過無線連接進(jìn)行通信,需要指定使用的無線信道模型以確定通信方式并得出網(wǎng)絡(luò)接入時(shí)延。不同類型的網(wǎng)絡(luò)具有不同的網(wǎng)絡(luò)特征、特定的優(yōu)化目標(biāo)和相應(yīng)的指標(biāo)計(jì)算公式,在控制器放置時(shí)需要考慮這些差異以構(gòu)建合適的模型,并使用合適的算法進(jìn)行求解。

5 總結(jié)

控制器的放置對使用分布式控制平面的SDN的實(shí)際部署至關(guān)重要,有效的放置方案會(huì)降低控制器與交換機(jī)以及控制器間的通信時(shí)延、提高控制網(wǎng)絡(luò)的可靠性并降低成本與能耗。本文首先詳細(xì)介紹了控制器放置問題的優(yōu)化指標(biāo),包括時(shí)延、控制器負(fù)載、可靠性和成本與能耗,然后根據(jù)優(yōu)化目標(biāo)和優(yōu)化目標(biāo)之間的權(quán)衡方式將已有研究提出的解決方案分為以性能為主要優(yōu)化目標(biāo)、以可靠性為主要優(yōu)化目標(biāo)、以成本與能耗為主要優(yōu)化目標(biāo)以及多目標(biāo)優(yōu)化等四類控制器放置方案,并對這些方案進(jìn)行詳細(xì)地對比與分析。最后,總結(jié)了分布式SDN控制器放置未來需要解決的問題。