許素欽　許國武　陳建成　黃紹君

摘要：該文主要分析了路由環(huán)路產(chǎn)生的原因和當(dāng)前基于距離矢量路由協(xié)議和鏈路狀態(tài)路由協(xié)議的路由環(huán)路避免機(jī)制，通過分析得到當(dāng)前主流環(huán)路避免機(jī)制存在的問題。最后介紹了路由環(huán)路避免技術(shù)的發(fā)展趨勢和路由環(huán)路解決方法性能的考量。

關(guān)鍵詞：路由環(huán)路；鏈路狀態(tài)路由協(xié)議；距離矢量路由協(xié)議；避免機(jī)制；性能

當(dāng)網(wǎng)絡(luò)拓?fù)浒l(fā)生改變時，路由器將對路由表進(jìn)行維護(hù)，如果網(wǎng)絡(luò)收斂緩慢或其他原因?qū)е洛e誤路由的添加，就有可能出現(xiàn)路由環(huán)路問題。基本上，路由環(huán)路的形成都是因?yàn)榈竭_(dá)目的路徑的不確定性或矛盾的路由條目選擇而造成的。路由環(huán)路造成網(wǎng)絡(luò)動蕩，引起數(shù)據(jù)包進(jìn)入黑洞，進(jìn)而丟包，造成網(wǎng)絡(luò)資源的嚴(yán)重浪費(fèi)，嚴(yán)重的會導(dǎo)致網(wǎng)絡(luò)癱瘓。為此，避免路由環(huán)路的技術(shù)就應(yīng)運(yùn)而生了。路由避免技術(shù)主要是通過路由協(xié)議本身的一些機(jī)制來實(shí)現(xiàn)。

1路由環(huán)路影響及產(chǎn)生的主要原因

互聯(lián)網(wǎng)技術(shù)的快速發(fā)展使應(yīng)用種類越來越多樣化，路由技術(shù)無疑成為網(wǎng)絡(luò)通信的核心技術(shù)。因此，對路由協(xié)議的健壯性和可靠性要求也越來越高?，F(xiàn)有的邊界網(wǎng)絡(luò)路由協(xié)議（BGP）已無法滿足當(dāng)前網(wǎng)絡(luò)路由協(xié)議的性能和可靠性等需求。大量文獻(xiàn)研究表明，BGP較差的可靠性將會直接影響互聯(lián)網(wǎng)的可靠性。Kushman、Kandula S等人通過實(shí)驗(yàn)分析提出接近50%的VoIP故障出現(xiàn)在BGP更新報(bào)文后的15分鐘內(nèi)；Labovitz等人指出，報(bào)文丟失的主要原因之一是因?yàn)槁酚稍诙虝r間內(nèi)的變化所致，許多IP地址因?yàn)锽GP的抖動而在短時間內(nèi)不可訪問。

因此互聯(lián)網(wǎng)的可靠性很大程度依賴于路由協(xié)議?；ヂ?lián)網(wǎng)是一個不斷變化的網(wǎng)絡(luò)，其拓?fù)浣Y(jié)構(gòu)也因鏈路（或節(jié)點(diǎn)）故障發(fā)生而不斷變化，在變化的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中能夠快速收斂得到正確路由是互聯(lián)網(wǎng)可靠性的重要保證。出于穩(wěn)定性考慮，當(dāng)前互聯(lián)網(wǎng)路由協(xié)議通常只選擇一條“最佳”路徑到達(dá)目的地，這種單路徑路由協(xié)議不具備瞬時恢復(fù)能力，路由收斂的延遲可能會導(dǎo)致瞬時路由環(huán)路或者瞬時路由失效等故障。

