基于遺傳算法的域間路由系統(tǒng)跳變鏈路生成

王 禹，王銀川，焦颯鑭，張勞模

(1.河南工程學院 軟件學院，河南 鄭州451191; 2.中國移動通信集團鄭州分公司 網(wǎng)絡部，河南 鄭州 450000)

邊界網(wǎng)關協(xié)議(border gateway protocol，BGP)是目前互聯(lián)網(wǎng)上唯一部署的域間路由協(xié)議，它負責自治域(autonomous system，AS)之間交換網(wǎng)絡可達性信息(network reachability information, NRI)，屬于增量路徑向量協(xié)議，可避免發(fā)生路由循環(huán)。BGP依賴于自治域之間的相互信任，極易受到錯誤配置、路由劫持和拒絕服務等攻擊[1-2]，以致影響互聯(lián)網(wǎng)正常通信。因此，BGP運行的安全性和穩(wěn)定性對于全球網(wǎng)絡至關重要。

考慮到日益增多的域間路由系統(tǒng)攻擊，其突發(fā)性和擴散性對路由系統(tǒng)的應急響應能力提出了更高的要求。Cheng等[3]提出了多項式時間的啟發(fā)算法來計算自治域之間的穩(wěn)定路徑；Damanik[4]為實現(xiàn)對路由系統(tǒng)不同級別的復雜失效路由進行建模，提出了多路徑快速恢復和優(yōu)化方法；Tran等[5]針對路由擁塞防御可行性進行深入分析，提出了實用性很強的重路由方案。但是，已有研究大多忽略了多節(jié)點資源/策略整合問題，且只著眼于實時性或近實時性操作，難以滿足多域資源調(diào)配復雜性下重路由或恢復路由時間緊迫程度的需求。

本研究提出構建多域社團，利用預計算多路徑跳變機制，基于遺傳算法生成跳變候選集，從而應對多自治域的路由系統(tǒng)通信失效場景。其本質(zhì)是預先為多域社團節(jié)點對(nodes pair)計算盡可能完備的不相交路徑集合，在多域中心控制器負載受限時立即隨機選取不同轉發(fā)路徑以實現(xiàn)跳變，進而實現(xiàn)通信可達的目標。

1 多域社團

域間路由系統(tǒng)在AS級拓撲結構上存在典型的社團特性，主要表現(xiàn)如下：社團內(nèi)部各組織聯(lián)系緊密，社團外部聯(lián)系松散；社團內(nèi)AS節(jié)點的地理位置靠近；社團內(nèi)AS節(jié)點通常具有較為一致的利益關系?；诖?，旨在更好地應對域間路由系統(tǒng)攻擊，尤其是BGP-LDoS對于拓撲關系的探測，本研究給出一種輕量級的協(xié)作防御模式，根據(jù)地理位置和權益關系將域間路由系統(tǒng)中已經(jīng)具備典型社團特征的多個自治系統(tǒng)，構建為共同面向域間路由安全的多自治系統(tǒng)社團。

假定編號為1～10的自治域擁有共同的通信、利益訴求且相互毗鄰，具備基本的社團特征，則可將其組織為多域社團，如圖1所示。該社團邊界的4個自治域編號分別為1、2、8、9，同社團外部連接的自治域包括A、B、C、D和E等。

圖1 多自治域社團

2 數(shù)據(jù)結構定義

結合域間路由系統(tǒng)結構特性，進行數(shù)據(jù)結構的定義。

2.1 節(jié)點的定義

對于單個自治域節(jié)點，定義“節(jié)點狀態(tài)信息”，用于體現(xiàn)該節(jié)點的即時狀態(tài)，格式為

"ASN":(bandwidth, AS_class, reachability, longitude, latitude)。

其中，ASN表示該節(jié)點全球唯一的自治域號碼，bandwidth為當前出口帶寬的最小值，AS_class為自治域類型，reachability表示節(jié)點此時的可達性，longitude和latitude分別代表該自治域所處區(qū)域中心的經(jīng)度和緯度。

多個自治域節(jié)點組成的nodes集合形式如下：

nodes ={′13335′:[1 024, ′Transit′, 1, ′4.881′, ′89.2343′], ′8888′:[1 024, ′Transit′, 1, ′8.888′, ′88.888′], ′1111′:[1 024, ′Stub′, 1, ′4.881′, ′89.2343′],…}。

2.2 邊的定義

