基于最小代價(jià)路徑的交換機(jī)遷移方法研究

賴英旭，蒲葉瑋，劉靜,3

（1.北京工業(yè)大學(xué)信息學(xué)部，北京 100124；2.信息保障技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京 100072；3.西安電子科技大學(xué)陜西省網(wǎng)絡(luò)與系統(tǒng)安全重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710071）

1 引言

軟件定義網(wǎng)絡(luò)（SDN,software-defined network）將網(wǎng)絡(luò)的轉(zhuǎn)發(fā)和控制功能分離，更加方便地實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)的控制，具有比傳統(tǒng)網(wǎng)絡(luò)更靈活的優(yōu)勢(shì)，所以被業(yè)界用來解決傳統(tǒng)網(wǎng)絡(luò)結(jié)構(gòu)僵化問題[1-2]。但當(dāng)流量出現(xiàn)激增或者其他變化時(shí)，控制器與交換機(jī)之間無法迅速地適應(yīng)這種負(fù)載改變，尤其是SDN 部署在大規(guī)模網(wǎng)絡(luò)時(shí)，會(huì)導(dǎo)致控制平面負(fù)載不均衡，控制器也更容易受到安全威脅[3]。

如何保護(hù)控制器，尤其是骨干控制器免受安全威脅與攻擊，提高SDN 控制平面的安全性，是一個(gè)非常重要的課題[4]。在SDN 中，根據(jù)OpenFlow協(xié)議的描述，當(dāng)流量到達(dá)時(shí)，若交換機(jī)的流表沒有條目可以匹配該流量，則交換機(jī)將向控制器發(fā)送Packet_In 數(shù)據(jù)分組來請(qǐng)求路由信息。然而該機(jī)制可能被攻擊者利用，向控制器發(fā)起攻擊，令控制器過載，導(dǎo)致系統(tǒng)崩潰，甚至導(dǎo)致控制器的級(jí)聯(lián)故障[5]。

骨干控制器是SDN 的核心，會(huì)接收到更多來自交換機(jī)的請(qǐng)求，處理大量的消息，這使它們更容易被惡意攻擊者識(shí)別或被惡意流量吞沒。為了保護(hù)骨干控制器，使其難以被識(shí)別，通過交換機(jī)遷移算法，將骨干控制器的流量遷移到其他控制器，降低骨干控制器被識(shí)別、被攻擊的可能性，同時(shí)使控制器之間的負(fù)載盡可能達(dá)到均衡。

本文的主要貢獻(xiàn)如下。

1)為了減少骨干控制器被識(shí)別的可能性，同時(shí)減少遷移交換機(jī)所產(chǎn)生的代價(jià)，本文提出基于最小代價(jià)路徑的交換機(jī)遷移算法（SMCP,switch migration algorithm based on minimum cost path）。通過改進(jìn)的迪杰斯特拉算法獲取最小代價(jià)遷移路徑，根據(jù)控制器的負(fù)載狀態(tài)，以及待遷移交換機(jī)的流量優(yōu)先級(jí)來確定最優(yōu)遷移交換機(jī)集合。本文算法可以確保遷移后控制平面負(fù)載有較好的均衡性，減少骨干控制器被監(jiān)聽、被識(shí)別的可能性，減少了遷移代價(jià)，同時(shí)保證重要流量被優(yōu)先處理。

2)本文提出的SMCP 通過減少遷移次數(shù)來進(jìn)一步降低遷移所產(chǎn)生的代價(jià)。對(duì)于過載控制器，采用一次均衡方法來降低其負(fù)載，在之后的每個(gè)均衡過程，本文算法都只進(jìn)行一次遷移操作，減少了遷移次數(shù)，降低了遷移代價(jià)，從而提高了系統(tǒng)的穩(wěn)定性。

3)為了減少頻繁遷移，規(guī)避不必要遷移操作，本文的遷移模型中加入了負(fù)載預(yù)測模塊。傳統(tǒng)方法僅通過控制器閾值來確定是否遷移，一旦負(fù)載值大于閾值就執(zhí)行遷移，這樣會(huì)產(chǎn)生大量的遷移代價(jià)并使系統(tǒng)的穩(wěn)定性降低。比如控制器在當(dāng)前時(shí)刻是超過閾值的，但是下一時(shí)刻控制器流量回歸正常，此時(shí)的遷移是不必要的，并且會(huì)產(chǎn)生相應(yīng)的不必要的代價(jià)。負(fù)載預(yù)測模塊可以預(yù)測下一時(shí)刻的負(fù)載情況，從而確定目標(biāo)控制器以及遷移觸發(fā)時(shí)機(jī)，減少不必要的遷移，保證系統(tǒng)穩(wěn)定性。

4)本文針對(duì)遷移過程中可能產(chǎn)生的孤立節(jié)點(diǎn)問題給出了解決方案。遷移某個(gè)或者某些交換機(jī)時(shí)可能會(huì)造成孤立節(jié)點(diǎn)問題，孤立節(jié)點(diǎn)內(nèi)的交換機(jī)會(huì)同時(shí)請(qǐng)求本域和目標(biāo)域控制器，給2 個(gè)控制器帶來負(fù)擔(dān)，降低控制器性能。本文提出孤立節(jié)點(diǎn)處理算法，解決遷移過程中出現(xiàn)的孤立節(jié)點(diǎn)問題，減少控制器響應(yīng)時(shí)間。

2 相關(guān)研究

傳統(tǒng)的SDN 實(shí)現(xiàn)依賴于集中式控制器，并且具有與性能和可伸縮性相關(guān)的若干限制。相關(guān)研究工作指出，部署分布式控制器是一種解決問題的有效方法[6-7]。

