[發明專利]面向數據中心的在線場景低帶寬開銷流量調度方案

有效

• 申請號: 201710805436.1
• 申請日: 2017-09-08
• 公開（公告）號: CN107483355B
• 公開（公告）日: 2020-06-16
• 發明（設計）人: 崔勇;李楚鳴;楊振杰;肖詩漢
• 申請（專利權）人: 清華大學
• 主分類號: H04L12/801
• 分類號: H04L12/801;H04L12/863
• 代理公司: 西安智大知識產權代理事務所 61215
• 代理人: 段俊濤

1.一種面向數據中心的在線場景低帶寬開銷流量調度方案，其特征在于，在數據中心間廣域網絡下按照以下步驟實現：

步驟(1)，將一個租用周期分為若干個傳輸時隙，即1，...，T，用一個有向圖G＝(V，E)來表示數據中心和數據中心之間的鏈路，其中V是有向圖的節點集合，表示所有的數據中心的集合，E是有向圖的邊集，表示所有的鏈路的集合，用五元組r_i＝(s_i，t_i，d_i，a_i，τ_i)來代表一個大塊傳輸流，其中s_i，t_i，d_i，a_i，τ_i分別代表第i個大塊傳輸流的源節點、目的節點、數據量、到達時間以及截止時間；運行集中控制器，動態地獲得每個大塊傳輸流的源節點、目的節點、數據量、到達時間和截止時間；

步驟(2)，運行在線租用方案生成算法，在每條大塊傳輸流到達時計算它的調度方案，算法初始化時，令所有帶寬值c_e＝0；

步驟(3)，每個大塊傳輸流到達時，通過在線租用方案生成算法計算最小的額外帶寬開銷，具體步驟如下：

步驟(3a)，通過深度優先搜索算法遍歷該流的全部可行路徑，找出在該流的持續時間[a_i，t_i]內帶寬值c_e未被完全利用的路徑，使用這些有剩余帶寬的路徑傳輸該流的數據；

用P₀表示在流量約束、容量約束和整數約束共三個約束下，使目標函數：

最小化的最優化問題；

其中，流量約束有兩個，第一個流量約束為：

且v≠s_i，v≠t_i，

且t∈N⁺

δ⁺(v)表示以節點v為起點的所有有向邊的集合，δ^-(v)表示以節點v為終點的所有有向邊的集合，x_i，e(t)表示第i個請求在連接e上的第t個時刻的傳輸數據量，N⁺表示正整數集合；

另一個流量約束為：

其中，δ⁺(s_i)表示以節點s_i為起點的所有有向邊的集合，δ^-(s_i)表示以節點s_i為終點的所有有向邊的集合；

所述容量約束為：

其中，c_e為邊e上租用的帶寬值，表示數據中心擁有者在鏈路e上租用的帶寬的單位數，δ_c表示單位帶寬的大小，δ_t表示每個時間片的大小；

所述整數約束為：

其中N表示自然數集合；

如果r_i傳輸完成，則算法終止，轉到步驟(3e)，否則，轉到步驟(3b)；

步驟(3b)，先令所有V_e＝0，V_e為邊e的租用價值；

步驟(3c)，通過深度優先搜索算法遍歷該流的全部可行路徑，因為步驟2中已經利用了所有剩余帶寬，所以所有可行路徑在任意時刻必有一個擁塞邊，即該時刻在擁塞邊上使用的帶寬值為c_e；在遍歷過程中，找出所有路徑上所有時刻的擁塞邊，對于某時刻某條路徑上的一個擁塞邊e，計算該邊的帶寬值c_e增大一個單位后，該時刻該路徑上能額外傳輸的數據量d，令

其中，u_e表示鏈路e的單位帶寬價格；

步驟(3d)，之后，選擇V_e最大的邊e，令c_e←c_e+1，以此引入新的剩余帶寬，再跳轉到步驟(3a)，利用剩余帶寬傳輸剩余的流量；

步驟(3e)，算法終止，得到該流的調度方案；

步驟(4)，根據算法結果生成流量調度方案，進行流量調度。