兩個毗鄰的自治域節(jié)點連接組成一條邊(edge)，形式為"ASN-ASN"。多條邊組成edges集合，形式如下：

edges = {′13335-18403′: 2 048, ′56149-18403′: 2 048, ′24088-55309′: 2 048, ′1111-8888′: 2 048, ′45899-45903′: 2 048,…}。

在定義了節(jié)點與節(jié)點集合、邊與邊集合之后，對國家/地區(qū)AS級自治域鏈路信息進行提取。

2.3 鏈路的定義

可使用多個自治域節(jié)點來表示一條雙向鏈路，例如某條鏈路以列表為類型，可表示為如下形式：

link =[′18403′, ′18403′, ′56149′, ′55309′, ′24088′, ′45903′]。

在此基礎上，由多條鏈路共同組成鏈路集合，例如：

links =[′18403′, ′18403′, ′56149′, ′55309′, ′24088′, ′45903′],[′18403′, ′13335′, ′56149′, ′55309′, ′24088′, ′45903′], …]。

3 恢復鏈路生成方法

遺傳算法是一種用于計算的搜索過程，用于尋找問題的精確解或近似解，也被稱為全局搜索啟發(fā)法?；谶z傳算法的恢復鏈路生成(genetic algorithm based recovery link generation,GARLG)方法，主要包括鏈路提純、鏈路有效性檢驗、鏈路適應度計算、鏈路遺傳概率計算、父體染色體和母體染色體選擇、變異計算和染色體交叉等子算法。

3.1 鏈路提純

定義link_refine，對鏈路實施提純，依次判斷該鏈路中的每個AS節(jié)點，如果發(fā)現(xiàn)某節(jié)點為NA，即該節(jié)點位于當前考察區(qū)域之外，則舍棄該鏈路；此外，將重復出現(xiàn)的節(jié)點予以去重操作。

例如，待檢驗鏈路為[′18403′, ′13335′, ′13335′, ′56149′, ′55309′, ′24088′, ′24088′,′45903′]，去重后為[′18403′, ′13335′, ′56149′, ′55309′, ′24088′, ′45903′]。

3.2 鏈路有效性檢驗

定義is_valid_link方法，用于判斷某條鏈路是否有效，需要結合nodes和edges數(shù)據(jù)集進行判斷。

①針對該鏈路中的所有節(jié)點，判斷其是否存在于nodes集合，以及reachability是否符合條件(reachability為1則表示可達)，從而認定其是否存活。②針對鏈路中涉及的各個邊，依次判斷其是否存在于edges集合，從而認定該鏈路是否保持連接；如果有任何一段邊存在于edges集合之外，則表明該鏈路無效。上述兩步若均滿足，則判定該鏈路為有效鏈路。

3.3 計算鏈路適應度

適應度(fitness)函數(shù)也稱評價函數(shù)，是根據(jù)目標函數(shù)確定的用于區(qū)分群體中個體好壞的標準。適應度函數(shù)總是非負的，而目標函數(shù)可能有正有負，故需要在目標函數(shù)與適應度函數(shù)之間進行變換。

基于前述的link_refine和is_valid_link，定義get_fitness來計算鏈路集合pop中的全部有效鏈路及其對應的fitness值。過程如下：首先從pop集合中篩選出有效路徑，然后比對該鏈路中每條邊的帶寬，從而獲得其最小帶寬值，作為該鏈路的fitness值。例如，[((′55315′, ′7552′, ′55308′), 2 048),((′135947′, ′38731′, ′63734′), 2 048)]分別表示兩條鏈路及其fitness值。

3.4 計算鏈路遺傳概率

根據(jù)每條鏈路的fitness值，計算出每一個體被遺傳到下一代群體中的概率

(1)

式中：p(xi)表示第i條鏈路遺傳至下一代的概率；xi表示鏈路群體中第i條鏈路；f(xi)表示第i條鏈路的fitness值。

以轉盤劃分(圖2)為例，鏈路群體的每一條鏈路可視為一個染色體，每個染色體的fitness值(即遺傳概率)對應餅圖中一小塊，fitness值越高，則餅圖中小塊所占面積越大。

圖2 輪盤劃分

遺傳算法中，輪盤賭選擇又稱比例選擇，運用該算法的目標是選取一個染色體。轉動輪盤，觀察輪盤停止時指針停在哪一塊區(qū)域，則選中與它對應的那個染色體。由此可知，每個個體被選中的概率與其fitness值成正比。按照上節(jié)fitness的定義可知，鏈路被選中的概率與其帶寬成正比，帶寬越大，鏈路越容易被選中。

