基于多鏈路權(quán)值減小的動(dòng)態(tài)SPT算法研究

郭文強(qiáng)，肖乾才，李明奇

（1.新疆財(cái)經(jīng)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，新疆 烏魯木齊 830012；2.電子科技大學(xué)；四川 成都 611731）

基于多鏈路權(quán)值減小的動(dòng)態(tài)SPT算法研究

郭文強(qiáng)1，肖乾才2，李明奇2

（1.新疆財(cái)經(jīng)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，新疆 烏魯木齊 830012；2.電子科技大學(xué)；四川 成都 611731）

分支更新的動(dòng)態(tài)最短路徑算法可以有效提高動(dòng)態(tài)最短路徑計(jì)算的效率。通過分析動(dòng)態(tài)最短路徑算法研究的現(xiàn)狀和問題，文章對(duì)Nfixed（v）的定義進(jìn)行了改進(jìn)，解決了原算法中的邊檢查冗余問題，改進(jìn)了MinD和MaxR算法邊檢查步驟，有效地減少了重復(fù)檢查次數(shù)。仿真結(jié)果顯示，改進(jìn)后的算法具有更高的效率。

線性規(guī)劃；網(wǎng)絡(luò)拓?fù)洌宦酚蓞f(xié)議；動(dòng)態(tài)最短路徑算法；動(dòng)態(tài)更新算法

在當(dāng)今的互聯(lián)網(wǎng)中，數(shù)據(jù)報(bào)文由路由器根據(jù)轉(zhuǎn)發(fā)表進(jìn)行轉(zhuǎn)發(fā)。轉(zhuǎn)發(fā)表的構(gòu)建則由路由協(xié)議在網(wǎng)絡(luò)拓?fù)渥兓胶蟾侣酚傻玫?。鏈路狀態(tài)路由協(xié)議通過路由器之間洪泛拓?fù)湫畔⑿纬赏煌負(fù)鋽?shù)據(jù)庫(kù)，之后計(jì)算最短路徑樹進(jìn)而計(jì)算路由，然后將路由下發(fā)形成轉(zhuǎn)發(fā)表，如OSPF[1]（開放最短路徑優(yōu)先）以及IS-IS[2]（中間系統(tǒng)對(duì)中間系統(tǒng)）協(xié)議。

當(dāng)拓?fù)渥兓螅瑯?biāo)準(zhǔn)的最短路徑算法Dijkstra算法[3]無法判斷改變的拓?fù)浣Y(jié)構(gòu)對(duì)已有SPT的作用范圍。只能全部重新計(jì)算。若變化的拓?fù)漭^少，實(shí)際上變化拓?fù)鋵?duì)SPT的影響較小，全拓?fù)溆?jì)算不僅效率低，而且導(dǎo)致路由不穩(wěn)定。這種無法判斷變化拓?fù)鋵?duì)最短路徑樹的影響范圍而只能進(jìn)行全拓?fù)溆?jì)算的最短路徑算法叫作靜態(tài)最短路徑算法。動(dòng)態(tài)最短路徑算法則根據(jù)變化的拓?fù)涓耂PT上受影響的節(jié)點(diǎn)，不受影響的節(jié)點(diǎn)無需更新，從而提高了拓?fù)溆?jì)算的效率與路由的穩(wěn)定性。根據(jù)算法處理變化拓?fù)涞臄?shù)量，動(dòng)態(tài)最短路徑算法可分成兩類：多條邊的權(quán)值發(fā)生改變的邊更新算法；單條邊的權(quán)值發(fā)生改變的點(diǎn)更新算法[4-6]。

McQuillan等[7]最早提出的一個(gè)最短路徑動(dòng)態(tài)更新算法，與P.Narvaez提出的King算法[8]在原理與思想上類似。但是，文獻(xiàn)[8]中的情況僅適用于Dijkstra算法的動(dòng)態(tài)最短路徑問題。而King算法則對(duì)它進(jìn)行了改進(jìn)，使之可應(yīng)用于Bellman-Ford，D’Esopo-Pape，Dijkstra等靜態(tài)算法，是一種通用的最短路徑動(dòng)態(tài)算法的框架。

由于網(wǎng)絡(luò)中邊的權(quán)值增大或減小對(duì)最短路徑樹的產(chǎn)生的影響不同，動(dòng)態(tài)算法將邊權(quán)值的增大和減小采用不同的處理辦法，將只能處理邊權(quán)值增大或者減小一種變化的算法叫作半動(dòng)態(tài)算法，而將可以同時(shí)處理邊權(quán)值增大和減小的算法叫作全動(dòng)態(tài)算法。

