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

麥振大

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

【關(guān)鍵詞】 域間流量控制 BGP路由選擇 負(fù)載平衡 AS關(guān)系 遺傳算法

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

一、數(shù)學(xué)模型

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

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

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

二、算法設(shè)計(jì)

2.1 外層遺傳算法

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

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

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

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

（2）交叉和變異：采用單點(diǎn)交叉以及單點(diǎn)隨機(jī)變異的運(yùn)算方式。

（3）適值計(jì)算

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

（4）選擇過(guò)程

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

（5）終止條件

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

三、實(shí)例分析

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

四、結(jié)論

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