[發明專利]一種基于最小費用流模型的虛擬鏈路映射算法

有效

• 申請號: 201410088288.2
• 申請日: 2014-03-12
• 公開（公告）號: CN103841000B
• 公開（公告）日: 2017-05-24
• 發明（設計）人: 蔣云良;陳曉華;李春芝
• 申請（專利權）人: 湖州師范學院
• 主分類號: H04L12/46
• 分類號: H04L12/46;H04L12/24
• 代理公司: 北京天奇智新知識產權代理有限公司11340
• 代理人: 韓洪

【技術領域】

本發明涉及虛擬鏈路映射算法的技術領域，特別是基于最小費用流模型的虛擬鏈路映射算法的技術領域。

【背景技術】

網絡虛擬化，是未來因特網、云計算和軟件定義網絡的重要技術。多個虛擬網絡能夠共享同一底層物理網絡資源。虛擬化技術分割、整合網絡基礎設施資源，使得在不影響現有網絡情況下部署新的網絡架構、協議以及應用成為可能。

隨著網絡虛擬化技術的發展，多路徑虛擬鏈路映射成為網絡虛擬化的重要技術。基于多商品流的虛擬網絡鏈路映射以底層網絡總體資源消耗最低的方式映射虛擬鏈路，取得較好的系統收益。然而基于多商品流的多路徑鏈路映射算法時間復雜度受虛擬網絡以及底層網絡規模影響較大，難以滿足在線虛擬網絡映射的實時性要求；且虛擬網絡請求是一個動態變化過程。因此研究虛擬網絡映射動態過程，設計有效的虛擬網絡多路徑鏈路映射算法對于保證在線虛擬網絡映射的實時性具有重要意義。

【發明內容】

本發明的目的就是解決現有技術中的問題，提出一種基于最小費用流模型的虛擬鏈路映射算法，發現虛擬網絡映射代價收益動態倒置現象，提出虛擬網絡多路徑鏈路映射的最小費用流模型及算法，設置單位網絡流量的費用參數，使得單條虛擬鏈路以最小代價、最小負載映射底層網絡鏈路，能夠提高系統收益、虛擬網絡接收率，且降低了時間復雜度。

為實現上述目的，本發明提出了一種基于最小費用流模型的虛擬鏈路映射算法，依次包括以下步驟：

a）建立最小費用流模型：

a1）無向網絡：無向網絡NG＝(V,A,C)，其中V是節點集合，A是無向邊集合，C是邊容量集合，對于每條邊(i,j)∈A，對應有一個邊容量c(i,j)≥0，邊容量簡寫為c_ij；

a2）無向網絡流及流量：在NG中，指定一點s為源點，指定另一點t為匯點，其余的點叫做中間點，滿足下述條件的f稱為s到t的無向網絡流：

（1）容量限制條件：

（2）方向條件：可行流具有方向性；

（3）平衡條件：對于中間點，流出量等于流入量，即每個i(i≠s,t),有對于s和t，v(f)稱為f的流量；

a3）最小費用流模型：給定NG，每一條邊(i,j)∈A上，給定一個單位流量的費用b(i,j)≥0，簡記為b_ij；最小費用流問題就是給定s、t和流量m，求出從s到t的流f滿足流量v(f)＝m，并使得流的總輸送費用取最小值，即得到最小費用流模型：

b）虛擬網絡多鏈路映射算法：

b1）輸入虛擬網絡VN和底層網絡SN，調用最小費用流模型找到一條虛擬鏈路的最小費用流映射，直到完成所有虛擬鏈路映射；

b2）找到一條未映射的虛擬鏈路lv，取出鏈路兩端點v1、v2以及鏈路流量vbw；

b3）找出lv映射的兩底層結點s1和s2；

b4）創建無向網絡NG＝(V,A,C)，設置每條邊的單位流量費用；

b5）調用最小費用流模型，如果找到s1到s2帶寬流量為vbw的最小費用流f，則分配f給lv；

b6）輸出虛擬網絡鏈路映射結果。

作為優選，所述步驟b1）中的虛擬網絡VN由虛擬節點和虛擬鏈路組成，底層網絡SN由底層節點和底層鏈路組成，虛擬網絡映射指把虛擬節點和鏈路映射到滿足虛擬資源需求的底層節點和鏈路，分為節點映射和鏈路映射。

作為優選，所述步驟b4）中不同的NG參數及單位流量費用，產生不同的映射算法，分別為：UNMCF-S和UMMCF-L；所述UNMCF-S設置NG及單位流量費用如下：容量c(i,j)＝bw(i,j)，如果c(i,j)＝＝0，表示節點i與j不存在鏈路；如果bw(i,j)＞0,單位流量費用b(i,j)＝1；如果bw(i,j)＝＝0,單位流量費用b(i,j)＝0；UMMCF-L設置NG及單位流量費用如下：容量c(i,j)＝bw(i,j)，如果c(i,j)＝＝0，表示節點i與j不存在鏈路；b(i,j)＝bwl(i,j)，其中bw(i,j)表示底層鏈路l(i,j)剩余的帶寬總量，bwl(i,j)表示底層鏈路l(i,j)已經映射的帶寬總量。

本發明的有益效果：本發明通過提出虛擬網絡多路徑鏈路映射的最小費用流模型及算法，設置單位網絡流量的費用參數，使得單條虛擬鏈路以最小代價、最小負載映射底層網絡鏈路，能夠提高系統收益、虛擬網絡接收率，且降低了時間復雜度。

本發明一種基于最小費用流模型的虛擬鏈路映射算法，依次包括以下步驟：

a）建立最小費用流模型：