通信網負載均衡仿真建模的探索

張晨光，陸曉萌

1.嘉善廣播電視臺，浙江嘉興 314100

2.愛立信公司，上海 200136

第一次接觸互連網是1997 年，當時在許多地方，互連網的主要用途還只是是收發電子郵件。現在互聯網的用途已經不僅于此了。根據中國互連網信息中心2011 年的數據，80.9%用戶的常用網絡服務是即時通訊。其他服務（比如，高清可視電話，網上高清電影等）都因網絡帶寬的限制而無法實現。中國用戶對互連網最不滿意的地方就是速度太慢，特別是對于某些沒有自己線路的運營商來說，提高網絡傳輸質量，尤為重要。

提高網絡通過量的辦法有兩種。第一種是增加網絡帶寬，提高交換設備的處理速度；第二種是采用新技術，使負載盡可能地分流到各條路徑上，以便充分利用網絡資源。

1 仿真的過程

網絡仿真是當今檢驗新技術的一種常用方法。它使用代碼與內存來構建網絡的各個單元，這些單元的參數可以按照仿真需要設置。尤其重要的是仿真可以節約運行時間，在幾天內仿真幾年甚至幾十年中可能發生的問題。我的主要任務是理論上論述負載平衡的可行性，并把負載平衡加入到仿真器中。

為了解釋仿真器的運行方式，作者按照仿真時間順序介紹一次最簡化的仿真過程。

1）建立網絡拓撲；

2）建立設置文件；

3）啟動仿真器；

4）帶寬和拓撲傳向路由發生器；

5）每個源在隨機時間點產生流量；

6）流量到達目的地以后被自動消除；

7）緩存狀態、流量延時信息等被存入數據文件。

2 仿真器內核的基本構成

仿真器內核是由CNCL 庫編寫的，而作者重點編寫的路由發生器是由LEDA 庫編寫的，之所以使用兩個不同的C++庫，是因為它們各有特點，然而使用不同的庫在聯合編譯是會有一些問題。

CNCL 庫是由德國Aachen 工業大學通信網教研室開發的C++庫，這個庫主要用于通信網軟件的開發。它比較適合構造仿真器，因為它有產生隨機數、事件驅動和統計等功能。

LEDA 是一個提供圖形數據類型和算法的C++類庫。LEDA提供了各種數據類型和算法。LEDA 提供了各種數據類型和算法。

2.1 網絡拓撲的建立

使用網絡教研室已有的Java 界面Simgui，可以畫所需的網絡拓撲。Simgui 提供了源、節點、目的地和緩沖等單元，這些單元的參數可以修改。把這些單元按照拓撲結構連接起來，就組成了一張圖。這張圖可以通過Export 命令存為*.cfg 文件最簡單的一個*.cfg 文件如下：

在實際的參數設置中，可以直接在*.cfg 文件中修改。

圖1 表示用LEDA 庫建立的節點模型與用CNCL 庫建立的節點模型的關系。

圖1

3 路由發生器的實現

3.1 連接權重的計算

大部分的主干網使用傳統的IP 路由協議，比如OSPF。這些協議都基于SPF 的。而SPF 的目標就是計算網絡兩個節點之間費用最小的路徑。這個費用一般是這兩個節點之間所有連接的權重(weight)之和,所以一個關鍵的問題是如何確定每一個連接的權重。

作者選擇較為直觀的可用帶寬。可用帶寬是指網絡帶寬減去正在使用和已經預定的帶寬。各個連接的權重與可用帶寬一般成反比。可用帶寬越大，權重越小，新流量選擇這一連接的可能性就越大。具體的計算方法是：

當-∞ ＜available_bandwidth ＜1bps 時

weight =2*CAPACITY-CAPACITY*available_bandwidth

當1bps ＜available_bandwidth ＜+∞時

weight =CAPACITY/ available_bandwidth

其中CAPACITY 是一個可以改變的常量，一般選擇各個的連接帶寬的公倍數，但是不應太大，以保證每條連接的初始值是一個較小的正整數。對于整個網絡而言每分鐘產生成千上萬的流量，這些流量都會對網絡的狀況發生影響，從而使可用帶寬不斷發生變化。

