基于云平臺(tái)的光纖路由規(guī)劃算法研究

胡朝舉++張和琳

摘 要：隨著信息通信行業(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)分析。通過(guò)在Spark平臺(tái)上對(duì)所提出的算法進(jìn)行實(shí)驗(yàn)，并與傳統(tǒng)的Dijkstra算法比較，結(jié)果表明該算法高效可行，達(dá)到了設(shè)計(jì)要求。

關(guān)鍵詞：光纖路由；最短路徑；云平臺(tái)；Spark

DOIDOI：10.11907/rjdk.1511307

中圖分類(lèi)號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)文章編號(hào)：16727800（2015）012004603

作者簡(jiǎn)介作者簡(jiǎn)介：胡朝舉（1963-），男，河北滄州人，碩士，華北電力大學(xué)控制與計(jì)算機(jī)工程學(xué)院副教授、碩士生導(dǎo)師，研究方向?yàn)閿?shù)據(jù)庫(kù)、信息安全；張和琳（1990-），男，福建福州人，華北電力大學(xué)控制與計(jì)算機(jī)工程學(xué)院碩士研究生，研究方向?yàn)閿?shù)據(jù)庫(kù)與信息系統(tǒng)。

0 引言

光纜傳輸系統(tǒng)是一種高效、可靠、大容量的通信手段，除了衛(wèi)星通信方式外，其它涉及到地面段通信手段的數(shù)據(jù)傳輸基本完全依賴(lài)光纜傳輸網(wǎng)絡(luò)[1]。目前，隨著光纖網(wǎng)絡(luò)日漸復(fù)雜，光纖資源作為底層的連接資源，如何實(shí)現(xiàn)對(duì)該類(lèi)資源的管理和調(diào)度已經(jīng)成為優(yōu)化資源配置、節(jié)約建設(shè)成本的關(guān)鍵問(wèn)題。因此，在數(shù)據(jù)處理量日趨龐大的今天，傳統(tǒng)的最短路徑算法已經(jīng)無(wú)法滿(mǎn)足高效率、快節(jié)奏的要求。

隨著云計(jì)算的提出及發(fā)展，其運(yùn)用領(lǐng)域越來(lái)越廣，其中效率最高的當(dāng)屬Spark。Spark支持內(nèi)存計(jì)算、多迭代批量處理、即席查詢(xún)、流處理和圖計(jì)算等多種范式[2]，它的內(nèi)存計(jì)算框架適合各種迭代算法和交互式數(shù)據(jù)分析，能夠提升大數(shù)據(jù)處理的實(shí)時(shí)性和準(zhǔn)確性，為并行求解光纖路由最短路徑提供了有效途徑。

本文在探討光纖業(yè)務(wù)需求的基礎(chǔ)上，抽象出數(shù)學(xué)模型，提出基于Spark平臺(tái)的光纖路由最短路徑的具體算法，并進(jìn)行實(shí)驗(yàn)分析。

1 基本概念

1.1 光纖路由

在光纖網(wǎng)絡(luò)高速發(fā)展的今天，作為光纖網(wǎng)絡(luò)重要載體的光纜及光纖，其應(yīng)用范圍越來(lái)越廣泛。在光纖網(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完整的光纖路由，其中用黑體線(xiàn)將起點(diǎn)和終點(diǎn)連接起來(lái)的為最優(yōu)光纖路由。因此可以將光纖路由規(guī)劃問(wèn)題抽象為圖論問(wèn)題。

圖1 光纖路由拓?fù)鋱D

1.2 圖論

圖論（Graph Theory）是數(shù)學(xué)的一個(gè)分支，以圖形為研究對(duì)象，研究點(diǎn)與線(xiàn)之間關(guān)系，它是由若干給定的點(diǎn)及連接兩點(diǎn)的線(xiàn)所構(gòu)成的圖形，對(duì)于這種圖形重點(diǎn)關(guān)注有多少個(gè)點(diǎn)和哪些結(jié)點(diǎn)之間有線(xiàn)連接，連接兩點(diǎn)之間的線(xiàn)表示相應(yīng)兩個(gè)結(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)過(guò)一個(gè)或若干個(gè)點(diǎn)到u。因此，在圖G=（V，E）中，如果存在一條從i到j(luò)的最短路徑（Vi，…，Vk，Vj），Vk是Vj前面的一個(gè)點(diǎn)，那么（Vi，…，Vk）也必定是從i到k的最短路徑。為求出最短路徑，Dijkstra提出以最短路徑長(zhǎng)度遞增逐次生成最短路徑的算法。

