基于聯(lián)盟博弈的自適應(yīng)SDN 交換機(jī)遷移機(jī)制

姚藍(lán)，蘭巨龍

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

1 引言

軟件定義網(wǎng)絡(luò)（SDN,software-defined networking）通過控制與轉(zhuǎn)發(fā)分離，能夠?yàn)殪`活的網(wǎng)絡(luò)管理和敏捷的服務(wù)創(chuàng)新提供有力的支持，目前已經(jīng)在企業(yè)網(wǎng)、數(shù)據(jù)中心網(wǎng)絡(luò)等得到推廣。SDN 使用邏輯集中的控制平面來收集網(wǎng)絡(luò)視圖信息、處理流請(qǐng)求、計(jì)算網(wǎng)絡(luò)策略[1]。但集中式的控制平面面臨嚴(yán)重的可擴(kuò)展性問題，這一可擴(kuò)展性問題主要指網(wǎng)絡(luò)中流量規(guī)模的增長帶來的控制器超負(fù)載問題，會(huì)嚴(yán)重影響控制器的性能。

為了提高可擴(kuò)展性并避免單點(diǎn)故障，SDN 常采用分布式控制平面[2]，部署多控制器對(duì)網(wǎng)絡(luò)進(jìn)行分域管理，將交換機(jī)靜態(tài)映射到一個(gè)或多個(gè)控制器上。但是，交換機(jī)和控制器之間的靜態(tài)映射易導(dǎo)致控制器響應(yīng)時(shí)間長且變化很大，這是因?yàn)榫W(wǎng)絡(luò)中的流量頻繁波動(dòng)。在空間上，總流量通常在白天達(dá)到高峰，而在晚上流量較少，此外，即使總流量保持不變，流量在短時(shí)間內(nèi)也具有突發(fā)性[3]。流量的不確定性會(huì)導(dǎo)致控制器之間負(fù)載不均衡，從而導(dǎo)致一些過載控制器的交換機(jī)響應(yīng)時(shí)間過長，而且控制器長時(shí)間超負(fù)載工作易發(fā)生故障，導(dǎo)致網(wǎng)絡(luò)癱瘓。因此，設(shè)計(jì)動(dòng)態(tài)的控制器與交換機(jī)映射機(jī)制，以縮短控制器響應(yīng)時(shí)間并更好地利用控制器資源，對(duì)提高SDN 控制平面的可擴(kuò)展性和可靠性具有重要的意義。Dixit等[4]提出通過動(dòng)態(tài)添加或減少控制器的數(shù)量來拓展控制平面，但如何設(shè)計(jì)適應(yīng)流量特征的控制器和交換機(jī)映射關(guān)系仍然是亟需解決的問題。從交換機(jī)的角度來看，它更容易映射到響應(yīng)時(shí)間短的控制器來提高性能；從控制器的角度來看，它管理較近的交換機(jī)所產(chǎn)生的控制流量開銷較小。綜上，設(shè)計(jì)動(dòng)態(tài)的控制器和交換機(jī)的映射目標(biāo)應(yīng)滿足以下3 個(gè)指標(biāo)：控制器上的負(fù)載是均勻的，實(shí)現(xiàn)最大利用率，減少流處理時(shí)間。

為了解決這些問題，本文提出一種基于聯(lián)盟博弈的交換機(jī)遷移機(jī)制（CGSM,coalitional gamebased switch migration），綜合考慮控制器資源利用率、控制開銷和流建立時(shí)間，設(shè)計(jì)可以動(dòng)態(tài)調(diào)整控制器的狀態(tài)和控制器?交換機(jī)映射關(guān)系的自適應(yīng)交換機(jī)遷移機(jī)制。本文的主要貢獻(xiàn)如下。

1) 針對(duì)SDN 中控制器?交換機(jī)不合理的映射關(guān)系導(dǎo)致控制平面性能低下的問題，提出適應(yīng)流量特征的自適應(yīng)交換機(jī)遷移機(jī)制，綜合考慮控制器資源利用率、控制開銷和流建立時(shí)間，將交換機(jī)遷移問題建模為組合優(yōu)化問題。

2) 設(shè)計(jì)了基于聯(lián)盟博弈的交換機(jī)遷移機(jī)制，把博弈論引入控制器運(yùn)行邏輯當(dāng)中，設(shè)計(jì)分布式算法，每個(gè)控制器獨(dú)立運(yùn)行算法，通過控制器之間聯(lián)合博弈、協(xié)調(diào)合作，實(shí)現(xiàn)自適應(yīng)的控制器狀態(tài)調(diào)整和彈性的控制器?交換機(jī)映射關(guān)系。

3) 開展相關(guān)實(shí)驗(yàn)對(duì)所提交換機(jī)遷移機(jī)制的性能進(jìn)行驗(yàn)證，仿真結(jié)果表明，本文所提機(jī)制能減少約19%的控制開銷和30%的平均流建立時(shí)間，提高了控制平面的性能。

2 相關(guān)研究

為了提高SDN 控制平面的可擴(kuò)展性[5]，許多研究人員對(duì)SDN 控制器和交換機(jī)的動(dòng)態(tài)映射機(jī)制展開了深入的研究。SDN 分布式控制平面是提高控制器可擴(kuò)展性的有效方法[6]。在這樣的架構(gòu)中，控制平面可以由多個(gè)控制器組成。多個(gè)控制器負(fù)責(zé)管理網(wǎng)絡(luò)的不同管理域，并與相鄰域交換本地信息以增強(qiáng)全局策略的實(shí)施，如 Hyperflow[7]、Onix[8]、ONOS[9]。Zhang 等[10]提出了基于交換機(jī)遷移的多域SDN 中的分發(fā)策略，通過優(yōu)化數(shù)據(jù)收集、交換機(jī)遷移和控制器狀態(tài)同步3個(gè)因素來確定目標(biāo)控制器和遷移的交換機(jī)，實(shí)現(xiàn)了更好的控制器負(fù)載平衡。

胡濤等[11]將控制器關(guān)聯(lián)問題建模為雙向匹配問題，從控制器和交換機(jī)的角度出發(fā)優(yōu)化控制器?交換機(jī)映射問題，仿真表明，該方案能有效降低流請(qǐng)求排隊(duì)時(shí)延，并且實(shí)現(xiàn)了控制器之間更好的負(fù)載平衡。Xiao 等[12]提出了用于SDN 控制平面的交換機(jī)遷移決策方案，設(shè)計(jì)遷移收益模型衡量遷移代價(jià)來解決遷移決策問題，以減少控制命令傳輸時(shí)延和平衡控制器負(fù)載，仿真表明，該方案可以將控制信令的平均傳輸時(shí)延減少17%，將處理時(shí)延減少22.7%。

Xu 等[13]提出了用于平衡控制器負(fù)載的SDN 交換機(jī)遷移方案，在保障遷移成本較低的前提下，實(shí)現(xiàn)SDN 控制器之間的負(fù)載平衡。該遷移方案不受交換機(jī)遷移中斷的影響，并且不會(huì)引起任何服務(wù)中斷。仿真表明，該機(jī)制通過僅遷移少量具有低開銷的交換機(jī)，就可以大大減少SDN 控制器之間的負(fù)載不平衡。Mykola 等[14]考慮流量的優(yōu)先級(jí)和用戶服務(wù)質(zhì)量體驗(yàn)來實(shí)施交換機(jī)遷移策略，實(shí)驗(yàn)結(jié)果表明，考慮流量的優(yōu)先級(jí)特征和用戶的需求，能更充分地利用控制平面資源。Bari 等[15]提出的交換機(jī)遷移機(jī)制動(dòng)態(tài)地改變了控制器的數(shù)量及其在不同條件下的位置，以實(shí)現(xiàn)負(fù)載平衡，但該機(jī)制沒有明確控制器之間的通信與信息同步機(jī)制。

Zhou 等[16]將交換機(jī)遷移解釋為簽名匹配問題，并將控制器和交換機(jī)映射問題建模為EMD（earth mover’s distance）模型，通過減少流量差異以保護(hù)網(wǎng)絡(luò)中重要節(jié)點(diǎn)的控制器，并提出了一種高效的啟發(fā)式方法來求解大規(guī)模網(wǎng)絡(luò)交換機(jī)遷移問題。Wang等[17]為了提高交換機(jī)遷移效率，設(shè)計(jì)了遷移效率感知的貪婪算法實(shí)施交換機(jī)遷移，以權(quán)衡遷移成本和負(fù)載均衡率。Grkemli 等[18]引入一種新穎的動(dòng)態(tài)控制平面體系結(jié)構(gòu)，根據(jù)特定的控制器負(fù)載和控制器資源利用率或數(shù)據(jù)流服務(wù)類型，在多個(gè)控制器實(shí)例之間分配不同的控制流。Li 等[19]分析了不同特征流請(qǐng)求的資源消耗，設(shè)計(jì)了一種基于數(shù)據(jù)流特征的動(dòng)態(tài)控制器關(guān)聯(lián)機(jī)制，通過基于聯(lián)盟博弈的最小集合覆蓋算法減少了控制平面處理數(shù)據(jù)流請(qǐng)求的資源消耗。Cheng 等[20]將交換機(jī)遷移問題建模為一個(gè)集中的資源利用最大化問題，結(jié)合控制器CPU、帶寬和內(nèi)存的資源利用率，通過非合作博弈論方法設(shè)計(jì)分布式算法，提高了SDN 的可擴(kuò)展性。Filali 等[21]提出了一種交換機(jī)遷移調(diào)度算法，使用多步自回歸移動(dòng)平均模型（ARIMA,autoregressive integrated moving average model）來預(yù)測控制器的長期負(fù)載水平，提前開啟交換機(jī)遷移操作以適應(yīng)流量需求，在確保控制器之間的負(fù)載平衡的同時(shí)，提高了遷移效率。

現(xiàn)有針對(duì)彈性控制問題的方法主要是通過交換機(jī)和控制器之間的重新布局來改變控制器的數(shù)量和位置，該策略會(huì)造成大量的交換機(jī)遷移，使網(wǎng)絡(luò)不穩(wěn)定?，F(xiàn)有解決控制器與交換機(jī)彈性映射的方法多采用集中式算法，以全局優(yōu)化的思想來達(dá)到最優(yōu)，隨著網(wǎng)絡(luò)規(guī)模的不斷增大，這些算法的計(jì)算量很大，嚴(yán)重影響了控制平面的擴(kuò)展性。

3 研究動(dòng)機(jī)

控制器和交換機(jī)之間的動(dòng)態(tài)映射可以更好地適應(yīng)網(wǎng)絡(luò)流量、提高控制器資源利用率。網(wǎng)絡(luò)中流量具有突發(fā)性，且高峰流量和低谷流量差距很大，實(shí)際網(wǎng)絡(luò)中有較多交換機(jī)遷移的場景。OpenFlow 1.3中設(shè)置了不同的控制器角色（主控制器和從控制器），通過改變控制器和交換機(jī)的主從關(guān)系，控制器和交換機(jī)可以多對(duì)多映射，實(shí)現(xiàn)控制器和交換機(jī)之間靈活的映射關(guān)系。

首先，當(dāng)網(wǎng)絡(luò)中有大部分控制器均處于輕載狀態(tài)時(shí)，直觀的想法是將輕載控制器的負(fù)載進(jìn)行合并，并將空閑的控制器關(guān)閉或者休眠以節(jié)省電力和通信成本。圖1(a)中，控制器c1和c2均處于輕載狀態(tài)，把控制器c2的所有負(fù)載交換機(jī)均遷移到控制器c1上，此時(shí)便可以將控制器c2休眠，以節(jié)省能量。

當(dāng)網(wǎng)絡(luò)中大部分處于工作狀態(tài)的控制器均已過載時(shí)，為了保障控制平面的服務(wù)性能，應(yīng)擴(kuò)展控制器資源，觸發(fā)休眠控制器，并將過載控制器的交換機(jī)遷移到新的控制器上。圖1(b)中，當(dāng)控制器c1過載時(shí)，為了防止控制器c1因過載而影響性能或者損壞，甚至導(dǎo)致網(wǎng)絡(luò)崩潰，應(yīng)觸發(fā)休眠控制器c2以分擔(dān)控制器c1的負(fù)載。

在SDN 中，多控制器中往往會(huì)出現(xiàn)一些控制器過載，而另一些控制器卻處于輕載的狀態(tài)，但不需要擴(kuò)展或縮減控制器資源，此時(shí)需要實(shí)施負(fù)載均衡策略以平衡控制器之間的負(fù)載，提高控制平面的處理性能。圖1(c)中，當(dāng)控制器之間負(fù)載不平衡時(shí)，將部分交換機(jī)從過載控制器遷移到輕載控制器，便可以提升控制平面數(shù)據(jù)流請(qǐng)求的處理效率。當(dāng)然，在擴(kuò)展控制器資源和縮減控制器資源之后，也應(yīng)進(jìn)行交換機(jī)遷移以實(shí)施負(fù)載均衡策略。

圖1 交換機(jī)遷移場景

因此，為了更好地利用控制器資源，控制器和交換機(jī)之間的映射應(yīng)適應(yīng)網(wǎng)絡(luò)流量特征，使控制平面可以處理更多的數(shù)據(jù)流，提升網(wǎng)絡(luò)性能。本文旨在設(shè)計(jì)自適應(yīng)的交換機(jī)遷移機(jī)制以實(shí)現(xiàn)控制器?交換機(jī)動(dòng)態(tài)可擴(kuò)展的彈性映射關(guān)系，它可以觸發(fā)新的控制器或?qū)⑦^載控制器的交換機(jī)遷移到輕載控制器上以應(yīng)對(duì)網(wǎng)絡(luò)中突發(fā)的流量，當(dāng)網(wǎng)絡(luò)中流量處于低谷時(shí)，它可以休眠部分控制器以節(jié)省能量。

4 模型構(gòu)建

本節(jié)首先基于圖論的知識(shí)，對(duì)網(wǎng)絡(luò)模型和控制器負(fù)載、控制器處理時(shí)延進(jìn)行描述，然后建立優(yōu)化目標(biāo)函數(shù)，設(shè)計(jì)分布式算法，以達(dá)到負(fù)載均衡的目的。

4.1 網(wǎng)絡(luò)建模

給定一個(gè)多控制器域SDN 模型，結(jié)合圖論的相關(guān)知識(shí)，對(duì)SDN 建模。整個(gè)網(wǎng)絡(luò)拓?fù)淇捎脽o向圖G=(V,E)表示，其中V表示網(wǎng)絡(luò)節(jié)點(diǎn)（即交換機(jī)和控制器所在位置），E表示節(jié)點(diǎn)間鏈路集合。網(wǎng)絡(luò)中共有m個(gè)控制器和n個(gè)交換機(jī)，定義SDN控制平面中控制器集合為C={c1,c2,???,cm}，各個(gè)控制器處理容量為α={α1,α2,???,αm}，交換機(jī)集合為S={s1,s2,…,sN}。設(shè)dij表示交換機(jī)i和控制器j之間的跳數(shù)，控制器與交換機(jī)采用帶內(nèi)通信，所有節(jié)點(diǎn)之間以最短距離通信。交換機(jī)i的流請(qǐng)求速率為λi，控制器與交換機(jī)之間的映射關(guān)系為xij，如式(1)所示。

定義1流建立時(shí)間。由于當(dāng)今的網(wǎng)絡(luò)能提供較大的帶寬，因此數(shù)據(jù)分組的傳播時(shí)延（以μs為單位）比控制器CPU 的處理時(shí)間（以ms 為單位）[7]要小。因此，本文僅在控制器上對(duì)流請(qǐng)求處理時(shí)間進(jìn)行建模。假設(shè)在時(shí)隙t中第i個(gè)交換機(jī)的流請(qǐng)求數(shù)量用λi(t)表示，流請(qǐng)求到達(dá)時(shí)間遵循泊松過程，其中λi(t)≤aj。因此，第j個(gè)控制器的負(fù)載可以表示為

本文做出以下假設(shè)：λi(t)是相互獨(dú)立的，控制器隊(duì)列調(diào)度遵循M/M/1 隊(duì)列。則第j個(gè)控制器平均數(shù)據(jù)流建立時(shí)間為

整個(gè)控制平面的所有控制器平均流建立時(shí)間為

定義2控制開銷η。出于SDN 的可擴(kuò)展性考慮，本文控制器與交換機(jī)之間的信息交流均采用帶內(nèi)通信，因此，控制流量會(huì)占用數(shù)據(jù)信道的帶寬，減少控制流量開銷，能提高數(shù)據(jù)平面的轉(zhuǎn)發(fā)性能。定義控制器開銷與控制器負(fù)載和控制機(jī)與交換機(jī)之間的跳數(shù)有關(guān)，如式(5)和式(6)所示。

其中，η表示所有控制器的總開銷，ηj表示控制器j產(chǎn)生的總的控制開銷。

定義3控制器資源利用率γj。控制器資源利用率為控制器負(fù)載與控制器最大容量的比值，這是判斷控制器是否過載的衡量指標(biāo)。當(dāng)控制器資源利用率大于0.9 時(shí)，控制器處于過載狀態(tài)；當(dāng)控制器資源利用率小于0.1 時(shí)，控制器處于輕載狀態(tài)。

4.2 優(yōu)化目標(biāo)函數(shù)

綜合上述流建立時(shí)間、控制開銷、控制器資源利用率，為了設(shè)計(jì)自適應(yīng)交換機(jī)遷移機(jī)制，出于節(jié)能考慮，設(shè)置控制器資源利用率閾值上限為0.9，閾值下限為0.1，即當(dāng)控制器資源利用率超過0.9時(shí)，控制器處于過載狀態(tài)，需要遷出交換機(jī)以卸載；當(dāng)控制器資源利用率低于0.1 時(shí)，出于節(jié)能，需要遷出交換機(jī)以休眠控制器；當(dāng)控制器資源利用率在0.1～0.9 時(shí)，實(shí)施負(fù)載均衡策略，以最小化基于流建立時(shí)間和控制開銷的加權(quán)效益?？刂破鲿?huì)時(shí)刻監(jiān)測自己的資源利用率情況，并相互通告以決定是否實(shí)施交換機(jī)遷移策略Γ，如式(8)所示。

控制器資源利用率為0.1～0.9 的優(yōu)化目標(biāo)函數(shù)設(shè)為

約束條件為

目標(biāo)函數(shù)式(9)為最小化基于流建立時(shí)間和控制開銷的加權(quán)和。式(10)和式(11)表示任何時(shí)刻每一個(gè)交換機(jī)能且只能映射到一個(gè)控制器上。式(12)表示每一個(gè)控制器的負(fù)載不得超過負(fù)載上限。

5 算法設(shè)計(jì)

現(xiàn)有解決控制器與交換機(jī)彈性映射的方法都是通過將控制器和交換機(jī)映射問題轉(zhuǎn)化為NP 難的整數(shù)線性規(guī)劃問題，設(shè)計(jì)啟發(fā)式算法求解，但這些算法多采用集中式算法，且本質(zhì)上是一種重映射算法，隨著網(wǎng)絡(luò)規(guī)模的不斷增大，這些算法具有較高的復(fù)雜度，嚴(yán)重影響了控制平面的擴(kuò)展性。

在大規(guī)模網(wǎng)絡(luò)當(dāng)中，SDN 常采用分布式控制平面，每個(gè)控制器僅管理域內(nèi)的交換機(jī)，通過與鄰居控制器交互來處理全局事件。傳統(tǒng)的采用集中式的算法往往不適應(yīng)SDN 控制平面分布式的網(wǎng)絡(luò)架構(gòu)，會(huì)帶來大量的同步和通信開銷。因此，本文設(shè)計(jì)一種分布式算法以適應(yīng)SDN 分布式的控制平面，每個(gè)控制器獨(dú)立運(yùn)行算法，通過與鄰居控制器交互來實(shí)現(xiàn)交換機(jī)的動(dòng)態(tài)遷移，分布式算法將計(jì)算任務(wù)分擔(dān)到每個(gè)控制器上，便于增加或休眠控制器，更適用于大規(guī)模網(wǎng)絡(luò)，能增加網(wǎng)絡(luò)的可靠性。

本文遵循分布式準(zhǔn)則設(shè)計(jì)聯(lián)盟博弈模型，通過控制器之間協(xié)調(diào)合作、相互博弈，來實(shí)施交換機(jī)遷移策略。博弈論是指研究多個(gè)個(gè)體或團(tuán)隊(duì)之間在特定條件制約下的對(duì)局中，利用相關(guān)方的策略來實(shí)施對(duì)應(yīng)策略的學(xué)科。博弈論考慮博弈中個(gè)體的預(yù)測行為和實(shí)際行為，并研究它們的優(yōu)化策略。在控制器?交換機(jī)映射問題中，控制器會(huì)偏好連接時(shí)延較小且產(chǎn)生的控制開銷較小的交換機(jī)，而不同的交換機(jī)連接到不同的控制器會(huì)導(dǎo)致不同的時(shí)延和控制開銷?？刂破髦g為了追求最大化自身性能效益會(huì)形成競爭關(guān)系，此時(shí)交換機(jī)便是控制器之間競爭的商品，通過控制器交互博弈來尋求自身性能的提升。這種競爭并非完全對(duì)立的競爭，而是通過彼此合作博弈，使最終整個(gè)控制平面的性能達(dá)到最優(yōu)。合作博弈采用的是一種合作的關(guān)系，其本質(zhì)的思想是聯(lián)盟和分配，每個(gè)參與者從聯(lián)盟中得到的收益不少于單獨(dú)經(jīng)營所獲得的收益，合作博弈能增進(jìn)整體的利益。在控制器和交換機(jī)的映射問題中，參與博弈的對(duì)象是各個(gè)控制器，博弈的商品是交換機(jī)，控制器之間通過合作博弈、改變交換機(jī)的映射關(guān)系來改進(jìn)自身性能。合作博弈的核心思想是參與人如何結(jié)盟以及如何重新分配結(jié)盟的支付，當(dāng)控制器自身的性能較差時(shí)，會(huì)通告其鄰居控制器，然后和鄰居控制器形成聯(lián)盟，對(duì)交換機(jī)進(jìn)行重新分配?？刂破髦g通過博弈獲取個(gè)體自身性能的提升，在整個(gè)控制平面中，控制器通過不斷形成聯(lián)盟博弈，優(yōu)化交換機(jī)的從屬關(guān)系，最終控制器和交換機(jī)映射問題收斂到納什穩(wěn)定狀態(tài)，實(shí)現(xiàn)了整個(gè)控制平面的全局優(yōu)化。

為了設(shè)計(jì)合適的控制器聯(lián)盟博弈模型，在控制器之間實(shí)施聯(lián)盟博弈策略，首先對(duì)決策域、收益函數(shù)、控制器通信機(jī)制進(jìn)行討論。

決策域是為了達(dá)到遷移交換機(jī)目的而形成的決策區(qū)域。當(dāng)網(wǎng)絡(luò)中控制器性能較差時(shí)，它會(huì)通告鄰居控制器其負(fù)載信息，并發(fā)出交換機(jī)遷移請(qǐng)求，同時(shí)，鄰居控制器會(huì)選擇接受或拒絕請(qǐng)求，接受請(qǐng)求的鄰居控制器會(huì)建立決策域，并做出遷移策略。在網(wǎng)絡(luò)中，多個(gè)決策域可以同時(shí)進(jìn)行，決策域之間不存在重疊。為了構(gòu)建決策域，本文引入控制器cj的鄰居集的概念。c i與cj形成鄰居集必須滿足以下條件：cj的控制域至少有一個(gè)交換機(jī)與ci中交換機(jī)相連，即ci和cj的控制域相連；交換機(jī)遷移只發(fā)生在2 個(gè)相鄰的控制器之間。如圖2 所示，控制器c1的鄰居控制器包括c2、c3、c4，由于控制器c1過載，會(huì)向鄰居控制器請(qǐng)求建立遷移決策域，由于控制器c3過載，選擇拒絕參與聯(lián)盟決策，因此，控制器c1、c2、c4會(huì)建立決策域Ω={c1,c2,c4}。

圖2 決策域

為了確定收益函數(shù)，由于優(yōu)化式(9)是全局化目標(biāo)函數(shù)，也是控制器實(shí)施交換機(jī)遷移的目的，為了設(shè)計(jì)分布式算法，需要對(duì)式(9)進(jìn)行改進(jìn)，定義控制器之間博弈的收益函數(shù)為

其中，τx和ηx分別是當(dāng)前控制器的平均流建立時(shí)間和控制開銷。通過式(13)所示的收益函數(shù)，控制器之間通過合作、博弈，以獲得更小的流建立時(shí)間和控制開銷。每個(gè)控制器計(jì)算其收益函數(shù)并獨(dú)立做出決策。隨著網(wǎng)絡(luò)負(fù)載的變化，活動(dòng)控制器的利用率和時(shí)延也發(fā)生變化，從而獲得的收益也不同。

對(duì)于給定的網(wǎng)絡(luò)拓?fù)洌刂破鲿?huì)向其鄰居控制器通告交換機(jī)遷移請(qǐng)求，構(gòu)建決策域并進(jìn)行遷移交換機(jī)行為。多個(gè)決策域可以同時(shí)進(jìn)行但并不重疊，通過控制器之間的相互交流，最終達(dá)到全網(wǎng)控制器負(fù)載均衡的目的。在決策域中，多控制器做出遷移策略的行為，建模為n人合作博弈模型，交換機(jī)為商品，控制器為博弈參與者，通過各控制器的競爭博弈，來決定將要遷移的交換機(jī)和目標(biāo)控制器，整個(gè)過程可分為3 個(gè)階段。

階段1在SDN 中，每個(gè)控制器實(shí)時(shí)計(jì)算自身和鄰域控制器的狀態(tài)，當(dāng)某一控制器過載時(shí)，會(huì)通告鄰域控制器交換機(jī)遷移請(qǐng)求，鄰域控制器根據(jù)自身狀態(tài)，選擇接受或拒絕請(qǐng)求，選擇接受的控制器會(huì)建立決策域。

階段2在決策域中，遷出控制器會(huì)隨機(jī)選擇交換機(jī)，參與博弈的控制器會(huì)計(jì)算接受交換機(jī)所付出的收益函數(shù)。

階段3若決策域中存在控制器接受交換機(jī)遷移，則啟動(dòng)交換機(jī)遷移機(jī)制，通告其他控制器交換機(jī)遷移活動(dòng)。待交換機(jī)遷移完成后，控制器集合會(huì)更新自身資源利用率和平均流建立時(shí)間，返回階段1。

控制器之間通過聯(lián)盟博弈來實(shí)施交換機(jī)的遷移，交換機(jī)遷移由單個(gè)控制器獨(dú)立運(yùn)行算法，多個(gè)控制器協(xié)同實(shí)現(xiàn)，這里需要對(duì)OpenFlow 協(xié)議進(jìn)行擴(kuò)展，使之支持多控制器協(xié)同機(jī)制，控制器之間的通信過程如圖3 所示。當(dāng)控制器ck向鄰居控制器發(fā)出請(qǐng)求時(shí)，鄰居控制器cn、cm回復(fù)遷移請(qǐng)求，選擇是否建立聯(lián)盟決策域，當(dāng)控制器ck、cn、cm形成聯(lián)盟決策域時(shí)，會(huì)計(jì)算收益函數(shù)，選擇要遷移的交換機(jī)以及遷移的目標(biāo)控制器，然后啟動(dòng)交換機(jī)遷移，通告其他控制器正在進(jìn)行交換機(jī)遷移活動(dòng)，待遷移結(jié)束后，控制器ck、cn、cm更新自身資源利用率、控制開銷以及流建立時(shí)間，并向其鄰居廣播更新。

圖3 控制器之間的通信過程

算法1 為基于聯(lián)盟博弈的自適應(yīng)交換機(jī)遷移機(jī)制。通過控制器博弈，每個(gè)控制器試圖最小化流建立時(shí)間和控制開銷。在此過程中，基于收益函數(shù)，一個(gè)或多個(gè)鄰居控制器可以實(shí)施負(fù)載均衡，共同分擔(dān)過載控制器的流請(qǐng)求（步驟12)～步驟19)）。當(dāng)網(wǎng)絡(luò)負(fù)載較低時(shí)，輕載控制器觸發(fā)控制器休眠消息（步驟6)），將其休眠以節(jié)約電力，如算法2 所示。類似地，隨著負(fù)載的增加，過載控制器可以卸載交換機(jī)到鄰居控制器或觸發(fā)控制器啟動(dòng)消息（步驟8)），如算法3 所示。待交換機(jī)遷移完畢，SDN 控制器互相通信共享網(wǎng)絡(luò)狀態(tài)信息，例如收益矩陣、資源利用率、流建立時(shí)間和控制開銷（步驟17)和步驟18)）。

算法1基于聯(lián)盟博弈的自適應(yīng)交換機(jī)遷移機(jī)制

輸入控制器?交換機(jī)之間的初始關(guān)系X=[xij]，控制器資源利用率閾值γmax和γmin，控制器流建立時(shí)間閾值τmax

輸出控制器?交換機(jī)之間新的映射關(guān)系

23) 系統(tǒng)沒有任何交換機(jī)要求遷移，算法收斂

當(dāng)控制平面資源利用率小于0.1 時(shí)，輕載控制器會(huì)運(yùn)行算法2 以觸發(fā)相關(guān)控制器休眠，節(jié)省控制資源。此時(shí)，網(wǎng)絡(luò)流量較少，這說明控制器足以處理這些數(shù)據(jù)流請(qǐng)求，出于節(jié)能的考慮，控制平面會(huì)休眠一些控制器，以節(jié)省控制資源。由于一些控制器的休眠，其上的交換機(jī)要遷移到其他控制器上，因此，會(huì)造成其他控制器的資源利用率和收益產(chǎn)生變化。因此，算法2 的核心思想是選擇合適的控制器進(jìn)行休眠（步驟6)），同時(shí)將其上的交換機(jī)遷移到其他的控制器上，并更新網(wǎng)絡(luò)資源狀態(tài)，包括控制器?交換機(jī)映射關(guān)系、每個(gè)控制器新的資源利用率和產(chǎn)生的當(dāng)前收益（步驟9)～步驟11)），一旦獲得遷移所有交換機(jī)的解決方案，輕載控制器就會(huì)觸發(fā)自我休眠（步驟12)），然后返回算 法1 執(zhí)行負(fù)載均衡算法，以最小化控制開銷和流建立時(shí)間。

算法2資源利用率較低場景下的交換機(jī)遷移

輸入控制器?交換機(jī)之間的原始初始關(guān)系X=[xij]，控制器資源利用率閾值γmax和γmin，控制器流建立時(shí)間閾值τmax

輸出控制器?交換機(jī)之間新的映射關(guān)系

當(dāng)控制平面資源利用率大于0.9 時(shí)，過載控制器應(yīng)啟動(dòng)算法3，確定其所管理的一組交換機(jī)，將這些交換機(jī)卸載到相鄰的控制器上。在此過程中，控制器執(zhí)行2 個(gè)過程：觸發(fā)新控制器，將過載控制器管理的交換機(jī)卸載到新的控制器（步驟6)～步驟12)）。首先，該算法選擇距離過載控制器較近的休眠控制器啟動(dòng)，并優(yōu)先選擇過載控制器中流請(qǐng)求較大的交換機(jī)進(jìn)行遷移（步驟7)～步驟9)），為了檢查最佳的交換機(jī)遷移方案，它會(huì)計(jì)算收益函數(shù)，以衡量卸載交換機(jī)對(duì)其鄰居控制器的收益可能產(chǎn)生的影響。然后，控制器請(qǐng)求卸載交換機(jī)到影響最小的控制器。最后，返回算法1 執(zhí)行負(fù)載均衡算法，以最小化控制開銷和流建立時(shí)間。

算法3資源利用率較高場景下的交換機(jī)遷移

輸入控制器?交換機(jī)之間的原始初始關(guān)系X=[xij]，控制器資源利用率閾值γmax和γmin，控制器流建立時(shí)間閾值τmax

輸出控制器?交換機(jī)之間新的映射關(guān)系

6 仿真結(jié)果分析

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

本節(jié)對(duì)所提機(jī)制的性能進(jìn)行仿真驗(yàn)證，實(shí)驗(yàn)環(huán)境設(shè)置如下。

本文選擇RYU[22]作為實(shí)驗(yàn)控制器，并使用Mininet[23]作為測試平臺(tái)?？紤]到RYU 和Mininet之間的性能干擾，本文將Mininet 和RYU 分別安裝在不同的物理設(shè)備上。本文配備6 臺(tái)具有相同實(shí)驗(yàn)配置的機(jī)器，英特爾酷睿i7@、3.6 GHz，4 GB RAM，2 Gbit/s 網(wǎng)卡和Ubuntu14.04 LTS。其中5 臺(tái)機(jī)器運(yùn)行RYU 控制器，另一臺(tái)則運(yùn)行Mininet，Iperf 用于在主機(jī)之間生成流量。

仿真采用拓?fù)銲nterllifiber，取自the Internet topology zoo[24]，其中包含73 個(gè)節(jié)點(diǎn)、93 條鏈路。實(shí)驗(yàn)中每個(gè)交換機(jī)接入2 個(gè)主機(jī)。為了模擬動(dòng)態(tài)的網(wǎng)絡(luò)流量，Iperf 生成動(dòng)態(tài)流量，數(shù)據(jù)流在主機(jī)上的生成和消失服從泊松分布。

6.2 仿真結(jié)果分析

將本文所提CGSM 機(jī)制與控制器?交換機(jī)靜態(tài)映射（SSC,static switch-controller）機(jī)制、基于貪心背包算法的控制器?交換機(jī)映射（DCP-GK,dynamic controller provisioning using greedy knapsack）機(jī)制和控制器利用率感知的交換機(jī)遷移（UMS,utilization-aware migrating switch）機(jī)制進(jìn)行對(duì)比。其中，SSC[25]為控制器部署按照交換機(jī)的距離進(jìn)行聚類分析，并劃分管理域，一旦控制器部署完成便不會(huì)改變控制器?交換機(jī)關(guān)聯(lián)關(guān)系；DCP-GK[15]基于貪心背包算法進(jìn)行交換機(jī)遷移；UMS[26]優(yōu)先將交換機(jī)遷移到利用率最低控制器上。

6.2.1 實(shí)驗(yàn)1

實(shí)驗(yàn)1 對(duì)4 種方案的控制器資源利用率進(jìn)行對(duì)比，如圖4 所示。從圖4 中可以看出，隨著流請(qǐng)求速率的增大，4 種方案的控制器資源利用率也在增大；在不同的流請(qǐng)求速率下，本文所提CGSM 機(jī)制的控制器資源利用率均高于其他方案。CGSM 能適應(yīng)網(wǎng)絡(luò)流量，動(dòng)態(tài)地增加或減少控制器資源，保證控制平面資源利用率在0.1～0.9，實(shí)現(xiàn)了控制器資源的合理利用。

6.2.2 實(shí)驗(yàn)2

圖5 和圖6 分別顯示了4 種方案的控制開銷和流建立時(shí)間。從圖5 和圖6 中可以看出，UMS 優(yōu)先將交換機(jī)遷移到利用率較低的控制器，算法單一，控制開銷相對(duì)較低，但由于遷移的控制器距離較遠(yuǎn)，導(dǎo)致流建立時(shí)間偏大；DCP-GK 基于貪心算法選擇遷移策略，難以實(shí)現(xiàn)最優(yōu)控制；CGSM 通過控制器之間相互合作、聯(lián)合博弈以最大化控制開銷和流建立時(shí)間的加權(quán)和，與DCP-GK 相比，CGSM 能減少約19%的控制開銷和30%的平均流建立時(shí)間。

圖4 4 種方案的控制器資源利用率

圖5 4 種方案的控制開銷

圖6 4 種方案的流建立時(shí)間

6.2.3 實(shí)驗(yàn)3

為了驗(yàn)證CGSM 機(jī)制的性能，實(shí)驗(yàn)3 從the Internet topology zoo 網(wǎng)絡(luò)拓?fù)渲羞x取4 個(gè)規(guī)模差異較大的網(wǎng)絡(luò)拓?fù)溥M(jìn)行仿真實(shí)驗(yàn)，網(wǎng)絡(luò)拓?fù)浼皡?shù)設(shè)置如表1 所示。

表1 網(wǎng)絡(luò)拓?fù)鋮?shù)

圖7 和圖8 顯示了不同網(wǎng)絡(luò)拓?fù)湎? 種方案的歸一化的控制開銷和流建立時(shí)間。從圖7 和圖8 中可以看出，由于 UMS 交換機(jī)遷移選擇僵化和DCP-GK 基于貪心算法遷移交換機(jī)，從本質(zhì)上都是集中式算法，且都是貪婪算法，難以實(shí)現(xiàn)全局的最優(yōu)控制。與UMS 和DCP-GK 相比，CGSM 采用分布式算法，通過控制器聯(lián)合博弈，最大化自身收益，實(shí)現(xiàn)了控制器?交換機(jī)的優(yōu)化映射，降低了網(wǎng)絡(luò)中通信開銷，減少了流建立時(shí)間。

圖7 不同網(wǎng)絡(luò)拓?fù)湎? 種方案的控制開銷

圖8 不同網(wǎng)絡(luò)拓?fù)湎? 種方案的流建立時(shí)間

圖9 顯示了不同網(wǎng)絡(luò)拓?fù)湎? 種方案的控制器負(fù)載均衡率。從圖9 可以看出，較其他算法，CGSM的控制器負(fù)載更均衡，SSC 由于采用靜態(tài)部署，不適應(yīng)網(wǎng)絡(luò)流量變化，其負(fù)載均衡性能最差。UMS和DCP-GK 本質(zhì)上都是貪婪算法，難以實(shí)現(xiàn)全局優(yōu)化，負(fù)載均衡性能有限。CGUM 可以動(dòng)態(tài)調(diào)整控制器狀態(tài)，保障控制器資源的動(dòng)態(tài)供應(yīng)，以及控制器和交換機(jī)動(dòng)態(tài)的映射關(guān)系，能更好地適應(yīng)流量特征，實(shí)現(xiàn)了更合理的交換機(jī)遷移機(jī)制和較好的負(fù)載均衡率。

圖9 不同網(wǎng)絡(luò)拓?fù)湎? 種方案的負(fù)載均衡率

7 結(jié)束語

本文對(duì)SDN 控制器和交換機(jī)映射不合理導(dǎo)致控制平面性能低下的問題，提出了一種基于聯(lián)盟博弈的自適應(yīng)交換機(jī)遷移機(jī)制——CGSM。CGSM采用分布式算法，將控制器和交換機(jī)映射問題建模為組合優(yōu)化問題，并設(shè)計(jì)了自適應(yīng)交換機(jī)遷移機(jī)制，通過控制器協(xié)調(diào)合作、聯(lián)合博弈以最大化自身利益，實(shí)現(xiàn)了全局優(yōu)化的控制器?交換機(jī)映射方案。仿真結(jié)果表明，相比現(xiàn)有的交換機(jī)遷移算法，該機(jī)制同時(shí)減小約19%的控制開銷和30%的平均流建立時(shí)間，獲得了較高的控制器資源利用率和良好的負(fù)載均衡。