麥振大

【摘要】 針對域間流量特點，提出一種基于前綴的域間流量控制算法。利用遺傳算法求解出傳輸自治系統(tǒng)中不同前綴的出口選擇和域內(nèi)各條鏈路的OSPF權重的優(yōu)化解，再利用邊界網(wǎng)關協(xié)議（BGP）對不同的前綴進行相應的通告來控制域間出流量，使域間流量分布更合理。

【關鍵詞】 域間流量控制 BGP路由選擇 負載平衡 AS關系 遺傳算法

Internet是由超過19，000個相對獨立的自治域組成的，這些自治域稱為自治系統(tǒng)（AS）。在一個自治域內(nèi)部，網(wǎng)絡管理者可以管理域內(nèi)的所有路由器，因而可以完全控制域內(nèi)路由及域內(nèi)的流量分布。綜述了當前的域間流量工程應用現(xiàn)狀后指出：“當前的域間流量工程是一種藝術而不是一種技術”。

一、數(shù)學模型

傳輸AS用圖G=（V，E）表示，其中V是域內(nèi)路由器集合，E是域內(nèi)路由器之間的鏈路集合。設邊e對應的鏈路容量為C（e），節(jié)點s到節(jié)點t之間的預期流量為d（s，t）。d（s，t）將分布到由域內(nèi)路由協(xié)議求得的節(jié)點s到節(jié)點t所經(jīng)過路徑的各段鏈路上，因而，鏈路e上的負載為鏈路e的利用率為l（e）/C（e）。設函數(shù)Фe（l（e））表示鏈路e的費用，域內(nèi)各段鏈路費用總和為： 當傳輸AS的網(wǎng)絡性能最優(yōu)時，對應F取值最小。費用函數(shù)Фe（l（e））是非線性的。鏈路負載在接近鏈路容量時網(wǎng)絡性能會急劇下降，相應地，鏈路費用在l（e）接近C（e）時會急劇變大，所以Фe（l（e））為類指數(shù)函數(shù)。將費用函數(shù)Фe（l（e））近似表示成分段線性函數(shù)

其中，ai和bi隨著l（e）/C（e）處于不同區(qū)間而取不同值。將取值區(qū)間分為六段：[0，1/3]， [1/3，2/3]， [2/3，9/10]，[9/10，1]， [1，11/10]， [ 11/10，+∞]，ai分別取1、3、10、70、500、5000，相應可求得bi在各區(qū)間的值。

如果節(jié)點s與節(jié)點t為邊界路由器，則s與t之間傳輸?shù)臄?shù)據(jù)除了包括本自治系統(tǒng)內(nèi)部從s到t的數(shù)據(jù)外，還包括其他自治系統(tǒng)經(jīng)過s和t傳輸?shù)臄?shù)據(jù)。對圖G擴展，向圖中的邊界路由器節(jié)點添加邊，表示與其它自治系統(tǒng)之間的域間鏈路。則傳輸AS域內(nèi)鏈路及域間鏈路費用總和為

式中E表示傳輸AS的邊界路由器與其他自治系統(tǒng)之間的域間鏈路集。

二、算法設計

2.1 外層遺傳算法

外層遺傳算法的作用是確定每個前綴所選擇的域間鏈路。在Internet中，大部分流量源自小部分前綴，[5]統(tǒng)計了AT&T中的流量分布，接近70%的數(shù)據(jù)量出自10%的前綴。實際上，由于每個傳輸AS可見的前綴數(shù)以萬計，為每個前綴進行設置是不現(xiàn)實的。

（1）染色體編碼：利用L=l1，l2，…ln表示前綴所選擇的鏈路，其中l(wèi)i∈[1，65535]，對應一個鏈路號。這里的前綴指經(jīng)傳輸AS傳輸IP數(shù)據(jù)包并且與傳輸AS之間存在多條鏈路的自治系統(tǒng)及其客戶所包含的前綴。（2）交叉與變異：交叉與變異采用染色體多點交叉與單點隨機變異的方式。（3）適值計算：由內(nèi)層算法給出。在內(nèi)層算法計算適值之前，由外層算法計算傳輸AS任意節(jié)點之間數(shù)據(jù)量的大小。（4）選擇：采用“杰出人才模型”方式。（5）終止條件：指定終止代數(shù)或在特定代數(shù)內(nèi)個體沒有進化。

2.2 內(nèi)層遺傳算法

（1）染色體編碼：利用W=w1，w2，…，wm表示各條域內(nèi)鏈路所對應的OSPF權重值，其中，wi∈[1，65535]表示第i條鏈路的OSPF權重值。由于在實際網(wǎng)絡中OSPF權重值一般不取上限65535，在計算過程中可引入一用戶自定義上限MAXWEIGHT。

（2）交叉和變異：采用單點交叉以及單點隨機變異的運算方式。

（3）適值計算

取鏈路費用與配置修改費用之和作為適值函數(shù)。在外層遺傳算法中確定每個前綴所走的域間鏈路后，根據(jù)前綴之間的預期流量、域內(nèi)各節(jié)點間的預期流量及網(wǎng)絡拓樸，可以求出傳輸AS各路由器之間的預期流量。

（4）選擇過程

選擇過程采用“杰出人才模型”方式。

（5）終止條件

采用進化到一定的代數(shù)后終止或在特定代數(shù)內(nèi)沒有更優(yōu)解出現(xiàn)則終止。

三、實例分析

Abilene網(wǎng)絡是Internet2高性能骨干網(wǎng)，連接了參與Internet2的二百多所大學和研究機構，網(wǎng)絡骨干節(jié)點拓樸如圖1所示。通過這些節(jié)點Abilene與77個AS相連。Abilene Observatory提供每個骨干路由器上傳輸流的BGP、TCP、UDP、IP、Router等統(tǒng)計數(shù)據(jù).其中，BGP類數(shù)據(jù)中的Source-Destination-prefix是以前綴-前綴形式表示的路由器的天流量，每條記錄包含一天中從源網(wǎng)絡向目的網(wǎng)絡傳輸?shù)牧鳌⒆止?jié)、包以及持續(xù)時間。

四、結論

本文針對傳輸AS，提出一種域間流量控制方法。傳輸AS測量其內(nèi)部的流量數(shù)據(jù)，規(guī)劃域間多鏈路接入點，調(diào)節(jié)域內(nèi)網(wǎng)絡參數(shù)，使域內(nèi)及域間流量分布更合理。Abilene網(wǎng)絡屬于中等規(guī)模網(wǎng)絡，運算結果表明，利用遺傳算法調(diào)節(jié)中等規(guī)模網(wǎng)絡間的多鏈路流量是可行的、有效的。對于頂層的傳輸AS，由于網(wǎng)絡路由器及前綴數(shù)量過于龐大，算法將進化緩慢，如何有效地選擇前綴及簡化計算過程將有待于進一步研究。