動(dòng)態(tài)路由優(yōu)化中的最短路徑并行計(jì)算方法研究進(jìn)展

1、1動(dòng)態(tài)路由優(yōu)化中的最短路徑并行計(jì)算方法研究進(jìn)展動(dòng)態(tài)路由優(yōu)化中的最短路徑并行計(jì)算方法研究進(jìn)展楊忠明楊忠明秦勇秦勇茂名學(xué)院廣東茂名525000摘要摘要:本文總結(jié)了國(guó)內(nèi)外一些最短路徑并行計(jì)算算法目前的主要研究結(jié)果，并從QoS路由選擇目標(biāo)中的一些方法特點(diǎn)對(duì)動(dòng)態(tài)路由優(yōu)化算法進(jìn)行改進(jìn)，使用最短路徑并行計(jì)算是解決動(dòng)態(tài)路由優(yōu)化的計(jì)算量問題的方法之一，并提出了最短路徑并行計(jì)算算法優(yōu)化路由策略的實(shí)驗(yàn)方法。關(guān)鍵詞關(guān)鍵詞:最短路徑；并行計(jì)算；動(dòng)態(tài)路由優(yōu)化；Qo

2、S路由；Pareto子集；中圖分類號(hào)中圖分類號(hào)：TP391文獻(xiàn)標(biāo)識(shí)碼文獻(xiàn)標(biāo)識(shí)碼：A1引言網(wǎng)絡(luò)中流量的特點(diǎn)是影響網(wǎng)絡(luò)路由設(shè)計(jì)的主要因素，對(duì)于路由算法設(shè)計(jì)則必須基于流量，但對(duì)于大多數(shù)AS(AutonomousSystem)，基于目前的算法，網(wǎng)絡(luò)中大部分時(shí)間內(nèi)的流量是相當(dāng)穩(wěn)定的，但是通常會(huì)存在一些時(shí)段，網(wǎng)絡(luò)中的流量會(huì)突然變化，對(duì)于現(xiàn)有的路由算法基于性能和復(fù)雜度考慮沒有進(jìn)行重新計(jì)算或調(diào)整。已經(jīng)許多研究者對(duì)AS中高突發(fā)流量究，通過這些高突發(fā)流量的

3、調(diào)查報(bào)告發(fā)現(xiàn)，導(dǎo)致網(wǎng)絡(luò)高突發(fā)流量的原因有諸如病毒的爆發(fā)、ISP路由變動(dòng)、拒絕服務(wù)攻擊等原因，另外基于多媒體的UDP流量日益增多，使得突發(fā)流量往往影響到網(wǎng)絡(luò)中的關(guān)鍵業(yè)務(wù)[14]。如果路由算法沒有考慮到網(wǎng)絡(luò)中的突發(fā)流量的負(fù)載均衡，通常會(huì)導(dǎo)致網(wǎng)絡(luò)鏈路和路由不必要的過載，延遲加大，丟包率增加，網(wǎng)絡(luò)的吞吐量降低，甚至威脅路由器安全。傳統(tǒng)的路由算法通常是基于數(shù)據(jù)傳輸對(duì)網(wǎng)絡(luò)情況的預(yù)測(cè)[5]。而基于算法性能和復(fù)雜度不考慮網(wǎng)絡(luò)突發(fā)流量的實(shí)際，算法通常是根

4、據(jù)采集到網(wǎng)絡(luò)流量的部分度量樣本，基于采樣對(duì)網(wǎng)絡(luò)性能優(yōu)化，而這些采樣并不能反映網(wǎng)絡(luò)的真實(shí)情況[6]。ZhangC.等提及算法考慮多個(gè)具有代表性的流量矩陣，然后找到一組優(yōu)化路由使得代表性的流量矩陣的最差代價(jià)達(dá)到最小，但是這里的最差代價(jià)并非全局僅限于網(wǎng)絡(luò)流量的采樣[78]。KulaS.等提及算法對(duì)實(shí)際網(wǎng)絡(luò)上流量進(jìn)行管理，以響應(yīng)瞬時(shí)流量的需求做出優(yōu)化[9]。這些動(dòng)態(tài)適應(yīng)算法的優(yōu)點(diǎn)在于如果它們能夠迅速收斂，則不需要過多的采樣或者做出預(yù)測(cè)。近年來(lái)在

