[發(fā)明專利]一種基于混合啟發(fā)式算法的跨域虛擬網(wǎng)絡(luò)映射方法

在審

• 申請?zhí)枺?/td>: 202011615443.3
• 申請日: 2020-12-30
• 公開（公告）號: CN112887220A
• 公開（公告）日: 2021-06-01
• 發(fā)明（設(shè)計）人: 張培穎;劉方琳
• 申請（專利權(quán)）人: 中國石油大學(xué)（華東）
• 主分類號: H04L12/803
• 分類號: H04L12/803;H04L12/721;G06N3/12
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發(fā)明提供了一種用于虛擬網(wǎng)絡(luò)映射的方法。本發(fā)明利用混合啟發(fā)式算法，對傳統(tǒng)映射方法中存在的問題進(jìn)行了優(yōu)化，使用動態(tài)計算的交叉概率和基于信息素的突變基因選擇策略來提高方法的靈活性，并引入基于負(fù)載平衡的權(quán)重更新機制，在平衡負(fù)載的同時，降低映射失敗的可能性。本發(fā)明提供的技術(shù)方案可以彌補啟發(fā)式映射方法的不足，降低映射成本，提高映射成功率，并在映射平均報價，鏈路負(fù)載均衡，映射成本效益比，接受率和運行時間等多個性能指標(biāo)上表現(xiàn)良好。

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

本發(fā)明涉及一種基于混合啟發(fā)式算法的跨域虛擬網(wǎng)絡(luò)映射方法，特別涉及一種考慮負(fù)載均衡的虛擬鏈路映射方法。

背景技術(shù)

物聯(lián)網(wǎng)，大數(shù)據(jù)，云計算和邊緣計算作為第三次信息革命的代表技術(shù)，通過它們的協(xié)調(diào)發(fā)展已逐漸成為我們生活中不可或缺的一部分。然而，三項技術(shù)的協(xié)調(diào)發(fā)展導(dǎo)致網(wǎng)絡(luò)服務(wù)的數(shù)量和規(guī)模空前增加，這極大地增加了對高流量網(wǎng)絡(luò)通信和靈活的網(wǎng)絡(luò)建設(shè)的需求。在該背景下，傳統(tǒng)的網(wǎng)絡(luò)架構(gòu)(即每次調(diào)整都需要重建底層物理網(wǎng)絡(luò)結(jié)構(gòu))已無法滿足需求，從而導(dǎo)致了互聯(lián)網(wǎng)僵化的問題。在這方面，大量注意力被轉(zhuǎn)移到網(wǎng)絡(luò)虛擬化技術(shù)中，該技術(shù)被視為解決互聯(lián)網(wǎng)僵化問題的核心技術(shù)。通過這種運行機制，底層物理網(wǎng)絡(luò)資源的可以得到高效、可控的利用,從而整體上提升網(wǎng)絡(luò)服務(wù)能力。

網(wǎng)絡(luò)虛擬化的重要意義可大體總結(jié)為以下三點：首先，對新技術(shù)研究的方面來說，可以為未來網(wǎng)絡(luò)技術(shù)、體系結(jié)構(gòu)以及業(yè)務(wù)應(yīng)用的實驗驗證提供一個真實的網(wǎng)絡(luò)環(huán)境。其次，多個網(wǎng)絡(luò)服務(wù)提供商的虛擬業(yè)務(wù)網(wǎng)絡(luò)可以共同部署在共享的底層物理網(wǎng)絡(luò)上,每個虛擬業(yè)務(wù)網(wǎng)絡(luò)可以為用戶提供定制化服務(wù)，從而使網(wǎng)絡(luò)業(yè)務(wù)的開發(fā)、部署、維護(hù)不再受到底層物理網(wǎng)絡(luò)的束縛。因此，網(wǎng)絡(luò)虛擬化技術(shù)被視為未來網(wǎng)絡(luò)環(huán)境中的重要基礎(chǔ)技術(shù)之一。

