IP路由查找算法

主要內(nèi)容路由查找問(wèn)題的產(chǎn)生背景典型的IPv4路由查找算法基于IXP2800的高速IPv6路由查找算法及實(shí)現(xiàn)參考文獻(xiàn)SurveyandTaxonomyofIPAddressLookupAlgorithms.IEEENetwork,2001.High-performanceIPv6ForwardingAlgorithmforMulti-coreandMultithreadedNetworkProcessors.InProceedingsofPPoPP’06,2006.地址前綴與地址聚合IP編址方案最初使用一個(gè)簡(jiǎn)單的二層結(jié)構(gòu)：上層為網(wǎng)絡(luò)，下層為主機(jī)。這個(gè)分層結(jié)構(gòu)反映在IP地址上，就是IP地址由兩個(gè)部分組成：網(wǎng)絡(luò)地址部分（地址前綴）和主機(jī)地址部分。地址前綴的兩種表示方法：不大于32比特的比特串跟上一個(gè)*，比如：1000001001010110*帶點(diǎn)十進(jìn)制表示加上地址前綴長(zhǎng)度，比如：130.86/16地址聚合（addressaggregation）：連接到同一個(gè)網(wǎng)絡(luò)的所有主機(jī)，在轉(zhuǎn)發(fā)表中對(duì)應(yīng)一個(gè)入口，即允許使用前綴來(lái)表示一組地址。轉(zhuǎn)發(fā)表舉例基于類的編址方案基于類的編址方案的缺點(diǎn)地址空間利用率低，地址短缺問(wèn)題日益突顯。核心路由器的轉(zhuǎn)發(fā)表規(guī)模急劇擴(kuò)大，導(dǎo)致查表時(shí)間及內(nèi)存需求增加。無(wú)類域間路由（CIDR）編址方案摒棄傳統(tǒng)的基于類的地址分配方式，允許使用任意長(zhǎng)度的地址前綴，有效提高地址空間的利用率。允許任意地、遞歸地進(jìn)行地址聚合，減少轉(zhuǎn)發(fā)表中的入口數(shù)目，有效解決路由表爆炸的問(wèn)題。地址聚合的例子（1）地址聚合的例子（2）路由器的地址查找問(wèn)題就是要從轉(zhuǎn)發(fā)表中查找匹配數(shù)據(jù)包目的地址的最長(zhǎng)的地址前綴。基于類的地址查找轉(zhuǎn)發(fā)表中的前綴被組織成三張表（分別對(duì)應(yīng)A、B、C三類地址前綴），地址查找就是在對(duì)應(yīng)的轉(zhuǎn)發(fā)表中進(jìn)行精確匹配查找。查找過(guò)程如下：根據(jù)IP地址的前幾位得到該地址所屬的地址類別根據(jù)地址類別提取目的地址中的網(wǎng)絡(luò)地址部分查找相應(yīng)的哈希表或進(jìn)行二分查找最長(zhǎng)地址前綴匹配的困難轉(zhuǎn)發(fā)表中的目的前綴具有任意的長(zhǎng)度，并且不再對(duì)應(yīng)地址的網(wǎng)絡(luò)部分，因而前綴長(zhǎng)度無(wú)法從目的地址本身獲得。轉(zhuǎn)發(fā)表查找要求采用最長(zhǎng)前綴匹配查找而不是精確匹配查找。地址查找在數(shù)值和長(zhǎng)度兩個(gè)維度上進(jìn)行。地址查找算法的評(píng)價(jià)標(biāo)準(zhǔn)查找速度存儲(chǔ)空間預(yù)處理和更新速度算法實(shí)現(xiàn)的靈活性（同時(shí)具有硬件和軟件實(shí)現(xiàn)方式）算法的可擴(kuò)展性（路由表規(guī)模，IPv6）經(jīng)典的IP地址查找算法線性表查找二進(jìn)制Trie樹(shù)（BinaryTrie）路徑壓縮Trie樹(shù)（path-compressedTrie）二進(jìn)制Trie樹(shù)采用基于樹(shù)的數(shù)據(jù)結(jié)構(gòu)，通過(guò)前綴中每一位的值來(lái)決定樹(shù)的分支。處于第L層的節(jié)點(diǎn)代表了一個(gè)地址前L比特均相同的地址空間，這L個(gè)比特串就是由從根節(jié)點(diǎn)到這個(gè)節(jié)點(diǎn)路徑上的L比特組成。與地址前綴對(duì)應(yīng)的節(jié)點(diǎn)包含了轉(zhuǎn)發(fā)信息。Trie樹(shù)代表的地址空間結(jié)構(gòu)Trie樹(shù)的查找從根節(jié)點(diǎn)開(kāi)始每次一位地查找：當(dāng)?shù)刂分械南鄳?yīng)位為0時(shí)選擇左分支，為1時(shí)選擇右分支。當(dāng)遇到那些對(duì)應(yīng)地址前綴的中間節(jié)點(diǎn)時(shí)，將此地址前綴記錄為目前為止找到的最長(zhǎng)地址前綴。當(dāng)不再有分支可以選擇時(shí)搜索過(guò)程結(jié)束，此時(shí)被記錄的最長(zhǎng)地址前綴就是查找結(jié)果。以上查找方法為基于長(zhǎng)度的順序前綴查找，每搜索一步，搜索空間就縮減一半，當(dāng)縮減為1時(shí)搜索結(jié)束。Trie樹(shù)的更新插入一個(gè)地址前綴以該前綴項(xiàng)為關(guān)鍵字在Trie樹(shù)中進(jìn)行查找；若查找過(guò)程在一個(gè)中間節(jié)點(diǎn)終止，將此節(jié)點(diǎn)標(biāo)記為前綴節(jié)點(diǎn)，并在此中間節(jié)點(diǎn)中加入前綴轉(zhuǎn)發(fā)信息；若不再有分支可選取，需要插入必要的分支節(jié)點(diǎn)。刪除一個(gè)地址前綴以該前綴項(xiàng)為關(guān)鍵字在Trie樹(shù)中進(jìn)行查找；若查找過(guò)程在一個(gè)中間節(jié)點(diǎn)終止，將此節(jié)點(diǎn)標(biāo)記為非前綴節(jié)點(diǎn)，刪除此節(jié)點(diǎn)的轉(zhuǎn)發(fā)信息；若查找過(guò)程終止于葉子節(jié)點(diǎn)，除了刪除該節(jié)點(diǎn)之外，還需要根據(jù)情況刪除其它一些內(nèi)部節(jié)點(diǎn)。路徑壓縮Trie樹(shù)路徑壓縮Trie樹(shù)壓縮單向分支每個(gè)節(jié)點(diǎn)需要維護(hù)一個(gè)變量，指示下一個(gè)需要檢查的比特位前綴節(jié)點(diǎn)需要保存地址前綴的比特串路徑壓縮Trie樹(shù)（續(xù)）當(dāng)二進(jìn)制Trie樹(shù)中的前綴分布較稀疏時(shí)，路徑壓縮算法能夠獲得良好的壓縮效果。二進(jìn)制Trie樹(shù)和路徑壓縮Trie樹(shù)的不足是查找過(guò)程需要大量的存儲(chǔ)器訪問(wèn)操作。研究表明，對(duì)于一個(gè)具有47113個(gè)前綴表項(xiàng)的典型骨干網(wǎng)路由器，使用BSDTrie會(huì)創(chuàng)建93304個(gè)節(jié)點(diǎn)，樹(shù)的最大高度為26，平均高度為20。而對(duì)于同樣的前綴表，二進(jìn)制Trie樹(shù)的最大高度為30，平均高度為22。查找算法使用的輔助策略（1）前綴擴(kuò)展（prefixexpansion）將一條長(zhǎng)度較短的地址前綴展開(kāi)成多條長(zhǎng)度較長(zhǎng)的地址前綴集合，這個(gè)前綴集的轉(zhuǎn)發(fā)信息就是原來(lái)地址前綴所對(duì)應(yīng)的轉(zhuǎn)發(fā)信息。例如：前綴1*的地址范圍可以用前綴10*和11*來(lái)涵蓋，也可以用前綴100*、101*、110*和111*來(lái)涵蓋。前綴擴(kuò)展的目的是為了獲得一組長(zhǎng)度差異較小的前綴集合，以利于快速查找。查找算法使用的輔助策略（2）獨(dú)立前綴轉(zhuǎn)化將地址前綴集轉(zhuǎn)化為一組不相交的前綴集所有的前綴節(jié)點(diǎn)都出現(xiàn)在葉子節(jié)點(diǎn)查找算法使用的輔助策略（3）壓縮技術(shù)壓縮前綴擴(kuò)展造成的信息冗余從壓縮數(shù)據(jù)中恢復(fù)原有信息不應(yīng)過(guò)于復(fù)雜優(yōu)化技術(shù)的應(yīng)用在滿足一定約束條件的前提下找到最佳的前綴集，比如在滿足查找速度的前提下減少算法的存儲(chǔ)空間。存儲(chǔ)層次設(shè)計(jì)盡量減小查找算法的數(shù)據(jù)結(jié)構(gòu)所占據(jù)的存儲(chǔ)空間，從而可以將數(shù)據(jù)結(jié)構(gòu)放入較高的存儲(chǔ)層次中。應(yīng)最小化訪存次數(shù)多分支Trie樹(shù)的基本算法查找的每一步檢查地址中的多個(gè)比特。查找步寬為k的多分支Trie樹(shù)，每個(gè)節(jié)點(diǎn)的最大分支數(shù)為2k

