基于遺傳算法的域間流量控制

麥振大

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

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

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

一、數學模型

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

其中，ai和bi隨著l（e）/C（e）處于不同區間而取不同值。將取值區間分為六段：[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在各區間的值。

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

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

二、算法設計

2.1 外層遺傳算法

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

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

2.2 內層遺傳算法

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

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

（3）適值計算

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

（4）選擇過程

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

（5）終止條件

采用進化到一定的代數后終止或在特定代數內沒有更優解出現則終止。

三、實例分析

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

四、結論

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