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

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

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

當網(wǎng)絡(luò)拓撲發(fā)生改變時，路由器將對路由表進行維護，如果網(wǎng)絡(luò)收斂緩慢或其他原因?qū)е洛e誤路由的添加，就有可能出現(xiàn)路由環(huán)路問題。基本上，路由環(huán)路的形成都是因為到達目的路徑的不確定性或矛盾的路由條目選擇而造成的。路由環(huán)路造成網(wǎng)絡(luò)動蕩，引起數(shù)據(jù)包進入黑洞，進而丟包，造成網(wǎng)絡(luò)資源的嚴重浪費，嚴重的會導(dǎo)致網(wǎng)絡(luò)癱瘓。為此，避免路由環(huán)路的技術(shù)就應(yīng)運而生了。路由避免技術(shù)主要是通過路由協(xié)議本身的一些機制來實現(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）已無法滿足當前網(wǎng)絡(luò)路由協(xié)議的性能和可靠性等需求。大量文獻研究表明，BGP較差的可靠性將會直接影響互聯(lián)網(wǎng)的可靠性。Kushman、Kandula S等人通過實驗分析提出接近50%的VoIP故障出現(xiàn)在BGP更新報文后的15分鐘內(nèi)；Labovitz等人指出，報文丟失的主要原因之一是因為路由在短時間內(nèi)的變化所致，許多IP地址因為BGP的抖動而在短時間內(nèi)不可訪問。

因此互聯(lián)網(wǎng)的可靠性很大程度依賴于路由協(xié)議?；ヂ?lián)網(wǎng)是一個不斷變化的網(wǎng)絡(luò)，其拓撲結(jié)構(gòu)也因鏈路（或節(jié)點）故障發(fā)生而不斷變化，在變化的網(wǎng)絡(luò)拓撲結(jié)構(gòu)中能夠快速收斂得到正確路由是互聯(lián)網(wǎng)可靠性的重要保證。出于穩(wěn)定性考慮，當前互聯(lián)網(wǎng)路由協(xié)議通常只選擇一條“最佳”路徑到達目的地，這種單路徑路由協(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é)議為例，運行RIP協(xié)議的路由器需要定期將整張路由表向相連的鄰居路由器廣播，鄰居路由器接收到這些路由更新信息后，按照距離矢量算法生成路由表。在RIP協(xié)議中設(shè)置了四個計時器來進行路由更新，其中抑制計時器為180秒，更新計時器為30秒，在極限情況下RIP協(xié)議的收斂時間可能達到210秒。在這么長的收斂時間里很有可能產(chǎn)生路由環(huán)路。通常RIP協(xié)議通過采用最大跳數(shù)、水平分割、路由毒化和毒性逆轉(zhuǎn)等技術(shù)來防止路由環(huán)路，但這些技術(shù)也存在局限性，如無法解決多個路由器發(fā)生路由環(huán)路問題。在基于鏈路狀態(tài)的路由協(xié)議中，因為網(wǎng)絡(luò)拓撲的變化，網(wǎng)絡(luò)會發(fā)布新的鏈路狀態(tài)信息，其余路由節(jié)點在收到新的鏈路狀態(tài)信息后會重新計算機路由并更新、轉(zhuǎn)發(fā)信息庫，但是由于各路由節(jié)點內(nèi)外環(huán)境的差異等原因?qū)е赂髀酚晒?jié)點收到的拓撲更新信息和使用新轉(zhuǎn)發(fā)表的時間是不一樣的，因此分散的路由節(jié)點對網(wǎng)絡(luò)拓撲結(jié)構(gòu)的認知失調(diào)，可能導(dǎo)致每個路由節(jié)點轉(zhuǎn)發(fā)的路徑之間產(chǎn)生環(huán)路。

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

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

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

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

3存在的問題

當前，大多數(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é)點間交互網(wǎng)絡(luò)拓撲信息，以此來保證網(wǎng)絡(luò)中的所有節(jié)點鏈路狀態(tài)數(shù)據(jù)庫的一致性。因此當有鏈路或網(wǎng)絡(luò)設(shè)備發(fā)生失效時，路由器需要檢測并全網(wǎng)通報這一失效信息，以便其他路由器獲知這一拓撲結(jié)構(gòu)的變化。從檢測到失效到全網(wǎng)所有節(jié)點的鏈路狀態(tài)數(shù)據(jù)庫最終重新達到一致這個過程稱為重收斂過程。然而重收斂過程將會給網(wǎng)絡(luò)帶來丟包以及延遲過長等潛在問題。

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

4總結(jié)

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