[發明專利]一種基于分布估計算法的組播虛擬網絡功能部署方法

有效

• 申請號: 201810174179.0
• 申請日: 2018-02-27
• 公開（公告）號: CN108400940B
• 公開（公告）日: 2019-11-05
• 發明（設計）人: 邢煥來;王心漢;戴朋林;羅壽西;趙路偉
• 申請（專利權）人: 西南交通大學
• 主分類號: H04L12/761
• 分類號: H04L12/761;H04L12/753;H04L12/727;H04L12/24
• 代理公司: 成都盈信專利代理事務所(普通合伙) 51245
• 代理人: 崔建中

本發明公開了一種基于分布估計算法的組播虛擬網絡功能部署方法。包括：以最小化傳播時延為優化目標，獲得一棵從源節點到所有目的節點可達的組播樹；以及，基于分布估計算法，以最小化服務時延為目標，在組播樹中為每一條從源節點到組播組成員的路徑，放置相同的服務功能鏈，并確定該路徑上的虛擬網絡功能部署方案。本發明的有益效果在于，將網絡功能虛擬化引入組播當中，將組播網絡中的網絡功能服務鏈問題拆分為兩個子問題，即最小傳輸時延組播樹生成問題與最優組播樹中虛擬網絡功能優化部署問題。仿真實驗與數據分析表明，相比于遺傳算法，本發明所使用的方法在算法性能上具有顯著優勢，能獲得更優的解。

技術領域

本發明涉及網絡通信技術與虛擬化技術領域，特別是一種基于分布估計算法的組播虛擬網絡功能部署方法。

背景技術

近年來，隨著網絡技術的不斷創新和高速寬帶網絡的快速發展，市場上出現了視頻會議、網絡游戲、數據分發、遠程教育等越來越多的網絡服務。這些網絡通信業務的要求不同于傳統的點對點網絡通信，要求數據的接收方是一組目的節點。組播技術的出現就是為了解決這個問題。組播是一種通過樹形網絡結構，將數據信息從源節點復用到一組目標節點的方法。當前的組播服務需要在到達目的地之前遍歷特定的專有網絡設備(即中間件)。中間件是網絡中必不可少的設備，但它們在網絡中是固定的，這就導致了業務部署緩慢、網絡僵化程度高等問題。

網絡功能虛擬化(Network Functions Virtualization,簡稱NFV)是歐洲電信標準協會(ETSI)于2012年首次提出的一種新型網絡架構。NFV通過虛擬化技術，將網絡功能從傳統網絡硬件中解耦出來，引入虛擬資源層，把功能網元彈性部署在虛擬機上，而下層硬件資源對于上層的功能網元來說是不可見的，管理員對下層硬件資源進行統一管理和調度。NFV可以動態地改變網絡功能的部署位置。NFV技術給組播通信帶來了變革，通過在通用的計算節點上部署需要被虛擬化的網絡功能(Virtualized Network Functions，簡稱VNF)，來代替傳統的中間件，使得網絡的靈活性極大提高。

服務功能鏈(Service Function Chaining,簡稱SFC)是一系列的有序的帶約束的VNF集合，數據流在到達用戶之前必須按照指定的順序依次通過VNF集合中的每個VNF。相比于單播中的SFC部署問題，將NFV技術引入組播后，帶來了新的挑戰。在組播網絡中，如何需找到一種合適的虛擬網絡功能部署方案，將各個VNF合理地放置在組播網絡中，使得組播源向每一個組播組成員發出的數據流都必須有序地流經各個VNF進行處理，并最終到達相應的目的地。這一問題稱之為組播虛擬網絡功能部署(Multicast VNF Deployment，簡稱MVNFD)問題。MVNFD問題是一個NP-hard問題，目前學術界對于該問題的研究還處于起步階段。

分布估計算法(Estimation of Distribution Algorithm,簡稱EDA)是一種基于統計學習理論的群體進化算法，通過建立概率模型描述候選解在搜索空間的分布信息，采用統計學習手段從群體宏觀的角度建立一個描述解分布的概率模型，然后對概率模型隨機采樣產生新的種群，如此反復實現種群的進化。與傳統的遺傳算法(Genetic Algorithm，簡稱GA)相比，EDA放棄了基于個體的交叉和變異操作。取而代之的是，引入基于概率模型的學習和抽樣方法，實現種群的整體高效進化。基于此，結合組播網絡中的網絡功能服務鏈問題實際情況，本發明使用EDA算法來解決最優組播樹虛擬網絡功能部署問題。

發明內容

本發明的目的是提供一種基于分布估計算法的組播虛擬網絡功能部署方法，在網絡組播服務請求到達時，找到一種虛擬網絡功能部署方案，使得得到的整個組播網絡中服務功能鏈上的所有節點的節點時延和每條傳輸路徑中的總鏈路時延之和最小。

實現本發明目的的技術方案如下：

一種基于分布估計算法的組播虛擬網絡功能部署方法，包括

步驟1：輸入網絡拓撲，構建組播樹；