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

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

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

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

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

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

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

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