徐 方

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

0 引 言

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

為了解決上述問(wèn)題，可以使用動(dòng)態(tài)路由算法來(lái)計(jì)算最短路徑.目前有很多研究者正在研究動(dòng)態(tài)路由算法，其中動(dòng)態(tài)Dijkstra算法［4］和可靠的動(dòng)態(tài)最短路徑（Reliability of Dynamic Shortest Path，以下簡(jiǎn)稱(chēng)：RDSP）［5］算法是動(dòng)態(tài)路由算法的典型代表.與靜態(tài)路由算法相比，動(dòng)態(tài)路由算法可能在某一個(gè)節(jié)點(diǎn)上需要更多的計(jì)算時(shí)間，然而，動(dòng)態(tài)路由算法可能會(huì)減少總的計(jì)算時(shí)間，因?yàn)樗梢詼p少計(jì)算的節(jié)點(diǎn)的數(shù)目.也就是說(shuō)，當(dāng)一個(gè)網(wǎng)絡(luò)中一些鏈接有新的權(quán)重時(shí)，動(dòng)態(tài)路由算法利用變化的鏈路找到受影響的節(jié)點(diǎn)，只需要重新計(jì)算這些受影響節(jié)點(diǎn)的最短路徑.因此，動(dòng)態(tài)路由算法可以比靜態(tài)路由算法需要更少的時(shí)間來(lái)計(jì)算最短路徑.然而，動(dòng)態(tài)的路由算法所需要的計(jì)算時(shí)間依賴(lài)于權(quán)重變化鏈路在網(wǎng)絡(luò)中的位置.

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

1 問(wèn)題的提出

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

Dijkstra算法是一個(gè)靜態(tài)的路由算法，被廣泛用于在網(wǎng)絡(luò)路由中.然而，這個(gè)被充分研究的靜態(tài)路由算法在某些場(chǎng)合下也是低效率的，比如在網(wǎng)絡(luò)中只有一小部分的鏈路狀態(tài)發(fā)生變化而需要更新時(shí).這是因?yàn)榇藭r(shí)，該算法會(huì)在所有節(jié)點(diǎn)上重新計(jì)算新的最短路徑，而不再利用原來(lái)的最短路徑信息.這一過(guò)程對(duì)于一個(gè)路由器來(lái)說(shuō)影響是非常大的，因?yàn)樗枰加么罅康腃PU資源.并且這個(gè)過(guò)程使用Dijkstra算法計(jì)算最短路徑需要一個(gè)較長(zhǎng)的時(shí)間，同時(shí)存在一個(gè)路由不穩(wěn)定的時(shí)間段.在該時(shí)間段內(nèi)，路由表不能真實(shí)反映實(shí)際的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，直到算法運(yùn)行完成才能得到真實(shí)的網(wǎng)絡(luò)拓?fù)洌谶@個(gè)時(shí)間段內(nèi)網(wǎng)絡(luò)就可能會(huì)出現(xiàn)丟包的現(xiàn)象［7］.

動(dòng)態(tài)路由算法優(yōu)于靜態(tài)路由算法，它通過(guò)利用大部分原有路由表中的信息，只需要重新計(jì)算受影響節(jié)點(diǎn)的最短路徑并更新路由表，因此它們可以減少計(jì)算時(shí)間.然而，動(dòng)態(tài)路由算法所需要的計(jì)算時(shí)間取決于變化的鏈路的位置.也就是說(shuō)，當(dāng)根節(jié)點(diǎn)附近有一些鏈路的權(quán)重有變化時(shí)，路由的收斂需要較長(zhǎng)的時(shí)間，這是因?yàn)榇藭r(shí)大量的節(jié)點(diǎn)會(huì)受到影響而不得不重新計(jì)算最短路徑.相反，如果在終端節(jié)點(diǎn)附近的一些鏈接有一個(gè)新的權(quán)重，計(jì)算時(shí)間則是較短的，因?yàn)榇藭r(shí)只有較少節(jié)點(diǎn)受影響.因此，動(dòng)態(tài)路由算法在計(jì)算時(shí)間上并不是一定優(yōu)于靜態(tài)路由算法，因?yàn)樗艿缴鲜鲆蛩氐挠绊?，這是網(wǎng)絡(luò)路由中的一個(gè)不確定性問(wèn)題.

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

2 多徑混合路由算法

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

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

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

3 性能分析

為了研究本文提出的路由算法MHSPT的性能，使用C＋＋語(yǔ)言編寫(xiě)了相應(yīng)的算法的仿真程序，將本文提出的MHSPT算法性能與Dijkstra、動(dòng)態(tài)Dijkstra（D－Dijkstra）和HSPT算法的性能進(jìn)行了比較.在仿真實(shí)驗(yàn)中，使用如表1所示的輸入?yún)?shù)：節(jié)點(diǎn)的數(shù)量、鏈路權(quán)重的變化率、鏈路權(quán)重的偏差.

表1 實(shí)驗(yàn)輸入?yún)?shù)Table 1 Input parameters in experiment

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

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

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

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

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

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

4 結(jié) 語(yǔ)

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

［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］劉代波，侯孟書(shū)，武澤旭，等.一種高效的最短路徑樹(shù)動(dòng)態(tài)更新算法［J］.計(jì)算機(jī)科學(xué)，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é)議的快速動(dòng)態(tài)路由算法研究［J］.重慶科技學(xué)院學(xué)報(bào)，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.