5、網(wǎng)絡(luò)流量領(lǐng)域值得關(guān)注的是域內(nèi)的流量工程與域間的路由和流量間交互作用，研究發(fā)現(xiàn)一個(gè)AS域內(nèi)的流量會(huì)導(dǎo)致AS出口處流量的變化這種流量變化會(huì)觸發(fā)相鄰AS路由的變化，導(dǎo)致網(wǎng)絡(luò)的不穩(wěn)定[1011]。COPE(CommoncaseOptimizationwithPenaltyEnvelope)算法被提出來(lái)解決這種情況[6]。要應(yīng)對(duì)網(wǎng)絡(luò)中突發(fā)流量，有效的辦法就是開發(fā)出簡(jiǎn)單快速的路由算法并進(jìn)行路由優(yōu)化。3下研究了最短路徑并行算法，給出了SPMD模式下的

6、最短路徑并行算法的簡(jiǎn)單實(shí)現(xiàn)過程，并在非循環(huán)圖網(wǎng)絡(luò)模型和強(qiáng)連通隨機(jī)網(wǎng)絡(luò)模型上對(duì)算法的加速比和并行效率進(jìn)行了測(cè)試[23]。但在網(wǎng)絡(luò)分割策略中采用靜態(tài)負(fù)載平衡策略，沒有考慮動(dòng)態(tài)變化的網(wǎng)絡(luò)帶寬和各個(gè)節(jié)點(diǎn)機(jī)的動(dòng)態(tài)變化情況，不能高效利用各節(jié)點(diǎn)機(jī)的計(jì)算資源，但還需要在各種不同規(guī)模的網(wǎng)絡(luò)中對(duì)算法性能作進(jìn)一步的實(shí)際測(cè)試。3未來(lái)最短路徑并行算法的研究熱點(diǎn)與工作(1)研究最短路徑并行算法在分布式并行集群上的實(shí)現(xiàn)方法，并在大規(guī)模實(shí)際網(wǎng)絡(luò)中對(duì)算法的效率及性能作詳

7、細(xì)深入的測(cè)試。(2)優(yōu)化在最短路徑并行算法中的負(fù)載平衡算法，以期能夠更加有效的利用分布式并行計(jì)算環(huán)境的資源，從而也可以進(jìn)一步提高求解大規(guī)模網(wǎng)絡(luò)上最短路徑的速度。(3)研究最短路徑并行算法對(duì)動(dòng)態(tài)性和實(shí)時(shí)性要求較高的系統(tǒng)中的實(shí)際應(yīng)用。4并行路由算法的啟發(fā)在QoS路由的選擇目標(biāo)中通常希望端到端的延遲最小丟失率最小瓶頸帶寬最大所占用的網(wǎng)絡(luò)資源最少多個(gè)目標(biāo)的選擇中多個(gè)目標(biāo)往往是相互沖突的，不能歸一化，如果只強(qiáng)調(diào)改善某個(gè)目標(biāo)其后果會(huì)使另一目標(biāo)或整個(gè)

8、網(wǎng)絡(luò)性能變壞。因此在多目標(biāo)規(guī)劃中一般不存在所有目標(biāo)函數(shù)共同的極大點(diǎn)，即絕對(duì)最優(yōu)解，多次運(yùn)行單目標(biāo)優(yōu)化過程并逼近Pareto最優(yōu)解或在它們之間進(jìn)行折衷和權(quán)衡，使各子目標(biāo)函數(shù)都盡可能優(yōu)化。但是這個(gè)過程的計(jì)算量非常大，時(shí)間復(fù)雜度高，且非常容易受到網(wǎng)絡(luò)狀態(tài)和路由請(qǐng)求約束的個(gè)數(shù)和參數(shù)的影響，通過并行的約束淘汰和全局的尋優(yōu)計(jì)算，可大幅度地減少路由算法搜索時(shí)間，全局的代價(jià)評(píng)估可提高算法整體的效率性能、算法廣播次數(shù)少，但數(shù)據(jù)量大，因此只適用于中小型網(wǎng)路

9、。求解目標(biāo)的相似性程度越高，并行計(jì)算的效率也就越高，并行路由搜索應(yīng)考慮網(wǎng)絡(luò)結(jié)構(gòu)是否一致，算法是否一致，處理器處理能力是否一致，通信方式是否一致，代價(jià)是否有較大偏離。為有效提高計(jì)算效率，可將QoS度量的Pareto子集并行搜索條件設(shè)定為執(zhí)行同樣的算法和通信方法，使用相同的處理器每個(gè)處理器保持同樣的網(wǎng)絡(luò)圖鄰接矩陣的副本。可以預(yù)期處理器基于各自QoS度量計(jì)算路由時(shí)，檢測(cè)和判斷將產(chǎn)生差異，比如檢測(cè)丟包率和誤碼最為費(fèi)時(shí)，剩余帶寬較費(fèi)時(shí)，檢測(cè)跳數(shù)和