[發明專利]一種基于就近原則的虛擬網絡映射方法

有效

• 申請號: 201110023701.3
• 申請日: 2011-01-21
• 公開（公告）號: CN102075429A
• 公開（公告）日: 2011-05-25
• 發明（設計）人: 黃韜;劉江;呂博;陳建亞;劉韻潔
• 申請（專利權）人: 北京郵電大學
• 主分類號: H04L12/56
• 分類號: H04L12/56
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

網絡虛擬化技術是推動互聯網體系架構發展的重要方法之一，其本質是通過抽象、分配、隔離機制在一個公共物理網絡上獨立地運營多個虛擬子網，各虛擬子網可以使用相互獨立的協議體系，并能夠根據用戶動態變化的需求對整個網絡中節點和鏈路資源進行合理配置，從而增強網絡的靈活性與多樣性，實現網絡的可測可控性，最優化網絡資源的分配與調度，提高安全和服務質量、降低運營維護成本，以求根本性地解決互聯網現有的僵化、以補丁和更新為主的發展現狀。

網絡虛擬化技術可以用于為新型網絡體系結構的研究提供共享物理實驗網絡的基礎，同時它還能夠將底層物理設施提供商與網絡服務運營商相分離，允許多個運營商的網絡共享同一個公共的底層物理網絡基礎架構(鏈路、交換節點等)，每個網絡都在其中擁有既不受其他網絡影響又可以靈活調整的網絡資源份額，不同網絡運營商可以采用不同的網絡協議，提供創新的端到端服務，因此網絡虛擬化也很有希望成為一種未來網絡的主流運營模式。

背景技術

虛擬網絡映射問題則是網絡虛擬化技術中必不可少的環節，它的主要功能是將用戶的虛擬網絡請求(Virtual?Request)合理地映射至運營商提供的底層物理網絡設施(Substrate?Network)，映射過程不僅要實現虛擬網絡之間的分隔與互不影響，從而保證每個虛擬網絡用戶的服務質量(QoS)，同時也要盡量合理地分配底層物理網絡資源，提高資源利用率。如圖1所示。

在圖1中，兩個不同的虛擬網絡被映射在底層物理網絡上，并向相應的用戶提供服務。由于虛擬網絡請求拓撲的多樣性，以及節點和鏈路兩組限制條件需要同時考慮，使得將多個不同的虛擬網絡映射到一個公共底層物理網絡成為NP-hard問題。為解決該問題，國外很多研究學者已經提出了一些求解映射匹配次優解的映射方法，但現有算法普遍存在匹配方程求解復雜、計算花銷大、缺乏具體路徑選擇方法等問題。

虛擬網絡映射的實現過程可以分為兩個步驟：節點映射和鏈路映射?，F有的主要方法是使用貪婪算法進行節點映射，使用K最短路徑算法進行鏈路映射。系統以時間窗為單位，一個時間窗內的所有虛擬網絡請求將按照其收入排序，從規模最大的請求開始進行映射。若映射成功，則更新底層物理網絡狀態；若失敗，則將請求放入等待隊列；若失敗次數超過預設參數DELAY，則直接拒絕該請求。

其中，對每個虛擬網絡請求的映射步驟如下：

首先進行節點映射：對虛擬網絡請求中的每個虛網節點(V_node)，使用貪婪算法尋找擁有最大剩余資源的底層物理網節點(S_node)；若該S_node滿足該V_node的CPU限制，則該V_node映射成功；若對某V_node，沒有滿足要求的S_node，則節點映射失敗；若所有V_node映射成功，則節點映射完成。

節點映射完成后進行鏈路映射：對虛擬網絡請求中的每條虛網鏈路(V_hnk)，確定其兩端點V_node1、V_node2映射至底層物理網絡中的S_node1、S_node2；使用K最短路徑算法尋找S_node1、S_node2之間的第1-K條最短路徑；若其中某條路徑滿足該V_hnk的帶寬要求，則該V_hnk映射成功；若所有K條路徑均不滿足帶寬要求，則鏈路映射失??；若所有V_link映射成功，則鏈路映射完成。

在現階段的虛擬網絡映射算法中，由于設計節點映射算法時沒有考慮到其對鏈路映射的影響，因此一個使用貪婪算法優化后的節點映射結果有可能導致鏈路映射復雜或無法完成。例如，貪婪算法選擇的節點在底層物理網拓撲中可能相距很遠(多跳)，那么它們中間的鏈路和節點就會被經常使用，從而加重負擔；同時，由于一條虛鏈路將會占用多條底層物理網鏈路，底層物理網的資源利用率會變差，即系統的收入/支出(Revenue/Cost)會降低。

發明內容

本發明分析了節點映射算法與鏈路映射算法的關系，發現在節點映射過程中，如果僅以底層物理網節點的剩余資源為目標，則上述對鏈路映射的負面影響幾乎不能避免，因此若能提出一種方法，在考慮底層物理網節點剩余資源的同時，也考慮節點之間的距離，并使用參數調節這兩個因素的影響，則可以大大簡化鏈路映射的復雜度，并提高底層物理網的資源利用率。