為了提高SDN 中控制平面的性能，應(yīng)該考慮多方面的問題，例如，最大化控制器的性能，把控制器部分工作移交到轉(zhuǎn)發(fā)設(shè)備，使一組控制器節(jié)點(diǎn)能夠?qū)崿F(xiàn)分布式控制平面。這些工作提出了一個(gè)邏輯上集中的控制平面，并著手解決全局視圖和狀態(tài)分布式控制平面的一致性，實(shí)現(xiàn)更好的可擴(kuò)展性，但當(dāng)大量的不均勻流量到達(dá)這些分布式控制器時(shí)，這種方法會(huì)導(dǎo)致控制器之間的負(fù)載不平衡[8]。

Cheng 等[9]提出了一種博弈決策機(jī)制，用于將交換機(jī)從過載控制器遷移到空閑控制器，解決了帶約束條件的資源利用率最大化問題，但缺乏博弈觸發(fā)機(jī)制，并且整個(gè)過程會(huì)額外產(chǎn)生較大的網(wǎng)絡(luò)開銷。Liang 等[10]通過構(gòu)建控制器集群的交換機(jī)遷移機(jī)制來均衡控制器負(fù)載，動(dòng)態(tài)地遷移交換機(jī)，實(shí)現(xiàn)控制器間的負(fù)載轉(zhuǎn)移，但是該操作導(dǎo)致控制器響應(yīng)時(shí)間增加。在分布式最近遷移算法[11]中，選擇物理位置最近的控制器作為目標(biāo)控制器，方便操作，不過該方法很可能帶來新的負(fù)載不平衡。在最大化資源利用率遷移算法（MUMA,maximizing resource utilization migration algorithm）中[12]，當(dāng)發(fā)生負(fù)載不平衡時(shí)，控制器隨機(jī)選擇一個(gè)交換機(jī)用于遷移，不過算法沒有考慮負(fù)載均衡性，遷移后可能產(chǎn)生新的過載情況。Wang 等[13]以提高遷移效率為目的，基于貪婪算法，通過構(gòu)建遷移效率模型對(duì)遷移成本和負(fù)載平衡率進(jìn)行優(yōu)化。Ye 等[14]提出利用資源消耗模型來解決交換機(jī)遷移問題，將交換機(jī)看作資源消耗者，控制器作為資源提供者，用馬爾可夫鏈求解該問題，能達(dá)到較高的負(fù)載均衡率，但是由于待遷移的交換機(jī)及目標(biāo)控制器都是隨機(jī)選擇的，導(dǎo)致算法的效率較低。Li 等[15]提出了一種基于模糊多目標(biāo)粒子群算法的動(dòng)態(tài)切換遷移策略，通過求解多目標(biāo)優(yōu)化問題來解決控制器平面的負(fù)載均衡問題，算法綜合考慮了代價(jià)、效率與均衡性，但算法的運(yùn)算量和數(shù)據(jù)的存儲(chǔ)量都很大，對(duì)網(wǎng)絡(luò)本身的穩(wěn)定性也有一定的負(fù)面影響。Kim 等[16]提出了一種稱為漸進(jìn)和聲搜索（P-HS,progressive-harmony search）的啟發(fā)式算法，用于控制平面的負(fù)載均衡，解決了分布式SDN 控制器環(huán)境中的動(dòng)態(tài)控制器供應(yīng)問題，算法可以最大程度地減少交換機(jī)與控制器之間的通信時(shí)延，不過遷移過程所消耗的代價(jià)、遷移效率以及遷移后造成的新問題并沒有考慮全面。

通過調(diào)查國內(nèi)外的研究發(fā)現(xiàn)，控制平面負(fù)載不均衡問題普遍采用交換機(jī)遷移的策略來解決，但是遷移時(shí)機(jī)以及遷入遷出控制器的選擇比較僵硬，大部分遷移算法都是超過固定的閾值后，選擇負(fù)載較大的控制器下的交換機(jī)進(jìn)行遷移，然后判斷遷移后的過載控制器是否仍然過載，不斷進(jìn)行遷移操作直至恢復(fù)正常，雖然單次遷移效率較高，但是對(duì)于傳輸速率較大的網(wǎng)絡(luò)來說，在遷移過程中容易產(chǎn)生更大的網(wǎng)絡(luò)代價(jià)。對(duì)于控制器負(fù)載在當(dāng)前時(shí)刻超過閾值，但是下一時(shí)刻回歸正常，這種情況的遷移是不必要的，并且未考慮遷移后所產(chǎn)生的孤立節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)的影響，反而加重了控制器負(fù)擔(dān)，使遷移策略并不完善。

為了解決上述問題，本文在遷移方法中加入了負(fù)載預(yù)測算法，從而解決遷移時(shí)機(jī)以及遷入遷出控制器的選擇僵硬問題，通過預(yù)測控制器下一時(shí)刻的負(fù)載情況從而確定遷移觸發(fā)時(shí)機(jī)和遷出控制器、目標(biāo)控制器集合，減少頻繁的遷移，提高網(wǎng)絡(luò)的穩(wěn)定性。通過交換機(jī)集合遷移的方式，減少遷移次數(shù)，縮短了遷移所花費(fèi)的時(shí)間，同時(shí)劃分流量優(yōu)先級(jí)，保證重要流可以優(yōu)先處理。通過孤立節(jié)點(diǎn)處理算法，解決遷移過程中出現(xiàn)的孤立節(jié)點(diǎn)問題，減少交換機(jī)跨域請(qǐng)求，提高控制器響應(yīng)時(shí)間。

3 問題描述與遷移模型建模

本文研究背景是分布式架構(gòu)下的SDN。在SDN中，邏輯集中控制器（決策者）通過向交換機(jī)發(fā)送帶有處理策略的數(shù)據(jù)分組來管理數(shù)據(jù)平面。由于在一定時(shí)間內(nèi)流量具有不穩(wěn)定性和不均衡特性，當(dāng)控制器域內(nèi)交換機(jī)流量突然增加時(shí)，會(huì)影響控制器對(duì)請(qǐng)求的響應(yīng)，造成控制器過載。

