[發(fā)明專利]一種基于資源碎片避免的服務(wù)功能鏈部署算法

有效

• 申請?zhí)枺?/td>: 201910367967.6
• 申請日: 2019-05-05
• 公開（公告）號: CN110134493B
• 公開（公告）日: 2023-01-10
• 發(fā)明（設(shè)計）人: 趙季紅;潘峰;曲樺;王珂;趙建龍;顏皓靚
• 申請（專利權(quán)）人: 西安郵電大學(xué)
• 主分類號: H04L41/0895
• 分類號: H04L41/0895;H04L41/14;H04L41/16;G06N3/12
• 代理公司: 西安通大專利代理有限責(zé)任公司 61200
• 代理人: 安彥彥

1.一種基于資源碎片避免的服務(wù)功能鏈部署算法，其特征在于，包括如下步驟：

1)采用資源碎片度度量底層網(wǎng)絡(luò)物理節(jié)點和鏈路的資源碎片狀態(tài)，并將資源碎片度最小化作為優(yōu)化目標(biāo)；

2)將遺傳算法中個體染色體的適應(yīng)度函數(shù)值作為空間解好壞的標(biāo)準，使用融合模擬退火的遺傳算法完成虛擬網(wǎng)絡(luò)功能的映射；

3)采用改進的迪杰斯特拉算法完成虛擬鏈路的映射；

其中，步驟1)中，優(yōu)化目標(biāo)的目標(biāo)函數(shù)通過以下過程得到：

1.1)底層網(wǎng)絡(luò)用帶權(quán)無向圖G_s(N_s,E_s)來表示，其中N_s代表底層網(wǎng)絡(luò)物理節(jié)點的集合，E_s代表物理鏈路的集合；如果物理節(jié)點n∈N_s與m∈N_s之間存在端到端的連接則說明存在物理鏈路e^nm∈E_s；用C_S(n)表示物理節(jié)點n可用的計算資源也即部署在節(jié)點n上的虛擬機可用資源之和，B_S(e^nm)表示物理鏈路e^nm可用的帶寬資源；用|N_S|和|E_S|分別表示物理節(jié)點和物理鏈路的數(shù)目；

1.2)服務(wù)功能鏈請求用有向圖G_v(N_v,E_v)來表示，其中N_v表示服務(wù)功能鏈的VNF節(jié)點集合，E_v表示服務(wù)功能鏈的虛擬鏈路集合；e^nm∈E_v表示VNF n∈N_v到VNFm∈N_v的一條虛擬鏈路；用C_v(n)表示虛擬節(jié)點n的計算資源需求，B_v(e^nm)表示虛擬鏈路e^nm的帶寬資源需求；用|N_v|和|E_v|分別用來表示虛擬節(jié)點和虛擬鏈路的數(shù)目；

定義表示物理節(jié)點n_i∈N_s的CPU計算資源剩余率，表示物理鏈路e_j∈E_s的帶寬資源剩余率，分別用來表示VNFn'∈N_v是否已經(jīng)被映射到物理節(jié)點n_i∈N_s和虛擬鏈路e'∈E_v是否已經(jīng)被映射到物理鏈路e_j∈E_s：

定義表示物理節(jié)點n_i∈N_s的相鄰節(jié)點數(shù)，表示物理鏈路e'∈E_v的相鄰鏈路數(shù)，表示兩物理節(jié)點n_i和n_j之間鏈路的剩余帶寬資源率，表示兩物理鏈路e_i與e_j相交節(jié)點的剩余計算資源率；

定義物理節(jié)點的連通性影響矢量λⁿ如下：

定義鄰接矩陣M^e表示鏈路與相鄰節(jié)點的連通能力，鄰接矩陣M^e如(4)式所示；由(3)式和(4)式得到物理節(jié)點的連通矢量kⁿ，如(5)式所示；

kⁿ＝λⁿ*M^e (5)

(5)式中物理節(jié)點的連通矢量定義Mⁿ表示物理節(jié)點與相鄰鏈路的連通能力：

進一步得到物理鏈路的連通矢量k^e表達式如下：

k^e＝λ^e*Mⁿ (7)

上式中定義物理節(jié)點的連通矢量kⁿ、物理鏈路的連通矢量k^e表示物理節(jié)點和鏈路的RFD矢量，由物理節(jié)點n_i的資源碎片度和物理鏈路e_i的資源碎片度得物理節(jié)點n_i和鏈路e_i的RFD表達式如下；

1.3)在滿足部署約束的條件下，使底層網(wǎng)絡(luò)產(chǎn)生的資源碎片最小化，由資源碎片度得到目標(biāo)函數(shù)如(10)式所示，式中R_s(n_i)、R_s(e_j)分別為物理節(jié)點n_i的剩余計算資源、物理鏈路e_j的剩余帶寬資源：

約束條件：

底層網(wǎng)絡(luò)需要滿足虛擬節(jié)點的計算資源以及虛擬鏈路的帶寬資源需求：

服務(wù)功能鏈中的每個VNF只能被映射一次：

為了滿足流量守恒約束以確保服務(wù)功能鏈的連續(xù)性，得到鏈路映射約束條件：