[發(fā)明專利]一種基于QoS保障的服務(wù)功能鏈動態(tài)部署方法

有效

• 申請?zhí)枺?/td>: 201810078926.0
• 申請日: 2018-01-26
• 公開（公告）號: CN108260169B
• 公開（公告）日: 2021-04-02
• 發(fā)明（設(shè)計）人: 唐倫;趙培培;周鈺;楊友超;馬潤琳;陳前斌
• 申請（專利權(quán)）人: 重慶郵電大學(xué)
• 主分類號: H04W28/24
• 分類號: H04W28/24;H04L12/727;H04L12/24;H04W28/08
• 代理公司: 北京同恒源知識產(chǎn)權(quán)代理有限公司 11275
• 代理人: 趙榮之

1.一種基于QoS保障的服務(wù)功能鏈動態(tài)部署方法，其特征在于：該方法包括以下步驟：

S1：針對切片網(wǎng)絡(luò)中通信業(yè)務(wù)的QoS問題，建立面向可靠性需求的服務(wù)功能鏈SFC部署模型，該模型以最小化端到端時延為目標(biāo)；

S2：綜合考慮節(jié)點位置和可靠性，利用新穎的節(jié)點排序方法分別對物理節(jié)點和服務(wù)功能鏈中的虛擬網(wǎng)絡(luò)功能VNF排序；

S3：根據(jù)節(jié)點排序結(jié)果確定節(jié)點映射優(yōu)先級，選擇滿足資源約束的節(jié)點進行虛擬網(wǎng)絡(luò)功能的部署，實現(xiàn)負載的均衡；

S4：在鏈路映射過程中，尋找滿足鏈路資源約束并保證可靠性需求的時延最短路徑進行映射；

在步驟S1中，所述服務(wù)功能鏈部署網(wǎng)絡(luò)模型為：

底層網(wǎng)絡(luò)形式化為一個無向圖G^S＝(N^S,L^S)，其中N^S表示底層節(jié)點集合，每個節(jié)點能夠部署一個或多個VNF，L^S表示所有底層鏈路的集合；每個底層節(jié)點m∈N^S的CPU容量為節(jié)點位置為loc(m)，連接節(jié)點m和n的鏈路l_mn的帶寬為可靠性為R(l_mn)；是節(jié)點m和n之間無環(huán)路的路徑集；

SFCs鏈形式化成有向圖，表示為G^V＝(N^V,L^V)，N^V表示所有的VNF集合，L^V表示連接VNF的所有虛擬鏈路的集合；每個SFC由一些有序的VNF功能組成，用Q表示單位時間內(nèi)到達的SFC請求強度，SFC集合表示為S＝{s_q|q＝1,2,…Q}，每個SFC∈Q由和連接相鄰兩個VNF u和v的虛擬鏈路組成；SFC中每個VNFu的CPU資源需求為虛擬鏈路l_uv帶寬需求為定義一個二進制變量表示虛擬鏈路l_uv是否映射到物理鏈路l_mn∈L^S上；每個VNF所代表的虛擬機的位置為loc'(u)，映射到底層節(jié)點時最大距離偏移不能超過lp'(u)，虛擬鏈路映射到底層鏈路后的的時延為d_uv，映射到底層鏈路后的可靠性不能低于R(l_uv)；

在步驟S1中，所述面向可靠性需求為選擇可靠性高的節(jié)點和鏈路進行SFC的部署并且所選鏈路滿足鏈路對可靠性的最低需求；

在步驟S1中，所述以最小化端到端時延為目標(biāo)的動態(tài)部署模型為：

第一部分為最大化接入SFC請求的數(shù)目，是為了最大化資源的利用率；第二部分為最小化端到端時延；使用SFC中每跳鏈路的時延疊加來計算端到端時延；每跳鏈路的時延表示為處理時延和傳輸時延的和；其中處理時延與節(jié)點需要處理的負載有關(guān)，處理的負載定義為需要處理的總的VNF資源需求和底層節(jié)點的處理能力之比，當(dāng)節(jié)點的CPU負載增大時，該節(jié)點的處理時延迅速增加，假設(shè)處理時延是處理負載的凸函數(shù)，使用分段線性化來近似凸時延曲線；傳輸時延與需要處理的SFC鏈路映射到底層鏈路的跳數(shù)有關(guān)；

