多路由配置中備份拓?fù)浯嬖诘牟蛔闩c改進(jìn)算法研究

楊栩灼

摘要：本文介紹了多路由在配置中，由于備份拓樸數(shù)增加的時(shí)候會(huì)使得可用鏈路的增加，導(dǎo)致路由內(nèi)存被占用過大的問題，提出改進(jìn)關(guān)鍵節(jié)點(diǎn)的算法，減少路由跳數(shù)，起到優(yōu)化的作用。通過對(duì)算法的綜合評(píng)估認(rèn)為改進(jìn)后的算法具有可行性。

關(guān)鍵詞：多路由配置；創(chuàng)建備份拓樸；改進(jìn)算法

中圖分類號(hào)：G424 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）06-0049-02

1多路由配置中備份拓?fù)浯嬖诘牟蛔?/p>

因?yàn)槎嗦酚膳渲梅椒ㄔ诂F(xiàn)實(shí)使用過程中，假如傳輸?shù)臄?shù)據(jù)包沒有通過故障鏈路，那么當(dāng)其在故障狀態(tài)下傳輸?shù)臄?shù)據(jù)包時(shí)其路由跳數(shù)是沒有變化的。但是當(dāng)相關(guān)數(shù)據(jù)傳輸過程中需要經(jīng)過故障鏈路時(shí)，這時(shí)的路由跳數(shù)就會(huì)出現(xiàn)增加的現(xiàn)象。由于路由跳數(shù)的不斷增加會(huì)使得流量加大、信道容易出現(xiàn)阻塞，相關(guān)數(shù)據(jù)報(bào)文也會(huì)出現(xiàn)延遲的現(xiàn)象。所以，一定需要想辦法減少路由跳數(shù)的增加。此外，在具體的備份拓?fù)溥^程中，有一部分鏈路是受到相應(yīng)的保護(hù)，因此，對(duì)于備份路由過程可用的鏈接數(shù)相對(duì)較少，這樣會(huì)使得在恢復(fù)過程出現(xiàn)了有限可用鏈路的共享現(xiàn)象，很容易出現(xiàn)鏈路的超載。事實(shí)上，超載的鏈路是容易出現(xiàn)網(wǎng)絡(luò)負(fù)荷的一個(gè)重要因素，同時(shí)也會(huì)降低用戶體驗(yàn)。假如在增加備份拓?fù)涞南嚓P(guān)數(shù)目時(shí)，那么備份拓?fù)溥^程中，就會(huì)使得受保護(hù)的鏈路出現(xiàn)下降。這個(gè)時(shí)候，備份拓?fù)鋽?shù)的不斷增加就會(huì)使得可用鏈路也會(huì)隨之增加，那么路由的內(nèi)存不斷上升。因此，需要對(duì)原有方法進(jìn)行優(yōu)化。

2改進(jìn)多路由配置中備份拓?fù)涞乃惴?/p>

2.1關(guān)鍵節(jié)點(diǎn)的選取

在路由過程中備份拓?fù)滏溌返谋Ｗo(hù)算法基本步驟：首先需要與關(guān)鍵點(diǎn)建立起相連的路徑，并對(duì)其進(jìn)行保護(hù)處理；其次是需要與普通節(jié)點(diǎn)相連的路徑建立起保護(hù)的過程。當(dāng)鏈路進(jìn)行保護(hù)之后，需要對(duì)已生成的備份拓?fù)淠芊駶M足已有的拓?fù)鋭?chuàng)建規(guī)則，假如可以滿足規(guī)則那么就繼續(xù)進(jìn)行，否則，程序就需要終止這個(gè)過程。這個(gè)算法的目的就是為了進(jìn)一步增加關(guān)鍵節(jié)點(diǎn)的可用鏈路，從而可以更好地減少因選擇最短路徑而出現(xiàn)的跳數(shù)。

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

2.2算法流程

說明：算法中的輸入變量等于關(guān)鍵節(jié)點(diǎn)個(gè)數(shù)K，其中輸出變量等于備份拓?fù)鋫€(gè)數(shù)N。同時(shí)定義N等于1，算法總共由五個(gè)步驟組成，具體執(zhí)行算法如下：

第一步：按照所定義好的關(guān)鍵點(diǎn)選取方法來對(duì)相關(guān)鍵節(jié)點(diǎn)的選取。

第二步：需要選取第K個(gè)關(guān)鍵節(jié)點(diǎn)，通常來說有這樣的兩種選取方法。

1）應(yīng)用Top K選擇方法：根據(jù)介數(shù)值的高低來對(duì)相關(guān)節(jié)點(diǎn)執(zhí)行降序的排列，同時(shí)還需要選取前K個(gè)節(jié)點(diǎn)來作為具體的關(guān)鍵節(jié)點(diǎn)。

