高速路由器的數(shù)據(jù)轉(zhuǎn)發(fā)技術(shù)研究.pdf

1、隨著光纖通信技術(shù)的飛速發(fā)展，鏈路的傳輸能力迅速提升，而路由器轉(zhuǎn)發(fā)數(shù)據(jù)的能力相對落后，其主要原因之一是路由查找的困難。路由查找是為到達路由器的數(shù)據(jù)包找到轉(zhuǎn)發(fā)端口，其依據(jù)是路由表。一方面，隨著因特網(wǎng)規(guī)模擴大，路由表急劇膨脹，需要更大的存儲空間，導致路由查找速度降低。另一方面，由于路由表結(jié)構(gòu)的復雜，必須采用最長地址前綴匹配算法，既要比較目的IP地址和地址前綴的值，又要比較地址前綴的長度—二維查找。這些特點說明了路由查找技術(shù)研究的意義和難度。面

2、對不斷膨脹的路由表和高速數(shù)據(jù)轉(zhuǎn)發(fā)的需要，路由查找技術(shù)的研究受到廣泛的重視。傳統(tǒng)的二維查找算法不能滿足高速數(shù)據(jù)轉(zhuǎn)發(fā)的要求，許多研究者提出了新的解決方法，路由器的數(shù)據(jù)轉(zhuǎn)發(fā)能力有明顯提高。仍然，有許多問題需要研究，如：（1）在提高路由查找效率的同時，如何保證高效的路由更新操作？（2）基于硬件的算法能夠提高路由查找的速率，但需要克服高能耗、路由更新的困難；（3）設計適應IPv6地址結(jié)構(gòu)的算法等。針對這些問題，本文選擇了“高速數(shù)據(jù)轉(zhuǎn)發(fā)引擎的關鍵技

3、術(shù)研究”這一課題，對數(shù)據(jù)轉(zhuǎn)發(fā)引擎的主要技術(shù)，如交換結(jié)構(gòu)、調(diào)度算法、路由查找等進行了系統(tǒng)的分析。然后，基于路由表結(jié)構(gòu)的分析，提出了一種研究路由查找技術(shù)的新思路。本文從分析路由表中地址前綴之間的關系出發(fā)，提出了一種分類方法，將地址前綴分為：獨立前綴、根前綴、子前綴。然后，采用數(shù)據(jù)結(jié)構(gòu)Trie描述地址前綴，定義了地址前綴的級別，提出了路由表結(jié)構(gòu)的概念。通過分析實際路由表，發(fā)現(xiàn)：各級別地址前綴數(shù)的比例相對固定；級別的最大值遠小于理論值；與同一I

4、P地址匹配的地址前綴數(shù)較小，即只需要在較少的地址前綴中搜索最長匹配前綴等。通過研究路由發(fā)布行為對路由表的增長、結(jié)構(gòu)變化的影響，發(fā)現(xiàn)：地址分配策略對路由表中獨立前綴、根前綴的長度分布會產(chǎn)生顯著的影響，但對子前綴的長度分布沒有明顯的影響；用戶發(fā)布分段的地址前綴是導致獨立前綴增長的主要原因之一；發(fā)布子前綴是導致路由查找困難的根本原因等。利用地址前綴級別的定義，提出了一種基于層次劃分技術(shù)的路由查找算法。路由表中每項地址前綴有唯一的級別，由此，提

5、出了一種按層次劃分路由表的方法，將路由表按級別劃分為幾個部分。各部分路由表中地址前綴互不相交，對于任何IP地址最多有一個匹配的地址前綴，因而在各部分路由表中可采用精確匹配算法查找路由。然后，在各部分路由表中查找的結(jié)果中，選擇最長匹配的地址前綴。這樣，將最長前綴匹配算法轉(zhuǎn)化為精確匹配算法。采用并行結(jié)構(gòu)，路由查找的復雜度為：O(1)。與現(xiàn)有基于劃分技術(shù)的路由查找算法相比，算法簡單，易于硬件實現(xiàn)，且路由更新效率有顯著的提高。通過分析基于三元內(nèi)

6、容尋址存儲器（TCAM）數(shù)據(jù)轉(zhuǎn)發(fā)引擎的特征，提出了一種路由更新機制。當前，大多采用TCAM來實現(xiàn)基于硬件的路由查找，數(shù)據(jù)轉(zhuǎn)發(fā)引擎有較高的效率，但其中的地址前綴必須有序排列，才能找到最長匹配的地址前綴。這樣帶來了路由更新的困難。根據(jù)路由表結(jié)構(gòu)的特征，所有地址前綴可以按其級別劃分，同一級別地址前綴在TCAM中連續(xù)存儲，各級別中的地址前綴無需排序，即在TCAM中地址前綴按級別存儲。這樣，每次插入地址前綴時，移動操作的數(shù)量只與劃分路由表之后插入

7、的地址前綴有關，與初始的地址前綴無關。最壞情況下，插入地址前綴的復雜度為：O(W)，W為父前綴數(shù)。在仿真實驗中，與現(xiàn)有的算法相比平均插入操作復雜度減少90﹪。利用因特網(wǎng)數(shù)據(jù)流的特征，提出了一種優(yōu)化TCAM能耗的結(jié)構(gòu)。在基于TCAM的數(shù)據(jù)轉(zhuǎn)發(fā)引擎中，每次路由查找并行操作，提高了路由查找的速率，同時帶來了高能耗。根據(jù)地址前綴分類方法，提出了一種二級路由查找結(jié)構(gòu)，即獨立前綴和根前綴在第一級，子前綴在第二級，且按所屬的根前綴不同將子前綴分為小塊