Hadoop平臺(tái)下一種改進(jìn)螞蟻算法的QoS路由研究

陳志高

(湖南科技職業(yè)學(xué)院 長(zhǎng)沙 410004)

0 引言

云計(jì)算是分布式處理、并行處理和網(wǎng)格計(jì)算的綜合發(fā)展，即把存儲(chǔ)于個(gè)人電腦、移動(dòng)電話和其他設(shè)備上的大量信息和處理器資源集中在一起協(xié)同工作，極大規(guī)模擴(kuò)展信息技術(shù)能力，向外部客戶提供服務(wù)的一種計(jì)算方式［1］。當(dāng)前我國(guó)正處于云計(jì)算的成長(zhǎng)期，未來(lái)十年，我國(guó)許多IT企業(yè)以及各中小企業(yè)都將分享未來(lái)數(shù)千億的“云計(jì)算蛋糕”，越來(lái)越多的云服務(wù)將在網(wǎng)絡(luò)上應(yīng)用和運(yùn)行［2］。我國(guó)雖然已經(jīng)廣泛應(yīng)用了寬帶技術(shù)，但網(wǎng)速仍低于其他國(guó)家［3］。隨著云計(jì)算網(wǎng)絡(luò)的擴(kuò)展和云服務(wù)的增多，對(duì)我國(guó)現(xiàn)有的網(wǎng)絡(luò)性能提出了更高的要求，云環(huán)境下的QoS路由已經(jīng)至關(guān)重要。開(kāi)放最短路徑優(yōu)先算法(open shortest path first，OSPF)是滿足QoS的路由的典型代表，它是現(xiàn)有網(wǎng)絡(luò)普遍采用的一種路由協(xié)議，它采用的路由算法是鏈路狀態(tài)路由算法(link state routing，LS).但是LS不是多徑路由算法，并且不具有擁塞規(guī)避機(jī)制［4］，當(dāng)一條鏈路即將或者已經(jīng)發(fā)生擁塞時(shí)，只有簡(jiǎn)單的丟棄數(shù)據(jù)包，即使網(wǎng)絡(luò)中其他鏈路還是空閑的，這使得網(wǎng)絡(luò)資源無(wú)法得到充分的利用。

1 云計(jì)算的基礎(chǔ)架構(gòu)與螞蟻算法

1.1 云計(jì)算環(huán)境介紹

目前，云計(jì)算的基礎(chǔ)架構(gòu)技術(shù)主要有谷歌非開(kāi)源的體系GFS(google file system)和Hadoop技術(shù)對(duì)于GFS的開(kāi)源實(shí)現(xiàn)HDFS(Hadoop Distributed File-System)。Hadoop是一個(gè)可靠、高效、可伸縮，并能夠?qū)Υ罅繑?shù)據(jù)進(jìn)行分布處理的軟件框架，由于它以并行的方式工作，可以在廉價(jià)的PC機(jī)上利用群集等技術(shù)處理PB級(jí)的數(shù)據(jù)，并自帶有JAVA語(yǔ)言編寫(xiě)的框架，可以免費(fèi)使用。

Hadoop核心部分HDFS和MaPReduee都采用了Master/slave結(jié)構(gòu)，因此整個(gè)Hadoop系統(tǒng)也統(tǒng)一成這種兩層結(jié)構(gòu)。一個(gè)HDFS集群由一個(gè)NameNode(名字節(jié)點(diǎn))和若干個(gè)DataNode(數(shù)據(jù)節(jié)點(diǎn))組成。其中，NameNode是主服務(wù)器，負(fù)責(zé)管理文件系統(tǒng)的名字空間和客戶端對(duì)文件的訪問(wèn)，Datanode是從服務(wù)器，在集群中通常是每個(gè)物理節(jié)點(diǎn)上布置一個(gè)，負(fù)責(zé)它們所在的物理結(jié)點(diǎn)上的存儲(chǔ)管理。在節(jié)點(diǎn)內(nèi)部，文件通常被分割為一個(gè)或多個(gè)數(shù)據(jù)塊(block)，這些數(shù)據(jù)塊存儲(chǔ)在一組DataNode中。

1.2 螞蟻算法

