[發明專利]一種基于地理位置約束的批量虛擬網絡映射方法

有效

• 申請號: 201410026410.3
• 申請日: 2014-01-20
• 公開（公告）號: CN103746894B
• 公開（公告）日: 2017-02-01
• 發明（設計）人: 廖丹;程科;孫罡;虞紅芳;許都;陸川
• 申請（專利權）人: 電子科技大學
• 主分類號: H04L12/46
• 分類號: H04L12/46;H04L29/06
• 代理公司: 成都行之專利代理事務所(普通合伙)51220
• 代理人: 溫利平

技術領域

本發明屬于互聯網通信技術領域，更為具體地講，涉及一種基于地理位置約束的批量虛擬網絡映射方法。

背景技術

隨著越來越多的互聯網新型應用的出現，現有的互聯網架構很難滿足這些不同應用對互聯網架構的要求，令互聯網發展呈現出僵化現象。網絡虛擬化技術是一種解決互聯網僵化問題的有效手段。網絡虛擬化技術對公用的底層基礎網絡設施進行抽象并提供統一的可編程接口，將多個彼此隔離且具有不同拓撲的虛擬網絡（Virtual?Network，VN）映射到公用的基礎設施網絡（Substrate?Network，SN）上，為用戶提供差異化服務。

圖1是虛擬網絡映射示意圖。如圖1所示，虛擬網絡映射包括虛擬節點的映射和虛擬鏈路的映射。因為不同的虛擬網絡可以映射到同一個物理網絡上，所以為了增加接受率，映射方法的選擇是非常重要的。即使提前知道所有的虛擬網絡請求，但由于虛擬節點和虛擬鏈路對資源的要求、地理位置對虛擬節點的約束以及映射的復雜性，使得虛擬網絡映射變得非常困難。大多數方法的建議是先使用貪婪算法去預先映射虛擬節點，然后集中進行虛擬鏈路映射。然而即使所有的虛擬節點映射完成，虛擬鏈路的映射也相當復雜。并且預先進行虛擬節點映射而不考慮其與虛擬鏈路映射的關系往往限制了解決方案，得不到一個較好的映射結果。所以，目前使用的虛擬網絡映射算法，在映射虛擬節點的時候，也同時映射虛擬鏈路。

在進行虛擬網絡映射時，還需要關注映射成本最小化和節點生存性問題。映射成本最小化是指最終得到的虛擬網絡映射方案所產生的成本最小。節點生存性問題是指虛擬網絡映射完成后，如果物理網絡中的物理節點失效，如何將其上映射的虛擬節點及其鏈路遷移至其他有效的物理節點和物理鏈路上。

目前很多虛擬網絡映射方法都是在映射的時候考慮節點生存性問題。通常在某一時刻只有一個虛擬網絡需要映射的時候，考慮在某一時刻最多只有一個虛擬節點失效的情況下，為原虛擬網絡增加K個備份節點，一般情況下備份節點與原虛擬節點一一對應，以保證在有虛擬節點失效的情況下（因為最多只有一個節點映射失效）能成功遷移恢復，簡稱K-冗余映射方案。該方案的主要思路如下：首先增強原始虛擬網絡，為原始的虛擬網絡的增加K個備份節點及相應的備份鏈路。圖2是增強型虛擬網絡示意圖。如圖2所示，V0至V3表示虛擬節點，其上所標示的數值為節點資源需求，虛擬節點之間的連線為虛擬鏈路，其上所標示的數值為鏈路資源需求。在該增強型虛擬網絡中，每個虛擬節點都設置了備份節點，即K=4，其對應的節點資源需求和鏈路資源需求與原始節點一致。在映射的過程中，首先映射原始虛擬網絡，然后再映射備份節點和備份鏈路，顯而易見，備份節點與原始節點不可映射至同一物理節點。由于只考慮某一時刻最多只有一個虛擬節點失效的情況，因此不同的備份節點可以映射至同一個物理節點，備份鏈路也可以與工作鏈路資源共享。

此方案主要有兩個缺點：第一，此方案中在進行虛擬網絡映射的時候，同時到達的虛擬網絡只有一個，這只考慮了實際情況中的一種，還有另外一種情況就是：即使在進行靜態虛擬網絡映射的時候，在某一時刻也可能有多個虛擬網絡同時到達，那么在這種情況下，不僅要考慮各個虛擬網絡內部的資源共享，還要考慮同時到達的多個虛擬網絡之間的資源共享情況；第二，虛擬節點的映射沒有考慮到地理位置的約束，只要滿足虛擬節點的容量要求以及相應的虛擬鏈路容量要求，虛擬節點就可以映射到物理網絡中的任意物理節點上，這和實際情況是不相符的。

發明內容

本發明的目的在于克服現有技術的不足，提供一種基于地理位置約束的批量虛擬網絡映射方法，在考慮地理位置約束的同時，通過反向生成新虛擬網絡提高備份資源共享程度，節約網絡資源。

為實現上述發明目的，本發明基于地理位置約束的批量虛擬網絡映射方法，包括以下步驟：

S1：在到達的每個虛擬網絡請求中，以虛擬節點的地理位置坐標為圓心，根據預設的映射半徑確定每個虛擬節點的可映射物理節點集合；

S2：依次映射每個虛擬網絡，映射虛擬節點時，在其可映射物理節點中，優先選擇本次映射中之前虛擬網絡已映射的物理節點進行映射；

S3：根據已映射的物理節點拓撲反向生成新虛擬網絡，其虛擬節點與步驟S2中映射的物理節點對應，節點資源需求為與該物理節點上所映射的原虛擬節點的節點資源需求之和，虛擬鏈路的鏈路資源需求為對應的物理路徑上所承載的原虛擬鏈路的鏈路資源需求之和；

S4：生成步驟S3中得到的新虛擬網絡的增強型虛擬網絡，并將備份節點和備份鏈路進行映射。