基于“下一跳代價(jià)遞減”準(zhǔn)則的IP快速重路由方法研究.pdf

1、隨著互聯(lián)網(wǎng)所提供的豐富多彩的服務(wù)不斷帶給著人們驚喜，IP業(yè)務(wù)已悄然取代了傳統(tǒng)的話音業(yè)務(wù)，成為了網(wǎng)絡(luò)業(yè)務(wù)的主體。近年來，隨著越來越多的實(shí)時(shí)性業(yè)務(wù)，諸如IP電話（VOIP）和基于流媒體的視頻業(yè)務(wù)（YouTube）等皆賴以互聯(lián)網(wǎng)的傳送，人們對(duì)互聯(lián)網(wǎng)的網(wǎng)絡(luò)生存性提出了更高的要求。
　　 本論文重點(diǎn)研究網(wǎng)絡(luò)生存性問題，特別是對(duì)基于快速重路由方法的IP網(wǎng)絡(luò)生存性問題。第一章就網(wǎng)絡(luò)生存性研究的相關(guān)問題進(jìn)行調(diào)研分析，從網(wǎng)絡(luò)分層的視角重點(diǎn)總結(jié)和分

2、析了SDH/SONET網(wǎng)絡(luò)的生存性、自動(dòng)交換光網(wǎng)絡(luò)（ASON）生存性、純IP網(wǎng)的網(wǎng)絡(luò)生存性、MPLS網(wǎng)的網(wǎng)絡(luò)生存性以及多層網(wǎng)絡(luò)生存性等問題。
　　 隨著路由器處理能力的提升，IP網(wǎng)（互聯(lián)網(wǎng)）生存性改進(jìn)主要有2個(gè)方向，一是不改變目前無連接、分組、最短徑轉(zhuǎn)發(fā)的模式，而對(duì)相關(guān)路由協(xié)議進(jìn)行“修補(bǔ)”，但在恢復(fù)時(shí)間和效率上效果欠佳；二是引入一層全新的具有面向連接能力的MPLS（多協(xié)議標(biāo)記交換）層，利用MPLS增強(qiáng)生存性，這種方法代價(jià)較高，特

3、別是運(yùn)維成本較高。近來出現(xiàn)了兩類方法-Valiant負(fù)載均衡方法和IP快速重路由方法，第二章對(duì)這兩類方法的機(jī)理、局限性和改進(jìn)方向進(jìn)行了深入分析。同時(shí)借鑒公路網(wǎng)故障情況下的重選路策略，提出IP網(wǎng)絡(luò)備選接口的選擇可以參照最短徑距離遞減的思想。
　　 公路網(wǎng)的許多特點(diǎn)與互聯(lián)網(wǎng)類似，特別是其承載的個(gè)體都遵循“無連接、分組和獨(dú)立最短徑尋址”等基本特性。公路網(wǎng)在（道路或者路口）故障時(shí)，汽車（行人）會(huì)臨時(shí)偏離原有的（最短徑）路線，但是會(huì)遵循“

4、方向不變”的原則，即其繞行后總是希望盡早回復(fù)到前往目的地的“方向”。借鑒到互聯(lián)網(wǎng)上，那么什么是IP報(bào)文偏離最短徑后繞行到目的地的“方向”?
　　 本文提出的“下一跳代價(jià)遞減”準(zhǔn)則即為IP報(bào)文偏離最短徑后繞行到目的地的“方向”。網(wǎng)絡(luò)故障情況下，IP報(bào)文選擇非最短徑下一跳的節(jié)點(diǎn)時(shí)，只需遵循“下一跳代價(jià)遞減”（NHCD：Next Hop Cost Decrease）準(zhǔn)則，即此時(shí)相對(duì)偏射節(jié)點(diǎn)，接收被偏轉(zhuǎn)IP報(bào)文的節(jié)點(diǎn)，到目的節(jié)點(diǎn)最短徑上

