校園網多徑混合路由算法

徐 方

（湖北工程學院現(xiàn)代教育技術中心，湖北 孝感 432000）

0 引 言

隨著校園網應用的不斷深入，校園網中不僅有傳統(tǒng)的網絡（WEB）服務、文件傳輸協(xié)議（File Transfer Protlcol，以下簡稱：FTP）服務、域名解析系統(tǒng)（Donain Name System，以下簡稱：DNS）服務、E－Mail服務等，而且大量的新型的網絡應用也不斷增加，如遠程教學、網絡課程、視頻點播以及迅速增長的對等網絡（Peer－to－Peer，以下簡稱：P2P）應用，這些使得校園網絡內承載了大量的視頻和語音的流量.這些應用對網絡的性能提出了更高的要求，特別是對路由協(xié)議的收斂時間.開放最短路徑優(yōu)先協(xié)議 （Open Shortest Path First，以下簡稱：OSPF）是一種基于區(qū)域實現(xiàn)的、建立在鏈路狀態(tài)（Link State）算法和最短路徑優(yōu)先（Shortest Path First，以下簡稱：SPF）算法基礎之上的內部網關動態(tài)路由協(xié)議［1］，也是校園網內應用最廣泛的協(xié)議.開放最短路徑優(yōu)先協(xié)議是最常用的自治系統(tǒng)內部的路由協(xié)議，如何在其中設計高速的路由算法就顯得更加重要.在使用OSPF協(xié)議的網絡中，當遇到突發(fā)事件網絡的拓撲發(fā)生變化時，網絡路由算法就開始重新計算并更新路由表.例如，如果網絡中有一個鏈路發(fā)生了故障，則路由協(xié)議會重新計算最短路徑.在這種情況下，傳統(tǒng)的OSPF使用迪杰斯特拉（Dijkstra）算法進行最短路徑的計算［2］.然而，當網絡中鏈路的權重有新的變化時，網絡會使用Dijkstra算法在每個節(jié)點上進行重復的大量計算和不必要的修正，而不關注鏈路權重的變化在網絡中發(fā)生的位置.因此，這可能會導致整個路由表頻繁更新，從而使網絡變得不穩(wěn)定［3］.

為了解決上述問題，可以使用動態(tài)路由算法來計算最短路徑.目前有很多研究者正在研究動態(tài)路由算法，其中動態(tài)Dijkstra算法［4］和可靠的動態(tài)最短路徑（Reliability of Dynamic Shortest Path，以下簡稱：RDSP）［5］算法是動態(tài)路由算法的典型代表.與靜態(tài)路由算法相比，動態(tài)路由算法可能在某一個節(jié)點上需要更多的計算時間，然而，動態(tài)路由算法可能會減少總的計算時間，因為它可以減少計算的節(jié)點的數目.也就是說，當一個網絡中一些鏈接有新的權重時，動態(tài)路由算法利用變化的鏈路找到受影響的節(jié)點，只需要重新計算這些受影響節(jié)點的最短路徑.因此，動態(tài)路由算法可以比靜態(tài)路由算法需要更少的時間來計算最短路徑.然而，動態(tài)的路由算法所需要的計算時間依賴于權重變化鏈路在網絡中的位置.

混合式路由算法可以結合動態(tài)路由算法和靜態(tài)路由算法的優(yōu)點，它的路由收斂的計算時間會更少.目前有些研究者提出了混合式路由的想法，使用混合最短路徑樹（Hybrid Shortest Path Tree，以下簡稱：HSPT）［2］可以有效地計算最短路徑，其中靜態(tài)和動態(tài)的算法運行的次數是非常關鍵的因素.本文提出了一種多徑混合路由算法，當一些鏈路的權重發(fā)生變化時，它使用多徑信息來創(chuàng)建最短路徑，如果找不到多條路徑，則使用混合路由算法計算最短路徑.為了評價所提出的算法，將其與靜態(tài)的Dijkstra、動態(tài)Dijkstra算法和HSPT算法進行了比較.

1 問題的提出

