[發明專利]一種CDN節點部署方法及裝置

有效

• 申請號: 201911046743.1
• 申請日: 2019-10-30
• 公開（公告）號: CN111181761B
• 公開（公告）日: 2021-08-31
• 發明（設計）人: 袁兩勝
• 申請（專利權）人: 騰訊科技（深圳）有限公司
• 主分類號: H04L12/24
• 分類號: H04L12/24;H04L29/08
• 代理公司: 北京同達信恒知識產權代理有限公司 11291
• 代理人: 李娟

1.一種CDN節點部署方法，其特征在于，包括：

對包括多個節點位置及連接關系的圖形初始化，得到多個拓撲結構，每個拓撲結構包括多個CDN節點位置及各CDN節點與非CDN節點間通信路徑；

基于當前多個拓撲結構，采用鄰域NS搜索方法和大鄰域LNS搜索方法混合的方式，進行多輪鄰域搜索至滿足迭代結束條件，新得到多個拓撲結構；其中，在每一輪的鄰域搜索中，選取所述當前多個拓撲結構中的至少一個拓撲結構，并對選取的各拓撲結構進行至少一次鄰域搜索；在每一次領域搜索中，確定進行鄰域搜索的拓撲結構中的至少一個CDN節點，在對應的鄰域搜索范圍內確定至少一個非CDN節點，將所述至少一個非CDN節點替換所述至少一個CDN節點，并重新確定各CDN與各非CDN節點間的通信路徑；

從新得到的多個拓撲結構中選擇目標拓撲結構，基于目標拓撲結構中CDN節點的位置及對應的通信路徑，進行CDN節點部署。

2.根據權利要求1所述的方法，其特征在于，采用NS搜索方法和LNS搜索方法混合的方式，進行多輪鄰域搜索，包括：

采用NS搜索方法進行一輪鄰域搜索，采用LNS搜索方法進行另一輪鄰域搜索；和/或

分別采用NS搜索方法和LNS搜索方法，混合搜索完成一輪鄰域搜索。

3.根據權利要求1或2所述的方法，其特征在于，采用鄰域NS搜索方法和大鄰域LNS搜索方法混合的方式，進行多輪鄰域搜索，包括：

對采用NS搜索方法的拓撲結構，在該拓撲結構對應的第一鄰域搜索范圍內搜索N1個CDN節點替換該拓撲結構中的N1個CDN節點，并重新確定對應的通信路徑；

對采用LNS搜索方法的拓撲結構，在該拓撲結構對應的第二鄰域搜索范圍內搜索N2個CDN節點替換該拓撲結構中的N2個CDN節點，并重新確定對應的通信路徑；

其中N2大于N1，且第二鄰域搜索范圍大于第一鄰域搜索范圍。

4.根據權利要求1所述的方法，其特征在于，對包括多個節點位置及連接關系的圖形初始化，得到多個拓撲結構，包括：

基于包括多個節點位置及連接關系的圖形，采用隨機選取多個CDN節點位置及并確定對應的通信路徑的方式得到多個拓撲結構；或者

基于包括多個節點位置及連接關系的圖形，利用拓撲結構中各CDN節點的所需總帶寬不超過預設節點帶寬，且該CDN節點對應的通信路徑的鏈路帶寬不超過預設鏈路帶寬的約束條件，得到多個拓撲結構。

5.根據權利要求1所述的方法，其特征在于，確定滿足迭代結束條件，包括：

若迭代次數達到預設次數，確定滿足迭代結束條件；或者

對每一輪鄰域搜索完成后新得到的各拓撲結構，確定該拓撲結構中各CDN節點的部署代價及建立該CDN節點對應的通信路徑的鏈路代價，得到該拓撲結構的總代價，確定其中至少一個達到總代價要求時，確定滿足迭代結束條件。

6.根據權利要求1所述的方法，其特征在于，進行多輪鄰域搜索至滿足迭代結束條件，包括：

每一輪鄰域搜索基于當前的多個拓撲結構進行鄰域搜索，得到多個子拓撲結構，從當前的多個拓撲結構和多個子拓撲結構中，選擇一半數量的拓撲結構新得到多個拓撲結構，判斷是否滿足迭代結束條件，若不滿足，并將新得到的多個拓撲結構作為下一輪鄰域搜索的當前拓撲結構，其中，第一輪鄰域搜索的當前拓撲結構為初始化得到的多個拓撲結構。

7.根據權利要求6所述的方法，其特征在于，從當前的多個拓撲結構和多個子拓撲結構中，選擇一半數量的拓撲結構新得到多個拓撲結構，包括：

確定當前各拓撲結構中各CDN節點的部署代價及建立該CDN節點對應的通信路徑的鏈路代價，得到該拓撲結構的總代價；

確定當前各子拓撲結構中各CDN節點的部署代價及建立該CDN節點對應的通信路徑的鏈路代價，得到該子拓撲結構的總代價；

按照總代價從小到大的順序，從當前的多個拓撲結構和多個子拓撲結構中，選擇一半數量的拓撲結構新得到多個拓撲結構。