3.1 問題描述

分布式多控制器架構(gòu)如圖1 所示。當(dāng)更多的交換機(jī)與控制器B 連接，或控制器B 聚合了大量的流請(qǐng)求時(shí)，控制器 B 處于負(fù)載過重狀態(tài)。根據(jù)OpenFlow1.3 協(xié)議的定義，如果交換機(jī)的主控制器處于過載或低效狀態(tài)，此交換機(jī)可以從控制平面中選擇一個(gè)其他控制器作為新的主控制器，因此該過程被描述為交換機(jī)遷移[17]。

圖1 分布式多控制器架構(gòu)

3.2 符號(hào)和定義

整個(gè)網(wǎng)絡(luò)用圖G=(V,E)來表示，其中V和E分別表示節(jié)點(diǎn)集合和鏈路集合。控制器集合用C表示，交換機(jī)集合用S表示。?=[xij]M×N是所有網(wǎng)絡(luò)元素的連接矩陣，其中M和N表示控制器和交換機(jī)個(gè)數(shù)，xij表示交換機(jī)Si和控制器Cj之間的映射關(guān)系，如式(1)所示。

1)控制器的負(fù)載值定義為控制器接收來自其域內(nèi)交換機(jī)Packet_In 的數(shù)量，如式(2)所示。

其中，LCj表示控制器的負(fù)載值，表示控制器Cj從交換機(jī)Si接收到的Packet_In 數(shù)量。

2)控制器狀態(tài)定義為φj，φj的值如式(3)所示。

其中，LCthreshold為控制器閾值。當(dāng)控制器負(fù)載值大于閾值時(shí)，設(shè)定為1。

3)當(dāng)φj=1時(shí)，需要通過遷移操作來降低其負(fù)載。遷移過程中會(huì)產(chǎn)生一定的代價(jià)，遷移代價(jià)主要由以下3 個(gè)部分組成：消息交換代價(jià)、負(fù)載增加代價(jià)、規(guī)則部署代價(jià)。遷移代價(jià)定義如式(4)所示。

其中，rmc是交換機(jī)遷移的消息交換代價(jià)，rlc是負(fù)載增加代價(jià)，rrc是規(guī)則部署代價(jià)。

消息交換代價(jià)rmc。遷移請(qǐng)求將不同的交換機(jī)消息傳遞給目標(biāo)控制器，因此該過程將產(chǎn)生消息交換代價(jià)，如式(5)所示。

其中，ε表示交換機(jī)的平均通信速率，hir表示交換機(jī)Si到控制器Cr之間的跳數(shù)，hjk表示交換機(jī)Sj到控制器Ck之間的跳數(shù)，xir和xjk分別表示控制器Cr和Ck域內(nèi)設(shè)備的連接關(guān)系，trk表示控制器Cr域內(nèi)的交換機(jī)與目標(biāo)控制器Ck的時(shí)延總和。

負(fù)載增加代價(jià)rlc。負(fù)載增加代價(jià)定義如式(6)所示。

規(guī)則部署代價(jià)rrc。選擇要遷移的交換機(jī)時(shí)，控制器必須在域內(nèi)將遷移規(guī)則flow_mod 部署到此交換機(jī)中，其定義如式(7)所示。

其中，δrule是控制器發(fā)送的flow_mod 規(guī)則分組。

4)用控制器負(fù)載的標(biāo)準(zhǔn)差來表示負(fù)載平衡因子，如式(8)所示。

交換機(jī)Sk遷移之后，新的負(fù)載平衡因子如式(9)所示。

5)遷移效率的定義如式(10)所示。

6)在遷出控制器Cm域中選擇目標(biāo)交換機(jī)時(shí)，Cm以高遷移效率遷移部分交換機(jī)節(jié)點(diǎn)以減輕其負(fù)載；從時(shí)延的角度來看，Cm優(yōu)先放棄遠(yuǎn)離它的交換機(jī)。因此，定義目標(biāo)交換機(jī)被選擇的概率如式(11)所示。

7)鏈路擁塞率，用吞吐量和鏈路的帶寬容量的比值來表示。

其中，qlink表示鏈路的擁塞率，B表示鏈路的吞吐量。通過發(fā)送PORT_STATS_REQUEST 消息到交換機(jī)，獲取交換機(jī)端口接受和發(fā)送的字節(jié)數(shù)以及時(shí)間。鏈路的吞吐量用式(13)表示。

其中，T、R分別表示發(fā)送、接收的字節(jié)，t表示統(tǒng)計(jì)的時(shí)間。擁塞率可由式(12)和式(13)計(jì)算得到。

8)通過計(jì)算交換機(jī)被選擇的概率以及鏈路擁塞率，得到優(yōu)先級(jí)因子，用來在最小代價(jià)路徑中確定目標(biāo)交換機(jī)。設(shè)θ為優(yōu)先級(jí)因子，如式(14)所示。

3.3 流量類別分類

在遷移過程中，除了要考慮遷移代價(jià)和負(fù)載均衡度，還要考慮流量類別，需要讓重要流具有較高的遷移優(yōu)先級(jí)。為了保證重要流能夠被優(yōu)先處理，本文通過對(duì)流量進(jìn)行識(shí)別，劃分優(yōu)先級(jí)。

SDN 結(jié)合深度分組檢測（DPI,deep packet inspection）[18]技術(shù)可以做到對(duì)流量的識(shí)別。本文的流量劃分方案如表1 所示，通過劃分比特率將流量分為6 類。

表1 流量分類