3.5 選擇父體/母體染色體

利用累積概率和輪盤賭算法，分別計算選擇父體染色體和母體染色體，要求二者相異。輪盤旋轉停止后，需要判斷指針落于哪個區(qū)域，采用累計概率(cumulative probability)的計算方式進行選擇判斷。每條染色體的累計概率

(2)

染色體遺傳概率的取值為0～1，將其依次進行排列，計算得到累計概率值。若qi大于當前輪盤指針的數(shù)值，則染色體i被選中(即第i條鏈路)；若qi小于當前輪盤指針的數(shù)值，則比較下一個染色體qi+1，直至選出符合的個體為止。

3.6 變異操作

遺傳算法中的變異(mutation)運算[6]，是指將個體染色體編碼串中的某些基因座上的基因值用該基因座上的其他等位基因來替換，從而形成新的個體，包括基本位變異、均勻變異、邊界變異、非均勻變異和高斯近似變異等。針對染色體可能出現(xiàn)的變異特性，引入基本位變異操作。當設置的變異發(fā)生概率(較小概率)小于該閾值時，可以隨機實施鏈路中AS節(jié)點刪除操作，或者鏈路中兩個AS節(jié)點的交換操作，增加鏈路突變優(yōu)化的可能性。

3.7 染色體交叉

遺傳算法的交叉(crossover)運算，是指對兩個相互配對的染色體按某種方式相互交換其部分基因，從而形成兩個新的個體。常見的交叉算子包括：單點交叉(one-point crossover)，指在個體編碼串中只隨機設置一個交叉點，然后在該點相互交換兩個配對個體的部分染色體；兩點交叉(two-point crossover)，指在個體編碼串中隨機設置兩個交叉點，然后再進行部分基因交換；均勻交叉(uniform crossover)，也稱一致交叉，指兩個配對個體每個基因座上的基因都以相同的交叉率進行交換，從而形成兩個新個體；算術交叉(arithmetic crossover)，指由兩個個體的線性組合而產(chǎn)生出兩個新個體，該操作對象一般是由浮點數(shù)編碼表示的個體。本研究采用單點交叉方式，當滿足隨機數(shù)小于設定的交叉率CROSSOVER_RATE時，利用輪盤賭算法從種群中選擇出父體染色體和母體染色體，并隨機產(chǎn)生交叉點位，完成染色體鏈路的交叉。如果新鏈路能夠通過有效性檢驗，則將其加入種群中。隨著多輪交叉與變異，種群不斷擴展，性能更優(yōu)的鏈路將存在于種群之中，保證恢復鏈路。

4 實驗

仿真實驗的數(shù)據(jù)來源于應用互聯(lián)網(wǎng)數(shù)據(jù)分析中心(center for applied Internet data analysis，CAIDA)2020年發(fā)布的互聯(lián)網(wǎng)拓撲數(shù)據(jù)集(Internet topology data kit，ITDK)[7]，該數(shù)據(jù)集由基于Ark(archipelago)推導獲得的traceroutes命令生成。首先分別實施了功能與性能實驗，針對西歐相互毗鄰的部分國家，抽取其ASN、地理位置、鏈路等自治域節(jié)點信息，如表1所示。驗證過程共400輪，依照不同的初始種群規(guī)模、變異率、交叉率、生成鏈路數(shù)目的組合進行，然后對比已有典型跳變算法并分析其優(yōu)劣。

表1 自治域節(jié)點信息

4.1 功能實驗

針對所提方法，一方面需要驗證鏈路生成的有效性，另一方面需要注意約束性節(jié)點的可控性。驗證過程中391輪完成恢復鏈路計算任務，正確率達97.8%左右。圖3和圖4展示了以ASN 205996為起點、以ASN 16313為終點的鏈路生成實驗結果。

圖3 預計算生成2條最佳路徑

圖4 預計算生成5條最佳路徑

假定ASN 60768遭受BGP-LDoS已失效，則經(jīng)過所提遺傳算法的計算，在已有種群基礎上新生成的鏈路符合恢復路徑的需求，其中設置了約束性排除節(jié)點ASN 60768。以預計算生成兩條最佳路徑為例，Path1為[′205996′, ′31428′, ′200804′, ′57495′, ′31167′, ′12605′, ′16313′]，Path2為[′205996′, ′31428′, ′200804′, ′20958′, ′31167′, ′12605′, ′16313′]，見圖3。