1.4 廣度優(yōu)先搜索算法

廣度優(yōu)先搜索算法是最簡(jiǎn)單的圖搜索算法之一，是連通圖的一種遍歷策略，也是許多重要的圖算法原型。給定圖G=（V，E）和一個(gè)可以識(shí)別的源節(jié)點(diǎn)s，對(duì)圖G中的點(diǎn)進(jìn)行系統(tǒng)性探索發(fā)現(xiàn)可以從源節(jié)點(diǎn)s到達(dá)所有節(jié)點(diǎn)。該算法能夠計(jì)算從源節(jié)點(diǎn)s到每個(gè)可到達(dá)節(jié)點(diǎn)的距離，同時(shí)生成一棵“廣度優(yōu)先搜索樹(shù)”[6]。廣度優(yōu)先搜索算法的執(zhí)行方法主要是：從任意節(jié)點(diǎn)s出發(fā)，先遍歷與s相鄰的m個(gè)節(jié)點(diǎn)（k1，k2，…，km），然后再遍歷與ki相鄰的節(jié)點(diǎn)。廣度優(yōu)先搜索基于其搜的特性，適用于分布式計(jì)算。

1.5 Spark模型

Spark中最重要的核心概念是彈性分布式數(shù)據(jù)集（Resilient Distributed Datasets），簡(jiǎn)稱(chēng)RDD，是Spark的最基本抽象，是對(duì)分布式內(nèi)存的抽象使用，實(shí)現(xiàn)了以操作本地集合的方式來(lái)操作分布式數(shù)據(jù)集[7]。其實(shí)際數(shù)據(jù)分布存儲(chǔ)于一批機(jī)器內(nèi)存中，相對(duì)于MapReduce，Spark是直接處理內(nèi)存，而不是使用大量的磁盤(pán)IO來(lái)操作文件，因此，相比迭代運(yùn)算和迭代算法，效率有很大的提升。RDD實(shí)現(xiàn)了map、filter、join、flatMap等數(shù)據(jù)集操作方法，在容錯(cuò)性方面有所提高。

Spark通過(guò)轉(zhuǎn)換操作，可以將一個(gè)RDD轉(zhuǎn)換為另外一個(gè)RDD，然后這個(gè)RDD還可以繼續(xù)轉(zhuǎn)換成另外一個(gè)RDD，且這個(gè)過(guò)程是并行、分布式的。Spark在實(shí)現(xiàn)迭代時(shí)，由于中間結(jié)果無(wú)需進(jìn)行IO操作，而且能進(jìn)行多次的RDD轉(zhuǎn)換操作。因此，Spark迭代計(jì)算時(shí)速度相較于MapReduce顯著提高。

2 算法設(shè)計(jì)

傳統(tǒng)最短路徑算法有Dijkstra、Floyd、Bellman-Ford和SPFA等，以其算法簡(jiǎn)單且高效曾流行于一時(shí)，但是對(duì)于圖的信息量越來(lái)越大的今天，傳統(tǒng)的最短路徑算法不再適用于大圖計(jì)算。本文主要結(jié)合Dijkstra算法和廣度優(yōu)先搜索的思想及特性，提出一個(gè)基于Spark云計(jì)算平臺(tái)的數(shù)據(jù)結(jié)構(gòu)及算法。

2.1 數(shù)據(jù)模型構(gòu)建

光纖路由規(guī)劃問(wèn)題，其可以抽象為圖模型，對(duì)于一個(gè)管線(xiàn)網(wǎng)絡(luò)，可以看成是一個(gè)無(wú)向圖的問(wèn)題，對(duì)于規(guī)模比較小的問(wèn)題用傳統(tǒng)的最短路徑算法來(lái)求解，如Dijkstra算法。

