[發明專利]基于最小費用最大流的負載均衡的多服務遷移方法及系統

有效

• 申請號: 202011436474.2
• 申請日: 2020-12-10
• 公開（公告）號: CN112601232B
• 公開（公告）日: 2022-04-26
• 發明（設計）人: 唐歡;王洋;張錦霞;須成忠;葉可江
• 申請（專利權）人: 中國科學院深圳先進技術研究院
• 主分類號: H04W16/18
• 分類號: H04W16/18;H04W28/16;H04W48/04;H04W48/10;H04W76/10
• 代理公司: 深圳市科進知識產權代理事務所(普通合伙) 44316
• 代理人: 魏毅宏

1.一種基于最小費用最大流的負載均衡的多服務遷移方法，其特征在于：該方法具體步驟包括如下：

根據邊緣服務器的地理位置以及連接關系，構建網絡拓撲圖；

計算每一對邊緣服務器間的最短路徑距離，并生成最短路徑距離矩陣；

根據所述距離矩陣，并結合每個服務的訪問信息、每個邊緣服務器的承載量及其與服務延遲的關系，建立最小費用最大流模型，所述模型包括源結點、服務結點、邊緣服務器結點和終結點；

對模型進行求解得到最小費用最大流，并將服務結點放置在對應的邊緣服務器結點上；

更新每個服務的訪問信息，調整邊緣服務器結點連至終結點的邊的權值，并更新服務結點在邊緣服務器結點上的位置，實現負載均衡；

對每個服務的訪問信息進行實時的監控和統計，在訪問信息的變化率超過設定閾值時，調整其對應的服務結點和邊緣服務器結點；

所述最小費用最大流模型具體為：

以S結點與T結點為模型的源結點和終結點，Ni代表第i個服務結點，Ej代表第j個邊緣服務器結點，源結點S只與服務結點Ni相連，每個服務結點Ni和所有邊緣服務器結點Ej相連，每個邊緣服務器結點Ej均與終結點T相連；模型中的每條邊均關聯容量和通信成本；

所述每個邊緣服務器結點Ej根據其所能承載服務的數量通過至少兩條邊與終結點T相連，每條邊的成本權值均不同并呈遞增關系；

其中，將所述每個邊緣服務器結點Ej到所述終結點T的一條邊拆成多條邊，邊的數目為對應邊緣服務器結點Ej所能放置的服務數量，并賦予每條邊一定的成本權值，使得服務更趨向于放置在那些負載量小的邊緣服務器結點；從而實現邊緣服務器結點的負載均衡，并可以通過對邊緣服務器結點Ej到終結點T的邊上的成本權值進行調節來保證其均衡程度；

每條邊的成本權值根據以往放置相應個數服務所產生的延遲和成本來決定，或者根據用戶的需求或者整個邊緣網絡的實時負載情況來決定。

2.根據權利要求1所述的基于最小費用最大流的負載均衡的多服務遷移方法，其特征在于：所述更新服務結點在邊緣服務器結點上的位置，具體過程包括：

在對模型求解算法的殘余網絡中，更新每個服務結點放置在邊緣服務器結點上的訪問成本以及遷移成本；

根據更新的訪問信息，對殘余網絡中的服務結點以及邊緣服務器結點進行相應的刪添；

根據當時的邊緣網絡指標變化以及每個邊緣服務器結點的負載情況，調整邊緣服務器結點連至終結點的邊的權值；

利用增量式最小費用最大流算法進行求解，并根據求解得到的最小費用最大流，更新服務結點在邊緣服務器結點上的位置。

3.根據權利要求2所述的基于最小費用最大流的負載均衡的多服務遷移方法，其特征在于：所述增量式最小費用最大流算法，具體包括如下：

服務結點的訪問量發生改變，并在訪問次數的變量大于預先學習得到的閾值時，更新服務結點的位置；

服務結點的數量改變時，刪除服務結點或增加服務結點，并更新服務結點的位置；

邊緣服務器結點的承載量發生改變時，并在邊緣服務器結點的容量減小且從其流出的流大于該邊減少后的容量或者出現邊緣服務器結點刪除時、以及邊緣服務器結點容量增加或有新的邊緣服務器結點添加時，更新服務結點的位置。

4.根據權利要求3所述的基于最小費用最大流的負載均衡的多服務遷移方法，其特征在于：從所述改變的結點出發，重新尋找新的最小費用最大流，并對服務結點的進行遷移和放置，更新服務結點在邊緣服務器結點上的位置。