陳志高

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

0 引言

云計(jì)算是分布式處理、并行處理和網(wǎng)格計(jì)算的綜合發(fā)展，即把存儲(chǔ)于個(gè)人電腦、移動(dòng)電話和其他設(shè)備上的大量信息和處理器資源集中在一起協(xié)同工作，極大規(guī)模擴(kuò)展信息技術(shù)能力，向外部客戶提供服務(wù)的一種計(jì)算方式［1］。當(dāng)前我國正處于云計(jì)算的成長期，未來十年，我國許多IT企業(yè)以及各中小企業(yè)都將分享未來數(shù)千億的“云計(jì)算蛋糕”，越來越多的云服務(wù)將在網(wǎng)絡(luò)上應(yīng)用和運(yùn)行［2］。我國雖然已經(jīng)廣泛應(yīng)用了寬帶技術(shù)，但網(wǎng)速仍低于其他國家［3］。隨著云計(jì)算網(wǎng)絡(luò)的擴(kuò)展和云服務(wù)的增多，對(duì)我國現(xiàn)有的網(wǎng)絡(luò)性能提出了更高的要求，云環(huán)境下的QoS路由已經(jīng)至關(guān)重要。開放最短路徑優(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í)，只有簡單的丟棄數(shù)據(jù)包，即使網(wǎng)絡(luò)中其他鏈路還是空閑的，這使得網(wǎng)絡(luò)資源無法得到充分的利用。

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

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

目前，云計(jì)算的基礎(chǔ)架構(gòu)技術(shù)主要有谷歌非開源的體系GFS(google file system)和Hadoop技術(shù)對(duì)于GFS的開源實(shí)現(xiàn)HDFS(Hadoop Distributed File-System)。Hadoop是一個(gè)可靠、高效、可伸縮，并能夠?qū)Υ罅繑?shù)據(jù)進(jìn)行分布處理的軟件框架，由于它以并行的方式工作，可以在廉價(jià)的PC機(jī)上利用群集等技術(shù)處理PB級(jí)的數(shù)據(jù)，并自帶有JAVA語言編寫的框架，可以免費(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ì)文件的訪問，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)化算法。該算法是模擬自然界中的螞蟻在覓食過程中形成的一種用來在圖中尋找優(yōu)化路徑的機(jī)率型技術(shù)，其核心思想是:螞蟻在尋找食物的路徑上會(huì)留下一種叫“信息素”的化學(xué)物質(zhì)，這些“信息素”能夠?yàn)楹罄m(xù)尋找食物的螞蟻提供選擇行走路線的啟發(fā)式信息，通過不斷更新信息素，可以在較短時(shí)間內(nèi)找到蟻穴和食物之間的最優(yōu)路徑。該算法具有并行性高、收斂速度快等優(yōu)點(diǎn)，并在旅行商問題、路由問題和調(diào)度問題都取得了一些比較滿意的實(shí)驗(yàn)結(jié)果，但是標(biāo)準(zhǔn)螞蟻算法容易陷入局部最優(yōu)解［6］。林國輝等人［7］提出了基于螞蟻算法的擁塞規(guī)避路由算法，對(duì)鏈路的擁塞狀態(tài)做出快速反應(yīng)，分散流量，以避免鏈路的擁塞。后來段海濱等［8］提出了一種利用云模型定性關(guān)聯(lián)規(guī)則來有效限制基本蟻群算法陷入局部最優(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)過的各個(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)行，勢必將會(huì)引起最短路徑上的數(shù)據(jù)流量陡增。在我國目前有限的基礎(chǔ)帶寬上，各節(jié)點(diǎn)之間所能提供的網(wǎng)絡(luò)最大容量是參差不齊的，一旦所有的業(yè)務(wù)都放到最優(yōu)路徑上傳輸，將會(huì)使某些網(wǎng)絡(luò)容量較小的節(jié)點(diǎn)提前進(jìn)入擁塞，目前在我國廣泛使用的路由協(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)度.以此表中概率值的更新來模擬螞蟻尋路遺留信息素的行為，即利用螞蟻算法來更新路由表，本文對(duì)此作如下改進(jìn):

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

定義:

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

b.當(dāng)最優(yōu)路徑出現(xiàn)擁塞時(shí)采用何種方法選擇新的次優(yōu)路徑規(guī)避擁塞等問題，王傳臣等人［10］提出采用雙向螞蟻尋路的方法(見圖1)，該方法雖然能提高新路徑搜索的速度，但運(yùn)算規(guī)模過于復(fù)雜，本文提出連接螞蟻算法(link connection ant algorithm，LM)來規(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形成一條繞過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上的任意一條鏈路，bandwidth(j)表示相鄰節(jié)點(diǎn)間的直通鏈路j的可用帶寬。

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

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

c.端到端丟失率限制:

其中i為L上不包括起始節(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ò)無法滿足當(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的選路和信息素更新過程。

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

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

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

圖5 NS2仿真

另外通過與文獻(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路由算法。通過各節(jié)點(diǎn)信息素濃度的概率表來替換路由表，可以快速搜索符合QoS條件的最優(yōu)路徑，并通過連接螞蟻來解決鏈路的擁塞問題。通過仿真，結(jié)果表明該算法在hadoop云環(huán)境下同樣具有比目前LS算法更高的優(yōu)越性。

［1］房秉毅，張?jiān)朴?，程?云計(jì)算國內(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ī)避路由算法［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)知網(wǎng)絡(luò)中基于蟻群算法的網(wǎng)絡(luò)流量預(yù)測模型［J］.電子學(xué)報(bào)，2011，39(10):2245-2250.