在步驟S2中，所述節(jié)點位置和可靠性為：

節(jié)點位置用節(jié)點連接度G(m)、節(jié)點的有效性E(m)和適應(yīng)性T(m)表示；其中節(jié)點的連接度由相鄰的鏈路總數(shù)決定；節(jié)點的有效性用節(jié)點效率表示，節(jié)點效率定義為與其他節(jié)點之間的距離的倒數(shù)，距離表示鏈路的跳數(shù)，傳輸距離越短，節(jié)點效率就越高；節(jié)點的適應(yīng)性是指當(dāng)節(jié)點m失效后，所有以最短徑通過m節(jié)點相連的其他節(jié)點為恢復(fù)與m相連的鏈路所增加通信距離的最小值，增加的通信距離越小，恢復(fù)時間越短，節(jié)點適應(yīng)值越大，反之，節(jié)點適應(yīng)值越小；

節(jié)點可靠性可用節(jié)點正常工作概率來表示；而節(jié)點正常工作概率與節(jié)點失效率λ_m有關(guān)；節(jié)點失效率用平均故障間隔時間MTBF和平均修復(fù)時間MTTR來表示；則節(jié)點的正常工作概率表示為1-λ_m；

假設(shè)鏈路的失效滿足泊松分布，則時間間隔t內(nèi)，沒有發(fā)生失效的概率為鏈路的可靠度為其中λ_mn為鏈路l_mn的失效率，t為鏈路l_mn上的時延；在進行VNF部署時考慮到鏈路因素，在時延約束下，做出以下轉(zhuǎn)化：最大化上式相當(dāng)于最小化下式：由于d′_uv映射到每條物理鏈路上值是相同的，進一步轉(zhuǎn)化為下式：minλ_mn；在節(jié)點排序時把鏈路影響因素表示為：

在步驟S2中，所述新穎的節(jié)點排序方法為：采用Google的PageRank算法中的思想，重新定義節(jié)點的重要性，表示為下式：

其中r(m)表示節(jié)點m的得分，用于表征節(jié)點的重要性，γ是一個介于0和1之間的阻尼系數(shù)，J(m)表示與節(jié)點m相鄰的節(jié)點集合，表示歸一化的節(jié)點資源狀態(tài)，表示為

根據(jù)PageRank的思想，得到最終的節(jié)點迭代得分表達式，表示為下面的向量表達式，通過不斷地迭代，得到所有節(jié)點的重要性：

r＝(1-γ)C+γHr

在步驟S3中，所述虛擬網(wǎng)絡(luò)功能的部署具體為：根據(jù)節(jié)點得分結(jié)果進行VNF的部署；首先對節(jié)點和VNF得分按照降序排列，然后根據(jù)合并排序的思想，把得分值大的VNF部署到得分值大的物理節(jié)點上，該物理節(jié)點必須滿足VNF的資源需求約束；若經(jīng)過循環(huán)后物理網(wǎng)絡(luò)中所有節(jié)點都不能滿足VNF資源約束，就拒絕該SFC；按此步驟依次進行該SFC中VNF的部署，直到部署完成或不滿足資源約束而拒絕；進行VNF排序時需要一定的變化；由于SFC中VNF不需要考慮節(jié)點正常工作概率和鏈路的可靠性性質(zhì)，節(jié)點歸一化中的資源狀態(tài)表示為SFC中每跳鏈路有鏈路可靠性約束，SFC中鏈路的影響條件改變?yōu)?/p>

2.根據(jù)權(quán)利要求1所述的一種基于QoS保障的服務(wù)功能鏈動態(tài)部署方法，其特征在于：在步驟S4中，所述鏈路映射過程具體為：首先根據(jù)SFC中每跳鏈路的可靠性要求進行大小排序，首先選擇可靠性要求較高的鏈路進行映射，刪除所有不滿足該SFC相應(yīng)鏈路需求的底層鏈路，然后執(zhí)行K-最短路徑算法選出K條時延最短的路徑，按照時延大小遞增排序，最后選擇滿足該SFC的鏈路可靠性約束的時延最短的那條路徑。