[發明專利]一種基于歷史數據實現拓撲感知的虛擬網絡映射方法

有效

• 申請號: 201210461017.8
• 申請日: 2012-11-16
• 公開（公告）號: CN102932479B
• 公開（公告）日: 2013-02-13
• 發明（設計）人: 廖建新;張磊;卿蘇德;徐童;沈奇威;張樂劍;戚琦
• 申請（專利權）人: 北京郵電大學
• 主分類號: H04L29/08
• 分類號: H04L29/08
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及一種實現虛擬網絡映射的方法，屬于計算機網絡技術領域，特別是屬于網絡 虛擬化技術領域。

背景技術

網絡虛擬化是指將一個共用的物理網絡基礎設施從邏輯上劃分為多個相互隔離的、具有 不同網絡拓撲的虛擬網絡。虛擬網絡一般包括多個虛擬節點和多條虛擬鏈路，每個虛擬節點 和每條虛擬鏈路都具有不同的資源需求，如虛擬節點對中央處理單元CPU的資源需求，虛擬 鏈路對物理鏈路帶寬的需求。服務提供商SP通過租用底層物理網絡的基礎設施切片，充分利 用底層物理網絡基礎設施上提供的訪問控制權，能夠在不需進行相關物理網絡硬件的投入前 提下，能夠快速部署自定制的網絡協議或架構即虛擬網絡，給終端用戶提供多樣化的服務。

在虛擬網絡向底層物理網絡的映射過程中，由于需要同時滿足節點和鏈路的資源需求， 網絡虛擬化的映射問題是一個NP-hard問題。目前與其相關的解決方案普遍基于啟發式方法 而設計，但目前的啟發式虛擬網絡映射方案存在如下問題：(1)目前的資源評分標準是將物 理節點的CPU能力值乘以該節點相鄰鏈路帶寬之和作為度量值，然而這種資源評分標準并不 準確，導致方案有可能選擇CPU能力強而鏈路弱的物理節點進行映射，以致虛擬網路映射在 鏈路映射階段失敗；(2)總是使用貪婪算法選擇評分最高的物理節點進行映射，而忽略了已 經映射好的虛擬節點的位置即未考慮虛擬網絡的拓撲。因此，在進行虛擬網絡映射的過程中， 如何更好的對底層物理網絡資源能力進行評價，如何根據已經映射完畢的虛擬節點及其拓撲 結構，實現下一步節點映射的優化選擇是目前計算機網絡工程領域一個急需要解決的技術難 題。

發明內容

有鑒于此，本發明的目的是發明一種實現虛擬網絡映射的方法，能夠利用底層網絡積累 的大量的虛擬網絡成功映射的歷史數據集合，實現對底層物理網絡資源能力的科學評價，并 能夠結合已經映射完畢的虛擬節點及其拓撲結構，實現下一步節點映射的優化選擇。

為了達到上述目的，本發明提出了一種基于歷史數據實現拓撲感知的虛擬網絡映射方法， 所述方法包括下列操作步驟：

(1)根據底層物理網絡積累的虛擬網絡成功映射的歷史數據集合，計算底層物理網絡節 點之間的依賴關系矩陣M，具體包括如下操作步驟：(11)對底層物理網絡的所有物理節點從 1進行編號，直到編號n，n是一個自然數，等于底層物理網絡的物理節點數目；(12)從 底層物理網絡積累的虛擬網絡成功映射的歷史數據集合中，取出每一個映射記錄；對每一個 映射記錄，都構造一個n行n列的空矩陣P，初始時該矩陣P的每個元素值為0值；在該映 射記錄中，如果第i個底層物理節點至少被該映射記錄中一個虛擬節點成功映射過，則讓矩 陣P的第i行第i列的元素a_ii取值為1；在該映射記錄中，如果第i個底層物理節點和第j個 底層物理節點之間的一條物理路徑至少被該映射記錄中的一條虛擬鏈路成功映射過，則讓矩 陣P的第i行第j列的元素a_ij和第j行第i列的元素a_ji都取值為該條物理路徑的跳數的倒數， 其中i和j都是大于等于1、小于等于n的自然數，i和j必須不相等；(13)把步驟12中所構 造的所有矩陣P進行矩陣相加求和，得到一個新的n行n列矩陣S；(14)對矩陣S進行歸一 化處理，得到底層物理網絡節點之間的依賴關系矩陣M；歸一化處理的具體方式是：對于矩 陣M第i行第i列的元素M_ii取值為該元素表示底層物理網絡第i個物理節點的平均 重要度因子；對于矩陣M第i行第j列的元素M_ij取值為該元素表示底層物理網 絡第i個物理節點和第j個物理節點之間的平均關聯度因子；上述式中S_ii表示矩陣S第i行第 i列的元素，S_ij表示矩陣S第i行第j列的元素，i和j都是大于等于1、小于等于n的自然數， i和j必須不相等；

(2)對于一個需要進行映射的虛擬網絡，根據該虛擬網絡中虛擬節點對CPU資源的需 求大小，從大到小對該虛擬網絡的所有虛擬節點進行排序；