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

有效

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

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

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)輸出虛擬網絡鏈路映射結果。

2.如權利要求1所述的一種基于最小費用流模型的虛擬鏈路映射算法，其特征在于：所述步驟b1)中的虛擬網絡VN由虛擬節點和虛擬鏈路組成，底層網絡SN由底層節點和底層鏈路組成，虛擬網絡映射指把虛擬節點和鏈路映射到滿足虛擬資源需求的底層節點和鏈路，分為節點映射和鏈路映射。

3.如權利要求1所述的一種基于最小費用流模型的虛擬鏈路映射算法，其特征在于：所述步驟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)已經映射的帶寬總量。