[發明專利]一種最大化最小公平多數據流傳輸調度方法

有效

• 申請號: 201310005320.1
• 申請日: 2013-01-07
• 公開（公告）號: CN103036792A
• 公開（公告）日: 2013-04-10
• 發明（設計）人: 蘇森;雙鍇;王藝文;徐鵬;王玉龍
• 申請（專利權）人: 北京郵電大學
• 主分類號: H04L12/733
• 分類號: H04L12/733;H04L12/911
• 代理公司: 北京思創畢升專利事務所 11218
• 代理人: 郭韞

1.一種最大化最小公平多數據流傳輸調度方法，其特征在于：所述方法包括：

輸入數據中心網絡拓撲信息和數據流傳輸請求信息，計算網絡拓撲中每條邊的中介性特征值；所述數據中心網絡拓撲信息包括各個數據中心之間的鏈路連接關系和每條鏈路的帶寬容量；所述數據流傳輸請求信息包括每個數據流傳輸請求的發送端、目的端和請求傳輸的數據量；

基于所述中介性特征值，對兩點間的不同路徑進行評估，為每個數據流傳輸請求選出特定的K條不重疊傳輸路徑的集合P_i；以及

基于每個數據流傳輸請求的所述K條不重疊傳輸路徑的集合P_i，迭代求出其對應最優的滿足最大化最小公平規則的網絡帶寬資源分配方案。

2.根據權利要求1所述的最大化最小公平多數據流傳輸調度方法，其特征在于：所述基于所述中介性特征值，對兩點間的不同路徑進行評估，為每個數據流傳輸請求選出特定的K條不重疊傳輸路徑的集合P_i包括：

(A1)：給定網絡G(V，E)，源點和目的點分別為v_s和v_t，以及需要求出的路徑數目K；

(A2)：在網絡G上求解其最短路徑p1，將p1加入集合Ps，并將p1所占據的帶寬資源從G中減去，得到殘余網絡Gr；所述Ps為分配給每個數據流傳輸請求的路徑集合；

(A3)：在殘余網絡Gr上重復步驟(A2)直至路徑數達到K或無法求出新的最短路徑；若其中出現多條長度相等的路徑的情況，選擇中介性特征值和最小的路徑；所述中介性特征值和是指每個路徑中各條邊的中介性特征值的和；

(A4)：若求出K條路徑，則轉入步驟(A10)，否則設置變量k＝1，并轉入步驟(A5)；

(A5)：將Ps中的路徑按照長度從小到大進行排序，然后從Ps中選出第k條路徑，p_k＝(v₁，v₂，...，v_i，v_j，...，v_n)，其中，n為該路徑上的節點數量，i，j均為初始值為0的整數；

(A6)：對任意0＜j＜n，先將p_k的鏈路(v_i，v_j)長度設為無窮，之后在網絡G上求出從v_l至v_n的最短路徑p_d，并將其加入集合B，重復步驟(A6)直至j＝n-1；

(A7)：將i加1，恢復G中各鏈路長度為初始值，重復步驟(A6)直至i＝n-2；

(A8)：從集合B中選出中介特征值和最小的一條路徑p’，并將其加入集合Ps；

(A9)：若求出K條路徑，則轉入步驟(A10)，否則將k加1，并重復步驟(A5)至步驟(A9)，直至B中不存在任何路徑，然后轉入步驟(A10)；

(A10)結束。

3.根據權利要求2所述的最大化最小公平多數據流傳輸調度方法，其特征在于：所述基于每個數據流傳輸請求的所述K條不重疊傳輸路徑的集合P_i，迭代求出其對應最優的滿足最大化最小公平規則的網絡帶寬資源分配方案包括：

(B1)：基于對數據中心網間帶寬資源開銷的預測信息，利用時間延展網絡轉換方法將具有動態空閑帶寬資源的網絡轉換為靜態流網絡；

(B2)：基于所述靜態流網絡，對所有數據流傳輸請求建立最大化最小公平多商品流線性規劃模型；

(B3)：迭代地求解所述最大化最小公平多商品流線性規劃模型，得出各個數據流傳輸請求的最大傳輸流量以及對應的數據傳輸路徑。

4.根據權利要求3所述的最大化最小公平多數據流傳輸調度方法，其特征在于：所述步驟(B1)的所述時間延展網絡轉換方法是這樣實現的：將網絡資源從時間維度進行延展，使具有動態空閑帶寬資源的網絡的動態帶寬資源和節點的存儲資源能力統一轉化到一張靜態流網絡上。