[發明專利]一種跨數據中心的虛擬網絡映射方法

有效

• 申請號: 201310576720.8
• 申請日: 2013-11-18
• 公開（公告）號: CN104038400A
• 公開（公告）日: 2014-09-10
• 發明（設計）人: 廖丹;孫罡;肖克祥;狄浩;虞紅芳;孫健
• 申請（專利權）人: 電子科技大學
• 主分類號: H04L12/46
• 分類號: H04L12/46;H04L29/06
• 代理公司: 成都行之專利代理事務所(普通合伙) 51220
• 代理人: 溫利平

1.一種跨數據中心的虛擬網絡映射方法，其特征在于，包括以下步驟：

（1）、確定虛擬網絡的生存能力需求s_V：

虛擬節點n_V映射在物理節點n_S上表示為：n_V→n_S:M(n_V)＝n_S,n_V∈V_V,n_S∈V_S當M(n_V)＝n_S時x(n_V,n_S)為1，否則x(n_V,n_S)為0，則生存能力約束為：

ΣnV∈VVx(nV,nS)≤(1-sV)*|VV|,∀nS∈VS]]>

其中，V_V為虛擬節點集合，V_S為物理節點集合；

（2）、確定虛擬網絡中虛擬節點的最終分組：

（2、1）、通過虛擬節點分組算法VNGP（Virtual?Node?Group?Partition）將虛擬網絡中的虛擬節點進行分組：

將虛擬節點集合V_V放入到N(s_V)個分組中，N(s_V)為V_V的分組數目，即V_V＝G₁∪G₂∪…∪G_i，第i個分組G_i內的虛擬節點數目|G_i|≤[(1-s_V)*|V_V|],分組數目N(s_V)≤|V_V|，其中，i＝1,2,…N(s_V)，[]表示向下取整；

（2、2）、在虛擬節點集合V_V中增加輔助節點，使N(s_V)個分組中都有[(1-s_V)*|V_V|]個節點；

（2、3）、基于當前分組G_i尋找不同分組間的所有節點對集合U：

定義所有節點對之間的權值為y(m,n)或y(n,m)，m≠n，y(m,n)的表達式為：

則集合U={(m,n)|∀m∈Gi,∀n∈Gj,∀i∈[1,N(sV)-1],∀j∈[i+1,N(sV)]}]]>那么在已知各個分組大小的條件下，V_V中的虛擬節點以最小化組間虛擬鏈路的總需求帶寬為：

minGi,i∈[1,N(nS)]Σ(m,n)∈Uy(m,n)]]>

其中，由于每個分組的大小確定為[(1-s_V)*|V_V|]，因此可以得到集合U的大小為：

|U|=N(sV)*(N(sV)-1)2*[(1-sV)*|VV|]2]]>

（2、4）、在確定每個分組大小和分組數目條件下，通過交換不同分組內的虛擬節點和輔助節點來尋找最終分組：

將分組G_i中的第a,a≤|G_i|個虛擬節點n_V^a和第j個分組G_j中的第b,b≤|G_j|個虛擬節點n_V^b交換，且n_V^a和n_V^b的交換不影響其它分組相關的權值y(m,n)，最小化組間虛擬鏈路的總需求帶寬所減小的差值Δ為：

Δ=(Σn∈Gj,n≠nVa,nVby(n,nVa)+Σm∈Gi,m≠nVa,nVby(m,nVb))-(Σm∈Gi,m≠nVa,nVby(m,nVa)+Σn∈Gj,n≠nVa,nVby(n,nVb))]]>定義不同分組的節點對之間的資源需求w(n_V^a,G_i,n_V^b,G_j)的計算公式為：

w(nVa,Gi,nVb,Gj)=Σm∈Gj,m≠nVa,nVby(m,nVa)+Σn∈Gi,n≠nVa,nVby(n,nVb)]]>

其中，n_V^a,n_V^b∈V_V,i,j∈[1,N(s_V)],i≠j；

逐一從U中選擇一對(m,n),m∈G_i,n∈G_j代入w(n_V^a,G_i,n_V^b,G_j)計算w(m,G_i,n,G_j)和w(n,G_i,m,G_j)，ε為準確度，如果w(m,G_i,n,G_j)＜w(m,G_i,n,G_j)/(1+ε)，將n轉移至G_i并將m轉移至G_j，同時更新U后轉至步驟（2、3），如果(m,n)不是遍歷的最后一個節點對，繼續步驟（2、4）否則，算法結束；

（2、5）、刪除虛擬節點集合V_V中增加的輔助節點；

（3）、虛擬網絡在滿足生存能力需求條件下，通過GVNM（Grouped?Virtual?Network?Mapping）子算法將分組后的虛擬網絡映射到底層數據中心網絡上：

(3、1)、定義集合M，且初始化為空集，用于記錄已映射的虛擬節點；

（3、2）、若M不為空，選擇與M中虛擬節點間的虛擬鏈路總需求帶寬最大的未映射分組G_i，進入步驟（3、3），若M為空，則選取按資源需求降序排列的第一個分組G_i，直接對G_i進行映射；

（3、3）、遍歷未映射其它分組的物理節點，從中尋找令G_i中的虛擬節點和相關虛擬鏈路的映射成本最小的可映射物理節點n_s，其中，E_V為虛擬鏈路集合，如果找到物理節點n_s，則映射G_i和相關虛擬鏈路，并將G_i中的虛擬節點放入集合M中，如果沒有找到可映射的物理節點n_s，此次映射失??；

（3、4）、逐一映射完所有分組，完成映射，否則返回步驟（3、2）；

（4）、對跨數據中心虛擬網絡做增強性可靠設計：

定義虛擬網絡所需的可靠性為r_V，物理節點n_s∈V_S上數據中心內的服務器失效概率為p(n_s)，分組G_i的可靠性為r(G_i)，當分組G_i內沒有備份虛擬節點且映射在物理節點n_s上時，r(G_i)為(1-p(nS))^|G_i|，虛擬網絡的實際可靠性為且當每個分組G_i的可靠性r(G_i)都不小于r_V^(1/N(s_V))時，虛擬網絡所需的可靠性為r_V可以得到保證；

在本地的數據中心內，定義分組G_i的本地備份虛擬節點集合為B_i,映射在物理節點n_s上的分組G_i所需的本地備份虛擬節點數目|B_i|的計算公式為：

|Bi|=arg minx∈N{Σi=0x(x+|Gi|i)p(nS)i(1-p(nS))|Gi|+x-i≥rV^(1/N(ns))}]]>

每個本地備份虛擬節點所需的計算容量為組內工作虛擬節點所需計算容量的最大值，定義為：

CV(nB)=maxnV∈GiCV(nV),∀nB∈Bi.]]>

2.根據權利要求所述的跨數據中心的虛擬網絡映射方法，其特征在于，所述的權值y(m,n)還可以為y(n,m)，y(n,m)的表達為：