根據(jù)不同流量的特點(diǎn)，本文采用的負(fù)載優(yōu)先級(jí)劃分方案如表2 所示。

表2 優(yōu)先級(jí)劃分

3.4 孤立點(diǎn)問題

遷移策略決定將交換機(jī)從某個(gè)域遷移到另外一個(gè)域，以減少該域控制器的負(fù)載。如果有一個(gè)或者多個(gè)交換機(jī)連接在待遷移的目標(biāo)交換機(jī)之下，此時(shí)遷移該目標(biāo)交換機(jī)可能會(huì)出現(xiàn)孤立節(jié)點(diǎn)問題，即該節(jié)點(diǎn)不再屬于任意一個(gè)域，而要請(qǐng)求2 個(gè)域，導(dǎo)致控制器響應(yīng)時(shí)間增加。遷移的目標(biāo)交換機(jī)越多，這種額外的負(fù)擔(dān)越大。

如圖2(a)所示，若控制器A 超過閾值，假設(shè)要將圖中的S1節(jié)點(diǎn)遷移到控制器B 中，遷移完成后如圖2(b)所示，此時(shí)S2和S3這2 個(gè)節(jié)點(diǎn)成為孤立節(jié)點(diǎn)，孤立節(jié)點(diǎn)S2和S3請(qǐng)求控制器時(shí)，不僅要向本域內(nèi)控制器A 發(fā)出請(qǐng)求，還要向遷移目標(biāo)域中的控制器B 發(fā)出請(qǐng)求，這將給2 個(gè)控制器帶來負(fù)擔(dān)，導(dǎo)致性能下降。

圖2 遷移前后的控制器集群對(duì)比

4 遷移模型

本文遷移模型如圖3 所示，包括4 個(gè)模塊：流量統(tǒng)計(jì)模塊、流量預(yù)測模塊、遷移策略決策模塊及動(dòng)作管理模塊，每個(gè)模塊對(duì)應(yīng)功能具體如下。

1)流量統(tǒng)計(jì)模塊。該模塊主要負(fù)責(zé)統(tǒng)計(jì)控制器接收來自自身域內(nèi)交換機(jī)的流量信息，評(píng)估當(dāng)前控制器的流量負(fù)載，并判斷當(dāng)前控制器在監(jiān)測時(shí)間段內(nèi)，流量是否超過預(yù)設(shè)的閾值。

2)流量預(yù)測模塊。該模塊接收來自統(tǒng)計(jì)模塊的負(fù)載統(tǒng)計(jì)信息與初步計(jì)算信息，根據(jù)預(yù)測模型預(yù)測控制器負(fù)載，得到負(fù)載預(yù)測矩陣，確定遷出控制器、目標(biāo)控制器，判斷是否需要遷移，避免頻繁遷移。

3)遷移策略決策模塊。該模塊作為本文方案的核心模塊，負(fù)責(zé)根據(jù)網(wǎng)絡(luò)信息，利用相應(yīng)模型及工具，求解并決策具體交換機(jī)遷移策略。

4)動(dòng)作管理模塊。該模塊接收來自策略決策模塊的具體遷移策略，并負(fù)責(zé)向數(shù)據(jù)層交換機(jī)發(fā)送具體策略，實(shí)現(xiàn)交換機(jī)遷移過程。

圖3 動(dòng)態(tài)遷移模型

4.1 流量預(yù)測模塊

現(xiàn)階段的遷移算法大都是控制器超過閾值就進(jìn)行遷移，這樣會(huì)產(chǎn)生大量的遷移代價(jià)。比如控制器在當(dāng)前時(shí)刻是超過閾值的，但是下一時(shí)刻控制器流量回歸正常，則該時(shí)刻的遷移是不必要的，所以需要一種方法來避免這種不必要的遷移動(dòng)作的發(fā)生。

自回歸滑動(dòng)平均（ARMA,auto-regressive moving average）模型可以有效分析短時(shí)間內(nèi)流量穩(wěn)定的網(wǎng)絡(luò)數(shù)據(jù)，但對(duì)于存在網(wǎng)絡(luò)異常的長時(shí)間網(wǎng)絡(luò)流量數(shù)據(jù)卻并不適合。其主要原因在于該模型建立的前提是被分析數(shù)據(jù)是平穩(wěn)隨機(jī)過程，而SDN 流量具有非線性和不規(guī)則性的特點(diǎn)[19]，所以普通的ARMA 模型不再適用。

差分整合滑動(dòng)平均自回歸（ARIMA，auto-regressive integrated moving average）模型[20]利用有限次差分操作后可以實(shí)現(xiàn)數(shù)據(jù)轉(zhuǎn)化，使數(shù)據(jù)成為平穩(wěn)數(shù)據(jù)，實(shí)現(xiàn)簡單，所以在本文流量預(yù)測模塊采用ARIMA 模型。

ARIMA（p,d,q）模型的計(jì)算式為

其中，B為滯后算子，有

ARIMA 建模首先需要判斷被分析數(shù)據(jù)的平穩(wěn)性，對(duì)于非平穩(wěn)序列采取差分運(yùn)算去掉其趨勢(shì)或周期性，然后確定數(shù)據(jù)的自回歸參數(shù)p和滑動(dòng)平均參數(shù)q，具體的建模及預(yù)測流程如下。

1)采用迪基-福勒檢驗(yàn)方法檢測被分析數(shù)據(jù)的平穩(wěn)性。

2)數(shù)據(jù)平穩(wěn)化。差分d次，若數(shù)據(jù)平穩(wěn)則d為0。

3)參數(shù)分析。分別求得ACF 和PACF 曲線，觀察并根據(jù)AIC 判斷擬合效果接近程度，確定p和q。