在傳統(tǒng)的最短路徑算法中，對(duì)于有n個(gè)結(jié)點(diǎn)的圖G=（V，E），主要存儲(chǔ)結(jié)構(gòu)是一個(gè)n×n的鄰接矩陣及兩個(gè)1×n的距離矩陣和前驅(qū)矩陣。在光纖路由圖模型中任意一個(gè)結(jié)點(diǎn)v和其它結(jié)點(diǎn)u相鄰的數(shù)量m遠(yuǎn)小于節(jié)點(diǎn)個(gè)數(shù)n，因此若以n×n的鄰接矩陣W=[w（i，j）]存儲(chǔ)邊和點(diǎn)，則W類(lèi)似一個(gè)稀疏矩陣。因此若使用三元組存儲(chǔ)則將大大減少內(nèi)存使用。圖2為n為8的無(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í)，三元組的存儲(chǔ)結(jié)果明顯比鄰接矩陣節(jié)省空間。

當(dāng)進(jìn)行最短路徑計(jì)算時(shí)，若有源節(jié)點(diǎn)s，定義節(jié)點(diǎn)二元組V>，其中id為結(jié)點(diǎn)編號(hào)，len為該結(jié)點(diǎn)到結(jié)點(diǎn)s的最短路徑，prev為其最短路徑前驅(qū)節(jié)點(diǎn)；邊三元組T，即T<>，>，len>，用來(lái)計(jì)算從s通過(guò)結(jié)點(diǎn)v1再到節(jié)點(diǎn)v2的距離，每次計(jì)算后同時(shí)更新T和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有邊，且長(zhǎng)度為len；初始化節(jié)點(diǎn)二元組集合Vertex={V1，V2，…，Vn}，其中 Vi=[vi，[len，prev]]，且len=∞，prev=-1，表示無(wú)前驅(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；初始化活動(dòng)集合Alive=Vertex。

（2）若集合Alive為空，則結(jié)束計(jì)算。否則，合并活動(dòng)集合Alive，若在Alive中對(duì)于任意的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。對(duì)于Alive和Vertex，Vv=min{Va，Vv|va=vv}。

（4）生成新活動(dòng)集合Alive。新建空集Alive，集合M={Ti，Ti.vsrc∈{Ta.va，Ta∈Alive}}，對(duì)于Ti，若newlen=len1+len

3 實(shí)驗(yàn)驗(yàn)證及分析

文中結(jié)合Scala語(yǔ)言、Spark編程模式并結(jié)合廣度優(yōu)先搜索算法和Dijkstra算法的思想，設(shè)計(jì)一個(gè)基于Spark平臺(tái)的光纖路由規(guī)劃并行最短路徑算法。實(shí)驗(yàn)搭建的Spark集群在standalone模式下運(yùn)行，有1個(gè)Master節(jié)點(diǎn)和8個(gè)Worker節(jié)點(diǎn)，同時(shí)Master節(jié)點(diǎn)是namenode節(jié)點(diǎn)，其它的worker是datanode，并通過(guò)高速交換機(jī)形成一個(gè)192.168.0.1網(wǎng)段的內(nèi)部網(wǎng)絡(luò)。Spark集群每個(gè)節(jié)點(diǎn)配置為雙核，2G內(nèi)存容量，操作系統(tǒng)為Ubuntu12.04。實(shí)驗(yàn)集群在無(wú)其它任務(wù)運(yùn)行的條件下進(jìn)行。

本實(shí)驗(yàn)主要目標(biāo)是測(cè)試上述設(shè)計(jì)算法的計(jì)算性能，在不同Worker節(jié)點(diǎn)個(gè)數(shù)下的計(jì)算性能，以及和Dijkstra算法進(jìn)行比較。實(shí)驗(yàn)用Spark計(jì)算框架支持Scala、Python和Java多種語(yǔ)言編程，由于Spark內(nèi)核是采用Scala語(yǔ)言編寫(xiě)，所以本實(shí)驗(yàn)選擇使用Scala語(yǔ)言編寫(xiě)實(shí)現(xiàn)并行最短路徑算法。

3.1 正確性驗(yàn)證

算法正確性驗(yàn)證采用單機(jī)環(huán)境，整個(gè)基于Spark的最短路徑算法程序是由Scala語(yǔ)言來(lái)編寫(xiě)實(shí)現(xiàn)的。為了驗(yàn)證算法的正確性和計(jì)算過(guò)程，實(shí)驗(yàn)采用數(shù)據(jù)為圖2中展示的一個(gè)結(jié)點(diǎn)個(gè)數(shù)為8邊個(gè)數(shù)為9的無(wú)向圖。初始化結(jié)點(diǎn)1的數(shù)據(jù)為（1，（0，-1）），其它結(jié)點(diǎn)初始化為（id，（∞，-1），其運(yùn)行步驟如表1所示。

表1中的活動(dòng)結(jié)點(diǎn)狀態(tài)列供下一步驟使用，通過(guò)活動(dòng)節(jié)點(diǎn)就可知道下一步要更新的結(jié)點(diǎn)及要計(jì)算的節(jié)點(diǎn)，由表1的步驟5可看出算法的運(yùn)行結(jié)果是正確的。步驟0為通過(guò)計(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通過(guò)合并活動(dòng)節(jié)點(diǎn)4的結(jié)果并更新節(jié)點(diǎn)4。其計(jì)算過(guò)程與算法所設(shè)計(jì)的過(guò)程完全一致。

3.2 集群運(yùn)行

集群環(huán)境下，實(shí)驗(yàn)用Spark集群?jiǎn)?dòng)8個(gè)Worker節(jié)點(diǎn)，測(cè)試用數(shù)據(jù)存儲(chǔ)在HDFS文件系統(tǒng)中。利用Spark集群測(cè)試在不同節(jié)點(diǎn)個(gè)數(shù)下的運(yùn)行效率及在普通環(huán)境下Dijkstra算法的效率。

