名空間路由研究和源管理路由算法的分析與建模.pdf

1、網絡路由一直是網絡的關鍵問題。今天的計算機網絡非常龐大、高速,傳載著各種多媒體信息,因此,網絡路由面臨新的挑戰(zhàn)。路由算法層出不窮,目的都是為了尋找滿足要求的路徑來傳遞信息。而目前因特網使用的路由算法,主要是基于1959年提出的Dijkstra算法和1962年提出的基于Bellman-Ford算法等理論研究成果。這些經典路由算法都是假設在網絡拓撲的基礎上定義一個度量,在這個度量的基礎上計算每個節(jié)點到達其他節(jié)點的最短路由,并且為每個子網保持

2、一個路由表項。它們的特點是全局維護,精確路由指向,最短路徑路由。隨著網絡規(guī)模不斷擴大,子網數量急劇增多,目前全局最優(yōu)的傳統(tǒng)路由算法將面臨嚴重挑戰(zhàn)。網絡發(fā)展趨勢引發(fā)在理論上重新審視現有路由算法和開拓新路由方案的迫切需求。
　　 本文在研究了VRR(Virtual Ring Routing)和ROFL(Routing on Flat Labels)路由算法的基礎上,總結出的名空間路由思想:它是基于拓撲獨立的路由法則；具有非精確路由指

3、向,每個節(jié)點只指向有限個其他可達節(jié)點,按照路由法則將信息轉發(fā)到記錄中“最近”指向節(jié)點去；非全局路由維護,每個節(jié)點只需獨立維護各自指定節(jié)點的可達性。
　　 本文研究了把VRR(Virtual Ring Routing)和ROFL(Routing on Flat Labels)應用到BGP路由協(xié)議的可行性,并把這種方法稱為源管理路由方案。有如下發(fā)現:節(jié)點命名對路由性能有明顯的影響,而在VRR(Virtual Ring Routing

4、)和ROFL(Routingon Flat Labels)中命名是隨機的；拓撲相關的命名策略并不能提高路由性能；核心AS在源管理路由算法中起到重要作用。
　　 探討了源管理路由方案在基于AS商業(yè)關系的實際網絡拓撲中的可行性,發(fā)現:直接把源管理路由方案應用實際AS商業(yè)關系的網絡拓撲中,源管理路由方案得到的路徑并不是都符合BGP路由策略；提出基于分層源管理路由方案建立和維護多條虛擬鄰居路徑的方法以提供基于AS商業(yè)關系的完備路由信息,

5、確保完整路徑的有效性。
　　 提出了源管理路由算法的理論模型,該路由算法思想雖然簡單,卻沒有理論模型來描述它的路由選擇問題以及計算任意節(jié)點間的路徑長度,尤其是從理論上來評估源管理路由算法的性能。模型中通過利用虛擬環(huán)路徑這一獨特想法來描述路徑選擇問題,根據源節(jié)點和目的節(jié)點名字在標識符數值上的距離,分析在虛擬環(huán)上出現的所有可能路徑的概率,計算在虛擬環(huán)上路徑的平均跳數,最終估算出實際物理路徑的長度。分析影響路由性能的因素,網絡中的節(jié)點

6、數量,虛擬鄰居路徑的長度,源節(jié)點目的節(jié)點名字在標識符數值上的距離以及網絡拓撲都影響著源管理路由算法路徑長度的分布。通過全面深入的分析源管理路由算法,對其路由效率及可擴展性有了完整的認識,為適應于未來核心網絡路由打下堅實的理論基礎。
　　 針對源管理路由方案中核心節(jié)點路由表可能會過于龐大的問題,研究了通過命名來壓縮路由表的可能性。提出了一種基于概率的啟發(fā)性命名算法,通過節(jié)點到達連續(xù)地址節(jié)點的下一跳盡可能相同(并將這些地址是連續(xù)的節(jié)