張晨光，陸曉萌

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

2.愛立信公司，上海 200136

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

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

1 仿真的過程

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

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

1）建立網(wǎng)絡(luò)拓撲；

2）建立設(shè)置文件；

3）啟動仿真器；

4）帶寬和拓撲傳向路由發(fā)生器；

5）每個源在隨機時間點產(chǎn)生流量；

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

7）緩存狀態(tài)、流量延時信息等被存入數(shù)據(jù)文件。

2 仿真器內(nèi)核的基本構(gòu)成

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

CNCL 庫是由德國Aachen 工業(yè)大學通信網(wǎng)教研室開發(fā)的C++庫，這個庫主要用于通信網(wǎng)軟件的開發(fā)。它比較適合構(gòu)造仿真器，因為它有產(chǎn)生隨機數(shù)、事件驅(qū)動和統(tǒng)計等功能。

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

2.1 網(wǎng)絡(luò)拓撲的建立

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

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

圖1 表示用LEDA 庫建立的節(jié)點模型與用CNCL 庫建立的節(jié)點模型的關(guān)系。

圖1

3 路由發(fā)生器的實現(xiàn)

3.1 連接權(quán)重的計算

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

作者選擇較為直觀的可用帶寬?？捎脦捠侵妇W(wǎng)絡(luò)帶寬減去正在使用和已經(jīng)預定的帶寬。各個連接的權(quán)重與可用帶寬一般成反比。可用帶寬越大，權(quán)重越小，新流量選擇這一連接的可能性就越大。具體的計算方法是：

當-∞ ＜available_bandwidth ＜1bps 時

weight =2*CAPACITY-CAPACITY*available_bandwidth

當1bps ＜available_bandwidth ＜+∞時

weight =CAPACITY/ available_bandwidth

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

3.2 最佳路徑的建立和取消

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

從源到目的地的最優(yōu)路徑找到以后，路由發(fā)生器的下面的任務(wù)就是通知在最優(yōu)路徑上的所有節(jié)點為這一流量請求預留網(wǎng)絡(luò)資源。按照正在使用和預留的帶寬計算每個連接的可用帶寬，并把結(jié)果存到一個連接數(shù)組中。同時，按照可用帶寬計算各個連接的權(quán)重，以備新流量出現(xiàn)時，計算新的最優(yōu)路徑時使用。

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

3.3 路由發(fā)生器與仿真器內(nèi)核的接口

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

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

3.4 源的實現(xiàn)

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

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

由此整個仿真器的工作方式以及數(shù)據(jù)的統(tǒng)計設(shè)計已經(jīng)基本完成，可以在計算機上進行實際仿真，得出相應(yīng)的實驗結(jié)果，分析該結(jié)果可用對網(wǎng)絡(luò)中的負載均衡有更加進一步的了解。

[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++語言和面向?qū)ο蟪绦蛟O(shè)計.清華大學出版社，1997.

[4]劉紅.應(yīng)用于MPLS網(wǎng)絡(luò)負載均衡的啟發(fā)式自適應(yīng)遺傳算法研究，2003.