[發明專利]一種基于最大加權匹配的鏈路優先虛擬網絡映射方法

有效

• 申請號: 202010067331.2
• 申請日: 2020-01-20
• 公開（公告）號: CN111245701B
• 公開（公告）日: 2021-08-31
• 發明（設計）人: 唐亞哲;陳立水;陸曉兵;陳星;李寧;王靜;王俊芳;吳巍
• 申請（專利權）人: 中國電子科技集團公司第五十四研究所
• 主分類號: H04L12/46
• 分類號: H04L12/46;H04L12/721;H04L12/729
• 代理公司: 河北東尚律師事務所 13124
• 代理人: 王文慶

1.一種基于最大加權匹配的鏈路優先虛擬網絡映射方法，其特征在于，包括以下步驟：

步驟一：計算給定的網絡拓撲圖的最大加權匹配；

步驟二：將最大加權匹配中所有的虛擬鏈路按照帶寬需求進行降序排序，對首條待映射的虛擬鏈路，將其映射到鏈路綜合帶寬度量指標值最大的物理鏈路上，其余虛擬鏈路依次以鏈路距離最小為目標選擇物理鏈路，即選擇與被映射的物理鏈路之間平均距離最小的物理鏈路；

步驟三：剩余未映射的虛擬節點按照資源值的大小進行降序排序，然后依次映射到使整體鏈路資源開銷最小的物理節點上；

步驟四：剩余未被映射的虛擬鏈路使用KSP映射算法進行映射；

其中，步驟二中鏈路綜合帶寬度量指標值的計算公式為：

其中cb(l_i)表示當前物理鏈路l_i的綜合帶寬度量指標值；N(l_i)表示l_i的鄰接鏈路，即與l_i有共同節點的鏈路；權值γ∈(0,1)，調節當前物理鏈路和鄰接鏈路之間的相對權重，當γ＝0時，式子即退化為鏈路帶寬，僅用鏈路自身的帶寬值作為鏈路重要性的指標；γ越大，則鄰接鏈路的帶寬值影響越大，表示鄰接鏈路l_j在當前物理鏈路l_i的所有鄰接鏈路中所占的比重；nbw(l_i)和nbw(l_j)分別表示當前物理鏈路l_i和鄰接鏈路l_j的鏈路帶寬；

步驟二中鏈路距離計算公式為：

其中dis(l_a,b,l_c,d)表示物理鏈路l_a,b與物理鏈路l_c,d的距離；sp(node1,node2)表示節點node1到節點node2之間的最短路徑的長度，a,b和c,d分別為兩條物理鏈路的兩個節點。

2.根據權利要求1所述的基于最大加權匹配的鏈路優先虛擬網絡映射方法，其特征在于，步驟三中物理節點的鏈路資源開銷計算公式為：

其中為還未被映射的虛擬節點，為所有未被映射的虛擬節點集合；是屬于最大加權匹配中的某一已被映射的虛擬鏈路，表示虛擬鏈路的鏈路帶寬需求，和之間存在虛擬鏈路；表示物理節點到物理節點的最短路徑所含的物理鏈路條數；為網絡中所有與相連的虛擬鏈路集合；為網絡請求中未被映射過的物理節點，為所映射到的物理節點。

3.根據權利要求1所述的基于最大加權匹配的鏈路優先虛擬網絡映射方法，其特征在于，步驟四具體為：

計算出待映射虛擬鏈路的兩個虛擬節點所映射到的兩個物理節點之間的前K條最短路徑，將最短路徑根據路徑的跳數升序進行排列，依次檢查最短路徑上所有的物理鏈路的剩余帶寬資源是否滿足待映射虛擬鏈路的帶寬需求；若滿足，則將待映射虛擬鏈路映射到第一條滿足條件的最短路徑上；若檢查完K條最短路徑仍沒有滿足條件的，則虛擬鏈路映射失敗；其中K為設定值。