4)構(gòu)建模型。利用上述步驟得到的參數(shù)構(gòu)建ARIMA（p,d,q）模型，并利用流量統(tǒng)計(jì)模塊所得到的流量數(shù)據(jù)訓(xùn)練檢測。

5)預(yù)測分析。根據(jù)預(yù)測算法得到遷出控制器、目標(biāo)控制器以及遷移觸發(fā)時(shí)機(jī)。

算法1控制器負(fù)載預(yù)測算法

算法1 的詳細(xì)流程如下。流量統(tǒng)計(jì)模塊完成統(tǒng)計(jì)與初步評(píng)估之后，流量預(yù)測模塊會(huì)收到來自流量統(tǒng)計(jì)模塊的負(fù)載信息，初步判斷過載控制器和目標(biāo)控制器。通過構(gòu)建的預(yù)測模型來預(yù)測下一時(shí)刻的負(fù)載情況，得到控制器負(fù)載預(yù)測矩陣，判斷下一時(shí)刻過載控制器，如果依然過載，則選擇該控制器為遷出控制器，并發(fā)出遷移觸發(fā)信號(hào)Move。通過負(fù)載矩陣判斷下一時(shí)刻目標(biāo)控制器是否是最低值，如果是，則選其為目標(biāo)控制器；否則，選擇矩陣中最低值控制器作為目標(biāo)控制器，并發(fā)送Move_Start 信號(hào)給過載控制器，響應(yīng)Move 信號(hào)，開始遷移操作。

4.2 遷移策略決策模塊

該模塊是整個(gè)遷移模型的核心，本文提出基于改進(jìn)迪杰斯特拉的最小代價(jià)遷移算法，來減少遷移代價(jià)，保證控制器的性能。

4.2.1 確定最小代價(jià)路徑

首先通過預(yù)測模型得到遷出控制器、目標(biāo)控制器。起點(diǎn)v0為遷出控制器，權(quán)值設(shè)置為遷移的代價(jià)。

在圖G=(V,E)中，初始化點(diǎn)vi與點(diǎn)vj的之間的權(quán)值w[i][j]（由式(4)得出），即遷移該節(jié)點(diǎn)所產(chǎn)生的代價(jià)，尋找由頂點(diǎn)v0到目標(biāo)點(diǎn)的最小代價(jià)路徑。

基于改進(jìn)的迪杰斯特拉最小代價(jià)路徑算法步驟如下。

1)評(píng)估函數(shù)F(n)=f(n)+g(n)，其中g(shù)(n)為啟發(fā)函數(shù)，表示從當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的遷移代價(jià)估值；f(n)為前n個(gè)點(diǎn)所產(chǎn)生的代價(jià)。

2)邊的松弛。檢查邊(s,t)是否存在某一點(diǎn)z，使f((s,z)+(z,t))＜f(s,t)，則更新最小路徑。

3)采用啟發(fā)式搜索，在這里評(píng)估函數(shù)F（n）用D[v]表示，并且在函數(shù)中加入當(dāng)前點(diǎn)到終點(diǎn)的歐氏距離。所以D[v]定義為

其中，啟發(fā)函數(shù)用歐氏距離表示，g(v)=distance(v,t)。d[v]表示起點(diǎn)到當(dāng)前點(diǎn)v的路徑長度，即所花費(fèi)的遷移代價(jià)。

設(shè)起點(diǎn)、終點(diǎn)分別是s、t，邊為e(v,m)，則松弛邊e為

如果D[m]＞d[v]+e(v,m)+distance(m,t))，則更新D[m]為

因?yàn)閐[m]是初始點(diǎn)s→m路徑長，此時(shí)邊e(v,m)的另一個(gè)端點(diǎn)為v，松弛該邊為s→v和v→w，故

所以得到改進(jìn)條件為

式(20)是采用啟發(fā)式搜索的迪杰斯特拉算法。

本節(jié)獲取預(yù)測算法所得到的遷出控制器、目標(biāo)控制器，計(jì)算遷移交換機(jī)節(jié)點(diǎn)所產(chǎn)生的代價(jià)，然后通過改進(jìn)迪杰斯特拉算法，得到一條最小代價(jià)路徑path[]。

4.2.2 對(duì)于遷移節(jié)點(diǎn)的選擇

把path[]這條路徑上屬于遷出控制器域的交換機(jī)節(jié)點(diǎn)加入待選擇節(jié)點(diǎn)集合MigNode{}中，并對(duì)集合中的節(jié)點(diǎn)進(jìn)行判斷，判斷遷移目標(biāo)交換機(jī)節(jié)點(diǎn)是否會(huì)出現(xiàn)孤立節(jié)點(diǎn)，把出現(xiàn)的孤立節(jié)點(diǎn)和目標(biāo)交換機(jī)節(jié)點(diǎn)組成一個(gè)邏輯節(jié)點(diǎn)，并且將這個(gè)邏輯節(jié)點(diǎn)加入待選擇節(jié)點(diǎn)集合中。

遷移優(yōu)先級(jí)S_Pri 與遷移因子θ成正比，與流量的pri 成反比（優(yōu)先級(jí)越高pri 越小）。

如果流的pri=1，則優(yōu)先處理該流，直接將該節(jié)點(diǎn)加入待遷移集合MigNode{}中。

計(jì)算目標(biāo)控制器能接受的流量LCin，L Cin定義為目標(biāo)控制器負(fù)載和控制平面控制器的負(fù)載均值的差值，如式(22)所示。

其中，LCtarget是目標(biāo)控制器負(fù)載。

節(jié)點(diǎn)選擇問題實(shí)際是動(dòng)態(tài)規(guī)劃問題，優(yōu)化的目標(biāo)是：在總?cè)萘縇Cin的限制下，選擇的節(jié)點(diǎn)的優(yōu)先級(jí)最大。若存在pri=1 的流，則優(yōu)先處理該節(jié)點(diǎn)，剩余負(fù)載空間lc=LCin-Load[path(pri=1)]。