螞蟻算法(Ant Colony Algorithm)是由意大利學(xué)者M(jìn)arco Dorigo等人于1992年提出的一種并行高效的模擬進(jìn)化算法。該算法是模擬自然界中的螞蟻在覓食過(guò)程中形成的一種用來(lái)在圖中尋找優(yōu)化路徑的機(jī)率型技術(shù)，其核心思想是:螞蟻在尋找食物的路徑上會(huì)留下一種叫“信息素”的化學(xué)物質(zhì)，這些“信息素”能夠?yàn)楹罄m(xù)尋找食物的螞蟻提供選擇行走路線的啟發(fā)式信息，通過(guò)不斷更新信息素，可以在較短時(shí)間內(nèi)找到蟻穴和食物之間的最優(yōu)路徑。該算法具有并行性高、收斂速度快等優(yōu)點(diǎn)，并在旅行商問(wèn)題、路由問(wèn)題和調(diào)度問(wèn)題都取得了一些比較滿意的實(shí)驗(yàn)結(jié)果，但是標(biāo)準(zhǔn)螞蟻算法容易陷入局部最優(yōu)解［6］。林國(guó)輝等人［7］提出了基于螞蟻算法的擁塞規(guī)避路由算法，對(duì)鏈路的擁塞狀態(tài)做出快速反應(yīng)，分散流量，以避免鏈路的擁塞。后來(lái)段海濱等［8］提出了一種利用云模型定性關(guān)聯(lián)規(guī)則來(lái)有效限制基本蟻群算法陷入局部最優(yōu)解的方法，并得到比鏈路狀態(tài)路由算法(link state routing，LS)更好的結(jié)果。

2 連接螞蟻算法

2.1 模型設(shè)計(jì)

要實(shí)現(xiàn)云環(huán)境下的高效的QoS路由，在真實(shí)環(huán)境下必須實(shí)現(xiàn)兩個(gè)條件:a.數(shù)據(jù)傳送的路徑必須是最優(yōu)路徑;b.最優(yōu)路徑所經(jīng)過(guò)的各個(gè)節(jié)點(diǎn)間必須有足夠的帶寬運(yùn)行云服務(wù);如果在最優(yōu)路徑上某些節(jié)點(diǎn)間出現(xiàn)擁塞則必須選擇次優(yōu)路徑進(jìn)行分流或擁塞控制。由于螞蟻算法在選擇最短路徑上由較快的收斂性，因此條件a.容易實(shí)現(xiàn)，但是一旦搜索到了最短路徑，所有的云服務(wù)都將從該路徑上運(yùn)行，勢(shì)必將會(huì)引起最短路徑上的數(shù)據(jù)流量陡增。在我國(guó)目前有限的基礎(chǔ)帶寬上，各節(jié)點(diǎn)之間所能提供的網(wǎng)絡(luò)最大容量是參差不齊的，一旦所有的業(yè)務(wù)都放到最優(yōu)路徑上傳輸，將會(huì)使某些網(wǎng)絡(luò)容量較小的節(jié)點(diǎn)提前進(jìn)入擁塞，目前在我國(guó)廣泛使用的路由協(xié)議都不具備擁塞規(guī)避的功能，如果不能及時(shí)調(diào)節(jié)將會(huì)使后續(xù)業(yè)務(wù)繼續(xù)從最優(yōu)路徑上傳輸，導(dǎo)致?lián)砣蛿?shù)據(jù)重傳加劇，這對(duì)云服務(wù)的運(yùn)行是很不利的。

2.2 連接螞蟻算法

章洋等人［9］提出的LB算法將網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)的路由表用一張概率表替換，表中用Pdn表示每個(gè)節(jié)點(diǎn)到達(dá)可能的目標(biāo)節(jié)點(diǎn)d選擇相鄰節(jié)點(diǎn)n的概率，概率即為螞蟻算法中信息素的強(qiáng)度.以此表中概率值的更新來(lái)模擬螞蟻尋路遺留信息素的行為，即利用螞蟻算法來(lái)更新路由表，本文對(duì)此作如下改進(jìn):

a.將ρ改為閾值函數(shù)

定義:

ε為揮發(fā)約束系數(shù)，且ε∈(0，1)，ρ1為信息素殘留在各節(jié)點(diǎn)的最低值。

