IGP快速收斂技術白皮書

IGP4央速收斂技術白皮書TOC\o"1-5"\h\z\o"CurrentDocument"1前言L\o"CurrentDocument"2技術簡介2\o"CurrentDocument"3關鍵技術3\o"CurrentDocument"ISPF3\o"CurrentDocument"PRC4\o"CurrentDocument"智能定時器5\o"CurrentDocument"鏈路狀態(tài)信息快速通告6\o"CurrentDocument"4典型應用7.\o"CurrentDocument"5結束語8\o"CurrentDocument"附錄A參考資料9\o"CurrentDocument"附錄B縮略語.9.IGP快速收斂技術白皮書摘要：IGP快速收斂是一項綜合性的技術，它通過ISPF、PRC來實現(xiàn)單路由器上的路由快速計算，結合鏈路狀態(tài)信息的快速通告、指數(shù)退避定時器等技術來實現(xiàn)整個網(wǎng)絡的路由快速收斂。本篇文檔介紹了^?快速收斂中所用到的先進技術，最后，闡明了快速收斂對于現(xiàn)代組網(wǎng)的重要意義。關鍵詞：快速收斂、ISIS、OSPF、ISPF、PRC、指數(shù)退避定時器、智能定時器1前言如下圖所示，在一臺路由器上，路由系統(tǒng)中的路由收斂過程大致可以分解為以下幾個步驟：（1）IGP收到變化的鏈路狀態(tài)報文；（2）IGP將變化的鏈路狀態(tài)報文通告給鄰居，并進行路由計算；（3）IGP根據(jù)計算結果向路由管理平面通告路由的變化；（4）路由管理平面將變化的路由下刷到FIB中，指導轉發(fā)。若要使得路由收斂的速度加快，就需要針對上述幾個關鍵過程進行優(yōu)化。其中，IGP路由計算結果一＞路由管理平面一＞FIB的過程與軟件系統(tǒng)的設計有關，不在本文的描述范圍之內，可參閱相關的文檔。IGP快速收斂技術主要關注于鏈路狀態(tài)信息的接收、發(fā)送，以及路由計算過程的優(yōu)化。其中