1)問題分析

在前i個(gè)交換機(jī)節(jié)點(diǎn)中，選擇若干個(gè)節(jié)點(diǎn)加入待遷移集合{}內(nèi)。

狀態(tài)：在前i個(gè)交換機(jī)節(jié)點(diǎn)中，選擇若干節(jié)點(diǎn)加入所剩負(fù)載空間為lc 的待遷移集合MigNode{}中獲得最大優(yōu)先級(jí)。

決策：是否選擇第i個(gè)交換機(jī)節(jié)點(diǎn)加入MigNode{}中。

2)狀態(tài)轉(zhuǎn)移方程

設(shè)F(i,j)表示負(fù)載容量為lc 的待遷移集合加入前i個(gè)交換機(jī)節(jié)點(diǎn)后所占據(jù)的最大優(yōu)先級(jí)，則有

其中，F(xiàn)(0,j)=0，Load[i]表示第i個(gè)節(jié)點(diǎn)的負(fù)載，S_Pri[i]表示第i個(gè)節(jié)點(diǎn)的遷移優(yōu)先級(jí)。

4.2.3 對(duì)于孤立節(jié)點(diǎn)的處理

通過上述方法，將部分孤立節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)作為邏輯節(jié)點(diǎn)一起遷移，解決部分孤立節(jié)點(diǎn)，不是所有的孤立節(jié)點(diǎn)都可以跟隨目標(biāo)交換機(jī)節(jié)點(diǎn)一起遷移到目標(biāo)控制器域中去。未被解決的孤立節(jié)點(diǎn)內(nèi)的交換機(jī)在遷移完成后會(huì)同時(shí)請(qǐng)求本域和目標(biāo)域控制器，給2 個(gè)控制器帶來負(fù)擔(dān)，造成控制器性能降低，這是亟待解決的一個(gè)問題。

從圖G中的遷出控制器節(jié)點(diǎn)出發(fā)，訪問該節(jié)點(diǎn)鄰接頂點(diǎn)Vi1,Vi2,…,Vin，然后訪問Vi1相鄰的V21,V22,…,V2n，直到遍歷所有節(jié)點(diǎn)，得到廣度優(yōu)先遍歷生成樹。

存儲(chǔ)方法：用孩子兄弟表示法來存儲(chǔ)，如圖4所示，每個(gè)節(jié)點(diǎn)由3 個(gè)部分組成。

圖4 節(jié)點(diǎn)構(gòu)成示意

孤立節(jié)點(diǎn)處理算法偽代碼如算法2 所示。

算法2孤立節(jié)點(diǎn)處理算法

算法2 的詳細(xì)流程如下。首先判斷目標(biāo)交換機(jī)節(jié)點(diǎn)是不是葉子節(jié)點(diǎn)，如果是葉子節(jié)點(diǎn)，則不會(huì)產(chǎn)生孤立節(jié)點(diǎn)，直接刪除。當(dāng)目標(biāo)交換機(jī)節(jié)點(diǎn)的孩子節(jié)點(diǎn)不為空時(shí)，如果存在右兄弟，找到右兄弟的左孩子，并將目標(biāo)交換機(jī)節(jié)點(diǎn)的孩子節(jié)點(diǎn)連接到右兄弟的孩子節(jié)點(diǎn)上；否則，找到其前驅(qū)節(jié)點(diǎn)，連接到其前驅(qū)節(jié)點(diǎn)上。該節(jié)點(diǎn)的孩子節(jié)點(diǎn)如果為空，證明已經(jīng)處理掉該節(jié)點(diǎn)遷移所產(chǎn)生的孤立節(jié)點(diǎn)，刪掉該節(jié)點(diǎn)。處理的原則就是盡量保持在和原先交換機(jī)一個(gè)結(jié)構(gòu)層次上，即盡量將其孩子節(jié)點(diǎn)連接到同一級(jí)交換機(jī)下。

4.3 動(dòng)作管理模塊

在該模塊中完成交換機(jī)遷移操作并更新網(wǎng)絡(luò)元素的連接矩陣Ω=[xij]M×N，改變控制器角色。如圖5 所示，首先通過預(yù)測模塊確定的過載控制器和目標(biāo)控制器，過載控制器選擇要遷移的遷移交換機(jī)組，并將觸發(fā)遷移信號(hào)Move 發(fā)送到目標(biāo)控制器Ctarget。Ctarget接收到Move 信號(hào)后將響應(yīng)遷移開始信號(hào)Move_Start，開始執(zhí)行遷移動(dòng)作。如果交換機(jī)遷移完成，則遷移交換機(jī)的主控制器將從過載控制器轉(zhuǎn)移到目標(biāo)控制器，遷移活動(dòng)中斷，并且會(huì)將更新消息廣播到整個(gè)網(wǎng)絡(luò)。

圖5 交換機(jī)遷移過程

基于最小代價(jià)路徑的交換機(jī)遷移算法偽代碼如算法3 所示。

算法3基于最小代價(jià)路徑的交換機(jī)遷移算法