網絡路由的收斂是指在最佳路徑的判斷上所有路由器達成一致的過程.當出現(xiàn)某些網絡事件引起路由發(fā)生故障或不可達時，路由器就會發(fā)出路由更新的消息.遍及整個網絡的路由更新會引發(fā)路由器重新計算最佳路徑，所有的路由器最終形成一個公認的最佳路徑［6］.然而，網絡中鏈路狀態(tài)的變化會導致每個路由器重新計算自己的最短生成樹（Shortest Path Tree，以下簡稱：SPT）并完全更新相應設備的路由表.但是研究發(fā)現(xiàn)，在很多情況下，舊的SPT和新的SPT幾乎沒有什么變化.這種現(xiàn)象的出現(xiàn)，主要原因是在較大范圍的路由區(qū)域內，少數幾條鏈路狀態(tài)的變化對SPT的生成影響不大.所以，研究一種新的動態(tài)更新SPT的算法來處理網絡鏈路的變化是很有必要的.

Dijkstra算法是一個靜態(tài)的路由算法，被廣泛用于在網絡路由中.然而，這個被充分研究的靜態(tài)路由算法在某些場合下也是低效率的，比如在網絡中只有一小部分的鏈路狀態(tài)發(fā)生變化而需要更新時.這是因為此時，該算法會在所有節(jié)點上重新計算新的最短路徑，而不再利用原來的最短路徑信息.這一過程對于一個路由器來說影響是非常大的，因為它需要占用大量的CPU資源.并且這個過程使用Dijkstra算法計算最短路徑需要一個較長的時間，同時存在一個路由不穩(wěn)定的時間段.在該時間段內，路由表不能真實反映實際的網絡拓撲結構，直到算法運行完成才能得到真實的網絡拓撲，在這個時間段內網絡就可能會出現(xiàn)丟包的現(xiàn)象［7］.

動態(tài)路由算法優(yōu)于靜態(tài)路由算法，它通過利用大部分原有路由表中的信息，只需要重新計算受影響節(jié)點的最短路徑并更新路由表，因此它們可以減少計算時間.然而，動態(tài)路由算法所需要的計算時間取決于變化的鏈路的位置.也就是說，當根節(jié)點附近有一些鏈路的權重有變化時，路由的收斂需要較長的時間，這是因為此時大量的節(jié)點會受到影響而不得不重新計算最短路徑.相反，如果在終端節(jié)點附近的一些鏈接有一個新的權重，計算時間則是較短的，因為此時只有較少節(jié)點受影響.因此，動態(tài)路由算法在計算時間上并不是一定優(yōu)于靜態(tài)路由算法，因為它受到上述因素的影響，這是網絡路由中的一個不確定性問題.

目前一些研究者提出了混合路由算法的思想，它結合了靜態(tài)路由算法和動態(tài)路由算法的優(yōu)點.混合路由算法比靜態(tài)或者動態(tài)的算法更高效.但是，如果混合路由算法使用多徑信息，它的性能會提高很多.也就是說，多徑混合路由算法比混合路由算法具有更少的計算時間.

2 多徑混合路由算法

本文提出的多徑混合路由算法利用多徑信息減少了總的最短路徑樹的執(zhí)行時間.該算法被稱為多路徑混合的最短路徑樹（Multi－path Hybrid Shortest Path Tree，MHSPT），是在 HSPT算法的基礎上提出來的.為了使HSPT有效地計算最短路徑，應用靜態(tài)算法和動態(tài)算法運行的次數是關鍵的因素.當根節(jié)點附近的鏈路的權重變化時，網絡中受影響的節(jié)點數目會很大，適合使用靜態(tài)路由算法來計算最短路徑.此時動態(tài)路由算法不存在優(yōu)勢，因為此時根節(jié)點附近的很多節(jié)點都要重新計算路由.在這種情況下，靜態(tài)路由算法是一個快速的計算方法.如果此時使用動態(tài)路由算法，每個節(jié)點計算最短路徑就需要更多的計算時間，從而增加了總的計算時間.然而，當終端節(jié)點附近的鏈路權重變化時，適合使用動態(tài)路由算法來計算最短路徑.動態(tài)路由算法適合于這種場合是因為此時終端節(jié)點附近只有少量的節(jié)點需要重新計算路徑.在這種情況下，使用動態(tài)路由算法僅僅需要重新計算被影響的少數節(jié)點的最短路徑信息，而不需要像靜態(tài)路由算法那樣需要計算所有節(jié)點最短路徑信息，所以此時動態(tài)路由算法收斂快于靜態(tài)路由算法.此外，MHSPT使用了多徑信息，多徑信息的獲取方法參照文獻［8］.如果其他的最小權重路徑被發(fā)現(xiàn)，該算法使用多路徑信息，可以減少計算時間.如果其他的最低成本的路徑都沒有找到，該算法可以使用的多徑信息減少的受影響的節(jié)點數目.MHSPT算法的偽代碼如圖1所示.

