[發(fā)明專利]一種基于最大加權(quán)匹配的鏈路優(yōu)先虛擬網(wǎng)絡(luò)映射方法

有效

• 申請?zhí)枺?/td>: 202010067331.2
• 申請日: 2020-01-20
• 公開（公告）號: CN111245701B
• 公開（公告）日: 2021-08-31
• 發(fā)明（設(shè)計）人: 唐亞哲;陳立水;陸曉兵;陳星;李寧;王靜;王俊芳;吳巍
• 申請（專利權(quán)）人: 中國電子科技集團(tuán)公司第五十四研究所
• 主分類號: H04L12/46
• 分類號: H04L12/46;H04L12/721;H04L12/729
• 代理公司: 河北東尚律師事務(wù)所 13124
• 代理人: 王文慶

本發(fā)明公開了一種基于最大加權(quán)匹配的鏈路優(yōu)先虛擬網(wǎng)絡(luò)映射方法，涉及計算機網(wǎng)絡(luò)技術(shù)領(lǐng)域，尤其涉及虛擬網(wǎng)絡(luò)映射，本方法能有效減少虛擬鏈路的物理鏈路條數(shù)。本發(fā)明在鏈路優(yōu)先映射方法的基礎(chǔ)上，將隨機鏈路映射改為以鏈路距離最小化為目標(biāo)的映射方式，并且新定義一種鏈路綜合帶寬度量指標(biāo)，綜合考慮鏈路自身的帶寬和鄰接鏈路的帶寬，然后將最大加權(quán)匹配中的首條虛擬鏈路映射到綜合帶寬度量指標(biāo)最大的物理鏈路上，提升后續(xù)的映射成功概率。通過上述方案，本發(fā)明能夠有效減少虛擬網(wǎng)絡(luò)映射結(jié)果中虛擬鏈路的平均物理鏈路條數(shù)，并提升虛擬網(wǎng)絡(luò)的接受率。

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

本發(fā)明屬于計算機網(wǎng)絡(luò)技術(shù)領(lǐng)域，特別涉及一種基于最大加權(quán)匹配的鏈路優(yōu)先映射方法。

背景技術(shù)

網(wǎng)絡(luò)虛擬化技術(shù)可以在底層物理網(wǎng)絡(luò)上創(chuàng)建出多個邏輯上相互獨立的虛擬網(wǎng)絡(luò)，虛擬網(wǎng)絡(luò)映射問題是網(wǎng)絡(luò)虛擬化領(lǐng)域的重要研究內(nèi)容，高效的虛擬網(wǎng)絡(luò)映射算法可以提升網(wǎng)絡(luò)資源利用率，提供高質(zhì)量的虛擬網(wǎng)絡(luò)映射結(jié)果。

虛擬網(wǎng)絡(luò)映射問題本質(zhì)上是研究如何對物理網(wǎng)絡(luò)的資源進(jìn)行合理分配，但這種資源分配問題具有許多新特性，如請求的資源和待分配的資源均具有網(wǎng)絡(luò)結(jié)構(gòu)，分配資源的約束條件較多，因此是極具挑戰(zhàn)性的。如何設(shè)計虛擬網(wǎng)絡(luò)映射算法高效合理地進(jìn)行虛擬網(wǎng)絡(luò)映射是網(wǎng)絡(luò)虛擬化領(lǐng)域的關(guān)鍵技術(shù)。

目前虛擬網(wǎng)絡(luò)映射算法分為精確解算法和非精確解算法。精確解算法的總體思路是基于最優(yōu)化理論，將虛擬網(wǎng)絡(luò)映射問題建模并劃歸到數(shù)學(xué)規(guī)劃問題，通過最優(yōu)化理論求得數(shù)學(xué)規(guī)劃問題的最優(yōu)解。非精確解法一般通過啟發(fā)式的方式，利用待解問題的特性，通過特定的求解方式，在可接受的時間內(nèi)給出較優(yōu)的可行解。

不同算法對虛擬網(wǎng)絡(luò)映射失敗的情況也做了不同的處理，一類是直接拒絕映射失敗的虛擬網(wǎng)絡(luò)請求，每一個虛擬網(wǎng)絡(luò)請求到達(dá)便立即處理以保證應(yīng)用場景所需的實時性。另一類則設(shè)計了帶時間窗的處理模型，將在同一個時間窗內(nèi)到達(dá)的虛擬網(wǎng)絡(luò)請求按照其可能帶來的收益進(jìn)行從大到小的排序并依次嘗試映射。將映射失敗的虛擬網(wǎng)絡(luò)請求放回等待隊列，在下一個時間窗口中將等待隊列中的虛擬網(wǎng)絡(luò)請求取出并和新到達(dá)的虛擬網(wǎng)絡(luò)請求一同處理，若超過指定的時間還沒有被映射的請求將被拒絕。這樣處理雖然可以提升運營商的收益，但是虛擬網(wǎng)絡(luò)請求必須要等到時間窗口結(jié)束后才集中處理，這樣用戶申請?zhí)摂M網(wǎng)絡(luò)請求的實時性將無法被滿足。

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

本發(fā)明的所要解決的技術(shù)問題在于提供一種基于最大加權(quán)匹配的鏈路優(yōu)先虛擬網(wǎng)絡(luò)映射方法。

為實現(xiàn)上述目的，本發(fā)明采用以下技術(shù)方案：

一種基于最大加權(quán)匹配的鏈路優(yōu)先虛擬網(wǎng)絡(luò)映射方法，包括以下步驟：

步驟一：計算給定的網(wǎng)絡(luò)拓?fù)鋱D的最大加權(quán)匹配；

步驟二：將最大加權(quán)匹配中所有的虛擬鏈路按照帶寬需求進(jìn)行降序排序，對首條待映射的虛擬鏈路，將其映射到鏈路綜合帶寬度量指標(biāo)值最大的物理鏈路上，其余虛擬鏈路依次以鏈路距離最小為目標(biāo)選擇物理鏈路，即選擇與被映射的物理鏈路之間平均距離最小的物理鏈路；

步驟三：剩余未映射的虛擬節(jié)點按照資源值的大小進(jìn)行降序排序，然后依次映射到使整體鏈路資源開銷最小的物理節(jié)點上；

步驟四：剩余未被映射的虛擬鏈路使用KSP映射算法進(jìn)行映射。

其中，步驟二中鏈路綜合帶寬度量指標(biāo)值的計算公式為：