將變化的拓?fù)浣Y(jié)構(gòu)分為兩類[9-11]：串行變化拓?fù)浜筒⑿凶兓負(fù)??？梢宰C明并行變化拓?fù)淠軌蛞淮涡愿峦戤叄凶兓負(fù)鋭t存在錯(cuò)誤。同時(shí)不能得到一種有效的方法對(duì)變化邊的串并行關(guān)系進(jìn)行判斷。因此，不能處理拓?fù)浣Y(jié)構(gòu)中多條邊同時(shí)發(fā)送變化的情況。

Xiao[12-13]先后提出了兩個(gè)半動(dòng)態(tài)最短路徑算法。處理邊權(quán)值減小的半動(dòng)態(tài)算法（MinD，MaxR）為分支更新算法，處理邊權(quán)值增大的半動(dòng)態(tài)最短路徑算法為點(diǎn)更新算法。并給出了將處理邊權(quán)值增大的動(dòng)態(tài)最短路徑算法改進(jìn)為分支更新算法的思路。然而，MinD以及MaxR算法中存在錯(cuò)誤以及冗余計(jì)算。本文將對(duì)此進(jìn)行改進(jìn)。

1 多鏈路權(quán)值減小算法改進(jìn)

MinD以及MaxR算法具有相同的算法框架，不同的僅僅是出隊(duì)方式。因此本文的改進(jìn)對(duì)MinD以及MaxR算法均有效。

1.1 Nfixed（v）定義改進(jìn)

在XiaoBin鏈路權(quán)值減小算法中，Nfixed（v）為一節(jié)點(diǎn)集合保證了算法節(jié)點(diǎn)更新范圍的正確性。Nfixed（v）在MinD以及MaxR算法中的定義和用法完全相同。根據(jù)算法對(duì)Nfixed（v）的用法，Nfixed（v）的定義存在錯(cuò)誤。

在原算法中，Nfixed（v）的定義如下所示：對(duì)給定的節(jié)點(diǎn)及其路徑值的增量，首先將其加入Nfixed（v），節(jié)點(diǎn)加入如果滿足下面2個(gè)條件：

（1）P(v')∈Nfixed(v) ；（2）vv′'?MM or v'∈M but M.v'.d1=0 and M.v'.d1≥d

條件1表明等待加入的節(jié)點(diǎn)必須為子節(jié)點(diǎn)；條件2表明其他邊權(quán)值減小，但是增量大于 節(jié)點(diǎn)的增量。按照上面的定義進(jìn)行更新將存在錯(cuò)誤，如圖1所示。

圖1 多鏈路權(quán)值減小

圖1中兩條邊權(quán)值減小，分別是(S,A)和(B,C),初始化后，隊(duì)列M中有兩個(gè)元素{A，(-8,0,0)}以及{C，(0,B,-2)}。首先處理邊{A，(-8,0,0)}，C節(jié)點(diǎn)應(yīng)加入Nfixed(A)，因?yàn)槌跏蓟?B,C),時(shí)，加入隊(duì)列M的元素為{C，(0,B,-2)},而A節(jié)點(diǎn)的更新量為-8，從而C節(jié)點(diǎn)加入Nfixed(A)并將{C，(0,B,-2)}從M中刪除。此時(shí)邊(B,C),的變化將不會(huì)更新SPT。從而，S到C的最短路徑將是S→A→C, 最短路徑的值為8。而路徑S→A→B→C的值為6，存在錯(cuò)誤。出錯(cuò)的原因，為B節(jié)點(diǎn)為A節(jié)點(diǎn)的子節(jié)點(diǎn)，父節(jié)點(diǎn)所進(jìn)行的更新子節(jié)點(diǎn)會(huì)繼承。因此，不能簡(jiǎn)單地刪除(B,C)的變化，提出的改進(jìn)措施是將第2個(gè)條件進(jìn)行修改：

當(dāng)子節(jié)點(diǎn)在M中并且增量大于d時(shí)，且潛在的父節(jié)點(diǎn)為v的子孫節(jié)點(diǎn)時(shí)，將不被加入Nfixed(v)，以免產(chǎn)生錯(cuò)誤的更新。

1.2 邊的改進(jìn)

