[發明專利]一種異構計算環境下的網絡模擬任務負載平衡方法

有效

• 申請號: 201410407933.2
• 申請日: 2014-08-18
• 公開（公告）號: CN104184674B
• 公開（公告）日: 2017-04-05
• 發明（設計）人: 王曉鋒;卞娜云;劉淵;陳世云
• 申請（專利權）人: 江南大學
• 主分類號: H04L12/803
• 分類號: H04L12/803
• 代理公司: 無錫市大為專利商標事務所(普通合伙)32104
• 代理人: 徐士金,韓鳳

技術領域

本發明涉及一種異構計算環境下的網絡模擬任務負載平衡方法，屬于計算機網絡技術領域。

背景技術

在網絡模擬，尤其是大規模的網絡模擬中，有限的計算資源遠不能滿足巨大的計算需求，所以通常采用并行分布式的網絡模擬器。并行網絡模擬即是多機同時模擬的一個過程，即通過將一個大規模網絡的模擬任務劃分，然后計算集群中的每一個計算節點負責模擬該網絡的一個部分，從而擴大網絡模擬的規模和性能。然而對于分布式網絡模擬而言，一個關鍵問題是如何針對計算環境有效的平衡模擬任務，因為計算節點負載均衡程度越高，模擬所需要的運行時間就越少。

在網絡模擬運行過程中，路由模擬和數據包轉發模擬是兩項相當耗時的任務。路由模擬主要是基于網絡拓撲圖，計算網絡模擬過程中數據包轉發模擬所需的路由表信息并存儲，當網絡拓撲規模較大時，路由模擬需要很大的計算開銷；數據包轉發模擬運行同樣占計算開銷的很大比例，它主要是基于離散事件模擬技術刻畫網絡中每一個數據包轉發的行為，進而推演出整個網絡的行為。由此說明，提升路由模擬以及數據包轉發模擬的負載均衡度，進一步提升模擬性能，是降低整個網絡模擬的計算開銷的關鍵。

現有技術中針對同構環境下負載平衡方法本發明稱這類方法為均勻負載平衡方法(ULB，Uniform?Load?Balance)。ULB方法將數據包轉發模擬任務均勻分配給各個計算節點，然而該方法能對同構計算環境下的網絡模擬任務進行有效劃分，實現模擬任務的負載平衡、通信開銷與同步開銷最小化等，從而降低網絡模擬的運行時間，但是上述方法無法滿足異構計算環境下的網絡模擬負載均衡的要求。

現有技術中針對異構環境下負載平衡方法本發明稱這一類方法為線性負載平衡方法(LLB，Liner?Load?Balance)。LLB方法根據異構環境下不同計算節點不同的計算能力，按比例分配網絡模擬任務,然而該方法只能用于保證數據包轉發模擬任務的負載平衡，不能保證路由模擬任務負載平衡。

發明內容

本發明的目的在于針對上述現有技術的不足,提出的一種異構計算環境下網絡模擬任務負載均衡方法,綜合考慮路由模擬任務以及數據包轉發模擬任務的負載平衡，以降低網絡模擬時間開銷，提高并行模擬效率。同時，該方法的運行時間較低，具有面向大規模網絡與大規模計算環境的可擴展性。

按照本發明提供的技術方案，所述的異構計算環境下的網絡模擬任務負載平衡方法包括以下步驟：

(1)讀入一個異構計算環境參數，包括異構計算環境中計算節點個數M，第i個計算節點數據包轉發模擬能力參數K_i，第i個計算節點路由模擬能力函數F_i(n)，1≤i≤M；

(2)讀入一個網絡模擬的實際拓撲圖G(V,E)，其中點集合V＝{v₁…,v_j,…,v_N}，點權值w_v(v_j)，邊權值w_e(v_i,v_j)；v_j表示第j個拓撲節點，N為拓撲節點的個數，1≤j≤N；

(3)初始化參數：初始化無進展遷移次數Counter為0，初始化網絡模擬任務負載均衡度B的閾值B_Delta為0.95，初始化當前最優的負載平衡度B_est為0；

(4)負載平衡初始化：將拓撲圖G(V,E)初始劃分為{G₁,…,G_i,…,G_M}，使得數據包轉發模擬任務負載均衡度BP最大；

(5)計算當前最優的負載平衡度B_est；

(6)判斷B_est是否小于B_Delta且Counter是否小于3，滿足則終止循環，輸出負載平衡結果{G₁,…,G_i,…,G_M}；不滿足則轉到步驟(7)；

(7)統計當前各G_i的拓撲節點個數n_i，并根據各計算節點的路由模擬計算開銷函數獲得路由模擬運行時間最小的劃分Gi_min與最大的劃分Gi_max；

(8)從中選擇某一待移動的拓撲節點v_m，其中v_m必須與中的某個節點之間存在鏈路且點權值是所有與存在鏈路的節點中最小；