路由計算的優(yōu)化是重點。目前的主流IGP協(xié)議（ISIS、OSPF）使用經(jīng)典的SPF算法計算網(wǎng)絡拓撲信息以及路由信息。在絕大多數(shù)情況下，當鏈路狀態(tài)信息（對應于ISIS協(xié)議中的LSP、OSPF協(xié)議中的LSA）發(fā)生變化時，整個網(wǎng)絡拓撲以及路由需要全部重新計算。對于現(xiàn)在的骨干網(wǎng)絡，通常網(wǎng)絡拓撲都比較復雜，路由量非常巨大，同時路由收斂性能要求也比較高。這種情況下，全部網(wǎng)絡信息重新計算一遍不僅消耗的時間長、收斂慢，而且會耗費大量的CPU資源，對網(wǎng)絡設備以及軟件系統(tǒng)都造成了一定的沖擊，如果是很少一點的網(wǎng)絡信息變化而導致的全部重新計算，帶來的消耗更是沒有必要。在這種情況下，IGP協(xié)議的快速收斂就體現(xiàn)出了其巨大的優(yōu)勢。2技術簡介快速收斂是由多項技術結合而成的。在路由計算方面，主要的思想就是“增量計算”（即，只計算變化的部分，而不是全部計算）。SPF算法將整個網(wǎng)絡信息分為兩個部分（如下圖所示）：一個部分是網(wǎng)絡的頂點（對應于網(wǎng)絡中的路由器、共享網(wǎng)段）和邊（路由器以及共享網(wǎng)段之間的鏈路）組成的網(wǎng)絡拓撲；另一個部分是掛在頂點上的葉子（網(wǎng)段路由、主機路由）。進行路由計算的路由器稱為“根（ROOT）”；路由計算的第一步就是根據(jù)拓撲計算出以ROOT為根的一棵最短路徑樹，第二步就是根據(jù)最短路徑樹計算各個頂點上的葉子（路由）。ROOT根節(jié)點'?--RT檀一?；'頂點在最短路徑樹上的邊不在最短路徑樹上的邊隹葉子（路由）針對網(wǎng)絡拓撲中的最短路徑樹的增量計算稱為ISPF（IncrementalSPF）；而針對葉子（路由）的增量計算則稱為PRC（PartialRouteCalculate）。“增量計算”能夠極大地提高單路由器的計算性能，降低CPU負荷。另一方面，普通的路由計算定時器一般在10秒時間間隔，也阻礙了路由計算的快速進行，因此定時器的優(yōu)化也成為要點。采用指數(shù)退避的形式來控制定時器的超時時間間隔從短間隔逐步增加到長間隔，可以有效的加快路由的計算速度，同時避免了短時間內進行多次的路由計算。本文以下將這種定時器稱為“智能定時器”。在只有少量信息變化的情況下，如果要求整個網(wǎng)絡的快速收斂，不僅要求單路由器的快速計算，同時還需要變化的路由信息能夠快速的傳播到整個網(wǎng)絡中，采用“鏈路狀態(tài)信息快速通告”的技術可以實現(xiàn)這一需求。3關鍵技術3.1ISPF在SPF計算中，網(wǎng)絡是由頂點（路由器以及共享網(wǎng)段）以及邊（路由器之間以及與共享網(wǎng)段之間的鏈接）構成，最終形成一棵以計算路由器為根的最短路徑樹；而路由則是附著在樹的頂點上的葉子。ISIS以及OSPF協(xié)議在數(shù)據(jù)庫中存儲的是自己特定格式的鏈路信息，這些信息并不能直接反映出拓撲的情況以及路由與拓撲的關系，因此SPF必須通過全部的計算過程來確定最短路徑樹，并計算出路由。但是，SPF并不保存這個計算結果；這樣當有信息發(fā)生變化時，SPF只能再次全部重新計算一遍。ISPF只處理網(wǎng)絡拓撲的信息，即只負責計算出最短路徑樹。通過重新組織鏈路信息，ISPF形成了一個直接反映網(wǎng)絡拓撲的“圖”狀數(shù)據(jù)庫；而計算出的最短路徑樹則保存在這個“圖”中。當鏈路狀態(tài)信息發(fā)生變化，ISPF會判斷出哪部分網(wǎng)絡拓撲受到了影響，從而只計算那些受到了影響的部分，而不是全部網(wǎng)絡拓撲。如下圖所示：RTA為根節(jié)點（進行計算的路由器），鏈路RTC3RTF（紅色的鏈路）的cost由3增長為5,那么受到影響的部分只有RTF、RTH兩臺路由器（紅色圈中），而其他部分的路由器（黑色圈中）則沒有受到影響。ISPF會判斷出這種影響范圍，之后只計算更新RTF、RTH發(fā)布的路由。網(wǎng)絡拓撲變化的位置不同，收到影響的范圍就不同，ISPF計算所消耗的時間就不同，所以，ISPF計算所消耗的時間是不確定的，即使是在相同的網(wǎng)絡結構中。當然，如果發(fā)生變化的是根節(jié)點的邊（圖中的RTA3RTB和RTA3RTC），那么受影響的范圍就包括了整個拓撲，在這種情況下，ISPF相當于進行了全部重新計算。3.2PRC任何一條路由都是網(wǎng)絡節(jié)點上的“一片樹葉”，在SPF術語中稱為葉子。這個比喻很形象，同時也反映出了路由與網(wǎng)絡節(jié)點之間的關系：從根節(jié)點看，只要到網(wǎng)絡節(jié)點的最短路徑確定了，那么到節(jié)點發(fā)布的路由的最短路徑也就確定了。因此，PRC就是直接利用ISPF計算出的最短路徑樹來計算葉子路由的。當有路由信息改變，PRC直接判斷出那條路由（葉子）發(fā)生了變化，之后直接進行路由的選擇與更新（基于現(xiàn)有的ISPF的計算結果）。由于ISIS以及OSPF協(xié)議的鏈路信息格式的限制，路由信息與網(wǎng)絡節(jié)點（發(fā)布路由器）之間的關系并不直接，不同發(fā)布者發(fā)布的相同路由直接也沒有直接的聯(lián)系，因此PRC重新組織數(shù)據(jù)庫。如下圖所示：10.0.0./24一方面以“路由”為基點，將所有發(fā)布了這條路由的因素組織在一起，這樣在計算路由時可以很直觀的在所有因素中選擇最佳路由；另一方面以“發(fā)布者”為基點，將這個發(fā)布者發(fā)布的所有路由都集結在一起，這樣當ISPF宣布某個節(jié)點的最短路徑發(fā)生變化時，這個節(jié)點發(fā)布的所有路由都會被直接的更新。特別的，對于OSPF協(xié)議，這種數(shù)據(jù)庫的組織方式還可以方便的實現(xiàn)TransitArea的Summary路由（第三類以及第四類）更新過程，而不用重新進行整個區(qū)域的計算。詳細的Summary路由計算過程、以及TransitArea的更新過程請參見“RFC2328”。3.3智能定時器為了能夠快速響應網(wǎng)絡信息的變化，同時由不會過于頻繁的進行路由計算，采用了“智能定時器”的技術。所謂“智能定時器”，是指能夠根據(jù)預先配置的參數(shù)，依照指數(shù)退避的規(guī)律動態(tài)的改變時間間隔的定時器。智能定時器有三個可配置的參數(shù)：初始時間間隔、遞增時間間隔、最大時間間隔。定時器最初的時間間隔就是“初始時間間隔”，第二次的時間間隔則是“遞增時間間隔”，之后每次的時間間隔都會是前一次的2倍，即“遞增時間間隔”X2n,直到到達“最大時間間隔”為止。通常情況下，“初始時間間隔”可以配置為10毫秒左右（或者小于10毫秒），可以快速響應突然的變化；“遞增時間間隔”則可以設置在幾十毫秒或者1秒的級別；“最大時間間隔”可以設置在5秒或者10秒的級別。