以預計算生成5條最佳路徑為例，同樣設置了約束性排除節(jié)點ASN 60768，依照不同線型和灰度可得5條路徑，即Path1為[′205996′, ′31428′, ′200804′, ′57495′, ′31167′, ′12605′, ′16313′]，Path2為[′205996′, ′31428′, ′200804′, ′20958′, ′31167′, ′12605′, ′16313′]，Path3為[′205996′, ′10429′, ′200804′, ′57495′, ′31167′, ′12605′, ′16313′]，Path4為[′205996′, ′10429′, ′200804′, ′20958′, ′31167′, ′12605′, ′16313′]，Path5為[′205996′, ′10429′, ′2856′, ′45758′, ′29686′, ′8839′, ′16313′]，見圖4。

4.2 性能實驗

本階段實驗方案包含兩項。

其一，在相異參數(shù)配置下，分別生成滿足規(guī)范條件的最優(yōu)鏈路候選集。假定不同情況下候選集合中鏈路數(shù)目均相同(以生成2條恢復鏈路為目標)，比對生成候選鏈路所需要的迭代次數(shù)。遺傳算法中變異率一般取值較小，則針對初始種群數(shù)目、變異率、交叉率的4類配置如下：

A參數(shù)配置：初始種群為40，變異率為0.05，交叉率為0.90。

B參數(shù)配置：初始種群為60，變異率為0.05，交叉率為0.90。

C參數(shù)配置：初始種群為60，變異率為0.08，交叉率為0.95。

D參數(shù)配置：初始種群為90，變異率為0.08，交叉率為0.95。

圖5展示了不同參數(shù)配置下的迭代次數(shù)，可知在初始種群數(shù)量相同時，變異率和交叉率閾值較高時所需迭代次數(shù)相對較少，即具有更好的生成性能；在交叉率和變異率保持一致時，初始種群數(shù)量越大越有利于發(fā)現(xiàn)最優(yōu)路徑，縮短生成時長。

圖5 不同配置類型下候選集生成迭代次數(shù)

其二，在相同參數(shù)配置下，以B參數(shù)配置為模板，生成滿足規(guī)范條件的最優(yōu)鏈路候選集，根據(jù)目標鏈路數(shù)目的不同，比較生成迭代次數(shù)。圖6為不同鏈路數(shù)目下候選集生成迭代次數(shù)，可知在目標鏈路數(shù)目分別為2、4、6和8時，迭代次數(shù)依次呈遞增態(tài)勢分布，且增長幅度不斷降低?？紤]到種群的不斷優(yōu)化，所以符合需求的鏈路能夠得以更快地被發(fā)掘。

圖6 不同鏈路數(shù)目下候選集生成迭代次數(shù)

4.3 對比實驗

跳變是主動防御技術的核心技術之一，張連成等[8]提出了一種基于路徑跳變的算法，即PPAH-SPD算法，該算法可隨機改變通信雙方之間的通信路徑與路由。以前述網(wǎng)絡拓撲結構為基準，將本算法與PPAH-SPD算法進行比較。

實驗硬件配置如下：CPU為Intel(R)Core(TM)i7-10750H，2.60 GHz，內(nèi)存16 G。針對不同跳變路徑長度，計算二者時間消耗情況。其中，本算法采用了前述的C參數(shù)配置，即初始種群為60、變異率為0.08、交叉率為0.95。兩類算法的生成時長對比見圖7。

圖7 兩類算法的生成時長對比

由圖7可知，當路徑長度均為3時，二者計算時長基本相當，PPAH-SPD算法略優(yōu)；隨著路徑長度的增加，兩類算法的時長都不斷提高，但本算法的增長態(tài)勢優(yōu)于PPAH-SPD算法?？梢钥吹?，當恢復路徑長度為6時，二者的時長差距為70 ms左右，由此可知隨著路徑長度的擴展，本算法計算復雜度的優(yōu)勢將更為顯著。

5 結語

在針對互聯(lián)網(wǎng)實際自治域拓撲的仿真實驗中，通過不斷優(yōu)化得到了最優(yōu)交叉率和變異率，所提算法能夠設置約束排除節(jié)點，預計算生成多路徑跳變集合，滿足路徑數(shù)目、跳數(shù)及帶寬需求。對算法進行功能和性能測算，并與已有典型算法對比，證明了本算法的有效性。