[發(fā)明專利]基于拓?fù)涓兄奶摂M網(wǎng)絡(luò)重映射方法

有效

• 申請?zhí)枺?/td>: 201310373370.5
• 申請日: 2013-08-23
• 公開（公告）號: CN103475504A
• 公開（公告）日: 2013-12-25
• 發(fā)明（設(shè)計）人: 王穎;李文璟;肖靄玲;邱雪松;孟洛明;王智立;陳興渝
• 申請（專利權(quán)）人: 北京郵電大學(xué)
• 主分類號: H04L12/24
• 分類號: H04L12/24;H04L12/46
• 代理公司: 北京路浩知識產(chǎn)權(quán)代理有限公司 11002
• 代理人: 王瑩

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

本發(fā)明涉及通信技術(shù)領(lǐng)域，尤其涉及一種基于拓?fù)涓兄奶摂M網(wǎng)絡(luò)重映射方法。

背景技術(shù)

網(wǎng)絡(luò)虛擬化是克服當(dāng)前因特網(wǎng)僵化狀況的一種新思路。通過網(wǎng)絡(luò)虛擬化技術(shù)，多個虛擬網(wǎng)絡(luò)可以共存于同一底層物理網(wǎng)絡(luò)之上，為終端用戶提供個性化的服務(wù)，有效地促進(jìn)了網(wǎng)絡(luò)創(chuàng)新的部署和應(yīng)用。網(wǎng)絡(luò)虛擬化將傳統(tǒng)的網(wǎng)絡(luò)服務(wù)提供商（Internet?Service?Provider，簡稱ISP）的設(shè)施與服務(wù)分離。由基礎(chǔ)設(shè)施提供商（Infrastructure?Provider，簡稱InP）負(fù)責(zé)管理和運營底層網(wǎng)絡(luò)設(shè)施；由服務(wù)提供商（Service?Provider，簡稱SP）租用InP的網(wǎng)絡(luò)資源組裝虛擬網(wǎng)絡(luò)，提供個性化的端到端服務(wù)。

虛擬網(wǎng)絡(luò)映射問題是網(wǎng)絡(luò)虛擬化技術(shù)面臨的一大難題，即當(dāng)SP發(fā)來帶有節(jié)點和鏈路約束的虛擬網(wǎng)絡(luò)創(chuàng)建請求時，為其分配InP持有的底層網(wǎng)絡(luò)資源。該問題是一個NP難(NP-hard)問題，早期關(guān)于虛擬網(wǎng)絡(luò)映射的研究只是單純地為該問題提供了啟發(fā)式的解決方法，但這些方法中都沒有考慮虛擬網(wǎng)絡(luò)映射的生存性問題。虛擬網(wǎng)絡(luò)映射的生存性，即在底層網(wǎng)絡(luò)設(shè)施發(fā)生故障時，如何對受到故障影響的已映射虛擬網(wǎng)絡(luò)進(jìn)行恢復(fù)，也就是由底層物理節(jié)點故障引起的虛擬網(wǎng)絡(luò)的重映射問題。現(xiàn)有的虛擬網(wǎng)絡(luò)重映射方法的基本思想是：SP在收到一個虛擬網(wǎng)絡(luò)創(chuàng)建請求時，對該請求進(jìn)行一定的擴充。在原請求的基礎(chǔ)上，增加一些虛擬節(jié)點和虛擬鏈路，為每個虛擬節(jié)點分配備份虛擬節(jié)點，為每條虛擬鏈路分配備份虛擬鏈路。在發(fā)生單一物理節(jié)點故障時，將受到影響的虛擬節(jié)點重映射到相對應(yīng)的備份虛擬節(jié)點所在的備份用物理節(jié)點上，然后將相關(guān)的虛擬鏈路重映射到其備份虛擬鏈路所在的備份用物理路徑上。

上述虛擬網(wǎng)絡(luò)重映射方法只有當(dāng)?shù)讓游锢砭W(wǎng)絡(luò)的剩余物理資源能夠同時滿足虛擬網(wǎng)絡(luò)對工作用和備份用資源的需求時，才會對該虛擬網(wǎng)絡(luò)創(chuàng)建請求進(jìn)行映射；在發(fā)生故障時，直接將受影響的虛擬資源遷移到備份用的物理資源上，雖然故障恢復(fù)的速度較快，但存在備份用資源浪費、虛擬網(wǎng)請求接收率低、及通常需要求解復(fù)雜的混合線性規(guī)劃等問題。

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

（一）要解決的技術(shù)問題

本發(fā)明的目的是提供一種基于拓?fù)涓兄奶摂M網(wǎng)絡(luò)重映射方法，使得在創(chuàng)建虛擬網(wǎng)絡(luò)時，不必考慮為其進(jìn)行復(fù)雜的備份，就能在物理網(wǎng)絡(luò)中發(fā)生節(jié)點故障時對受故障影響的虛擬網(wǎng)絡(luò)進(jìn)行重映射。

（二）技術(shù)方案

為了解決上述技術(shù)問題，本發(fā)明提出了一種基于拓?fù)涓兄奶摂M網(wǎng)絡(luò)重映射方法，包括：

S1、對底層物理網(wǎng)絡(luò)中每一個物理節(jié)點的候選物理節(jié)點集合和任意兩個物理節(jié)點間的候選物理路徑集合進(jìn)行初始化；

S2、當(dāng)有虛擬網(wǎng)絡(luò)創(chuàng)建的請求到達(dá)時，對其進(jìn)行虛擬網(wǎng)絡(luò)映射，并定期地向特定物理節(jié)點發(fā)送虛擬節(jié)點的鏡像文件；當(dāng)有虛擬網(wǎng)絡(luò)生命周期結(jié)束時，回收為其分配的物理節(jié)點及物理鏈路資源；

S3、當(dāng)物理節(jié)點發(fā)生故障時，獲取受該物理節(jié)點影響的虛擬節(jié)點集合，將受影響的虛擬節(jié)點集合重映射到該物理節(jié)點的候選物理節(jié)點集合中；

S4、查找受到故障物理節(jié)點影響的虛擬鏈路集合，獲取受影響的虛擬鏈路集合中每一條虛擬鏈路兩端的虛擬節(jié)點所在的物理節(jié)點，將受影響的虛擬鏈路集合重映射到相應(yīng)物理節(jié)點對間的候選物理路徑集合中。

優(yōu)選的，步驟S1中所述對底層物理網(wǎng)絡(luò)中每一個物理節(jié)點的候選物理節(jié)點集合進(jìn)行初始化包括：

對于每一個物理節(jié)點，其候選物理節(jié)點集合為滿足下式的所有物理節(jié)點的集合：