此外，虛擬網(wǎng)絡(luò)映射是網(wǎng)絡(luò)虛擬化中的重要技術(shù)之一，原因如下：(1)網(wǎng)絡(luò)虛擬化環(huán)境中，底層物理網(wǎng)絡(luò)需要同時承載多個虛擬邏輯網(wǎng)絡(luò)，虛擬網(wǎng)絡(luò)映射機制和算法將決定如何為不同虛擬網(wǎng)絡(luò)請求分配資源，這直接影響了底層物理網(wǎng)絡(luò)資源的利用效率；(2)網(wǎng)絡(luò)中不同業(yè)務(wù)應(yīng)用對網(wǎng)絡(luò)能力的需求各不相同，因此，虛擬網(wǎng)絡(luò)映射系統(tǒng)是否能實現(xiàn)靈活、多元化的映射目標(biāo)，是虛擬網(wǎng)絡(luò)能否滿足業(yè)務(wù)需求的重要保障；(3)當(dāng)前，網(wǎng)絡(luò)規(guī)模的逐漸增大，如何提高虛擬網(wǎng)絡(luò)映射算法的運行效率對虛擬化網(wǎng)絡(luò)的普及十分重要，這將決定網(wǎng)絡(luò)虛擬化技術(shù)是否能適用于大規(guī)模網(wǎng)絡(luò)應(yīng)用；(4)隨著云計算技術(shù)的發(fā)展，越來越多的企業(yè)和個人開始部署各自的虛擬化網(wǎng)絡(luò)環(huán)境，業(yè)務(wù)需求的增多要求管理系統(tǒng)提供更加靈活、可靠的映射算法。綜上所述，虛擬網(wǎng)絡(luò)映射問題的研究對網(wǎng)絡(luò)虛擬化技術(shù)的發(fā)展有著十分重要的意義。

已有的虛擬網(wǎng)絡(luò)映射方法可大致分為兩類，基于最優(yōu)化方法與基于啟發(fā)式算法。其中，啟發(fā)式算法是相對于最優(yōu)化算法提出的。一個問題的最優(yōu)算法求得該問題每個實例的最優(yōu)解。啟發(fā)式算法可以在可接受的時間內(nèi)求得近似最優(yōu)解。此外，啟發(fā)式算法一般用于解決NP-hard問題，其中NP是指非確定性多項式。

在網(wǎng)絡(luò)虛擬化問題中，大多數(shù)情況下，在規(guī)模較大的問題中，尋找最優(yōu)解決方案往往會消耗大量的計算資源。基于此原因，最優(yōu)化方法在大規(guī)模網(wǎng)絡(luò)環(huán)境中并沒有得到廣泛的應(yīng)用。此外，虛擬網(wǎng)絡(luò)映射問題已被證明是一種NP-hard問題，因此，研究以可接受的代價給出可行解的啟發(fā)式算法具有重要意義。

然而，先前的工作主要考慮算法框架的設(shè)計，例如：將啟發(fā)式算法與禁忌搜索算法或模擬退火算法結(jié)合使用，以避免陷入局部最優(yōu)解，或者將遺傳算法的變異算子添加到其他啟發(fā)式算法來增加種群多樣性。但是，算法步驟的細(xì)節(jié)通常保留傳統(tǒng)設(shè)計。例如，以靜態(tài)方式設(shè)置遺傳算法中的交叉概率，并且以隨機方式選擇突變中的突變基因。這使得算法的運行時間更短，代碼更易于實現(xiàn)，但是靜態(tài)方法過于依賴經(jīng)驗，無法靈活地適應(yīng)多種環(huán)境。另外，當(dāng)使用最短路徑算法估計鏈路映射的成本時，由于底物網(wǎng)絡(luò)資源不足，最短路徑可能無法滿足虛擬鏈路的帶寬資源約束。但是，與傳統(tǒng)的網(wǎng)絡(luò)環(huán)境相比，具有大量高需求物理設(shè)備(例如救災(zāi)，醫(yī)療，生命支持設(shè)備)的物聯(lián)網(wǎng)對網(wǎng)絡(luò)穩(wěn)定性和算法可靠性有更高的要求。因此，不合適的適應(yīng)度估計方法將導(dǎo)致適合度和質(zhì)量不匹配的映射方案，這將對物聯(lián)網(wǎng)環(huán)境中的物理世界造成更大的影響。