b.當(dāng)最優(yōu)路徑出現(xiàn)擁塞時(shí)采用何種方法選擇新的次優(yōu)路徑規(guī)避擁塞等問(wèn)題，王傳臣等人［10］提出采用雙向螞蟻尋路的方法(見(jiàn)圖1)，該方法雖然能提高新路徑搜索的速度，但運(yùn)算規(guī)模過(guò)于復(fù)雜，本文提出連接螞蟻算法(link connection ant algorithm，LM)來(lái)規(guī)避擁塞路徑:當(dāng)螞蟻算法搜索到了源節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t的最優(yōu)路徑為s→a→b→c→d→e→f→g→h→t，則意味著節(jié)點(diǎn)d與f之間的最優(yōu)路徑為d→e→f，當(dāng)節(jié)點(diǎn)d與f之間出現(xiàn)擁塞時(shí)只需要選擇另一個(gè)節(jié)點(diǎn)，使得該節(jié)點(diǎn)到d與f之間鏈路的代價(jià)之和最小，并能滿足網(wǎng)絡(luò)QoS要求即可，這樣可以讓其他的節(jié)點(diǎn)都同時(shí)向d與f各發(fā)送一個(gè)連接螞蟻，并比較這些節(jié)點(diǎn)中到d與f之間鏈路的代價(jià)之和，取最小的節(jié)點(diǎn)重新連接到d與f形成一條繞過(guò)d與f的擁塞鏈路的新的次優(yōu)路徑。

圖1 雙向螞蟻鏈路擁塞規(guī)避示意圖

圖2 連接螞蟻擁塞規(guī)避選路示意圖

在整個(gè)云網(wǎng)絡(luò)中，可將網(wǎng)絡(luò)模型看成一個(gè)有向圖G=(V，E)，其中V表示圖中所有云節(jié)點(diǎn)的集合，E表示圖中所有節(jié)點(diǎn)之間通信路徑連接的邊的集合。

如果某條路徑L滿足以下3個(gè)條件，則該路由請(qǐng)求可接受。

a.帶寬可用限制:bandwith(j)≤bandwith，其中j為L(zhǎng)上的任意一條鏈路，bandwidth(j)表示相鄰節(jié)點(diǎn)間的直通鏈路j的可用帶寬。

b.端到端時(shí)延限制:

其中i為L(zhǎng)上不包括起始節(jié)點(diǎn)的其它所有的節(jié)點(diǎn)，nodedelay(i)表示經(jīng)過(guò)路徑L上的節(jié)點(diǎn)i(不包括起始節(jié)點(diǎn))的時(shí)延，j為L(zhǎng)上的任意一條鏈路，linkdelay(j)表示經(jīng)過(guò)路徑L上的鏈路j的時(shí)延。

c.端到端丟失率限制:

其中i為L(zhǎng)上不包括起始節(jié)點(diǎn)的其它所有的節(jié)點(diǎn)，nodeloss(i)表示為在路徑L上的節(jié)點(diǎn)i的丟失率。

連接螞蟻算法(link connection ant algorithm，LM)的具體步驟為:

a.初始化網(wǎng)絡(luò)參數(shù)，判斷網(wǎng)絡(luò)各節(jié)點(diǎn)間的鏈路參數(shù)能否滿足當(dāng)前QoS要求，若QoS要求的總時(shí)延比任何一條鏈路上的時(shí)延要求的都小，即delay≤nodedelay(i)，則網(wǎng)絡(luò)無(wú)法滿足當(dāng)前QoS鏈路要求，退出;否則步驟b。

b.刪除帶寬小于需求帶寬的鏈路，使網(wǎng)絡(luò)圖中保留的各鏈路帶寬均符合QoS要求。

c.初始化各節(jié)點(diǎn)間鏈路上的信息素，設(shè)置為最低值ρ1。

d.從源節(jié)點(diǎn)發(fā)送k只螞蟻尋路，在每只螞蟻成功完成選路后在其所經(jīng)歷的路徑上進(jìn)行信息素的更新。

e.對(duì)所有螞蟻重復(fù)第d步，直到所有螞蟻都完成步驟d的選路和信息素更新過(guò)程。

f.選擇建立最小代價(jià)并滿足QoS鏈路要求的路徑作為可選路由，然后采用全局更新規(guī)則來(lái)更新各路徑上的信息素濃度。

g.重復(fù)第d到f，只到獲得全局最優(yōu)路徑。

3 算法仿真

在NS2仿真平臺(tái)上對(duì)本算法進(jìn)行了仿真，仿真所用的網(wǎng)絡(luò)結(jié)構(gòu)如圖3所示。

圖3 云節(jié)點(diǎn)拓?fù)鋱D

3.1 hadoop云環(huán)境構(gòu)建

仿真環(huán)境是在vmware workstation 8軟件安裝ubuntu linux 9.0群集，并在ubuntu linux 9.0操作系統(tǒng)下安裝hadoop，每個(gè)群集分為master和slave兩臺(tái)虛擬機(jī)，每個(gè)群集在共享磁盤上安裝hadoop，master和slave兩臺(tái)虛擬機(jī)各有兩塊網(wǎng)卡，其中一塊設(shè)置為心跳線連接，另一塊與外界網(wǎng)絡(luò)通信，兩臺(tái)虛擬機(jī)使用一個(gè)公共ip與外部網(wǎng)絡(luò)進(jìn)行通信，其運(yùn)行情況如圖4所示。

