[發(fā)明專利]基于穩(wěn)定匹配的流調度方法、裝置、計算機設備及存儲介質

在審

• 申請?zhí)枺?/td>: 201910073822.5
• 申請日: 2019-01-25
• 公開（公告）號: CN109873772A
• 公開（公告）日: 2019-06-11
• 發(fā)明（設計）人: 劉外喜;沈湘平;陳慶春;唐冬;盧錦杰;劉曉初
• 申請（專利權）人: 廣州大學
• 主分類號: H04L12/801
• 分類號: H04L12/801;H04L12/721;H04L12/24
• 代理公司: 廣州市華學知識產權代理有限公司 44245
• 代理人: 李君;裘暉

1.一種基于穩(wěn)定匹配的流調度方法，其特征在于，所述方法包括：

設置流和路徑；

為流和路徑構建偏好表；

根據(jù)流和路徑的偏好表，構建流-路徑穩(wěn)定匹配模型；

根據(jù)流-路徑穩(wěn)定匹配模型，求解最優(yōu)解，采用一對一穩(wěn)定匹配方法在流和路徑之間找到最佳的一對一穩(wěn)定匹配，實現(xiàn)流的最優(yōu)調度。

2.根據(jù)權利要求1所述的基于穩(wěn)定匹配的流調度方法，其特征在于，所述設置流和路徑，具體包括：

設置流：一組流被定義為F＝{f₁，f₂，...}，其中|F|是流的總數(shù)量，將s_i表示為流f_i的大小，通過統(tǒng)計實時流持續(xù)時間和實時流速率，等效地計算流f_i的大小s_i，使s_i＝實時流持續(xù)時間*實時流速率；

設置路徑：一組路徑被定義為SP＝{sp₁，sp₂，...}，其中|SP|是路徑的總數(shù)量，設路徑sp_j具有k跳鏈路，路徑上各跳鏈路的空閑帶寬分別為{b_j1,b_j2,b_j3...b_jk}，將路徑sp_j的平均帶寬記為

3.根據(jù)權利要求1所述的基于穩(wěn)定匹配的流調度方法，其特征在于，所述為流和路徑構建偏好表，具體包括：

為每個流都構建一個對路徑的偏好表P(f_i)＝{sp₁，sp₂，...}；其中，每個路徑sp_j(sp_j∈P(f_i))的帶寬都足以接受流f_i，流優(yōu)先選擇有更多帶寬的路徑，以減少流完成時間；

為每個路徑都構建一個對流的偏好表P(sp_j)＝{f₁，f₂，...}；其中，每個流f_i(f_i∈P(sp_j))都可以被路徑sp_j接受，該偏好表中流的大小小于路徑的平均帶寬，且該偏好表中流的優(yōu)先級順序由流的大小決定，以充分利用路徑的帶寬。

4.根據(jù)權利要求1所述的基于穩(wěn)定匹配的流調度方法，其特征在于，所述構建流-路徑穩(wěn)定匹配模型，具體為：

給定SP和F的集合，模型如下：

Max|M|

S.t.

(1)b_j≥s_i；

(2)E(f_i,M(f_i))＝0；

(3)|M(f_i)|≤1；

(4)|M(sp_j)|≤1.

其中，M表示流和路徑之間的匹配，M(f_i)表示為傳輸f_i的路徑，M(sp_j)表示為與路徑sp_j匹配的流，i＝1,2,...,|F|；j＝1,2,...,|SP|；第一個約束條件確保所有路徑都不會過載，第二個約束條件確保沒有阻塞對出現(xiàn)，最后兩個約束條件確保流和路徑之間的一對一穩(wěn)定匹配。

5.根據(jù)權利要求1-4任一項所述的基于穩(wěn)定匹配的流調度方法，其特征在于，所述根據(jù)流-路徑穩(wěn)定匹配模型，求解最優(yōu)解，采用一對一穩(wěn)定匹配方法在流和路徑之間找到最佳的一對一穩(wěn)定匹配，具體包括：

通過對流-路徑穩(wěn)定匹配模型求解最優(yōu)解找到最多的匹配，獲得最多的沒有阻塞對的流與路徑之間的匹配；

采用一對一穩(wěn)定匹配方法在流和路徑之間找到最佳的一對一穩(wěn)定匹配，該穩(wěn)定匹配方法反復地執(zhí)行提議-拒絕的過程，其中，流負責提議，路徑選擇拒絕或接受該提議。