在采用不同路由算法的動態(tài)路由協(xié)議中，其路由協(xié)議的收斂速度也不一樣。如果動態(tài)路由協(xié)議的路由收斂速度越慢，就越容易出現(xiàn)路由環(huán)路?；诰嚯x矢量的路由協(xié)議是最容易產(chǎn)生路由環(huán)路。以RIP動態(tài)路由協(xié)議為例，運(yùn)行RIP協(xié)議的路由器需要定期將整張路由表向相連的鄰居路由器廣播，鄰居路由器接收到這些路由更新信息后，按照距離矢量算法生成路由表。在RIP協(xié)議中設(shè)置了四個計(jì)時器來進(jìn)行路由更新，其中抑制計(jì)時器為180秒，更新計(jì)時器為30秒，在極限情況下RIP協(xié)議的收斂時間可能達(dá)到210秒。在這么長的收斂時間里很有可能產(chǎn)生路由環(huán)路。通常RIP協(xié)議通過采用最大跳數(shù)、水平分割、路由毒化和毒性逆轉(zhuǎn)等技術(shù)來防止路由環(huán)路，但這些技術(shù)也存在局限性，如無法解決多個路由器發(fā)生路由環(huán)路問題。在基于鏈路狀態(tài)的路由協(xié)議中，因?yàn)榫W(wǎng)絡(luò)拓?fù)涞淖兓?，網(wǎng)絡(luò)會發(fā)布新的鏈路狀態(tài)信息，其余路由節(jié)點(diǎn)在收到新的鏈路狀態(tài)信息后會重新計(jì)算機(jī)路由并更新、轉(zhuǎn)發(fā)信息庫，但是由于各路由節(jié)點(diǎn)內(nèi)外環(huán)境的差異等原因?qū)е赂髀酚晒?jié)點(diǎn)收到的拓?fù)涓滦畔⒑褪褂眯罗D(zhuǎn)發(fā)表的時間是不一樣的，因此分散的路由節(jié)點(diǎn)對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的認(rèn)知失調(diào)，可能導(dǎo)致每個路由節(jié)點(diǎn)轉(zhuǎn)發(fā)的路徑之間產(chǎn)生環(huán)路。

2路由環(huán)路避免機(jī)制

在傳統(tǒng)路由算法中，基于鏈路狀態(tài)算法比基于距離矢量算法更具優(yōu)越性，所以相對來說鏈路狀態(tài)算法的路由協(xié)議更少出現(xiàn)路由環(huán)路。因此在大型網(wǎng)絡(luò)中基本上都采用基于鏈路狀態(tài)算法的路由協(xié)議來進(jìn)行路由收斂。

文獻(xiàn)中提出基于鏈路狀態(tài)快速感知的環(huán)路避免機(jī)制：主要利用CR在路由更新之前快速獲取最新的網(wǎng)絡(luò)拓?fù)湫畔?，通過控制路由器的重計(jì)算次序來避免環(huán)路的產(chǎn)生。文獻(xiàn)中提出以時間作為目的地序號來解決路由環(huán)路的方法：對消息項(xiàng)序號的重新設(shè)計(jì)，添加時間（Tim of Day，TOD）信息，避免因?yàn)楣?jié)點(diǎn)休眠重啟或者路由超時刪除時，路由消息項(xiàng)序號重新計(jì)數(shù)引發(fā)的重復(fù)廣播過期路由消息項(xiàng)的問題。按照路由更新的原則，選擇消息項(xiàng)序號最新的消息項(xiàng)，從根本上解決了路由消息循環(huán)傳輸?shù)膯栴}，確保在任何時刻網(wǎng)絡(luò)中都不會存在路由消息循環(huán)和暫態(tài)路由環(huán)路。文獻(xiàn)中提出BGP采用AS_PATH屬性檢測機(jī)制來實(shí)現(xiàn)環(huán)路避免，文獻(xiàn)中提出采用LFGM（Loop-Free Guarantee Mechanism）可使節(jié)點(diǎn)獲得更多不會產(chǎn)生環(huán)路的可達(dá)路徑。LFGM不僅能夠滿足多徑路由的無環(huán)需求，而且與最優(yōu)路徑選路及等代價最優(yōu)路徑選路方式相比，節(jié)點(diǎn)將能夠獲取更多數(shù)量的可用路由，從而為路由選擇提供了更大的可操作空間。文獻(xiàn)中提出一種偏轉(zhuǎn)路由方案以增強(qiáng)網(wǎng)絡(luò)在發(fā)生瞬時鏈路或節(jié)點(diǎn)故障情況下的可用性。