在XiaoBin算法中，檢查更新節(jié)點(diǎn)是否可更新非Nfixed(v)節(jié)點(diǎn)時(shí)，將邊權(quán)值的變大和減小分開處理，des（v）中的節(jié)點(diǎn)如果不在Nfixed(v)中，則可分為兩種情況：要么在M中，要么不在M中。對(duì)于第二類節(jié)點(diǎn)，可知在算法33行檢查時(shí)，d'≥d恒成立。另一方面之所以此節(jié)點(diǎn)未加入Nfixed(v)，一定是由于其某父節(jié)點(diǎn)的增量小于d。且因?yàn)槔^承關(guān)系，此種類型的節(jié)點(diǎn)被加入隊(duì)列M后還沒有更新SPT就被刪除，即此加入操作為無效的。此種類型的情況如圖2所示。

圖2 節(jié)點(diǎn)檢查

由圖2可見，在進(jìn)行初始化之后，M={{B，(-5,0,0)}，{D，（0,C,-6)}}。算法第2步取出{B，(-5,0,0)},由于-6＜-5，節(jié)點(diǎn)Ev′?MNfixed(B),Nfixed(B)={B}。從而在邊檢查時(shí)，將加入{E，(0,B,-4)}。而在取出{D，(0,C,-6)}更新時(shí)將刪除{E，(0,B,-4)},從而在{E，(0,B,-4)}中加入操作、刪除操作以及維護(hù)操作均是無效的。因此，將邊檢查的范圍改為：

這樣可減小一部分無效的入隊(duì)出隊(duì)操作。

2 仿真驗(yàn)證

本文仿真將比較改進(jìn)后的MinD算法以及Dijkstra算法以驗(yàn)證改進(jìn)算法的準(zhǔn)確性。

2.1 拓?fù)浣Y(jié)構(gòu)的產(chǎn)生

初始拓?fù)浣Y(jié)構(gòu)由Inet3.0軟件[14]構(gòu)成，Inet軟件生成的拓?fù)浣Y(jié)構(gòu)不僅可以保證連通性，還符合Internet經(jīng)過驗(yàn)證的冪律特性。Inet 3.0產(chǎn)生的拓?fù)浣Y(jié)構(gòu)由點(diǎn)和邊構(gòu)成。全部節(jié)點(diǎn)均分布在長(zhǎng)和寬均為10 000的平面內(nèi)，初始的隨機(jī)種子數(shù)為0。最后得到節(jié)點(diǎn)數(shù)為5 000，無向邊為8 901（有向邊17 802）的拓?fù)浣Y(jié)構(gòu)。由于產(chǎn)生的拓?fù)浣Y(jié)構(gòu)比較復(fù)雜，在本文中此拓?fù)浣Y(jié)構(gòu)將不以圖形的方式展現(xiàn)出來。

2.2 事件的產(chǎn)生

變化的拓?fù)浣Y(jié)構(gòu)由系統(tǒng)的隨機(jī)接口函數(shù)來實(shí)現(xiàn)。由于拓?fù)渥兓梢暈檫厵?quán)值的變化，因此文中的拓?fù)渥兓眠厵?quán)值的變化代替。用Inet 3.0生成的邊的順序進(jìn)行編號(hào)，用隨機(jī)數(shù)對(duì)邊拓?fù)淝笥?，以確定變化拓?fù)涞捻樞蚓幪?hào)。Inet 3.0構(gòu)成的邊拓?fù)錄]有方向，所以使用隨機(jī)數(shù)十位上的奇偶性確定邊的方向。十位數(shù)為奇數(shù)時(shí)，邊的方向即為邊拓?fù)渥陨淼姆较颍駝t，則相反。拓?fù)渥兓姆较蚣礄?quán)值增大或是減小通過隨機(jī)數(shù)的奇偶性確定，為奇數(shù)時(shí)，則邊權(quán)值變大，為偶數(shù)時(shí)，則邊權(quán)值變小。由于隨機(jī)數(shù)的個(gè)位數(shù)和十位數(shù)相互獨(dú)立，保證了變化拓?fù)浞较蚺c拓?fù)渥兓较虻莫?dú)立性。拓?fù)渥兓偭縿t用另一個(gè)隨機(jī)數(shù)確定。邊權(quán)值的變化量則用邊拓?fù)渥陨淼臋?quán)值為上界，以保證拓?fù)渥兓笃錂?quán)值為非負(fù)的性質(zhì)。

2.3 仿真結(jié)果

根據(jù)生成的拓?fù)浼白兓負(fù)?，由Dijkstra算法與改進(jìn)后的算法比較以驗(yàn)證改進(jìn)算法的正確性；比較邊檢查改進(jìn)前后算法的入隊(duì)次數(shù)情況。結(jié)果如表1所示。

