Hadoop平臺下一種改進螞蟻算法的QoS路由研究

陳志高

(湖南科技職業學院 長沙 410004)

0 引言

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

1 云計算的基礎架構與螞蟻算法

1.1 云計算環境介紹

目前，云計算的基礎架構技術主要有谷歌非開源的體系GFS(google file system)和Hadoop技術對于GFS的開源實現HDFS(Hadoop Distributed File-System)。Hadoop是一個可靠、高效、可伸縮，并能夠對大量數據進行分布處理的軟件框架，由于它以并行的方式工作，可以在廉價的PC機上利用群集等技術處理PB級的數據，并自帶有JAVA語言編寫的框架，可以免費使用。

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

1.2 螞蟻算法

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

2 連接螞蟻算法

2.1 模型設計

要實現云環境下的高效的QoS路由，在真實環境下必須實現兩個條件:a.數據傳送的路徑必須是最優路徑;b.最優路徑所經過的各個節點間必須有足夠的帶寬運行云服務;如果在最優路徑上某些節點間出現擁塞則必須選擇次優路徑進行分流或擁塞控制。由于螞蟻算法在選擇最短路徑上由較快的收斂性，因此條件a.容易實現，但是一旦搜索到了最短路徑，所有的云服務都將從該路徑上運行，勢必將會引起最短路徑上的數據流量陡增。在我國目前有限的基礎帶寬上，各節點之間所能提供的網絡最大容量是參差不齊的，一旦所有的業務都放到最優路徑上傳輸，將會使某些網絡容量較小的節點提前進入擁塞，目前在我國廣泛使用的路由協議都不具備擁塞規避的功能，如果不能及時調節將會使后續業務繼續從最優路徑上傳輸，導致擁塞和數據重傳加劇，這對云服務的運行是很不利的。

2.2 連接螞蟻算法

章洋等人［9］提出的LB算法將網絡中的每個節點的路由表用一張概率表替換，表中用Pdn表示每個節點到達可能的目標節點d選擇相鄰節點n的概率，概率即為螞蟻算法中信息素的強度.以此表中概率值的更新來模擬螞蟻尋路遺留信息素的行為，即利用螞蟻算法來更新路由表，本文對此作如下改進:

a.將ρ改為閾值函數

定義:

ε為揮發約束系數，且ε∈(0，1)，ρ1為信息素殘留在各節點的最低值。

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

圖1 雙向螞蟻鏈路擁塞規避示意圖

圖2 連接螞蟻擁塞規避選路示意圖

在整個云網絡中，可將網絡模型看成一個有向圖G=(V，E)，其中V表示圖中所有云節點的集合，E表示圖中所有節點之間通信路徑連接的邊的集合。

如果某條路徑L滿足以下3個條件，則該路由請求可接受。

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

b.端到端時延限制:

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

c.端到端丟失率限制:

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

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

a.初始化網絡參數，判斷網絡各節點間的鏈路參數能否滿足當前QoS要求，若QoS要求的總時延比任何一條鏈路上的時延要求的都小，即delay≤nodedelay(i)，則網絡無法滿足當前QoS鏈路要求，退出;否則步驟b。

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

c.初始化各節點間鏈路上的信息素，設置為最低值ρ1。

d.從源節點發送k只螞蟻尋路，在每只螞蟻成功完成選路后在其所經歷的路徑上進行信息素的更新。

e.對所有螞蟻重復第d步，直到所有螞蟻都完成步驟d的選路和信息素更新過程。

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

g.重復第d到f，只到獲得全局最優路徑。

3 算法仿真

在NS2仿真平臺上對本算法進行了仿真，仿真所用的網絡結構如圖3所示。

圖3 云節點拓撲圖

3.1 hadoop云環境構建

仿真環境是在vmware workstation 8軟件安裝ubuntu linux 9.0群集，并在ubuntu linux 9.0操作系統下安裝hadoop，每個群集分為master和slave兩臺虛擬機，每個群集在共享磁盤上安裝hadoop，master和slave兩臺虛擬機各有兩塊網卡，其中一塊設置為心跳線連接，另一塊與外界網絡通信，兩臺虛擬機使用一個公共ip與外部網絡進行通信，其運行情況如圖4所示。

3.2 NS2仿真環境

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

圖4 hadoop群集節點

圖5 NS2仿真

另外通過與文獻［10］中的方法進行對比網絡丟包率和數據包時延如圖6和圖7所示。

圖6 丟包率分析圖

從仿真結果圖6和圖7可以看出，本文算法采取的擁塞規避機制既能大大降低了網絡丟包率，又能縮減網絡平均延時，在hadoop云網絡環境下有較好的適用性。

圖7 時延分析圖

4 結論

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

［1］房秉毅，張云勇，程瑩.云計算國內外發展現狀分析［J］.電信科學.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］.華東師范大學學報.2010，1:127-134.

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

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

［6］田素貞，翟玉梅，劉傳領.基于云計算的多目標服務調度算法的改進研究［J］.陜西理工學院學報(自然科學版)，2012，28(1):24-28.

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

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

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

［10］李丹丹，張潤彤，王傳臣，肖東坡.認知網絡中基于蟻群算法的網絡流量預測模型［J］.電子學報，2011，39(10):2245-2250.