基于蟻群算法的路由算法研究

翟溪林

(山東農(nóng)業(yè)大學(xué)，山東 泰安 271000)

文章基于蟻群算法已有研究成果，提出基于蟻群算法的路由選擇算法，對(duì)推動(dòng)在網(wǎng)絡(luò)路由優(yōu)化上蟻群算法的應(yīng)用具有一定的實(shí)際應(yīng)用價(jià)值。

1 路由機(jī)制的研究

根據(jù)OpenFlow網(wǎng)絡(luò)與傳統(tǒng)網(wǎng)絡(luò)互通的情況，需要這樣一種方案來實(shí)現(xiàn)OpenFlow網(wǎng)絡(luò)層的三層通信，即在OpenFlow控制器中加入路由模塊，在不同OpenFlow網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中，實(shí)現(xiàn)不同IP網(wǎng)段間的通信[1-2]。

2 OpenFIow網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

在本網(wǎng)絡(luò)中，是利用鏈路層發(fā)現(xiàn)協(xié)議(Link Layer Discovery Protocol，LLDP)，OpenFlow交換機(jī)實(shí)現(xiàn)與對(duì)端的鏈路連接狀況和設(shè)備類型信息的周期性地互通，而利用交換機(jī)上傳的狀態(tài)信息，OpenFlow控制器便能對(duì)每一對(duì)端口間的連接情況予以掌握，從而將網(wǎng)絡(luò)的所有拓?fù)錉顩r獲取。依靠傳輸線，各節(jié)點(diǎn)互相連接是本結(jié)構(gòu)的特點(diǎn)，各節(jié)點(diǎn)與其他兩個(gè)及以上節(jié)點(diǎn)相接。可靠性高，結(jié)構(gòu)復(fù)雜，不過維護(hù)與管理不易。利用OpenFlow技術(shù)可對(duì)網(wǎng)絡(luò)資源與鏈路流量進(jìn)行良好的分配，網(wǎng)狀網(wǎng)結(jié)構(gòu)如圖1所示。

圖1 網(wǎng)狀網(wǎng)結(jié)構(gòu)示意

胖樹拓?fù)浣Y(jié)構(gòu)則是OpenFlow網(wǎng)絡(luò)數(shù)據(jù)中心另一種常見的結(jié)構(gòu)。中心流量改變不小，而且多是傳統(tǒng)的基于樹形的網(wǎng)絡(luò)架構(gòu)，收斂比存在上下行間的帶寬，如此易堵塞網(wǎng)絡(luò)[3-4]。就樹形傳統(tǒng)結(jié)構(gòu)，胖樹不止一個(gè)根節(jié)點(diǎn)，有生長向上的多個(gè)左右節(jié)點(diǎn)，通信瓶頸因根節(jié)點(diǎn)而產(chǎn)生，越向上接近根節(jié)點(diǎn)，鏈路占用越大帶寬。故而，就中心網(wǎng)絡(luò)且無堵塞的建立，可用這一結(jié)構(gòu)。而下層節(jié)點(diǎn)鏈路帶寬之和，為上層節(jié)點(diǎn)帶寬，為較理想的胖樹結(jié)構(gòu)，其結(jié)構(gòu)如圖2所示。

圖2 胖樹結(jié)構(gòu)示意

胖樹結(jié)構(gòu)具有良好的擴(kuò)展性，且等分帶寬高、網(wǎng)絡(luò)直徑短，是十分典型的多級(jí)交換網(wǎng)絡(luò)，其分為從下至上的邊緣層、匯聚層和核心層3層。需要注意，從邊緣交換機(jī)向上連接，上層不少于兩個(gè)交換機(jī)與各個(gè)邊緣交換機(jī)相連，則是依靠鏈路，各層交換機(jī)間相連的。而讓邊緣及核心交換機(jī)間有均衡的流量，是整個(gè)網(wǎng)絡(luò)擁塞率減少的關(guān)鍵。本結(jié)構(gòu)能提供多條從同一源節(jié)點(diǎn)至目的節(jié)點(diǎn)的路徑，使容錯(cuò)性較好，路徑多樣化。

3 基于蟻群算法的多路徑路由算法

