一種基於時空關聯的多徑虛擬網映射方法與流程
2023-06-01 00:12:56
本發明屬於網絡虛擬化技術領域，具體涉及一種基於時空二維關聯的多徑虛擬網映射方法。
背景技術：
在過去幾十年裡，網際網路發展速度之快是前有未有的，成為全球化的資源共享和信息交換平臺。但最初的網際網路體系架構設計遵循的是提供儘量簡單的服務模式，然而現在的網際網路卻因為這種簡單的模式在網絡規模不斷激增的情況下，在可擴展性、移動性、服務質量(QoS)、網絡安全以及能耗等方面的問題和不足都逐漸體現出來，導致網絡僵化局面。網絡虛擬化技術提供了很有前途的方式解決網絡僵化問題。在網絡虛擬化中，多個服務提供商在一個或多個基礎設施供應商租賃的底層網絡中構建異構虛擬網絡，並提供端到端的網絡服務，以便達到可以同時單獨的進行網絡技術創新和服務提升。
在網絡虛擬化中，虛擬網映射研究是重要的研究課題，目前國內外研究人員提出了一系列的虛擬網構建算法，但是他們都是基於一維空間屬性的對映射算法研究，各種假設，約束條件也是基於一維空間上的cpu資源，帶寬資源等。並沒有考慮到物理網絡上的時間屬性，即物理網絡是一個動態的，剩餘資源隨時間變化的，不同時間的網絡狀態是不一樣的。而大多數研究員並沒有考慮到時間因素對虛擬網映射的影響，從而會導致底層網絡資源隨著時間的推進而惡化。
技術實現要素：
本發明的目的是針對現有技術的不足，提出一種基於時空關聯的多徑虛擬網映射方法。
本發明的目的是通過以下技術方案來實現的：一種基於時空關聯的多徑虛擬網映射方法，包括如下步驟：
步驟1、建立時間和空間維度上二維資源度量模型。
步驟2、建立底層資源隨時間變化的基於時空二維的負載均衡的多商品流模型。
步驟3、基於加入時間維後時空二維資源度量模型和基於時空二維的多商品流模型，對虛擬網進行映射。
進一步地，步驟1所述的時間和空間維度上二維資源度量模型的建立，具體如下：
物理節點cpu基於時空二維資源度量A(ns)計算如下：
<![CDATA[ A ( n s ) = Σ i = 1 k ( R ( n s , t i ) × t i t i + T w ( t ) d t ) - - - ( 1 ) ]]>
<![CDATA[ w n = Σ i = 1 k ( C ( n s ) - R ( n s , t i ) C ( n s ) × t i t i + T w ( t ) d t ) - - - ( 2 ) ]]>
其中，R(ns,t)為節點ns在t時刻的剩餘資源，C(ns)為物理節點ns的總資源，wn表示節點二維負載強度。w(t)是一個單調遞減的權值函數且滿足i為正整數，k表示整個時間內時間片的數量，T為最小時間片。
物理鏈路帶寬基於時空二維資源度量A(l)計算如下：
<![CDATA[ A ( l ) = Σ i = 1 n ( R ( l , t i ) × t i t i + T w ( t ) d t ) - - - ( 3 ) ]]>
其中，R(l,t)為鏈路l在t時刻的剩餘帶寬資源，w(t)是一個單調遞減的權值函數且滿足i為正整數，n表示整個時間內時間片的數量，T為最小時間片。
進一步地，步驟2所述的底層資源隨時間變化的基於時空二維的負載均衡的多商品流模型，包括目標函數和約束條件，具體如下：
目標函數：
<![CDATA[ m i n Σ ( u , v ) l Σ i c ( u , v ) * f i ( u , v ) - - - ( 4 ) ]]>
約束條件：
<![CDATA[ Σ i ( f i ( u , v ) + f i ( v , u ) ) ≤ R ( l u v , t j ) , l u v l s - - - ( 5 ) ]]>
<![CDATA[ Σ w N s f i ( s i , w ) - Σ w N s f i ( w , s i ) = r i - - - ( 6 ) ]]>
<![CDATA[ Σ w N s f i ( d i , w ) - Σ w N s f i ( w , d i ) = - r i - - - ( 7 ) ]]>
<![CDATA[ Σ w N s f i ( u , w ) - Σ w N s f i ( w , u ) = 0 , u N s / { s i , d i } - - - ( 8 ) ]]>
<![CDATA[ f i ( u , v ) 0 , u , v N s - - - ( 9 ) ]]>
其中α是一個正係數，可以取1，δ是一個介於0-1之間的數，防止分母出現0的情況。fi(u,v)表示鏈路(u,v)分配給第i個商品的帶寬。ls表示物理網絡中物理鏈路集合，Ns表示物理網絡中物理節點集合。R(luv,tj)表示鏈路(u,v)在第tj時間片內的剩餘帶寬。{si,di,ri}分別表示第i個商品的源節點，目的節點和需求。
進一步地，步驟3所述的基於加入時間維後的時空二維資源度量模型和基於時空二維的多商品流模型，對虛擬網進行映射，具體過程如下：
3-1.將虛擬請求中虛擬節點按cpu資源非增序排列，依次將節點映射到滿足資源約束的節點負載強度wn最小的物理節點上。
所述的資源約束為startime≤t≤endtime，即虛擬節點nv請求的cpu資源不大於物理節點ns在虛擬網整個生命周期t時間段內的cpu資源R(ns,t)。
3-2.根據步驟2的多商品流模型，求解使其目標函數最小化的最優解，如果有最優解則鏈路映射成功並將其映射到相應的鏈路上去。否則映射失敗。
本發明有益效果如下：本發明從二維時空關聯的角度出發，提出了時間與資源負載的二維離散加權的方法，基於多徑映射的思想，提出了隨時間變化的多商品流模型映射虛擬網，本發明提高虛擬網映射成功率，能夠在長時間內很好地平衡網絡資源負載，從而提高網絡資源利用率。
附圖說明
圖1為本發明虛擬網映射流程圖；
圖2為兩條鏈路選擇實例；
圖3為本發明虛擬網映射示例圖。
具體實施方式
下面結合附圖對本發明作進一步的說明。
如圖1所示，本發明提供的一種基於時空關聯的多徑虛擬網映射方法，包括如下步驟：
步驟1、建立時間和空間維度上二維資源度量模型。
步驟2、建立底層資源隨時間變化的基於時空二維的負載均衡的多商品流模型。
步驟3、基於加入時間維後時空二維資源度量模型和基於時空二維的多商品流模型，對虛擬網進行映射。
進一步地，步驟1所述的時間和空間維度上二維資源度量模型的建立，具體如下：
物理節點cpu基於時空二維資源度量A(ns)計算如下：
<![CDATA[ A ( n s ) = Σ i = 1 k ( R ( n s , t i ) × t i t i + T w ( t ) d t ) - - - ( 1 ) ]]>
<![CDATA[ w n = Σ i = 1 k ( C ( n s ) - R ( n s , t i ) C ( n s ) × t i t i + T w ( t ) d t ) - - - ( 2 ) ]]>
其中，R(ns,t)為節點ns在t時刻的剩餘資源，C(ns)為物理節點ns的總資源，wn表示節點二維負載強度。w(t)是一個單調遞減的權值函數且滿足i為正整數，k表示整個時間內時間片的數量，T為最小時間片。
物理鏈路帶寬基於時空二維資源度量A(l)計算如下：
<![CDATA[ A ( l ) = Σ i = 1 n ( R ( l , t i ) × t i t i + T w ( t ) d t ) - - - ( 3 ) ]]>
其中，R(l,t)為鏈路l在t時刻的剩餘帶寬資源，w(t)是一個單調遞減的權值函數且滿足i為正整數，n表示整個時間內時間片的數量，T為最小時間片。
步驟2所述的底層資源隨時間變化的基於時空二維的負載均衡的多商品流模型，包括目標函數和約束條件，具體如下：
目標函數：
<![CDATA[ m i n Σ ( u , v ) l Σ i c ( u , v ) * f i ( u , v ) - - - ( 4 ) ]]>
約束條件：
<![CDATA[ Σ i ( f i ( u , v ) + f i ( v , u ) ) ≤ R ( l u v , t j ) , l u v l s - - - ( 5 ) ]]>
<![CDATA[ Σ w N s f i ( s i , w ) - Σ w N s f i ( w , s i ) = r i - - - ( 6 ) ]]>
<![CDATA[ Σ w N s f i ( d i , w ) - Σ w N s f i ( w , d i ) = - r i - - - ( 7 ) ]]>
<![CDATA[ Σ w N s f i ( u , w ) - Σ w N s f i ( w , u ) = 0 , u N s / { s i , d i } - - - ( 8 ) ]]>
<![CDATA[ f i ( u , v ) 0 , u , v N s - - - ( 9 ) ]]>
其中α是一個正係數，可以取1，δ是一個介於0-1之間的一個很小的數，防止分母出現0的情況。fi(u,v)表示鏈路(u,v)分配給第i個商品的帶寬。ls表示物理網絡中物理鏈路集合，Ns表示物理網絡中物理節點集合。R(luv,tj)表示鏈路(u,v)在第tj時間片內的剩餘帶寬。{si,di,ri}分別表示第i個商品的源節點，目的節點和需求。
步驟3所述的基於加入時間維後的時空二維資源度量模型和基於時空二維的多商品流模型，對虛擬網進行映射，具體過程如下：
3-1.將虛擬請求中虛擬節點按cpu資源非增序排列，依次將節點映射到滿足資源約束的節點負載強度wn最小的物理節點上。
所述的資源約束為startime≤t≤endtime，即虛擬節點nv請求的cpu資源不大於物理節點ns在虛擬網整個生命周期t時間段內的cpu資源R(ns,t)。
3-2.根據步驟2的多商品流模型，求解使其目標函數最小化的最優解，如果有最優解則鏈路映射成功並將其映射到相應的鏈路上去。否則映射失敗。
實施例
如圖2所示有兩條物理鏈路，現在有一個虛擬網請求，它的帶寬需求是2，開始時間t0，生命周期是100*slice。按照以前的研究基於當前時刻的資源剩餘量，link1會被優先考慮。事實上在後續時刻link1的資源並不充足，可能會造成鏈路負載過重。我們假設前面時間片上的概率強度分別是0.3，0.2，0.15，0.1，0.05…由公式(3)計算知A(link1)＝3.9,A(link2)＝4.2，根據我們的模型，我們會選擇link2，這樣可以確保底層網絡在較長時間裡保持負載均衡如圖3所示，虛擬網請求1的鏈路請求為30，物理網絡中沒有滿足條件的方案。採用多徑映射策略後，請求1的節點映射方案為{a→C,b→D}，鏈路映射方案為{(a,b)→(C,B,D),(a,b)→(C,E,D)}。