2）應(yīng)用Non-adjacent K選擇方法：這個(gè)關(guān)鍵節(jié)點(diǎn)不但擁有較大的介數(shù)值，并且有必要考慮關(guān)鍵節(jié)點(diǎn)在具體組網(wǎng)中體現(xiàn)的位置信息。假若關(guān)鍵節(jié)點(diǎn)是屬于相鄰的，那么其最大化可用的鏈路就會(huì)出現(xiàn)減少的可能。所以，假如當(dāng)前所選的關(guān)鍵節(jié)點(diǎn)與之前所選取的關(guān)鍵節(jié)點(diǎn)是屬于相鄰的，那么就需要跳過當(dāng)前的節(jié)點(diǎn)，此時(shí)就會(huì)選擇下一個(gè)節(jié)點(diǎn)作當(dāng)前的關(guān)鍵節(jié)點(diǎn)。

第三步：有必要與關(guān)鍵節(jié)點(diǎn)建立起具體的鏈路保護(hù)過程。使得能夠與特定關(guān)鍵節(jié)點(diǎn)形成鏈路，以此來更好地保證各個(gè)備份拓?fù)渲卸伎梢酝ㄟ^最小的受保護(hù)鏈路數(shù)，具體如圖1所示，從而可以達(dá)到保證各個(gè)關(guān)鍵節(jié)點(diǎn)在每個(gè)拓?fù)渲卸伎梢孕纬筛嗟目捎面溌贰?/p>

這里將關(guān)鍵節(jié)點(diǎn)中保護(hù)鏈路在各個(gè)備份拓?fù)渲姓加械臄?shù)量視為M，并將關(guān)鍵節(jié)點(diǎn)所擁有的最大出入度視為D，那么M>=ceil（D/N）+1。具體如圖1所示，當(dāng)出現(xiàn)的最大備份拓?fù)鋽?shù)是3時(shí)，以及關(guān)鍵節(jié)點(diǎn)為6時(shí)，其最大的出人度就等于3，那么各個(gè)備份拓?fù)渲兴艿奖Ｗo(hù)的鏈路數(shù)最小值就等于1。

第四步：執(zhí)行與之有關(guān)的普通節(jié)點(diǎn)的鏈路保護(hù)過程，并對(duì)各個(gè)鏈路實(shí)現(xiàn)保護(hù)。

第五步：判斷最新生成的備份拓?fù)淠芊穹舷嚓P(guān)規(guī)則。如果能夠滿足，那么這次運(yùn)行過程就結(jié)束。否則，就需要對(duì)N進(jìn)行累加1，接著執(zhí)行第一步。算法基本流程見圖2。

2.3算法的實(shí)現(xiàn)

3改進(jìn)算法后綜合評(píng)估

事實(shí)上，關(guān)鍵節(jié)點(diǎn)在網(wǎng)絡(luò)結(jié)構(gòu)中選擇是非常重要的，同時(shí)需要將關(guān)鍵節(jié)點(diǎn)的概念與備份拓?fù)浣Y(jié)合起來。當(dāng)在備份拓?fù)鋭?chuàng)建的最初階段，需要通過關(guān)鍵節(jié)點(diǎn)評(píng)估的方法來選出具體的數(shù)目節(jié)點(diǎn)來作為最關(guān)鍵的節(jié)點(diǎn)，其他的節(jié)點(diǎn)視為普通節(jié)點(diǎn)。這個(gè)算法按照關(guān)鍵節(jié)點(diǎn)的出入度以及備份拓?fù)鋽?shù)的最大化關(guān)鍵節(jié)點(diǎn)來產(chǎn)生有關(guān)的鏈路等。為了可以更好準(zhǔn)確的評(píng)估新的算法，這里提出了應(yīng)用基于緊密度與介數(shù)值的綜合評(píng)價(jià)方法：D（i）=C（i）B（i）。式中的D（i）是作為節(jié)點(diǎn)i的關(guān)鍵度，c（i）是作為節(jié)點(diǎn)i處于網(wǎng)絡(luò)中心的程度，B（i）是指節(jié)點(diǎn)i對(duì)于鄰節(jié)點(diǎn)所體現(xiàn)的重要程度。

對(duì)于關(guān)鍵節(jié)點(diǎn)的選取時(shí)，主要是將D（i）值高的節(jié)點(diǎn)根據(jù)順序來作為關(guān)鍵節(jié)點(diǎn)。之后再應(yīng)用Top K方法和Non-adjacent K方法來增加相關(guān)鍵節(jié)點(diǎn)的可用鏈路，以此來減少重路由所出現(xiàn)的跳數(shù)，從而達(dá)到優(yōu)化算法的過程，改進(jìn)后的算法具有可行性。

4結(jié)論

綜上所述，本算法的重點(diǎn)是對(duì)關(guān)鍵節(jié)點(diǎn)的合理選取，關(guān)鍵節(jié)點(diǎn)的數(shù)目和關(guān)鍵節(jié)點(diǎn)的具體位置對(duì)于實(shí)驗(yàn)結(jié)果都會(huì)產(chǎn)生不同的影響，因此，需要做到在保障網(wǎng)絡(luò)正常連通的情況下，選取合適的關(guān)鍵節(jié)點(diǎn)數(shù)目。通過對(duì)改進(jìn)后的算法進(jìn)行評(píng)估，認(rèn)為改進(jìn)后的算法具有可行性。