第一次第二次

計算請求計算請求第三、四次最大

時間間隔初始"遞增"2X遞增時間間隔時間間隔時間間隔第一次第二次第三次計算計算計算第一次第二次

計算請求計算請求第三、四次最大

時間間隔智能定時器是一個循環(huán)定時器，時間間隔不斷增大。一方面，他的初始時間很短，可以迅速響應網(wǎng)絡變化；另一方面，他的時間間隔不斷增加，可以防止頻繁的網(wǎng)絡變化導致的頻繁的路由計算。但是在以下三種情況下，智能定時器將被重置或者停止：（1）時間間隔連續(xù)三次達到了最大。如果此時有路由計算請求，那么下一次的時間間隔被重置為“初始時間間隔”；否則定時器被停止；（2）新產(chǎn)生的路由計算請求與前一次路由計算的時間間隔超過了“最大時間間隔”，那么立即重置定時器的時間間隔為“初始時間間隔”；（3）協(xié)議進程被RESET。在特殊情況下（例如網(wǎng)絡信息相對穩(wěn)定，網(wǎng)絡的任何變化都要求得到最快速的響應），智能定時器的“初始時間間隔”允許配置為0，使得第一次計算請求立即得到執(zhí)行；“最大時間間隔”也可以配置為0，表示每一次都立即進行路由計算。但是如果變化信息較多，將導致非常頻繁的路由計算，因此不建議這樣的配置。在ISIS以及OSPF協(xié)議中規(guī)定，同一個鏈路狀態(tài)報文不應該頻繁的產(chǎn)生。OSPF協(xié)議建議的缺省時間間隔為5秒，而ISIS協(xié)議建議的缺省時間間隔則是30秒，這個時間對于現(xiàn)在的網(wǎng)絡性能來說都太長，而使用智能定時器來控制這個時間間隔，可以很好的解決“頻繁產(chǎn)生”與“時間間隔長”之間的矛盾。3.4鏈路狀態(tài)信息快速通告鏈路狀態(tài)信息快速通告技術只針對ISIS協(xié)議而言。根據(jù)ISIS協(xié)議，當收到一條新的LSP時，只會在這條LSP上標記SRM標志，之后通過定時器定時發(fā)送帶有SRM標志的LSP。這種設置就延緩了網(wǎng)絡變化的傳遞，增大了整個網(wǎng)絡的收斂速度。為了避免這種情況，ISIS快速收斂允許在每次進行路由計算之前，將一定數(shù)量（可以配置）的LSP泛洪出去，在很大程度上提高了網(wǎng)絡的收斂速度。對于OSPF協(xié)議，當收到新的LSA時就會立即泛洪出去，因此不需要在這方面使用這樣的技術。4典型應用u復雜網(wǎng)絡簡單網(wǎng)絡廠一fRouter如上圖所示，是IGP快速收斂應用的典型網(wǎng)絡之一。在Router上將智能定時器的“初始時間間隔”配置為1毫秒；當網(wǎng)絡中只有簡單路由的變化時，Router上的路由收斂速度（流量切換速度）可以控制在10毫秒的量級；而對于某處的網(wǎng)絡拓撲變化，Router上也能夠很快的計算出結果。特別的，當這種變化發(fā)生在“簡單網(wǎng)絡”中時，Router根本不會去計算“復雜網(wǎng)絡”所對應的巨大量的網(wǎng)絡信息。通常情況下，網(wǎng)絡拓撲規(guī)模越大、結構越復雜，快速收斂技術帶來的效果越明顯（收斂時間可以提高1?3個量級），而這種快速收斂的效果具有不確定性。在相同的組網(wǎng)狀況下，對于同一臺路由器而言，不同位置的網(wǎng)絡變化所引起的路由收斂時間會不同，而相同位置的網(wǎng)絡變化所引起的不同路由器上的收斂時間也會不同。在考慮路由收斂時間時，不能僅僅考慮IGP路由計算的時間。正如前面所述，路由收斂時間還要包括IGP路由計算結果一＞路由管理平面一＞FIB的過程所消耗的時間，通常情況下，這個時間與發(fā)生變化的路由的數(shù)量有關，數(shù)量越大，收斂時間越長。5結束語使用IGP快速收斂特性，路由器的路由收斂速度可以得到極大的提高，同時降低了CPU的負載。使用智能定時器可以很方便的根據(jù)網(wǎng)絡自身的特點，控制路由計算的反應速度以及計算頻度，增強軟件系統(tǒng)以及網(wǎng)絡系統(tǒng)的路由穩(wěn)定性。附錄A參考資料Listofreference參考資料清單：ISO10589,"Intermediate-SystemtoIntermediate-System”RFC2328,“OSPFVersion2"InternetDraft,“draft-alaettinoglu-ISIS-