表1 仿真結(jié)果

與Dijkstra算法的比較結(jié)果未在表中給出，根據(jù)比較結(jié)果，改進(jìn)后算法是正確的。從表1的實(shí)驗(yàn)統(tǒng)計(jì)數(shù)據(jù)可知邊檢查的改進(jìn)減小了節(jié)點(diǎn)入隊(duì)的次數(shù)。

3 結(jié)語

本文糾正了XiaoBin多鏈路權(quán)值減小的分支更新動(dòng)態(tài)最短路徑算法中Nfixed（v）的定義錯(cuò)誤，改進(jìn)了其邊檢查的方式。仿真結(jié)果表明，改進(jìn)的算法具有正確性，并降低了隊(duì)列維護(hù)的冗余計(jì)算。

[1]MOY J. RFC2328: OSPF Version 2[EB/OL].（1998-04-23）[2016-11-22].http://www. ietf. org / rfc/ rfc2328.txt, April 1998.

[2]DAVID O. RFC1142: OSI IS-IS intra-domain routing protocol[EB/OL].（1990-02-11）[2016-11-22].http://datatracker.ietf.org/doc/rfc1142/. [3]EDSGER W D. A note on two problems in connection with graphs[J]. Numerical Math, 1959（1）：269-271.

[4]REINHARD B, DOROTHEA W. Batch dynamic single-source shortest-path algorithms: an experimental study[C].SEA’09 Proceedings of the 8th International Symposium on Experimental Algorithms, Heidelberg：Springer-Verlag, 2009：51-62.

[5]RICHARD B. On A routing problem[J]. Quarterly of Applied Mathematics, 1958（1）：87-90.

[6]KNUTH D E. A generalization of Dijkstra’salgorithm[J]. Information Processing Letters, 1977（1）：1-5.

[7]MCQUILLAN J M, RICHER I, ROSE E C. The new routing algorithm for the Arpanet[J]. IEEE Transactions on Communication, 1980（5）：711-719.

[8]NARVAEZ P, SIU K Y, TZENG H Y. New dynamic algorithms for shortest path tree computation[J]. Transactions on Networking, 2000（6）：734-746.

[9]NARVAEZ P, SIU K Y, TZENG H Y. New dynamic algorithms based on a ball-and-string model[J]. Transactions on Networking, 2001（6）：706-718.

[10]PAOLO G F, DANIELE F, ROBERTO G. Semi-dynamic shortest paths and breadth-first search in digraph[J].Theoretical Aspects of Computer Science, 1997（1200）：33-46.

[11]DANIELE F, MARCHETTI S, NANNI U. Fully dynamic output bounded single source path problem[J]. Algorithms, 2000（2）：251-281.

[12]XIAO BIN, CAO JIANGNONG, ZHUGE QINGFENG, et al. Shortest path tree update for multiple link state decrements[C]. Globecom’04 dallastexas IEEE, 2004：1163-1167.

[13]XIAO BIN, CAO JIANGNONG, SHAO ZILI, et.al. An efficient algorithm for dynamic shortest path tree update in network routing[J]. Journal of Communication and Networks, 2007（4）：409-510.

[14]WINICK J, JAMIN S. Inet-3.0：Internet topology generator[EB/OL].（2002-10-15）[2016-12-10]http：//www.ssat-inet.net/, UM-CSETR- 456-02, 2002.

Study of dynamic SPT algorithm for multi-link decrement

Guo Wenqiang1, Xiao Qiancai2, Li Mingqi2
（1.Computer Science and Engineering College of Xinjiang University of Finance , Urumqi 830012, China; 2.University of Electronic Science and Technology of China, Chengdu 611731, China）

Batch updating algorithms for dynamic shortest path can effectively improve the computing efficiency of shortest path. Through analyzing the current situation and problems of the shortest path algorithm of dynamic, the article improved the definition of Nfixed (V) to solve the edge check redundancy in the original algorithm, and improved MinD algorithm and MaxR edge inspection steps, effectively reduced the times of repeated inspections. The simulation results show that the improved algorithm has higher efficiency.

linear programming; network topology; routing protocols; dynamic shortest path algorithm; dynamic updating algorithm

國(guó)家自然科學(xué)基金項(xiàng)目；項(xiàng)目編號(hào)：61163066，60902074。新疆自然科學(xué)基金項(xiàng)目；項(xiàng)目編號(hào)：2013211A032。

郭文強(qiáng)（1975— ），男，吉林安圖，博士，教授；研究方向：信息安全，信號(hào)與信息處理。