算法3 的詳細(xì)流程如下。通過流量統(tǒng)計(jì)模塊以及預(yù)測模塊，首先得到過載控制器、目標(biāo)控制器和確定遷移時(shí)機(jī)，通過改進(jìn)的迪杰斯特拉算法得到2個(gè)控制器之間的最小代價(jià)遷移路徑。計(jì)算path[]路徑上的屬于過載控制器的節(jié)點(diǎn)負(fù)載之和，因?yàn)檫^載控制器一般是主干控制器，或者其他需要頻繁處理更多消息的控制器，目標(biāo)控制器的選擇一般是在很長的一段時(shí)間內(nèi)負(fù)載較少的控制器，所以如果不超過目標(biāo)控制器的容量閾值，則直接進(jìn)行遷移，并判斷遷移后是否出現(xiàn)孤立節(jié)點(diǎn)，同時(shí)得到邏輯節(jié)點(diǎn)LogNode，將邏輯節(jié)點(diǎn)加入待選擇節(jié)點(diǎn)集合A中，處理孤立節(jié)點(diǎn)；否則，計(jì)算目標(biāo)控制器所接受的負(fù)載，計(jì)算A中節(jié)點(diǎn)的最優(yōu)負(fù)載組合MigNode[]，進(jìn)行遷移，并判斷遷移后是否出現(xiàn)孤立節(jié)點(diǎn)，處理孤立節(jié)點(diǎn)。

5 實(shí)驗(yàn)結(jié)果分析

本文的實(shí)驗(yàn)環(huán)境為Mininet+OpenDaylight。通過在 Mininet 中運(yùn)行自定義的拓?fù)洳⑦B接OpenDaylight 來搭建本文實(shí)驗(yàn)的網(wǎng)絡(luò)環(huán)境，利用iperf 工具模擬發(fā)流測試控制器的性能。3 個(gè)ODL控制器C0、C1和C2部署在控制器集群中，12 個(gè)OpenvSwitch 連接到3 個(gè)控制器上。使用iperf 模擬不同速率的數(shù)據(jù)分組。實(shí)驗(yàn)拓?fù)淙鐖D6 所示。

圖6 實(shí)驗(yàn)拓?fù)?/p>

1)控制器負(fù)載

本文定義控制器負(fù)載占比為實(shí)際控制器收到Packet_In 請(qǐng)求數(shù)據(jù)分組與控制器容量的比值，如式(24)所示。

圖7 和圖8 清楚地顯示在相同的流量發(fā)送情況下，使用SMCP 算法和未使用任何負(fù)載均衡算法控制器負(fù)載占比的對(duì)比。

圖7 靜態(tài)分配下控制器負(fù)載占比

圖8 SMCP 下控制器負(fù)載占比

圖7 顯示了沒有負(fù)載平衡的3 個(gè)控制器的負(fù)載占比。圖8 是在運(yùn)行SMCP 算法后的控制器負(fù)載占比。由圖8 可知，在實(shí)現(xiàn)SMCP 算法后，負(fù)載只要高于閾值就會(huì)觸發(fā)Move_Req 信號(hào)，負(fù)載在下一時(shí)刻沒有降低至閾值之下，則響應(yīng)請(qǐng)求，通過遷移操作快速降低其負(fù)載，使控制器的負(fù)載基本維持在閾值以下；而在靜態(tài)分配情況下，控制器負(fù)載超過閾值，隨時(shí)間增加，過載情況繼續(xù)加劇。

2)響應(yīng)時(shí)間

通過測試控制器的響應(yīng)時(shí)間來衡量不同算法的負(fù)載均衡性，采用控制器負(fù)載均衡動(dòng)態(tài)自適應(yīng)算法（DALB,dynamic and adaptive algorithm for controller load balancing）[21]以及最大化資源利用率遷移算法（MUMA）來進(jìn)行比較。

響應(yīng)時(shí)間對(duì)比如圖9 所示。由圖9 可知，本文提出的SMCP 算法的控制器響應(yīng)時(shí)間較MUMA 和DALB 算法更短，其性能優(yōu)于MUMA 和DALB 算法的控制器性能。圖10 表示發(fā)送速率不變，隨著網(wǎng)絡(luò)規(guī)模的增加，控制器的平均響應(yīng)時(shí)間變化。實(shí)驗(yàn)表明，相比其他2 種負(fù)載均衡算法，SMCP 算法的控制器響應(yīng)時(shí)間更短，性能更優(yōu)。

圖9 響應(yīng)時(shí)間對(duì)比

圖10 網(wǎng)絡(luò)規(guī)模與響應(yīng)時(shí)間關(guān)系

3)均衡時(shí)間

在實(shí)驗(yàn)中增大發(fā)送速率，直到C0過載，通過比較控制器的負(fù)載以及不同的遷移算法實(shí)現(xiàn)控制器均衡的時(shí)間來衡量算法的優(yōu)劣性。

均衡時(shí)間對(duì)比如圖11 所示，反映了MUMA、DALB 和SMCP 中C0的負(fù)載隨時(shí)間變化的曲線。在150 s 時(shí)，C0接收到大量來自本域交換機(jī)的請(qǐng)求，造成過載。在方案DALB 中，需要2 個(gè)均衡過程才能完成，在300 s 時(shí)完成遷移。在方案SMCP 中，控制器通過一個(gè)均衡過程降低負(fù)載，在250 s 時(shí)完成遷移操作。而在MUMA 中，由于交換機(jī)的選擇是隨機(jī)的，C0的負(fù)載降低時(shí)間比DALB 和SMCP 都要長。因此，本文提出的方案縮短了遷移時(shí)間，使控制平面快速完成負(fù)載均衡。

圖11 均衡時(shí)間對(duì)比

4)系統(tǒng)穩(wěn)定性

系統(tǒng)的穩(wěn)定性與遷移次數(shù)有關(guān)，因?yàn)樵谶w移過程中，某些交換機(jī)可能無法及時(shí)處理新連接，從而造成遷移中斷等問題。

在當(dāng)前規(guī)模下，SMCP 算法只需要遷移1 次，而DALB 和MUMA 算法則需要遷移2 次。由表3可知，由于SMCP 每次負(fù)載均衡都只需要遷移1 次，隨著交換機(jī)規(guī)模不斷增加，這種差距表現(xiàn)出明顯的不斷擴(kuò)大的趨勢(shì)。