3.2 NS2仿真環(huán)境

仿真是在上述ubuntu linux 9.0操作系統(tǒng)下安裝NS-2.34版軟件，通過(guò)下載antnet-1.0，直接對(duì)其目錄下的antnet.tcl腳本進(jìn)行修改，并采用tcl腳本設(shè)置仿真進(jìn)行節(jié)點(diǎn)0到5的數(shù)據(jù)測(cè)試。數(shù)據(jù)源的發(fā)送速率R取值從2Mb/s開(kāi)始，以500 kb/s為步長(zhǎng)漸增，并且數(shù)據(jù)源的發(fā)送和停止的持續(xù)時(shí)間的平均值都是100ms。各條鏈路判斷擁塞的上限閾值為0.6，下限閾值為0.3，NS2仿真結(jié)果如圖5所示。

圖4 hadoop群集節(jié)點(diǎn)

圖5 NS2仿真

另外通過(guò)與文獻(xiàn)［10］中的方法進(jìn)行對(duì)比網(wǎng)絡(luò)丟包率和數(shù)據(jù)包時(shí)延如圖6和圖7所示。

圖6 丟包率分析圖

從仿真結(jié)果圖6和圖7可以看出，本文算法采取的擁塞規(guī)避機(jī)制既能大大降低了網(wǎng)絡(luò)丟包率，又能縮減網(wǎng)絡(luò)平均延時(shí)，在hadoop云網(wǎng)絡(luò)環(huán)境下有較好的適用性。

圖7 時(shí)延分析圖

4 結(jié)論

本文提出了在hadoop云平臺(tái)下一個(gè)基于連接螞蟻能夠滿足多種QoS約束條件和帶有擁塞規(guī)避特性的QoS路由算法。通過(guò)各節(jié)點(diǎn)信息素濃度的概率表來(lái)替換路由表，可以快速搜索符合QoS條件的最優(yōu)路徑，并通過(guò)連接螞蟻來(lái)解決鏈路的擁塞問(wèn)題。通過(guò)仿真，結(jié)果表明該算法在hadoop云環(huán)境下同樣具有比目前LS算法更高的優(yōu)越性。

［1］房秉毅，張?jiān)朴拢态?云計(jì)算國(guó)內(nèi)外發(fā)展現(xiàn)狀分析［J］.電信科學(xué).2010，8A:1-5.

［2］Nezamabadi-pour H，Saryazdi S.and Rashedi E.Edge detection using ant algorithm［J］.Soft Comput.，2006，10(7):623-628.

［3］華夏渝，鄭駿，胡文心.基于云計(jì)算環(huán)境的蟻群優(yōu)化計(jì)算資源分配算法［J］.華東師范大學(xué)學(xué)報(bào).2010，1:127-134.

［4］范杰，彭艦，黎紅友.基于蟻群算法的云計(jì)算需求彈性算法［J］.計(jì)算機(jī)應(yīng)用.2011，31(1):1-4.

［5］何志東，俞鶴偉，陶銘.雙向搜索蟻群算法在QoS單播路由中的應(yīng)用［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46(31):106-108.

［6］田素貞，翟玉梅，劉傳領(lǐng).基于云計(jì)算的多目標(biāo)服務(wù)調(diào)度算法的改進(jìn)研究［J］.陜西理工學(xué)院學(xué)報(bào)(自然科學(xué)版)，2012，28(1):24-28.

［7］林國(guó)輝，馬正新，王勇前，等.基于螞蟻算法的擁塞規(guī)避路由算法［J］.清華大學(xué)學(xué)報(bào)，2003，43(1):1-4.

［8］段海濱，王道波，于秀芬，等.基于云模型理論的蟻群算法改進(jìn)研究［J］.哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2005，37(1):115-119.

［9］章洋，范植華，何曉新，徐帆江，王宇心.移動(dòng)自組網(wǎng)絡(luò)中多徑路由的匿名安全［J］.電子學(xué)報(bào)，2005，33(11):2022-2030.

［10］李丹丹，張潤(rùn)彤，王傳臣，肖東坡.認(rèn)知網(wǎng)絡(luò)中基于蟻群算法的網(wǎng)絡(luò)流量預(yù)測(cè)模型［J］.電子學(xué)報(bào)，2011，39(10):2245-2250.