。同一層中不同子樹(shù)的步寬可以相同（固定步寬多分支Trie），也可以不同（可變步寬多分支Trie）。圖固定步寬的多分支Trie實(shí)現(xiàn)簡(jiǎn)單，但會(huì)浪費(fèi)較多的存儲(chǔ)空間，可變步寬的多分支Trie則相反。前綴表中的地址前綴必須轉(zhuǎn)換成多分支Trie查找能夠允許的地址前綴。圖多分支Trie樹(shù)的深度有很大縮減，因而提高了查找效率。多分支Trie的查找過(guò)程類似于二進(jìn)制Trie。多分支Trie的更新過(guò)程比二進(jìn)制Trie復(fù)雜：插入一個(gè)前綴時(shí)，需要找到相應(yīng)的subtrie，對(duì)前綴進(jìn)行擴(kuò)展，然后插入。刪除一個(gè)前綴時(shí)，需要?jiǎng)h除所有擴(kuò)展的前綴。需要額外的數(shù)據(jù)結(jié)構(gòu)保存原始前綴?？勺儾綄捙c固定步寬的多分支Trie樹(shù)多分支Trie例1多分支Trie例2在地址擴(kuò)展過(guò)程中，如果擴(kuò)展的地址前綴與原來(lái)的地址前綴沖突，應(yīng)保留原來(lái)的地址前綴。多分支Trie的優(yōu)化（1）步寬的選擇步寬的選擇是在算法查找速度、存儲(chǔ)空間和更新復(fù)雜度之間的折衷。一種較自然的做法是根據(jù)實(shí)際地址前綴的分布來(lái)選擇合適的步寬。使用某種優(yōu)化策略，使在搜索深度固定的情況下整個(gè)樹(shù)的存儲(chǔ)空間最小。