表3 不同網(wǎng)絡(luò)規(guī)模下的平均遷移次數(shù)

頻繁的遷移還會(huì)破壞網(wǎng)絡(luò)的穩(wěn)定性，圖12 是隨時(shí)間變化的遷移次數(shù)的變化曲線。由圖12 可以看出，由于MUMA 基于隨機(jī)選擇，無法保證遷移后控制平面是否均衡，因此遷移的頻率較高。DALB算法在一定程度上降低了遷移次數(shù)，但是遷移頻率依然高于SMCP。而SMCP 通過遷移交換機(jī)集合，在每個(gè)負(fù)載均衡過程中只需要遷移1 次，而且每次遷移操作都可以較好地實(shí)現(xiàn)控制平面的負(fù)載均衡。

圖12 遷移次數(shù)對(duì)比

吞吐量也是衡量系統(tǒng)穩(wěn)定性的一個(gè)重要指標(biāo)。圖13 和圖14 是3 種算法吞吐量的對(duì)比。由圖13可知，第200 s 開始，以3:1:2 的比例向控制器C0、C1、C2發(fā)送數(shù)據(jù)分組，Packet_In 請(qǐng)求增多，控制器間的負(fù)載不均衡導(dǎo)致吞吐量下降，MUMA 算法在250 s 后吞吐量有所上升，但基本保持在一種比較低的狀態(tài)；雖然DALB 吞吐量恢復(fù)到正常水平，但是與SMCP 算法相比，需要更長的時(shí)間；SMCP 算法能較快地遷移過載控制器C0的部分負(fù)載，且遷移后控制平面有較好的均衡性，從而提高了系統(tǒng)吞吐量。在圖14 中，網(wǎng)絡(luò)空閑時(shí)3 種算法吞吐量都不斷增長，隨著負(fù)載的加重，MUMA 的吞吐量快速降低，SMCP 和DALB 算法吞吐量也有所下降，但基本維持在較高的吞吐量，SMCP 下降速度要優(yōu)于DALB 算法，吞吐量也更高。

在衡量系統(tǒng)穩(wěn)定性時(shí)，分組丟失率也是非常重要的一個(gè)指標(biāo)。選擇控制器C0和C2域內(nèi)的2 臺(tái)主機(jī)進(jìn)行傳輸，通過發(fā)送不同速率的Packet_In 數(shù)據(jù)分組來對(duì)比3 種算法的分組丟失率。從圖15 實(shí)驗(yàn)結(jié)果可知，當(dāng)發(fā)送速率大于2 Mbit/s 時(shí)，3 種算法的分組丟失率都開始增加，MUMA 算法不能很好地感知網(wǎng)絡(luò)狀態(tài)，遷移后也可能造成新的過載，分組丟失率隨著發(fā)送速率的增加快速增加；SMCP 算法的控制器、交換機(jī)選取較靈活，并且遷移過程中充分考慮到時(shí)延、帶寬和跳數(shù)等影響網(wǎng)絡(luò)狀態(tài)的因素，與DALB算法相比，分組丟失率在一定程度上有所下降。

圖13 吞吐量隨時(shí)間變化曲線

圖14 吞吐量隨發(fā)送速率變化曲線

圖15 3 種算法的分組丟失率對(duì)比

6 結(jié)束語

本文就如何保護(hù)控制器，尤其是骨干控制器免受安全威脅與攻擊，提高SDN 控制平面的安全性問題，提出了基于最小代價(jià)路徑的交換機(jī)遷移方法。通過獲取數(shù)據(jù)平面負(fù)載信息，在預(yù)測模塊實(shí)現(xiàn)控制器負(fù)載預(yù)測，得到確定遷出-目標(biāo)控制器集合，根據(jù)最小代價(jià)路徑算法，得到一條最小代價(jià)路徑，對(duì)該路徑上的節(jié)點(diǎn)通過節(jié)點(diǎn)選擇算法，得到目標(biāo)交換機(jī)集合，實(shí)施遷移操作，最后通過孤立節(jié)點(diǎn)處理算法解決孤立節(jié)點(diǎn)問題。本文方法的優(yōu)勢(shì)如下。1)基于最小代價(jià)路徑的交換機(jī)遷移算法，得到一條最小代價(jià)遷移路徑，結(jié)合控制器的狀態(tài)，以及交換機(jī)負(fù)載的優(yōu)先級(jí)確定遷移交換機(jī)集合，然后將遷移集合內(nèi)的交換機(jī)遷移到目標(biāo)控制器，可以減少遷移所產(chǎn)生的代價(jià)，并且保證重要流優(yōu)先遷移。2)通過交換機(jī)集合遷移的方式，減少遷移次數(shù)，縮短遷移所花費(fèi)的時(shí)間，提高網(wǎng)絡(luò)的穩(wěn)定性。3)在本文的遷移模型中還加入了負(fù)載預(yù)測模塊，傳統(tǒng)的方式是判斷控制器負(fù)載情況，只要超過閾值就遷移，這樣會(huì)出現(xiàn)大量不必要的遷移，本文通過預(yù)測控制器未來時(shí)刻的負(fù)載情況，根據(jù)負(fù)載預(yù)測矩陣確定遷出-目標(biāo)控制器集合，以及觸發(fā)遷移時(shí)機(jī)，減少頻繁遷移，保證系統(tǒng)穩(wěn)定性。4)通過孤立節(jié)點(diǎn)處理算法減少控制器的響應(yīng)時(shí)間，提高了控制器性能。通過實(shí)驗(yàn)驗(yàn)證，本文算法可以很好地實(shí)現(xiàn)控制平面的負(fù)載均衡，減少主干控制器被監(jiān)聽被識(shí)別的概率，并且減少了遷移次數(shù)，降低了遷移代價(jià)，提高了控制器性能。