3.2 最佳路徑的建立和取消

每個連接的權重確定以后，下一個任務就是使用這些權重計算每一個流量要求的最佳路徑。這種最佳路徑的計算一般使用Dijkstra 算法。

從源到目的地的最優路徑找到以后，路由發生器的下面的任務就是通知在最優路徑上的所有節點為這一流量請求預留網絡資源。按照正在使用和預留的帶寬計算每個連接的可用帶寬，并把結果存到一個連接數組中。同時，按照可用帶寬計算各個連接的權重，以備新流量出現時，計算新的最優路徑時使用。

這樣，用戶的流量就從源經過各個指定的中間節點向目的地傳遞。經過一定的延時以后，這一流量到達目的地。目的地檢查這一流量的序列號，然后通知路由發生器這一流量已經結束。路由發生器采取相應的措施，釋放占用的網絡資源和某些被占用內存。

3.3 路由發生器與仿真器內核的接口

首先仿真器內核根據*.cfg 設置文件，建立各個源、節點和目的地，同時調用路由發生器的方法new_node(long obj_name,Rsobject *obj)，按照圖1 的方式在路由發生器內部建立各個源、節點和目的地對象。然后，設置器開始把各個源、節點和目的地按照*.cfg 中關于網絡拓撲的描述，建立基于CNCL 的庫的各個連接，同時調用路由發生器的方法new_edge(long obj_from, long output_port, long obj_to, long input_port, double bandwidth)建立各個連接，并把節點的端口號通知路由發生器，以備將來使用。

當某個源對象有流量要求時，它就調用路由發生器的方法create_path, 為它計算最優路徑，通知最優路徑上所有節點為這一流量預留帶寬。并為這一流量編號，根據這一統一編號，可以在路由發生器中找到這個流量的帶寬和最優路徑上所有節點的指針。當流量到達目的地以后，仿真器內核調用路由發生器的remove_path(long flow_number)。路由發生器利用這個統一編號讀出帶寬大小，從一個列表中依次讀出最優路徑上的節點，并通知各個節點釋放已經占用的帶寬。路由發生器除了與仿真器內核有接口外，還有一些用于統計仿真數據的接口函數、輸出最優路徑到文件和標準輸出的接口函數等。

3.4 源的實現

源模型主要是描述各個用戶的行為。每個用戶在何時發送一個流量、流量的大小以及流量的持續時間都是隨機的。如何產生統一的負載模型呢？下面介紹一種在本仿真器中使用的方法。

CNCL 數據庫提供了較好的隨機數類。先介紹一個基礎隨機數產生器Fibonacci。它是由一個稱為種子（SEED）的整數作為啟動數，不同的SEED 產生不同的隨機序列。隨機序列中的隨機數是確定的，也就是說，只要SEED 不變，第一次啟動時與第二次啟動時產生的隨機數序列完全一致。隨機數應該盡可能地隨機，以便正確反映現實世界。但是，用算法實現的隨機數只能是偽隨機數。也就是說它的隨機序列具有一定的周期，第二個周期的隨機數與第一個周期的隨機數完全一致。一種好的隨機數產生器應該在不過多占用內存的前提下，盡可能地使這種周期變大。Fibonacci 隨機數產生器的周期是N=（2^32-1）*2^96。這一周期足夠大，足以反映負載的隨機性。

由此整個仿真器的工作方式以及數據的統計設計已經基本完成，可以在計算機上進行實際仿真，得出相應的實驗結果，分析該結果可用對網絡中的負載均衡有更加進一步的了解。

[1]Daniel O.Awduche, Angela Chiu, Anwar Elwalid, Indra Widjaja, Xipeng Xiao, A Framework for Internet Traffic Engineering, INTERNET-DRAFT, May 2000.

[2]Eric C.Rosen, Arun Viswanathan, RossCallon, Multi-protocol Label Switching Architecture, Internet Draft, August 1999.

[3]宛延閨.C++語言和面向對象程序設計.清華大學出版社，1997.

[4]劉紅.應用于MPLS網絡負載均衡的啟發式自適應遺傳算法研究，2003.