多路徑混合路由算法分為如下步驟進行.首先，使用多徑信息找出最短路徑.如果發(fā)現(xiàn)了一個最短路徑，就把它歸入最短路徑樹中；如果沒有找到多路徑，就開始啟用混合路由算法.第二步，為了決定使用哪一種路由算法，需要使用深度優(yōu)先搜索（DFS）來計算整個網絡的深度.第三步，當某條鏈路的權重發(fā)生變化，并且發(fā)現(xiàn)它在網絡中的深度小于40%時，就使用靜態(tài)路由算法來計算最短路徑.當變化權重的鏈路的深度大于等于40%時，使用動態(tài)路由算法來計算最短路徑.

圖1 MHSPT算法的偽代碼Fig.1 Pseudo code for the MHSPT

3 性能分析

為了研究本文提出的路由算法MHSPT的性能，使用C＋＋語言編寫了相應的算法的仿真程序，將本文提出的MHSPT算法性能與Dijkstra、動態(tài)Dijkstra（D－Dijkstra）和HSPT算法的性能進行了比較.在仿真實驗中，使用如表1所示的輸入參數：節(jié)點的數量、鏈路權重的變化率、鏈路權重的偏差.

表1 實驗輸入參數Table 1 Input parameters in experiment

節(jié)點的數目表示在整個網絡中的節(jié)點的數目，節(jié)點數從60到360能充分表達節(jié)點規(guī)模從小到大時路由協(xié)議的性能.鏈路權重的變化率是新鏈路權重與舊鏈路權重的比值，根據網絡中鏈路的實際變化率統(tǒng)計，100%和300%是比較常見的情況.在本實驗中，鏈路權重平均值設為12.鏈路權重的偏差是當前鏈路權重與鏈路權重平均值之間的差異，在此選擇的偏差值為6和18，分別在平均值的之下和之上，與平均值的距離相等，也比較符合網絡中的實際情況.在相同環(huán)境的網絡中，使用上述幾種算法計算最短路徑，然后把各種算法所需要的總的計算時間進行比較.

圖2表明了上述4種路由算法隨著節(jié)點數量和鏈路權重變化率的變化計算最短路由總計算時間變化的情況.在圖2（a）中鏈路權重的變化率為100%，圖2（b）中鏈路權重的變化率是300%.隨著節(jié)點數量的增加，計算最短路徑的時間會隨之增加.從圖2（a）可以看出：當節(jié)點規(guī)模增加時MHSPT計算最短路徑樹的時間接近于HSPT.同樣在圖2（b）中也可以看到類似的情況.如果鏈路權重變化率較低，計算最短路徑的時間會呈線性增長.當鏈路權重的變化率較高時，MHSPT算法的性能表現(xiàn)會更好.

圖2 總的計算時間隨著節(jié)點數量和鏈路權重變化率的變化情況Fig.2 Total computation time with change of the number of nodes and the changed rate of link weights

圖3是上述4種不同路由算法隨著節(jié)點數量和鏈路權重偏差的變化計算最短路由總計算時間變化的情況，圖3（a）中鏈路權重的偏差是6，圖3（b）中鏈路權重偏差是18；鏈路權重偏差的平均值是12.從圖3中可以看出隨著節(jié)點的數量的增加和鏈路權重偏差的變化，MHSPT的性能優(yōu)于Dijkstra、D－Dijkstra和 HSPT算法.