5、的下一跳節(jié)點(diǎn)的最短徑代價(jià)遞減，即可確保不會(huì)形成路由環(huán)路。
　　 第三章提出了基于“下一跳代價(jià)遞減”準(zhǔn)則的IP重路由方法，它采用不同于RFC5286 LFA方法的新的無環(huán)路備選接口判定準(zhǔn)則。文章給出了“下一跳代價(jià)遞減”準(zhǔn)則情況下不會(huì)形成路由環(huán)路的兩種證明方法，并給出了基于“下一跳代價(jià)遞減”準(zhǔn)則生成備選接口的算法。
　　 第四章對(duì)基于“下一跳代價(jià)遞減”準(zhǔn)則的IP快速重路由方法進(jìn)行仿真，并與RFC5286的LFA方法進(jìn)行了比較

6、。雖然“下一跳代價(jià)遞減”準(zhǔn)則較LFA方法在故障覆蓋率上略顯不足（40％VS46.9％），但“下一跳代價(jià)遞減”準(zhǔn)則相對(duì)于LFA方法有如下的獨(dú)特優(yōu)勢，有利于其在實(shí)際網(wǎng)絡(luò)中快速部署，本文給出了相關(guān)的證明、算法、反例，得出：
　　 （1）NHCD可以統(tǒng)一處理鏈路失效和節(jié)點(diǎn)失效；
　　 （2）NHCD可以在網(wǎng)絡(luò)中多點(diǎn)故障的情況下使用；
　　 （3）NHCD可以與多種判定準(zhǔn)則混合使用（例如等價(jià)多路徑ECMP），提升整體網(wǎng)絡(luò)鏈

7、路故障覆蓋率；
　　 （4）NHCD計(jì)算復(fù)雜度要小于LFA方法。特別是基于以上特性，NHCD準(zhǔn)則可以在網(wǎng)絡(luò)常態(tài)（非故障）擁塞時(shí)用來進(jìn)行流量疏導(dǎo)，因而可以統(tǒng)一處理故障恢復(fù)和流量疏導(dǎo)；而且跟最短徑轉(zhuǎn)發(fā)一樣，都由本地路由器根據(jù)路由協(xié)議自動(dòng)處理，無需網(wǎng)管等人為處理。且這些部署可以逐步展開，即不需要一個(gè)網(wǎng)絡(luò)中的所有路由器同時(shí)具備NHCD能力。
　　 為此，第五章提出并重點(diǎn)分析了以基于“下一跳代價(jià)遞減”準(zhǔn)則的偏射機(jī)制為核心的備選接口

8、協(xié)議（AIP），AIP可以統(tǒng)一處理快速重路由和快速流量疏導(dǎo)，給出了綜合的無環(huán)路備選接口的選擇規(guī)則、詳細(xì)的備選接口算法、協(xié)議框架、處理流程及應(yīng)用建議。
　　 以下是本論文的主要?jiǎng)?chuàng)新性工作：
　　 （1）提出一種與RFC5286 LFA方法不同的適用于IP快速重路由的無環(huán)路備選接口判定準(zhǔn)則-“下一跳代價(jià)遞減準(zhǔn)則”。證明了在“下一跳最短徑轉(zhuǎn)發(fā)”的約束條件下，“下一跳代價(jià)遞減準(zhǔn)則”能保證IP重路由時(shí)不形成路由環(huán)路，并與RFC52

9、86的LFA方法進(jìn)行深入對(duì)比和仿真。
　　 （2）給出并證明了在“下一跳最短徑轉(zhuǎn)發(fā)”和“已偏射流量的節(jié)點(diǎn)不能接收其它節(jié)點(diǎn)的偏射流量”的約束條件下，“嚴(yán)格代價(jià)遞減準(zhǔn)則”和“下一跳代價(jià)遞減準(zhǔn)則”可以同時(shí)混合使用，并給出了通過Dijkstra最短徑算法的擴(kuò)展來生成的備選接口列表算法。
　　 （3）提出了統(tǒng)一處理故障恢復(fù)和流量疏導(dǎo)的備選接口協(xié)議AIP，分析了通過人工配置生成備選接口的方法，同時(shí)設(shè)計(jì)了AIP協(xié)議細(xì)節(jié)和處理流程，給出