本章將傳統(tǒng)的路由算法應(yīng)用到OpenFlow網(wǎng)絡(luò)中，針對(duì)OpenFlow數(shù)據(jù)中心網(wǎng)絡(luò)的多路徑，給出基于蟻群算法的多路徑路由選擇算法。

3.1 蟻群算法原理及模型

蟻群算法的基本原理如下。

根據(jù)自然界螞蟻的尋路特征，螞蟻經(jīng)過每條路徑時(shí)留下的信息素有以下特征。

(1)螞蟻對(duì)信息素釋放量與路徑長度成反比關(guān)系。

(2)螞蟻釋放的信息素有揮發(fā)性，其質(zhì)量濃度會(huì)隨著時(shí)間變長而下降，從而對(duì)螞蟻選路的影響性越低。

由于信息素的影響，螞蟻通過最短路徑上留下的信息素濃度最高，而其他路徑上的長度比最短路徑要長，因此，螞蟻在其他路徑上留下的信息素濃度比最短路徑上的信息素質(zhì)量濃度低，隨著時(shí)間變長，信息素?fù)]發(fā)。最終，所有螞蟻都會(huì)從最短路徑上經(jīng)過。

3.2 OpenFlow多路徑路由算法

基于蟻群算法，提出多路徑路由算法，整個(gè)路由選路過程如圖3所示。

圖3 路由過程

在整個(gè)OpenFlow網(wǎng)絡(luò)中，當(dāng)邊緣節(jié)點(diǎn)有數(shù)據(jù)流進(jìn)入時(shí)，控制器中會(huì)傳入有關(guān)節(jié)點(diǎn)信息，根據(jù)這些信息，控制器對(duì)源節(jié)點(diǎn)是否可直接至目的節(jié)點(diǎn)進(jìn)行檢查，若不行，通過螞蟻進(jìn)行尋路，最后會(huì)把至目的地的全部螞蟻記下，將最短路由即鏈路代價(jià)最短路徑篩選出。

4 仿真及分析

上文提出的多路徑算法是一種與OpenFlow數(shù)據(jù)中心相適應(yīng)基于蟻群算法的路由算法，本章對(duì)其進(jìn)行仿真。

在選擇源節(jié)點(diǎn)至目的節(jié)點(diǎn)的路徑時(shí)，基于蟻群算法的原理，經(jīng)對(duì)螞蟻選路滿足的條件予以判斷，將對(duì)帶寬要求滿足的后續(xù)節(jié)點(diǎn)選出，對(duì)下一跳節(jié)點(diǎn)的選擇則依照公式進(jìn)行，對(duì)信息素更新，進(jìn)行路徑篩選，最后是數(shù)據(jù)發(fā)送。

將這種算法應(yīng)用在復(fù)雜數(shù)據(jù)中心的網(wǎng)絡(luò)中，能在多路徑下創(chuàng)設(shè)合理的路由計(jì)算與查找以及將節(jié)點(diǎn)間的最短路徑問題妥善處理。不過，其會(huì)引起較長的最短路徑搜索時(shí)間，局部最優(yōu)解上也易收斂。為此，將一個(gè)條件即帶寬限制加入螞蟻尋路中，進(jìn)行對(duì)帶寬要求滿足的后續(xù)節(jié)點(diǎn)搜索，將最優(yōu)路徑選出。

5 結(jié)語

文章基于OpenFlow網(wǎng)絡(luò)路由功能的需求，OpenFlow網(wǎng)絡(luò)中實(shí)現(xiàn)控制器路由機(jī)制的必要性及OpenFlow網(wǎng)絡(luò)的兩種不同拓?fù)浣Y(jié)構(gòu)等基礎(chǔ)上，闡述了基于螞蟻算法的多路徑路由算法的特點(diǎn)、流程，并進(jìn)行了仿真及分析，由于數(shù)據(jù)中心網(wǎng)絡(luò)中拓?fù)鋸?fù)雜，不少轉(zhuǎn)發(fā)流量的路徑就控制了流量，網(wǎng)絡(luò)有限，且不可利用多條路由進(jìn)行流量轉(zhuǎn)發(fā)。基于OpenFlow的特征，對(duì)提出的算法利用控制器加以調(diào)用，對(duì)路由集中計(jì)算，向多條路徑分配流量并轉(zhuǎn)發(fā)，使網(wǎng)絡(luò)鏈路利用率增加。