[發(fā)明專利]一種基于雙啟發(fā)式算法的SDN網(wǎng)絡(luò)控制器部署方法及系統(tǒng)

有效

• 申請?zhí)枺?/td>: 202010147799.2
• 申請日: 2020-03-05
• 公開（公告）號: CN111404731B
• 公開（公告）日: 2022-08-19
• 發(fā)明（設(shè)計）人: 管紹朋;李奕;張聰輝;孫文文
• 申請（專利權(quán)）人: 山東工商學(xué)院
• 主分類號: H04L41/0894
• 分類號: H04L41/0894;H04L41/0803;H04L41/0895;H04L41/14
• 代理公司: 濟(jì)南圣達(dá)知識產(chǎn)權(quán)代理有限公司 37221
• 代理人: 閆圣娟

本公開提出了一種基于雙啟發(fā)式算法的SDN網(wǎng)絡(luò)控制器部署方法及系統(tǒng)，方法包括如下步驟：以SDN網(wǎng)絡(luò)中的控制器與交換機(jī)的傳輸時延最小為目標(biāo)，建立SDN控制器部署問題模型；分別選擇一種啟發(fā)式算法作為主算法和輔算法，確定主算法的關(guān)鍵參數(shù)；采用作為輔算法的啟發(fā)式算法對主算法的關(guān)鍵參數(shù)進(jìn)行迭代優(yōu)化，獲得主算法優(yōu)化后的參數(shù)；根據(jù)優(yōu)化后的參數(shù)，采用主算法對SDN控制器部署問題模型進(jìn)行求解，獲得SDN網(wǎng)絡(luò)控制器在拓?fù)渲械淖鴺?biāo)以及與交換機(jī)的映射關(guān)系。本公開提出了雙啟發(fā)式算法，結(jié)合兩種啟發(fā)式算法，使用輔算法對主算法的關(guān)鍵參數(shù)進(jìn)行優(yōu)化，提高算法的性能，降低求解的難度，使得問題求解更準(zhǔn)確，求得的近似最優(yōu)解更優(yōu)。

技術(shù)領(lǐng)域

本公開涉及相關(guān)技術(shù)領(lǐng)域，具體的說，是涉及一種基于雙啟發(fā)式算法的SDN網(wǎng)絡(luò)控制器部署方法及系統(tǒng)。

背景技術(shù)

本部分的陳述僅僅是提供了與本公開相關(guān)的背景技術(shù)信息，并不必然構(gòu)成在先技術(shù)。

隨著云計算、物聯(lián)網(wǎng)、大數(shù)據(jù)等信息技術(shù)的爆炸式發(fā)展，對網(wǎng)絡(luò)處理海量數(shù)據(jù)提出了更高的要求，比如更低的丟包率，毫秒級的時延，以及更為苛刻的安全級別。傳統(tǒng)網(wǎng)絡(luò)架構(gòu)很難滿足這些要求，于是誕生了一種新型的網(wǎng)絡(luò)架構(gòu)——軟件定義網(wǎng)絡(luò)(softwaredefined network,SDN)，二者架構(gòu)區(qū)別如圖1所示。SDN特點是控制轉(zhuǎn)發(fā)分離、集中式控制、可編程、開放接口、虛擬化。解決了傳統(tǒng)計算機(jī)網(wǎng)絡(luò)硬件不開放、不可編程等帶來的問題。將傳統(tǒng)網(wǎng)絡(luò)中耦合的數(shù)據(jù)轉(zhuǎn)發(fā)功能和控制功能分離，設(shè)置獨立的控制層和數(shù)據(jù)層，控制層通過下發(fā)流表的方式控制底層SDN交換機(jī)的數(shù)據(jù)轉(zhuǎn)發(fā)。SDN相對于傳統(tǒng)網(wǎng)絡(luò)，簡化的控制平面的設(shè)計，提高了網(wǎng)絡(luò)管理的效率，同時還具備靈活和可擴(kuò)展的特性。而在SDN中，控制層占據(jù)絕對重要的地位，為確?？刂茖拥聂敯粜?，SDN通常采取邏輯集中的多控制器部署方式。

控制器的個數(shù)決定了網(wǎng)絡(luò)的成本，同樣也決定了網(wǎng)絡(luò)中的平均傳輸時延。早在2012年，Heller B等就提出了這個問題，并將其命名為CPP(Controller PlacementProblem)，并指出CPP是一個多目標(biāo)優(yōu)化問題，無法在有限的計算機(jī)資源內(nèi)求出其最優(yōu)解。以圖2中Internet2 OS3E拓?fù)錇槔瑘D中黑色實心圓為控制器部署位置，需要在34個節(jié)點中部署6個控制器，并建立控制器與交換機(jī)的映射關(guān)系，計算得使用最優(yōu)化算法無疑是無法求解的。

因此，在有限的時間內(nèi)求解CPP問題的近似解成為主流解決辦法，而啟發(fā)式算法為解決該問題提供了新思路。啟發(fā)式算法(heuristic algorithm)是相對于最優(yōu)化算法提出的。一個問題的最優(yōu)算法求得該問題每個實例的最優(yōu)解。啟發(fā)式算法可以這樣定義：一個基于直觀或經(jīng)驗構(gòu)造的算法，在可接受的花費(指計算時間和空間)下給出待解決組合優(yōu)化問題每一個實例的一個可行解，該可行解與最優(yōu)解的偏離程度一般不能被預(yù)計。發(fā)明人發(fā)現(xiàn)，算法的實質(zhì)是一種隨機(jī)算法，設(shè)置稍有不當(dāng)，就會對結(jié)果產(chǎn)生很大的影響。

發(fā)明內(nèi)容

本公開為了解決上述問題，提出了一種基于雙啟發(fā)式算法的SDN網(wǎng)絡(luò)控制器部署方法及系統(tǒng)，設(shè)置了雙啟發(fā)式算法分別作為求解的主算法和輔算法，使用輔算法對主算法的參數(shù)進(jìn)行優(yōu)化，再使用優(yōu)化過后的主算法對SDN控制器部署問題進(jìn)行求解，給出控制器坐標(biāo)以及與交換機(jī)的映射關(guān)系，實現(xiàn)對SDN控制器的合理部署。

為了實現(xiàn)上述目的，本公開采用如下技術(shù)方案：

一個或多個實施例提供了一種基于雙啟發(fā)式算法的SDN網(wǎng)絡(luò)控制器部署方法，包括如下步驟：

以SDN網(wǎng)絡(luò)中的控制器與交換機(jī)的綜合傳輸時延最小為目標(biāo)，建立SDN控制器部署問題模型；

選擇一種啟發(fā)式算法作為主算法，確定主算法的關(guān)鍵參數(shù)；

選擇一種啟發(fā)式算法作為輔算法，對主算法的關(guān)鍵參數(shù)進(jìn)行迭代優(yōu)化，獲得主算法優(yōu)化后的參數(shù)；

根據(jù)優(yōu)化后的參數(shù)，采用主算法對SDN控制器部署問題模型進(jìn)行求解，獲得SDN網(wǎng)絡(luò)控制器在拓?fù)渲械淖鴺?biāo)以及與交換機(jī)的映射關(guān)系，即為SDN網(wǎng)絡(luò)控制器的部署方案。