上文提出，如果動態(tài)路由協(xié)議的路由收斂速度越慢，就越容易出現(xiàn)路由環(huán)路。針對該問題，IETF提出無環(huán)替代路方案和Not-via技術(shù)，以及后來其他研究人員提出的FIR、Safeguard、FCP、MRC等技術(shù)。上述技術(shù)基本上都可以保證單失效情況下路由的100%快速恢復(fù)，但其性能與網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和權(quán)重配置有很大關(guān)系，可能導(dǎo)致流量分配不均衡問題。因此，文獻(xiàn)提出基于單向轉(zhuǎn)發(fā)環(huán)的快速重路由策略，通過在網(wǎng)絡(luò)中預(yù)先簡歷兩個單向轉(zhuǎn)發(fā)環(huán)路來保證單失效情況下網(wǎng)絡(luò)路由的快速恢復(fù)。

3存在的問題

當(dāng)前，大多數(shù)大型ISP（網(wǎng)絡(luò)服務(wù)提供商）網(wǎng)絡(luò)使用ISIS（中間系統(tǒng)協(xié)4g）或者OSPF（開放最短路由優(yōu)先協(xié)議）這兩個協(xié)議作為域內(nèi)路由協(xié)議。作為典型的鏈路狀態(tài)協(xié)議，ISIS和OSPF都需要通過鏈路狀態(tài)通告在節(jié)點(diǎn)間交互網(wǎng)絡(luò)拓?fù)湫畔?，以此來保證網(wǎng)絡(luò)中的所有節(jié)點(diǎn)鏈路狀態(tài)數(shù)據(jù)庫的一致性。因此當(dāng)有鏈路或網(wǎng)絡(luò)設(shè)備發(fā)生失效時，路由器需要檢測并全網(wǎng)通報(bào)這一失效信息，以便其他路由器獲知這一拓?fù)浣Y(jié)構(gòu)的變化。從檢測到失效到全網(wǎng)所有節(jié)點(diǎn)的鏈路狀態(tài)數(shù)據(jù)庫最終重新達(dá)到一致這個過程稱為重收斂過程。然而重收斂過程將會給網(wǎng)絡(luò)帶來丟包以及延遲過長等潛在問題。

對于傳統(tǒng)業(yè)務(wù)，路由環(huán)路避免過程中的重收斂過程所造成的影響往往是可以容忍的。但近些年來，隨著對時延和丟包敏感的實(shí)時業(yè)務(wù)的大規(guī)模普及，用戶對網(wǎng)絡(luò)性能的要求也變得越來越嚴(yán)格。對于IP電話、流媒體、網(wǎng)游以及遠(yuǎn)程視頻會議等實(shí)時業(yè)務(wù)來說，丟包或長延時都將明顯的降低它們的性能甚至造成業(yè)務(wù)中斷。因此如何避免丟包以及降低時延已經(jīng)成為一個不得不面對的問題。

4總結(jié)

路由環(huán)路避免機(jī)制致力于解決網(wǎng)絡(luò)中環(huán)路問題，但該問題一直存在于各種路由環(huán)境中，并且嚴(yán)重影響路由協(xié)議陛能。解決路由環(huán)路問題往往以犧牲某部分陛能為代價，因此判斷該環(huán)路解決機(jī)制的重要因素應(yīng)該分為以下兩點(diǎn)：（1）該機(jī)制是否解決路由環(huán)路問題；（2）該機(jī)制應(yīng)用后對其他性能的影響程度?，F(xiàn)今，網(wǎng)絡(luò)應(yīng)用的快速發(fā)展使通信質(zhì)量越來越受到重視，因此網(wǎng)絡(luò)的可靠性和穩(wěn)定性成為研究人員的研究熱點(diǎn)，其中IP路由環(huán)路的避免技術(shù)研究無疑是研究熱點(diǎn)的重中之重，但是從目前的情況上來看，現(xiàn)存的環(huán)路避免算法的復(fù)雜度都比較高，因此其工程可行性較差，此問題的有效解決有待于進(jìn)一步的研究。endprint