圖3 總的計算時間隨著節(jié)點的數量和鏈路權重偏差變化的情況Fig.3 Total computation time with change of the number of nodes and deviation of link weights

從圖3可以看出：當節(jié)點規(guī)模不斷增大時，MHSPT算法中最小生成樹的計算時間小于其它3種算法，具有明顯的優(yōu)勢；隨著節(jié)點鏈路權重偏差的增加，MHSPT計算最短路徑的總時間有所增加，但也同樣少于其它算法.上述實驗結果表明，無論是從節(jié)點規(guī)模變化、鏈路權重變化率的變化，還是鏈路權重偏差的變化等方面比較，MHSPT算法都優(yōu)于目前其它先進的算法.

4 結 語

由于教育信息化的不斷深入發(fā)展，校園網上的應用系統(tǒng)越來越豐富，校園網承載的業(yè)務量也越來越大.此外，大量的實時業(yè)務對網絡的服務質量提出了更高的要求.因此，非常有必要在校園網絡路由協(xié)議中尋求一種快速生成最小生成樹和最短路徑的方法.本文結合靜態(tài)路由算法和動態(tài)路由算法的優(yōu)點，并利用多徑信息提出了一種混合路由算法.對比實驗表明，該算法降低了最短路徑的計算時間，加快了網絡的收斂過程.然而，本算法也存在一些不足的方面，如算法在節(jié)點上的計算復雜性可能會高于上述其它算法，這可能會增加網絡節(jié)點負載和能耗，不過這一點對于以有線網絡為主的校園網來說影響并不大.下一步的研究工作是將本文提出的算法與實際校園網絡緊密結合，進一步對所提出的算法進行完善.

［1］Wang F Y，Wu S F.On the vulnerabilities and protection of OSPF routing protocol ［C］／／Proceedings of the International Conference on Computer Communications and Networks，Washington，DC，USA：IEEE Computer Society，1998：148－152.

［2］Calduwel Newton P，Arockiam L，Kim T H.An Efficient Hybrid Path Selection Algorithm for an Integrated Network Environment［J］.International Journal of Database Theory and Application，2009，2（1）：31－38.

［3］Ameen，S Y ，Ibrahimi I A .MANET Routing Protocols Performance Evaluation with TCP Taho，Reno and New－Reno［J］.International Journal of u－and e－Service，Science and Technology，2011，4（1）：37－49.

［4］劉代波，侯孟書，武澤旭，等.一種高效的最短路徑樹動態(tài)更新算法［J］.計算機科學，2011，38（7）：96－99.Dai－Bo Liu，Meng－Shu Hou，Ze－Xu WU，et al.Efficient Dynamic Algorithm for Computation of Shortest Path Tree［J］.Computer Science，2011，38（7）：96－99.（in Chinese）

［5］Cho T H，Kim J W，Kim B J，et al.A Study on Shortest Path Decision Algorithm for Improving the Reliability of Dynamic Routing Algorithm ［J］.Journal of the Korean Institute of Information Scientists and Engineers，2011，38：450－459.

［6］余雪勇，卞乃猛，唐家益，等.基于OSPF協(xié)議的快速動態(tài)路由算法研究［J］.重慶科技學院學報，2008，10（3）：74－77.YU Xue－yong，BIAN Nai－meng，TANG Jia－yi，et al.Research on the Algorithm of Fast Dynamic Routing Based on OSPF［J］.Journal of Chongqing University of Science and Technology：Natural Sciences Edition，2008，10（3）：74－77.（in Chinese）

［7］Jedari B，Goudarzi R，Dehghan M.Efficient Routing using Partitive Clustering Algorithms in Ferry－based Delay Tolerant Networks［J］.International Journal of Future Generation Communication and Networking，2009，2（4）：1－14.

［8］Eramo V，Listanti M，Cianfrani A.Design and Evaluation of a New Multi－Path Incremental Routing Algorithm on Software Routers［J］.IEEE Transactions on Network and service management，2008，5（4）：188－203.