多路由配置中備份拓撲存在的不足與改進算法研究

楊栩灼

摘要：本文介紹了多路由在配置中，由于備份拓樸數增加的時候會使得可用鏈路的增加，導致路由內存被占用過大的問題，提出改進關鍵節點的算法，減少路由跳數，起到優化的作用。通過對算法的綜合評估認為改進后的算法具有可行性。

關鍵詞：多路由配置；創建備份拓樸；改進算法

中圖分類號：G424 文獻標識碼：A 文章編號：1009-3044（2018）06-0049-02

1多路由配置中備份拓撲存在的不足

因為多路由配置方法在現實使用過程中，假如傳輸的數據包沒有通過故障鏈路，那么當其在故障狀態下傳輸的數據包時其路由跳數是沒有變化的。但是當相關數據傳輸過程中需要經過故障鏈路時，這時的路由跳數就會出現增加的現象。由于路由跳數的不斷增加會使得流量加大、信道容易出現阻塞，相關數據報文也會出現延遲的現象。所以，一定需要想辦法減少路由跳數的增加。此外，在具體的備份拓撲過程中，有一部分鏈路是受到相應的保護，因此，對于備份路由過程可用的鏈接數相對較少，這樣會使得在恢復過程出現了有限可用鏈路的共享現象，很容易出現鏈路的超載。事實上，超載的鏈路是容易出現網絡負荷的一個重要因素，同時也會降低用戶體驗。假如在增加備份拓撲的相關數目時，那么備份拓撲過程中，就會使得受保護的鏈路出現下降。這個時候，備份拓撲數的不斷增加就會使得可用鏈路也會隨之增加，那么路由的內存不斷上升。因此，需要對原有方法進行優化。

2改進多路由配置中備份拓撲的算法

2.1關鍵節點的選取

在路由過程中備份拓撲鏈路的保護算法基本步驟：首先需要與關鍵點建立起相連的路徑，并對其進行保護處理；其次是需要與普通節點相連的路徑建立起保護的過程。當鏈路進行保護之后，需要對已生成的備份拓撲能否滿足已有的拓撲創建規則，假如可以滿足規則那么就繼續進行，否則，程序就需要終止這個過程。這個算法的目的就是為了進一步增加關鍵節點的可用鏈路，從而可以更好地減少因選擇最短路徑而出現的跳數。

對于關鍵節點方面的選取，通常用兩種方法。第一種方法就是選取出Top K個屬于高介數值的節點位置（也即是Top K方法）。第二種方法就是通過使用一樣的方法來選取Top K個節點，但是有必要考慮到節點的具體位置信息（也即是Non-adja-cent K方法），一般來說，如果選擇出的某一個關鍵節點能夠與現有關鍵節點相連接，那么就會放棄這個節點，再繼續去尋找下一個更合適的點作為最新的關鍵節點。

2.2算法流程

說明：算法中的輸入變量等于關鍵節點個數K，其中輸出變量等于備份拓撲個數N。同時定義N等于1，算法總共由五個步驟組成，具體執行算法如下：

第一步：按照所定義好的關鍵點選取方法來對相關鍵節點的選取。

第二步：需要選取第K個關鍵節點，通常來說有這樣的兩種選取方法。

1）應用Top K選擇方法：根據介數值的高低來對相關節點執行降序的排列，同時還需要選取前K個節點來作為具體的關鍵節點。

2）應用Non-adjacent K選擇方法：這個關鍵節點不但擁有較大的介數值，并且有必要考慮關鍵節點在具體組網中體現的位置信息。假若關鍵節點是屬于相鄰的，那么其最大化可用的鏈路就會出現減少的可能。所以，假如當前所選的關鍵節點與之前所選取的關鍵節點是屬于相鄰的，那么就需要跳過當前的節點，此時就會選擇下一個節點作當前的關鍵節點。

第三步：有必要與關鍵節點建立起具體的鏈路保護過程。使得能夠與特定關鍵節點形成鏈路，以此來更好地保證各個備份拓撲中都可以通過最小的受保護鏈路數，具體如圖1所示，從而可以達到保證各個關鍵節點在每個拓撲中都可以形成更多的可用鏈路。

這里將關鍵節點中保護鏈路在各個備份拓撲中占有的數量視為M，并將關鍵節點所擁有的最大出入度視為D，那么M>=ceil（D/N）+1。具體如圖1所示，當出現的最大備份拓撲數是3時，以及關鍵節點為6時，其最大的出人度就等于3，那么各個備份拓撲中所受到保護的鏈路數最小值就等于1。

第四步：執行與之有關的普通節點的鏈路保護過程，并對各個鏈路實現保護。

第五步：判斷最新生成的備份拓撲能否符合相關規則。如果能夠滿足，那么這次運行過程就結束。否則，就需要對N進行累加1，接著執行第一步。算法基本流程見圖2。

2.3算法的實現

3改進算法后綜合評估

事實上，關鍵節點在網絡結構中選擇是非常重要的，同時需要將關鍵節點的概念與備份拓撲結合起來。當在備份拓撲創建的最初階段，需要通過關鍵節點評估的方法來選出具體的數目節點來作為最關鍵的節點，其他的節點視為普通節點。這個算法按照關鍵節點的出入度以及備份拓撲數的最大化關鍵節點來產生有關的鏈路等。為了可以更好準確的評估新的算法，這里提出了應用基于緊密度與介數值的綜合評價方法：D（i）=C（i）B（i）。式中的D（i）是作為節點i的關鍵度，c（i）是作為節點i處于網絡中心的程度，B（i）是指節點i對于鄰節點所體現的重要程度。

對于關鍵節點的選取時，主要是將D（i）值高的節點根據順序來作為關鍵節點。之后再應用Top K方法和Non-adjacent K方法來增加相關鍵節點的可用鏈路，以此來減少重路由所出現的跳數，從而達到優化算法的過程，改進后的算法具有可行性。

4結論

綜上所述，本算法的重點是對關鍵節點的合理選取，關鍵節點的數目和關鍵節點的具體位置對于實驗結果都會產生不同的影響，因此，需要做到在保障網絡正常連通的情況下，選取合適的關鍵節點數目。通過對改進后的算法進行評估，認為改進后的算法具有可行性。