多分支Trie的優(yōu)化（2）24-8多分支trie快速查找算法的硬件實(shí)現(xiàn)查找最多只需要兩次訪存；采用硬件流水線技術(shù)，實(shí)際上只需要一次訪存的時(shí)間。算法要求的內(nèi)存空間比較大。TBL24TBLlong多分支Trie的優(yōu)化（3）壓縮在前綴擴(kuò)展的過(guò)程中，前綴的轉(zhuǎn)發(fā)信息被擴(kuò)展到了trie樹(shù)的多個(gè)連續(xù)節(jié)點(diǎn)中，造成大量的信息冗余。壓縮因前綴擴(kuò)展造成的大量冗余信息，減少算法占用的內(nèi)存空間?；谇熬Y長(zhǎng)度的二分查找前綴范圍查找任何地址區(qū)域所對(duì)應(yīng)的最長(zhǎng)前綴應(yīng)該是包含此區(qū)域的前綴中范圍最窄的那一項(xiàng)。地址區(qū)間的二分查找樹(shù)最長(zhǎng)前綴匹配查找變成在左端點(diǎn)集合中尋找離目的地址最近的左端點(diǎn)。路由表規(guī)模很大時(shí)，查找效果不好。更新性能較差?；赥CAM的硬件查找TCAM中每一個(gè)表項(xiàng)以<地址，掩碼>序偶的形式保存。TCAM在所有匹配的表項(xiàng)中選取地址最低的表項(xiàng)作為最后的結(jié)果，所以必須將前綴較長(zhǎng)的關(guān)鍵字表項(xiàng)存儲(chǔ)在低地址。查找速度快，實(shí)現(xiàn)簡(jiǎn)單。完成一次查找只需三步操作，采用流水線技術(shù)可以進(jìn)一步提高查找速度。容量小，代價(jià)高，功耗大，更新復(fù)雜（關(guān)鍵字需要排序）。IPv6地址查找的困難前綴更長(zhǎng)：IPv6地址長(zhǎng)度為128比特，路由器只轉(zhuǎn)發(fā)AggregatableGlobalUnicastAddress，這類地址的前3個(gè)比特總為001，且最后64比特用于標(biāo)識(shí)網(wǎng)絡(luò)接口。規(guī)模更大：目前IPv6尚未廣泛使用，IPv6路由表都很?。ɑ静怀^(guò)1000個(gè)前綴項(xiàng)），但估計(jì)的前綴項(xiàng)應(yīng)在50萬(wàn)條左右。IPv4路由查找算法不能直接應(yīng)用于IPv6：基于trie的算法訪存次數(shù)很多，或內(nèi)存需求很大，像Stanford算法直接應(yīng)用于IPv6查找會(huì)造成高達(dá)幾百兆的內(nèi)存需求?；赥CAM的方法不適用于規(guī)模巨大的表?；诘刂非熬Y長(zhǎng)度的二分查找的更新復(fù)雜度很大，無(wú)法接受。TrieC算法設(shè)計(jì)思想采用改進(jìn)的Stanford算法保留Stanford算法高速查找、易于更新及硬件實(shí)現(xiàn)復(fù)雜度低等優(yōu)點(diǎn)，但通過(guò)壓縮技術(shù)使得算法對(duì)存儲(chǔ)空間的需求量在可接受的范圍內(nèi)。已有IPv6路由表的統(tǒng)計(jì)結(jié)果和地址分配策略表明，長(zhǎng)度大于48比特的前綴比例很低，僅為5%左右，因此可對(duì)IPv6地址的高48位采用多分支trie進(jìn)行查找，剩余的16比特直接采用hash查找。根據(jù)IPv6地址前綴的分布特點(diǎn)，構(gòu)造查找步寬為24-8-8-8-16的五層多分支TrieC樹(shù)，限制最壞情況下路由查找的訪存次數(shù)。TrieC算法設(shè)計(jì)思想（續(xù)）使用壓縮前綴擴(kuò)展技術(shù)消除冗余信息：采用一個(gè)位向量記錄每個(gè)數(shù)據(jù)塊的起始位置，數(shù)據(jù)塊中的下一跳信息只在表是存儲(chǔ)一次。64條前綴壓縮成一個(gè)表項(xiàng)，用高18比特作為新表項(xiàng)的索引，低6比特用作另一個(gè)索引查找位向量。TrieC樹(shù)結(jié)構(gòu)構(gòu)造查找步寬為24-8-8-8-16的五層多分支TrieC樹(shù)：根節(jié)點(diǎn)采用TrieC15/6數(shù)據(jù)結(jié)構(gòu)，存儲(chǔ)長(zhǎng)度為[1,24]比特的地址前綴；第二層至第四層均采用TrieC4/4數(shù)據(jù)結(jié)構(gòu)，分別存儲(chǔ)長(zhǎng)度為[25,32]、[33,40]、[41,48]比特的地址前綴；第五層采用hash16數(shù)據(jù)結(jié)構(gòu)，存儲(chǔ)長(zhǎng)度為[49,64]比特的地址前綴。每一層節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)中都有一個(gè)標(biāo)志位用于指示是否需要繼續(xù)查找下一層節(jié)點(diǎn)。網(wǎng)絡(luò)處理算法在IXP2800上高效實(shí)現(xiàn)的關(guān)鍵減少訪存次數(shù)（TrieC限制了最大訪存次數(shù)）壓縮算法占用的內(nèi)存，使得算法的數(shù)據(jù)結(jié)構(gòu)可放在較高速的存儲(chǔ)器中（TrieC壓縮了由傳統(tǒng)前綴擴(kuò)展造成的存儲(chǔ)冗余）選擇合適的指令合理分配數(shù)據(jù)合理劃分任務(wù)使用各種延遲隱藏技術(shù)指令選擇以下指令對(duì)TrieC的高速實(shí)現(xiàn)非常重要：POP_COUNT指令：可在3個(gè)時(shí)鐘周期內(nèi)計(jì)算32位寄存器中1的個(gè)數(shù)，在RISC結(jié)構(gòu)上通常需要100多條指令。分支跳轉(zhuǎn)指令：可以在1條指令中完成分支跳轉(zhuǎn)操作，而在RISC體系結(jié)構(gòu)上通常至少需要3條指令。硬件CRC：使用微引擎內(nèi)部的CRC單元提供對(duì)TrieC樹(shù)最后一層的哈希計(jì)算（5個(gè)時(shí)鐘周期）。數(shù)據(jù)分配IXP2800具有4個(gè)可并行訪問(wèn)的SRAM控制器和3個(gè)DRAM控制器，每個(gè)DRAM控制器支持4個(gè)可交錯(cuò)訪問(wèn)的存儲(chǔ)器bank。采用以下四種數(shù)據(jù)分配模式進(jìn)行實(shí)驗(yàn)，只有前三種能夠在最壞情況下支持OC-192線速：所有TrieC表存儲(chǔ)在一個(gè)SRAM控制器中TrieC表按照TrieC樹(shù)的層次存儲(chǔ)在四個(gè)SRAM控制器中TrieC表按照TrieC樹(shù)的層次混合存儲(chǔ)在SRAM和DRAM控制器中所有的TrieC表存儲(chǔ)在DRAM控制器中，此時(shí)TrieC數(shù)據(jù)結(jié)構(gòu)被重新設(shè)計(jì)以適應(yīng)DRAM存儲(chǔ)器的訪問(wèn)特性。任務(wù)切分IXP2800支持兩種任務(wù)切分模式：Multi-processing：包括微引擎內(nèi)的多線程技術(shù)和基于多個(gè)微引擎的多線程技術(shù)，易于實(shí)現(xiàn)，易于平衡負(fù)載，但每個(gè)任務(wù)所用的資源不宜過(guò)多。Context-pipelining：將一個(gè)任務(wù)切分成若干個(gè)子任務(wù)分配到多個(gè)微引擎上執(zhí)行，子任務(wù)之間通過(guò)鄰居環(huán)或Scratchring連接形成流水線。每個(gè)任務(wù)可用的資源較多，但子任務(wù)間通信負(fù)載較高，且子任務(wù)間不易平衡負(fù)載。實(shí)驗(yàn)了multi-processing、Context-pipelining和混合三種模式，發(fā)現(xiàn)multi-processing模式更適合TrieC算法的實(shí)現(xiàn)。長(zhǎng)延遲隱藏TrieC算法是實(shí)現(xiàn)需要頻繁進(jìn)行I/O操作，I/O操作是典型的長(zhǎng)延遲操作，隱藏訪存延遲的手段包括：多線程技術(shù)是隱藏長(zhǎng)延遲的主要手段。I/O向量化：訪問(wèn)存儲(chǔ)器中連續(xù)存儲(chǔ)的內(nèi)容可以通過(guò)一條I/O指令來(lái)完成。IXP2800使用一條I/O指令最多可以訪問(wèn)64個(gè)字節(jié)（SRAM），所以TrieC結(jié)構(gòu)的大小都限制在64個(gè)字節(jié)內(nèi)。I/O交錯(cuò)（延遲槽填充）：在IXP2800上，分支指令和線程切換指令都會(huì)導(dǎo)致1個(gè)或者多個(gè)延遲槽。將無(wú)依賴關(guān)系的指令安排在分支指令或線程切換指令附近，以便讓IXP編譯器用它們填充到這些指令產(chǎn)生的延遲槽中。TrieC算法對(duì)表空間的壓縮性能GroupA：參考CERNET、6Bone、6Net和Telstra的IPv6路由表前綴長(zhǎng)度分布而生成，代表了目前為止實(shí)際的IPv6路由表。GroupB：采用M.Wang等人提出的非隨機(jī)IPv6路由表生成算法產(chǎn)生，代表理想狀態(tài)的IPv6路由表。GroupC：由GroupA和GroupB的算術(shù)平均生成。Trie