在圖的復(fù)雜度較低，即圖的邊數(shù)較少時(shí)，基于Spark的最短路徑算法在不同節(jié)點(diǎn)個(gè)數(shù)的集群下其運(yùn)行時(shí)間比較接近，8個(gè)節(jié)點(diǎn)的集群并不比1個(gè)節(jié)點(diǎn)的集群有多少優(yōu)勢(shì)；但隨著圖的邊數(shù)增加，8個(gè)節(jié)點(diǎn)的集群的優(yōu)勢(shì)慢慢得到體現(xiàn)，運(yùn)行時(shí)間相對(duì)于其它的集群明顯縮短，且運(yùn)行時(shí)間變化不明顯。

圖3 不同結(jié)點(diǎn)下運(yùn)行對(duì)比圖

圖4是傳統(tǒng)的單源最短路徑算法——Dijkstra算法的運(yùn)行時(shí)間當(dāng)圖的邊數(shù)少時(shí)，其運(yùn)行效率很高，運(yùn)行時(shí)間為納秒級(jí)，但隨著圖的邊數(shù)增加，其運(yùn)行時(shí)間開(kāi)始越來(lái)越長(zhǎng)，特別是在邊數(shù)1W以上后，其運(yùn)行時(shí)間呈指數(shù)型增長(zhǎng)，而且在實(shí)驗(yàn)過(guò)程中，當(dāng)邊條數(shù)超過(guò)5W時(shí)，程序?qū)⒊霈F(xiàn)OutOfMemoryError錯(cuò)誤。

通過(guò)圖3和圖4的對(duì)比可知，對(duì)于復(fù)雜度較低的圖傳統(tǒng)的最短路徑算法的運(yùn)行效率高于基于Spark的最短路徑算法；對(duì)于復(fù)雜度較高的圖，基于Spark的最短路徑算法的運(yùn)行效率比傳統(tǒng)的最短路徑算法高。

圖4 Dijkstra算法運(yùn)行效果

4 結(jié)語(yǔ)

本文基于光纖路由規(guī)劃問(wèn)題，分析光纖路由的結(jié)構(gòu)，設(shè)計(jì)了一種基于Spark云平臺(tái)的最短路徑并行算法，并在不同節(jié)點(diǎn)個(gè)數(shù)的集群下對(duì)算法的運(yùn)行時(shí)間進(jìn)行了測(cè)試。實(shí)驗(yàn)結(jié)果證明了算法的正確性、可行性和高效性，能夠快速解決規(guī)模較大的光纖路由規(guī)劃問(wèn)題。

參考文獻(xiàn)參考文獻(xiàn)：

[1] 郭利超，馬朝霞，周云鋒，等.通信光纜監(jiān)測(cè)管理一體化平臺(tái)設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)測(cè)量與控制，2012（8）：22132216.

[2] 葉飛，李莉，江濤，等.基于Hadoop的免疫規(guī)劃管理信息平臺(tái)研究[J].中國(guó)管理信息化，2015（8）：8687.

[3] 李楠.網(wǎng)絡(luò)優(yōu)化技術(shù)在光纜路由自動(dòng)設(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í)）