胡朝舉++張和琳
摘 要:隨著信息通信行業(yè)的快速發(fā)展,光纖網(wǎng)絡(luò)日益復(fù)雜,為了實(shí)現(xiàn)更加快速高效的光纖路由規(guī)劃,結(jié)合Dijkstra算法以起始點(diǎn)為中心向外層擴(kuò)展的特點(diǎn)和廣度優(yōu)先搜索算法的遍歷策略,提出一種最短路徑計(jì)算算法,并完成算法的并行設(shè)計(jì)與實(shí)驗(yàn)分析。通過在Spark平臺上對所提出的算法進(jìn)行實(shí)驗(yàn),并與傳統(tǒng)的Dijkstra算法比較,結(jié)果表明該算法高效可行,達(dá)到了設(shè)計(jì)要求。
關(guān)鍵詞:光纖路由;最短路徑;云平臺;Spark
DOIDOI:10.11907/rjdk.1511307
中圖分類號:TP312
文獻(xiàn)標(biāo)識碼:A 文章編號文章編號:16727800(2015)012004603
作者簡介作者簡介:胡朝舉(1963-),男,河北滄州人,碩士,華北電力大學(xué)控制與計(jì)算機(jī)工程學(xué)院副教授、碩士生導(dǎo)師,研究方向?yàn)閿?shù)據(jù)庫、信息安全;張和琳(1990-),男,福建福州人,華北電力大學(xué)控制與計(jì)算機(jī)工程學(xué)院碩士研究生,研究方向?yàn)閿?shù)據(jù)庫與信息系統(tǒng)。
0 引言
光纜傳輸系統(tǒng)是一種高效、可靠、大容量的通信手段,除了衛(wèi)星通信方式外,其它涉及到地面段通信手段的數(shù)據(jù)傳輸基本完全依賴光纜傳輸網(wǎng)絡(luò)[1]。目前,隨著光纖網(wǎng)絡(luò)日漸復(fù)雜,光纖資源作為底層的連接資源,如何實(shí)現(xiàn)對該類資源的管理和調(diào)度已經(jīng)成為優(yōu)化資源配置、節(jié)約建設(shè)成本的關(guān)鍵問題。因此,在數(shù)據(jù)處理量日趨龐大的今天,傳統(tǒng)的最短路徑算法已經(jīng)無法滿足高效率、快節(jié)奏的要求。
隨著云計(jì)算的提出及發(fā)展,其運(yùn)用領(lǐng)域越來越廣,其中效率最高的當(dāng)屬Spark。Spark支持內(nèi)存計(jì)算、多迭代批量處理、即席查詢、流處理和圖計(jì)算等多種范式[2],它的內(nèi)存計(jì)算框架適合各種迭代算法和交互式數(shù)據(jù)分析,能夠提升大數(shù)據(jù)處理的實(shí)時(shí)性和準(zhǔn)確性,為并行求解光纖路由最短路徑提供了有效途徑。
本文在探討光纖業(yè)務(wù)需求的基礎(chǔ)上,抽象出數(shù)學(xué)模型,提出基于Spark平臺的光纖路由最短路徑的具體算法,并進(jìn)行實(shí)驗(yàn)分析。
1 基本概念
1.1 光纖路由
在光纖網(wǎng)絡(luò)高速發(fā)展的今天,作為光纖網(wǎng)絡(luò)重要載體的光纜及光纖,其應(yīng)用范圍越來越廣泛。在光纖網(wǎng)絡(luò)的基礎(chǔ)建設(shè)中,光纖路由規(guī)劃是必不可少的環(huán)節(jié),規(guī)劃的優(yōu)劣程度直接影響建設(shè)成本。光纖路由的載體是地下井管道、電桿等基礎(chǔ)設(shè)施,光纖路由規(guī)劃就是根據(jù)組網(wǎng)需求在兩節(jié)點(diǎn)間鋪設(shè)一條光纜,并根據(jù)已有的光纜載體資源使用情況,尋找出一條合適的鋪設(shè)路徑,實(shí)現(xiàn)光纖資源的預(yù)占[3]。因此在光纜鋪設(shè)中,最重要的環(huán)節(jié)是為光纜在地下井管道和電桿中規(guī)劃一條合適的路由。
圖1展示了光纖路由拓?fù)浼耙粭l完整的光纖路由,其中用黑體線將起點(diǎn)和終點(diǎn)連接起來的為最優(yōu)光纖路由。因此可以將光纖路由規(guī)劃問題抽象為圖論問題。
圖1 光纖路由拓?fù)鋱D
1.2 圖論
圖論(Graph Theory)是數(shù)學(xué)的一個分支,以圖形為研究對象,研究點(diǎn)與線之間關(guān)系,它是由若干給定的點(diǎn)及連接兩點(diǎn)的線所構(gòu)成的圖形,對于這種圖形重點(diǎn)關(guān)注有多少個點(diǎn)和哪些結(jié)點(diǎn)之間有線連接,連接兩點(diǎn)之間的線表示相應(yīng)兩個結(jié)點(diǎn)之間的某種關(guān)系[4]。
1.3 Dijkstra算法
Dijkstra算法是典型的最短路徑算法,是一種用于尋找給定加權(quán)圖中單源點(diǎn)到其余各頂點(diǎn)的最短路徑算法,其主要特點(diǎn)是以起始點(diǎn)為中心向外層擴(kuò)展,直到終點(diǎn)為止[5]。
Dijkstra算法的基本思想如下:從任意結(jié)點(diǎn)v到任意結(jié)點(diǎn)u的最短路徑共有兩種可能:一是直接從v到u,二是從v經(jīng)過一個或若干個點(diǎn)到u。因此,在圖G=(V,E)中,如果存在一條從i到j(luò)的最短路徑(Vi,…,Vk,Vj),Vk是Vj前面的一個點(diǎn),那么(Vi,…,Vk)也必定是從i到k的最短路徑。為求出最短路徑,Dijkstra提出以最短路徑長度遞增逐次生成最短路徑的算法。
1.4 廣度優(yōu)先搜索算法
廣度優(yōu)先搜索算法是最簡單的圖搜索算法之一,是連通圖的一種遍歷策略,也是許多重要的圖算法原型。給定圖G=(V,E)和一個可以識別的源節(jié)點(diǎn)s,對圖G中的點(diǎn)進(jìn)行系統(tǒng)性探索發(fā)現(xiàn)可以從源節(jié)點(diǎn)s到達(dá)所有節(jié)點(diǎn)。該算法能夠計(jì)算從源節(jié)點(diǎn)s到每個可到達(dá)節(jié)點(diǎn)的距離,同時(shí)生成一棵“廣度優(yōu)先搜索樹”[6]。廣度優(yōu)先搜索算法的執(zhí)行方法主要是:從任意節(jié)點(diǎn)s出發(fā),先遍歷與s相鄰的m個節(jié)點(diǎn)(k1,k2,…,km),然后再遍歷與ki相鄰的節(jié)點(diǎn)。廣度優(yōu)先搜索基于其搜的特性,適用于分布式計(jì)算。
1.5 Spark模型
Spark中最重要的核心概念是彈性分布式數(shù)據(jù)集(Resilient Distributed Datasets),簡稱RDD,是Spark的最基本抽象,是對分布式內(nèi)存的抽象使用,實(shí)現(xiàn)了以操作本地集合的方式來操作分布式數(shù)據(jù)集[7]。其實(shí)際數(shù)據(jù)分布存儲于一批機(jī)器內(nèi)存中,相對于MapReduce,Spark是直接處理內(nèi)存,而不是使用大量的磁盤IO來操作文件,因此,相比迭代運(yùn)算和迭代算法,效率有很大的提升。RDD實(shí)現(xiàn)了map、filter、join、flatMap等數(shù)據(jù)集操作方法,在容錯性方面有所提高。
Spark通過轉(zhuǎn)換操作,可以將一個RDD轉(zhuǎn)換為另外一個RDD,然后這個RDD還可以繼續(xù)轉(zhuǎn)換成另外一個RDD,且這個過程是并行、分布式的。Spark在實(shí)現(xiàn)迭代時(shí),由于中間結(jié)果無需進(jìn)行IO操作,而且能進(jìn)行多次的RDD轉(zhuǎn)換操作。因此,Spark迭代計(jì)算時(shí)速度相較于MapReduce顯著提高。
2 算法設(shè)計(jì)
傳統(tǒng)最短路徑算法有Dijkstra、Floyd、Bellman-Ford和SPFA等,以其算法簡單且高效曾流行于一時(shí),但是對于圖的信息量越來越大的今天,傳統(tǒng)的最短路徑算法不再適用于大圖計(jì)算。本文主要結(jié)合Dijkstra算法和廣度優(yōu)先搜索的思想及特性,提出一個基于Spark云計(jì)算平臺的數(shù)據(jù)結(jié)構(gòu)及算法。
2.1 數(shù)據(jù)模型構(gòu)建
光纖路由規(guī)劃問題,其可以抽象為圖模型,對于一個管線網(wǎng)絡(luò),可以看成是一個無向圖的問題,對于規(guī)模比較小的問題用傳統(tǒng)的最短路徑算法來求解,如Dijkstra算法。
在傳統(tǒng)的最短路徑算法中,對于有n個結(jié)點(diǎn)的圖G=(V,E),主要存儲結(jié)構(gòu)是一個n×n的鄰接矩陣及兩個1×n的距離矩陣和前驅(qū)矩陣。在光纖路由圖模型中任意一個結(jié)點(diǎn)v和其它結(jié)點(diǎn)u相鄰的數(shù)量m遠(yuǎn)小于節(jié)點(diǎn)個數(shù)n,因此若以n×n的鄰接矩陣W=[w(i,j)]存儲邊和點(diǎn),則W類似一個稀疏矩陣。因此若使用三元組
以三元組表示圖G的邊和節(jié)點(diǎn)關(guān)系:E<1,2,3>,E<1,3,6>,E<2,1,3>,E<2,4,6>,E<3,1,6>,E<3,4,1>,E<4,2,6>,E<4,3,1>,E<4,5,2>,E<5,4,2>,E<5,6,5>,E<5,7,3>,E<6,5,5>,E<6,8,3>,E<7,5,3>,E<7,8,7>,E<8,6,3>,E<8,7,7>G8的鄰接矩陣和三元組相比,當(dāng)節(jié)點(diǎn)數(shù)較大時(shí),三元組的存儲結(jié)果明顯比鄰接矩陣節(jié)省空間。
當(dāng)進(jìn)行最短路徑計(jì)算時(shí),若有源節(jié)點(diǎn)s,定義節(jié)點(diǎn)二元組V
2.2 算法實(shí)現(xiàn)
結(jié)合Dijkstra算法和廣度優(yōu)先搜索算法的思想,以及前述設(shè)計(jì)的數(shù)據(jù)模型,算法流程具體如下:
(1)初始化邊和結(jié)點(diǎn)關(guān)系集合Edge={E1,E2,…,Em},其中Ei=[vsrc,vdst,len],表示從節(jié)點(diǎn)v1到節(jié)點(diǎn)v2有邊,且長度為len;初始化節(jié)點(diǎn)二元組集合Vertex={V1,V2,…,Vn},其中 Vi=[vi,[len,prev]],且len=∞,prev=-1,表示無前驅(qū)節(jié)點(diǎn);初始化三元組Triplet={T1,T2,…,Tm},Ti=[Vsrc,Vdst,len]即Ti=[[vsrc,[len1,prev1]],[vdst,[len2,prev2]],len],初始化源節(jié)點(diǎn)Vs相關(guān)元素,更新Vertex和Triplet中,設(shè)置len=0;初始化活動集合Alive=Vertex。
(2)若集合Alive為空,則結(jié)束計(jì)算。否則,合并活動集合Alive,若在Alive中對于任意的Vi和Vj,若有vi=vj,則合并Vi和Vj,prev=min{previ,prevj},len=min{leni,lenj},combine(Vi,Vj)Vk=[vi,[len,prev]]。
(3)讀取Alive節(jié)點(diǎn),更新Vertex。對于Alive和Vertex,Vv=min{Va,Vv|va=vv}。
(4)生成新活動集合Alive。新建空集Alive,集合M={Ti,Ti.vsrc∈{Ta.va,Ta∈Alive}},對于Ti,若newlen=len1+len 3 實(shí)驗(yàn)驗(yàn)證及分析 文中結(jié)合Scala語言、Spark編程模式并結(jié)合廣度優(yōu)先搜索算法和Dijkstra算法的思想,設(shè)計(jì)一個基于Spark平臺的光纖路由規(guī)劃并行最短路徑算法。實(shí)驗(yàn)搭建的Spark集群在standalone模式下運(yùn)行,有1個Master節(jié)點(diǎn)和8個Worker節(jié)點(diǎn),同時(shí)Master節(jié)點(diǎn)是namenode節(jié)點(diǎn),其它的worker是datanode,并通過高速交換機(jī)形成一個192.168.0.1網(wǎng)段的內(nèi)部網(wǎng)絡(luò)。Spark集群每個節(jié)點(diǎn)配置為雙核,2G內(nèi)存容量,操作系統(tǒng)為Ubuntu12.04。實(shí)驗(yàn)集群在無其它任務(wù)運(yùn)行的條件下進(jìn)行。 本實(shí)驗(yàn)主要目標(biāo)是測試上述設(shè)計(jì)算法的計(jì)算性能,在不同Worker節(jié)點(diǎn)個數(shù)下的計(jì)算性能,以及和Dijkstra算法進(jìn)行比較。實(shí)驗(yàn)用Spark計(jì)算框架支持Scala、Python和Java多種語言編程,由于Spark內(nèi)核是采用Scala語言編寫,所以本實(shí)驗(yàn)選擇使用Scala語言編寫實(shí)現(xiàn)并行最短路徑算法。 3.1 正確性驗(yàn)證 算法正確性驗(yàn)證采用單機(jī)環(huán)境,整個基于Spark的最短路徑算法程序是由Scala語言來編寫實(shí)現(xiàn)的。為了驗(yàn)證算法的正確性和計(jì)算過程,實(shí)驗(yàn)采用數(shù)據(jù)為圖2中展示的一個結(jié)點(diǎn)個數(shù)為8邊個數(shù)為9的無向圖。初始化結(jié)點(diǎn)1的數(shù)據(jù)為(1,(0,-1)),其它結(jié)點(diǎn)初始化為(id,(∞,-1),其運(yùn)行步驟如表1所示。 表1中的活動結(jié)點(diǎn)狀態(tài)列供下一步驟使用,通過活動節(jié)點(diǎn)就可知道下一步要更新的結(jié)點(diǎn)及要計(jì)算的節(jié)點(diǎn),由表1的步驟5可看出算法的運(yùn)行結(jié)果是正確的。步驟0為通過計(jì)算源節(jié)點(diǎn)1的相鄰點(diǎn),求得從1到2的距離為3及前驅(qū)節(jié)點(diǎn)為1,從1到3的距離為6及前驅(qū)節(jié)點(diǎn)為1;步驟1更新節(jié)點(diǎn)2和3,并分別計(jì)算出自身到其相鄰節(jié)點(diǎn)4的距離;步驟2通過合并活動節(jié)點(diǎn)4的結(jié)果并更新節(jié)點(diǎn)4。其計(jì)算過程與算法所設(shè)計(jì)的過程完全一致。 3.2 集群運(yùn)行 集群環(huán)境下,實(shí)驗(yàn)用Spark集群啟動8個Worker節(jié)點(diǎn),測試用數(shù)據(jù)存儲在HDFS文件系統(tǒng)中。利用Spark集群測試在不同節(jié)點(diǎn)個數(shù)下的運(yùn)行效率及在普通環(huán)境下Dijkstra算法的效率。 在圖的復(fù)雜度較低,即圖的邊數(shù)較少時(shí),基于Spark的最短路徑算法在不同節(jié)點(diǎn)個數(shù)的集群下其運(yùn)行時(shí)間比較接近,8個節(jié)點(diǎn)的集群并不比1個節(jié)點(diǎn)的集群有多少優(yōu)勢;但隨著圖的邊數(shù)增加,8個節(jié)點(diǎn)的集群的優(yōu)勢慢慢得到體現(xiàn),運(yùn)行時(shí)間相對于其它的集群明顯縮短,且運(yùn)行時(shí)間變化不明顯。 圖3 不同結(jié)點(diǎn)下運(yùn)行對比圖 圖4是傳統(tǒng)的單源最短路徑算法——Dijkstra算法的運(yùn)行時(shí)間當(dāng)圖的邊數(shù)少時(shí),其運(yùn)行效率很高,運(yùn)行時(shí)間為納秒級,但隨著圖的邊數(shù)增加,其運(yùn)行時(shí)間開始越來越長,特別是在邊數(shù)1W以上后,其運(yùn)行時(shí)間呈指數(shù)型增長,而且在實(shí)驗(yàn)過程中,當(dāng)邊條數(shù)超過5W時(shí),程序?qū)⒊霈F(xiàn)OutOfMemoryError錯誤。 通過圖3和圖4的對比可知,對于復(fù)雜度較低的圖傳統(tǒng)的最短路徑算法的運(yùn)行效率高于基于Spark的最短路徑算法;對于復(fù)雜度較高的圖,基于Spark的最短路徑算法的運(yùn)行效率比傳統(tǒng)的最短路徑算法高。 圖4 Dijkstra算法運(yùn)行效果 4 結(jié)語 本文基于光纖路由規(guī)劃問題,分析光纖路由的結(jié)構(gòu),設(shè)計(jì)了一種基于Spark云平臺的最短路徑并行算法,并在不同節(jié)點(diǎn)個數(shù)的集群下對算法的運(yùn)行時(shí)間進(jìn)行了測試。實(shí)驗(yàn)結(jié)果證明了算法的正確性、可行性和高效性,能夠快速解決規(guī)模較大的光纖路由規(guī)劃問題。 參考文獻(xiàn)參考文獻(xiàn): [1] 郭利超,馬朝霞,周云鋒,等.通信光纜監(jiān)測管理一體化平臺設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)測量與控制,2012(8):22132216. [2] 葉飛,李莉,江濤,等.基于Hadoop的免疫規(guī)劃管理信息平臺研究[J].中國管理信息化,2015(8):8687. [3] 李楠.網(wǎng)絡(luò)優(yōu)化技術(shù)在光纜路由自動設(shè)計(jì)中的應(yīng)用[D].北京:北京郵電大學(xué),2011. [4] REINHARD DIESTEL.圖論(第4版) [M].北京:高等教育出版社,2013. [5] 江家寶,鄭尚志.基于PSO算法的OSPF多約束路由策略[J].軟件導(dǎo)刊,2015,14(6):7679. (責(zé)任編輯:陳福時(shí))