信息網(wǎng)絡(luò)與協(xié)議

第六章路由和交換主要內(nèi)容概述路由查找算法交換結(jié)構(gòu)路由和交換路由代表更宏觀的概念，是將分組從網(wǎng)絡(luò)中的一個網(wǎng)絡(luò)投遞到另一個網(wǎng)絡(luò)的過程需要網(wǎng)絡(luò)中節(jié)點協(xié)作運行路由協(xié)議交換是指在同一個網(wǎng)絡(luò)節(jié)點內(nèi)的分組傳輸，是指將分組從一個端口（輸入端口）轉(zhuǎn)發(fā)到另一個端口（輸出端口）的過程屬于網(wǎng)絡(luò)設(shè)備自己的功能基于轉(zhuǎn)發(fā)表，查找算法和交換結(jié)構(gòu)路由協(xié)議、路由表和轉(zhuǎn)發(fā)表路由器之間通過路由協(xié)議交互信息執(zhí)行路由算法生成路由表<前綴/網(wǎng)絡(luò)號，下一跳IP地址>轉(zhuǎn)發(fā)表是基于路由表生成的<前綴/網(wǎng)絡(luò)號，下一跳IP地址，輸出端口等>在路由器或者交換機上，根據(jù)轉(zhuǎn)發(fā)表來決定分組的輸出端口IP分組目的IP地址交換結(jié)構(gòu)決定路由器性能：（1）路由查找算法：如何快速地決定輸出端口（2）交換結(jié)構(gòu)：如何快速地交換到輸出端口轉(zhuǎn)發(fā)表輸入端口輸出端口IP路由器功能數(shù)據(jù)路徑功能根據(jù)分組目的IP地址查找轉(zhuǎn)發(fā)表通過交換結(jié)構(gòu)轉(zhuǎn)發(fā)到輸出端口輸出端口調(diào)度和隊列管理控制面功能系統(tǒng)配置和管理運行路由協(xié)議，構(gòu)建路由表主要內(nèi)容概述路由查找算法交換結(jié)構(gòu)前綴最長匹配采用CIDR后，IP地址中前綴（網(wǎng)絡(luò)號的長度）不固定，可能匹配到多個轉(zhuǎn)發(fā)表項采用前綴最長匹配208.12.21.4500010101前綴最長匹配前綴最長匹配并不簡單！IP地址中沒有攜帶任何前綴長度信息有可能需要對轉(zhuǎn)發(fā)表中的所有表項都進行匹配效率低！為此，我們需要提出更加高效的路由查找算法！核心路由器經(jīng)常有上萬甚至幾十萬條前綴性能度量查找速度決定鏈路帶寬（10Gbps鏈路要求每秒轉(zhuǎn)發(fā)31.25*106個分組，最小IP分組長度為40字節(jié)）存儲（空間）需求存儲訪問速度、功耗基于緩存的軟件算法更新代價在峰值時，Internet上每秒鐘的BGP路由更新有幾百次，要求能夠處理每秒上千次更新可擴展性轉(zhuǎn)發(fā)表預(yù)計每年都在增加實現(xiàn)的靈活性既能軟件實現(xiàn)，也能硬件實現(xiàn)分類基于Trie的算法BinaryTrieTrie+Bitmap基于硬件的算法基于Trie的算法路由查找算法的關(guān)鍵是如何用一個高效的數(shù)據(jù)結(jié)構(gòu)來表示轉(zhuǎn)發(fā)表，基于Trie的方法是用Trie來表示轉(zhuǎn)發(fā)表在以下的敘述中，為了簡單起見，在不影響算法的有效性的情況下，轉(zhuǎn)發(fā)表中的表項用其所對應(yīng)的前綴來表示，并且在所有例子中我們都假設(shè)IP地址長度為8比特Trie：ReTrieval，一種樹型結(jié)構(gòu)，在路由查找算法中，使用Trie來組織轉(zhuǎn)發(fā)表，從根節(jié)點開始的路徑對應(yīng)著轉(zhuǎn)發(fā)表表項的前綴基于Trie的算法BinaryTrieLCTriepressedTrieMulti-BitTrieLuleaTreebitmap算法IPv6路由查找數(shù)據(jù)結(jié)構(gòu)使用二進制Trie來組織轉(zhuǎn)發(fā)表Trie中的每個節(jié)點有兩個指針：0-指針和1-指針，即每個節(jié)點最多有兩個子節(jié)點從根開始到節(jié)點X的路徑上的比特串代表了X所對應(yīng)的前綴P對于節(jié)點X，如果其前綴對應(yīng)著前綴數(shù)據(jù)庫中的某個表項，則該節(jié)點稱為前綴節(jié)點，前綴節(jié)點包含了下一跳信息前綴數(shù)據(jù)庫：轉(zhuǎn)發(fā)表中所有前綴的集合P110P20P30011011111000P4P5P6P7P8P9NextHopInformation(Ifaprefixnode)0-Pointer1-PointerPrefixDatabaseP1*

P2 1*

P3 00*

P4 101*

P5 111*

P6 1000*

P7 11101*

P8 111001*

P9 1000011*P110P20P30011011111000P4P5P6P7P8P9NodeStructure從根到X的路徑上的比特串代表了X所對應(yīng)的前綴P灰色節(jié)點為前綴節(jié)點，存儲下一跳信息，用前綴P來表示P110P20P30011011111000P4P5P6P7P8P9假設(shè)路由器接收到1個IP分組的目的地址為111010000路由查找返回其下一跳信息對于BinaryTrie，每經(jīng)過一次查找，可能的前綴集合減半，直到只有一個前綴為止如果不使用BinaryTrie，則查找時可能需要去匹配轉(zhuǎn)發(fā)表中的每個表項增加前綴（轉(zhuǎn)發(fā)表項）P110P20P30011011111000P4P5P6P7P8P9如果前綴對應(yīng)的節(jié)點已經(jīng)存在，則將其標(biāo)識為前綴節(jié)點，并且增加其在轉(zhuǎn)發(fā)表中的下一跳信息，例如增加前綴100*如果前綴對應(yīng)的節(jié)點不存在，則添加該節(jié)點，包括到該節(jié)點的完整路徑，例如增加前綴10100*00刪除前綴（轉(zhuǎn)發(fā)表項）P110P20P30011011111000P4P5P6P7P8P9如果前綴對應(yīng)的節(jié)點有子節(jié)點，則直接將其標(biāo)識為非前綴節(jié)點，并且刪除其下一跳信息，例如刪除前綴1000*如果前綴對應(yīng)的節(jié)點沒有子節(jié)點，則將該節(jié)點刪除，并且檢查其父節(jié)點，如果父節(jié)點有另一個子節(jié)點或者是前綴節(jié)點，則刪除操作終止，否則將父節(jié)點刪除，再查看它的上一級節(jié)點，執(zhí)行相同操作，例如刪除前綴111001*性能最差情況下，查找算法需要遍歷Trie的所有層次，所以最差情況下需要有W次存儲器訪問W為前綴的最大長度，對于IPv4為32查找復(fù)雜度和更新復(fù)雜度為O(W)最差情況下，增加一個前綴，需要增加W個節(jié)點存儲復(fù)雜度為O(NW)N為轉(zhuǎn)發(fā)表中的前綴數(shù)量問題P110P20P30011011111000P4P5P6P7P8P9返回其下一跳信息每個節(jié)點需要空間來保留指向下一跳信息和子節(jié)點的指針由于使用前綴最長匹配，還有可能存在回溯操作可以采用完全Trie和分離前綴Trie來避免這些情況查找10010011回溯P10P4Trie中的每個葉子節(jié)點都代表一個前綴，查找的時候直接用IP的所有比特去查找，從而避免回溯操作問題：存儲開銷太大，對于32比特的IPv4地址，需要的存儲空間為O(232)0P3001110P2P31P30P11P1P20P21P2完全Trie分離的前綴Trie（DisjointPrefixTrie）：給那些只有一個葉子節(jié)點添加另一個葉子節(jié)點，新的葉子節(jié)點的信息使用距離其最近的前綴節(jié)點，這個操作也被稱為LeafPushingP10P40010P3P21P1LeafPushing可以減少存儲開銷，因為此時每個節(jié)點只需要使用一個指針，要么是指向下一跳信息，要么是指子節(jié)點

但是LeafPushing增加更新復(fù)雜度！P2分離前綴TrieP2基于Trie的算法BinaryTrieLCTriepressedTrieMulti-BitTrieLuleaTreebitmap算法IPv6路由查找概述LCTrie:LevelCompressionTrie基本思想PathCompressionMulti-bitTrieP1100P3110P4CompressionP40010P31P1P2Multi-bit減少存儲，提高查找速度1PathCompressionCompression：Trie中只有一個子節(jié)點的非前綴節(jié)點能夠被刪除節(jié)點保持Compression相關(guān)信息skipvalue：指示路徑上有多少個比特被跳過segment：指示最后一次跳過操作以來具體遺漏的比特串P110P20P30011011111000P4P5P6P7P8P9P11P20P3

Skip=101011000P4Skip=1

P5P6

Skip=1P7P8

Skip=1P9

Skip=2

’11’CompressionTrie例子NextHopInformation(Ifaprefixnode)0-Pointer1-PointerSkipValueSegmentNodeStructureP11P20P3

Skip=1

Seg=001011000P4Seg=1

Skip=1

P5P6

Skip=1

Seg=0P7P8

Skip=1

Seg=1P9

Skip=2

Seg=1111101000PathCompression性能路徑壓縮可以有效地減少稀疏binarytrie的高度在最差情況下，如果為完全樹時，沒有壓縮的可能，因此采用路徑壓縮后查詢和更新復(fù)雜度與binarytrie一樣，都是O(W)Multi-bitTrie查找時同時檢查多個比特，稱為查找步長（Stride）如果前綴長度不為步長的整數(shù)倍，則對其進行擴充例如步長為3，對于前綴1*可以擴充為100,101,110,111步長為k，則Trie中的每個節(jié)點的條目數(shù)量為2k每個條目組成：<下一跳信息，指向下一個子節(jié)點的指針（可以為空）>P3--P3--P5P1--P1--P2P4--P2--000001010011100101110111PrefixPtrRootNodeP6--P6----P6--P6--------------000001010011100101110111PrefixPtrNode1--------P9----------P9--P9--P9--000001010011100101110111PrefixPtrNode3----P8------P7--P7--------------000001010011100101110111PrefixPtrNode2查找111010000對應(yīng)表項Multi-bitTrie(Stride=3)PrefixDatabaseP1*

P2 1*

P3 00*

P4 101*

P5 111*

P6 1000*

P7 11101*

P8 111001*

P9 1000011*Multi-bitTrieK-bitTrie可以將查找速度提高了K倍存儲空間大！LeafPushing優(yōu)化節(jié)點上的每個條目要么包含一個指針，要么包含下一跳信息相當(dāng)于把下一跳信息Pushdown到葉子節(jié)點存儲空間減少為1/2PrefixDatabaseP1*

P2 1*

P3 00*

P4 101*

P5 111*

P6 1000*

P7 11101*

P8 111001*

P9 1000011*P3--P3--P5P1--P1--P2P4--P2--000001010011100101110111Prefix/PtrRootNodeP6--P6----P6--P6--------------000001010011100101110111Prefix/PtrNode1--------P9----------P9--P9--P9--000001010011100101110111Prefix/PtrNode3----P8------P7--P7--------------000001010011100101110111Prefix/PtrNode2Ptr1Ptr2Ptr3P2P2P2P2P6P6P6P6P5P5P5P5P5LeafPushing(Stride=3)查找111010000對應(yīng)表項P2P6P5Multi-bitTrie性能步長為k比特，則查找的復(fù)雜度為O(W/k)W為地址的長度更新復(fù)雜度O(W/k+2k)每個節(jié)點有2k個條目存儲（空間）復(fù)雜度O(N*2k*W/k)N為轉(zhuǎn)發(fā)表表項數(shù)量LCTrie構(gòu)造節(jié)點分布稀疏時，PathCompression是壓縮Trie的有效途徑固定步長multi-bit能夠提高查找性能，但是當(dāng)節(jié)點分布稀疏時存儲冗余大節(jié)點分布越密，存儲效率越高，完全Trie無冗余！LCTrie：LevelCompressionTrie結(jié)合pression和multi-bitTrie的概念來優(yōu)化BinaryTrie結(jié)構(gòu)P1100P3110P4P3P1P1Ptr00011011P1P1P4P100011011LCTrie構(gòu)造1）如果Trie的中間節(jié)點包含前綴，則進行LeafPushing操作，使得Trie中只有葉子節(jié)點包含前綴（即為前綴節(jié)點）2）通過PathCompression將Trie壓縮3）當(dāng)子Trie的結(jié)構(gòu)為完全子Trie時執(zhí)行Multi-bit查找在LCTrie中每個節(jié)點需要保存：1）PathCompression信息(SkipValue,Segment)2）Multi-bit查找信息(Stride)01234567891011121314Skip=2

(01)Skip=3

(000)PathCompression01234567891011121314Skip=2

(01)Skip=3

(000)Stride=3Multi-bitTrie01234567891011121314Skip=2

(01)Skip=3

(000)Stride=2Stride=3Multi-bitTrie查找目的地址

11100000返回其下一跳信息LCTrie性能查找步長為k，則查找復(fù)雜度、更新復(fù)雜度及存儲復(fù)雜度與multi-bitTrie相同查找復(fù)雜度為O(W/k)W為地址長度更新復(fù)雜度為O(W/k+2k)O(N*2k*W/k)N為轉(zhuǎn)發(fā)表表項數(shù)量在最差情況下，LC-Trie的性能與步長為k的Multi-bitTrie差不多，但是由于使用了PathCompression，在實際情況下LC-Trie能夠更加有效地利用存儲空間基于Trie的算法BinaryTrieLCTriepressedTrieMulti-BitTrieLuleaTreebitmap算法IPv6路由查找目標(biāo)定義一種非常緊湊的轉(zhuǎn)發(fā)表表示形式將整個轉(zhuǎn)發(fā)表放到Level1/Level2緩存中實現(xiàn)在通用處理器（CPU）上通過軟件進行高速IP路由查找基本原理使用bitmap壓縮的Multi-bitTrieMulti-bitTrie中某個節(jié)點中所有連續(xù)并且具有相同值的條目使用1個條目來代替使用bitmap來指示有多少個條目被忽略111P3P3Ptr2P1P1Ptr1P4P2000001010011100101110RootNode10101111P3P1Ptr1P4P2Ptr2RootNodeLuleaPrefixDatabaseP1*

P2 1*

P3 00*

P4 101*

P5 111*

P6 1000*

P7 11101*

P8 111001*

P9 1000011*P3--P3--P5P1--P1--P2P4--P2--000001010011100101110111Prefix/PtrRootNodeP6--P6----P6--P6--------------000001010011100101110111Prefix/PtrNode1--------P9----------P9--P9--P9--000001010011100101110111Prefix/PtrNode3----P8------P7--P7--------------000001010011100101110111Prefix/PtrNode2Ptr1Ptr2Ptr3P2P2P2P2P6P6P6P6P5P5P5P5P5LeafPushing(Stride=3)1010111111101000111010001000100010101111P3P1Ptr1P4P2Ptr2P6Ptr3P6P2P6P91110100011101000P5P8P7P510001000RootNodeNode1Node2Node3數(shù)據(jù)結(jié)構(gòu)采用前綴分離（PrefixDisjoint）的Multi-bitTrie前綴節(jié)點只能是葉子節(jié)點三級結(jié)構(gòu)1624Level1Level2Level3每一級的查找結(jié)果可能是：1）下一跳的指針2）下一級節(jié)點的指針數(shù)據(jù)結(jié)構(gòu)第一級Trie的高度為16，相當(dāng)于Multi-bitTrie的步長為16比特，所以共有216個條目，對應(yīng)著深度為16的完全Trie的葉子節(jié)點Bit-Vector：每個比特對應(yīng)著1個條目，長度為216bits=8kbytes查找時使用地址的高16比特10010203140516171809010011112113114115Depth16Bit-Vector中的某個比特可以設(shè)置為：1，Trie在該層以下繼續(xù)，對應(yīng)節(jié)點為roothead(比特6,12,13)1，前綴的長度小于或者等于16。對應(yīng)節(jié)點為genuinehead(比特0,4,8,7,14,15)0，該比特對應(yīng)的前綴位于長度小于16的前綴覆蓋范圍內(nèi)(比特1,2,3;5;9,10,11)數(shù)據(jù)結(jié)構(gòu)指向下一跳信息的指針保存在genuinehead中，位于genuinehead后面的成員（Bit-Vector中0所對應(yīng)的節(jié)點）使用相同的指針指向第二級節(jié)點的指針保存在roothead中指針結(jié)構(gòu)指針類型下一跳或者第二級指針2b14b16b地址的高16比特所對應(yīng)的Bit-Vector中的比特之前有多少個1？基本思想Bit-Vector0A16前面有多少個比特1？ptr1PtrkA1664bits64bits64bitsBaseindex多少個1？A16Codeword查表多少個1？以及對應(yīng)16比特位模式多少個1？地址前10比特來索引地址前12比特來索引地址的后4比特16bits地址空間連續(xù)，指針長度固定10001000100000001011100010001010100000000000000010000r1r2r3r40（指向存儲起始）4k(212)bit-masks(each16bits)Codewordarray(4kentries)Baseindexarray016b10b012343+10+11+130查找結(jié)構(gòu)Bit-Vector被劃分為長度為16比特的bit-masks每個bit-mask對應(yīng)一個CodeWord每4個CodeWord對應(yīng)著一個BaseIndex地址的高16比特所對應(yīng)的Bit-Vector中的比特之前有多少個1？10010203140516171809010011112113114115Depth1616比特的Bit-Mask對應(yīng)著完全Trie的葉子節(jié)點數(shù)據(jù)結(jié)構(gòu)Bit-mask根據(jù)完全Trie生成，實際表明其數(shù)量僅僅為678個只需要10個比特來表示?。?！MapTable：保存所有可能的Bit-mask值，由codeword中的10比特值r和IP地址高16比特中的低4比特L索引678×16個表項，每個表項為4比特，表示到該比特為止1的個數(shù)r索引表的行L索引表的列MapTable是不變的，只需計算1次102416bixixbitBaseCodeSixTen01234515….MapTable++=pix查找指針I(yè)P地址轉(zhuǎn)發(fā)表BinaryTrie前綴分離Trie從根開始取高度為16的Trie，并且將其擴展為完全TrieBit-VectorPtr11000…00001000100000000166410…8096….Ptrk+mPtrk+m+1…………112128Ptrk+1……3248Lulea算法過程Ptr11000…00001000100000000166410…8096….Ptrk+m+1Ptrk+m+2…………112128Ptrk+1……3248m0r401234567k01r7查找的目的IP地址高16比特為：110110

對應(yīng)在Bit-Vector中的偏移值為118k+mMapTableCodeWordArrayBaseIndexArray01234515….MapTable1000…00001000100000000166410…8096….1121283248m0r401234567r7查找的目的IP地址高16比特為：110110

對應(yīng)在Bit-Vector中的偏移值為11860000111k+m+1Ptr1Ptrk+m+1Ptrk+m+2…………Ptrk+1……數(shù)據(jù)結(jié)構(gòu)第一級查找共需訪問7個字節(jié)2字節(jié)BaseIndex2字節(jié)CodeWord1字節(jié)（實際上4比特）的Maptable表項2字節(jié)指針第一級所需存儲大小2K字節(jié)的BaseIndex（2字節(jié)x216/26）8k字節(jié)的CodeWord（2字節(jié)x216/24）不定數(shù)量的指針（Bit-Vector中1的個數(shù)指定）5.3k字節(jié)的Maptable（(678×16×4/8)/1024=5.3KB）Maptable由三級共享！數(shù)據(jù)結(jié)構(gòu)第二級和第三級Trie的深度為8比特，稱為chunk，最多包含256個head根據(jù)Bit-Vector中指定的head的數(shù)量1～8個head，稀疏chunk，通過大小為8的8比特索引數(shù)組表示head，存儲空間最大為8+8×2字節(jié)9～64個head，密集chunk，與第一級類似，需要16個codeword，但只需1個基準(zhǔn)(BaseIndex)索引，存儲空間最大為16×2+2+64×2字節(jié)65～256個head，高密集chunk，與第一級類似，需要16個codeword，4個基準(zhǔn)索引（BaseIndex），存儲空間最多為16×2+4×2+256×2字節(jié)1624Level1Level2Level3性能轉(zhuǎn)發(fā)表大?。?0,000采用Lulea后實際的存儲大小：150K～160Kbyte足夠放在常用的通用處理的緩存中環(huán)境：200MHzPentiumProor333MHzAlpha21164每秒鐘能夠執(zhí)行幾百萬次，不需要任何硬件支持更新復(fù)雜度高！可能需要重建整個數(shù)據(jù)結(jié)構(gòu)！不適合路由表（轉(zhuǎn)發(fā)表）頻繁更新的環(huán)境！最差情況下查找復(fù)雜度和存儲開銷等同于步長為k的multi-bitTrie，分別為O(W/k)和O(N*2k*W/k)基于Trie的算法BinaryTrieLCTriepressedTrieMulti-BitTrieLuleaTreeBitmap算法IPv6路由查找概述基于Multi-bitExpandedTrie不使用任何LeafPushing設(shè)計準(zhǔn)則查找速度和存儲的可擴展性高速更新的能力大小適合分組轉(zhuǎn)發(fā)引擎或者處理器，并且開銷小分組轉(zhuǎn)發(fā)引擎提供了L3IP分組的交換、路由查找的功能，一般使用ASIC（專用集成電路）實現(xiàn)TreeBitmap具有適應(yīng)下一代存儲技術(shù)的能力，被CISCOCRS-1采用LeafPushing會顯著增加更新復(fù)雜度！原理與Lulea算法類似，通過Bitmap減少存儲空間需求克服Lulea算法中更新復(fù)雜度大的問題避免LeafPushing操作K=3指向下一跳信息-指向下一跳信息和子節(jié)點--指向子節(jié)點指向下一跳信息-000001010011100101110111RootNode指針信息P3P4P5P6P1P2將代表multi-bitTrie節(jié)點的子Trie的葉子節(jié)點Push到子節(jié)點，從而可以不用管葉子節(jié)點是否為前綴節(jié)點在節(jié)點中查找時實際使用K-1比特若K比特對應(yīng)的葉子節(jié)點存在，則查找繼續(xù)深入葉子節(jié)點所在的子節(jié)點例如：100和111Stride=3如何使用bitmap壓縮？對于multi-bitTrie的每個節(jié)點來說，需要存儲兩種類型的指針1）指向下一跳信息的指針，大小相同，若連續(xù)存放，可直接使用bitmap壓縮2）指向子節(jié)點的指針，大小相同，若連續(xù)存放，可直接使用bitmap壓縮在TreeBitmap算法中，每個節(jié)點占用的存儲空間相同，并且連續(xù)存放，所以bitmap壓縮后可以直接獲取子節(jié)點的地址，而不是存放子節(jié)點地址位置的指針數(shù)據(jù)結(jié)構(gòu)節(jié)點大小固定的Multi-bitTrie每個節(jié)點將所有的下一跳信息放到一個指針數(shù)組中節(jié)點只記錄該數(shù)組的起始位置使用bitmap來壓縮真正存儲的下一跳指針數(shù)量每個節(jié)點的所有子節(jié)點以連續(xù)的方式存儲節(jié)點只用記錄這些子節(jié)點的頭指針使用bitmap來壓縮真正存儲的子節(jié)點指針的數(shù)量Multi-bit節(jié)點的步長不超過8限制所需的更新時間，最差情況下256+C確保節(jié)點足夠小，處理器通過一次存儲器引用就能獲得節(jié)點的所有信息，這些信息被處理以找到最長前綴匹配數(shù)據(jù)結(jié)構(gòu)InternalNextHopBitmap和ExtendingPathsBitmap分別指示下一跳信息和子節(jié)點信息P1P2P3Stridek=310110001011000InternalNextHopBitmapP1P2P3ExtendingPathsBitmap00001101InternalNextHopBitmap長度：2k-1，第h層對應(yīng)的起始比特為2h（0,1,…k-1層）ExtendingPathsBitmap長度：2k數(shù)據(jù)結(jié)構(gòu)Multi-bit節(jié)點關(guān)聯(lián)的下一跳信息存儲在ResultArray中，每個節(jié)點保存一個指向ResultArray的起始位置的指針只有在最后找到最長匹配前綴的時候才真正訪問ResultArray給定節(jié)點的子節(jié)點以連續(xù)的方式進行存儲，每個節(jié)點只需保存一個指向子節(jié)點起始位置的指針RootnodeNode1Node2Node3Node4Node5Level1Level2Level3RootnodeNode1Node2Node3Node4Node5Level1Level2Resultptr1011000ResultP1ResultP2ResultP3Childptr00001101HeadPointerHead

PointerInternalnext

hopbitmapExtending

pathsbitmapResultarrayRootNode00001101Node1Node2Node3Resultptr1011000P1P2P3Childptr00001101RootNodeResultptr0100000Childptr01000000Resultptr1000000Childptr00000000Resultptr1000100Childptr01000000P6P4P5P7P7Resultptr0010000Childptr00000000Resultptr1000000Childptr00000000P8查找11101100Node1Node2Node3Node4Node5性能與Lulea算法類似，通過Multi-bitTrie和Bitmap來壓縮存儲空間，并且獲得更快的查找速度與Lulea算法不同，通過使用兩個Bitmap，避免了LeafPushing，實現(xiàn)了快速更新每個節(jié)點只需執(zhí)行一次存儲器訪問，而Lulea需要3次（Codeword+baseindex+NexthopPointer），只是在最后找到最長匹配前綴時執(zhí)行ResultArray訪問基于Trie的算法BinaryTrieLCTriepressedTrieMulti-BitTrieLuleaTreebitmap算法IPv6路由查找基本原理IPv6地址長度為128比特>>32比特但是，IPv6的前綴節(jié)點密度要遠遠小于IPv4更加有利于壓縮：PathCompression和BitmapCompression而且，前綴分布不均勻，Bitmap壓縮率對于前綴Trie的不同部分顯著變化使用可變長度步長！100010010NumberofPrefixs[2004]324864前綴長度主要分布在32、48、64數(shù)據(jù)結(jié)構(gòu)采用變長步長，Trie被分割為不同高度的subtrieSubtrie為完全BinaryTrie，可表示為<root,SubTrieHeight>SubTrie有2SubTrieHeight個邊緣節(jié)點Variable-Stridebitmap,acompressedsubtriedatasturcturePathCompressionPrefixNexthopBNIP2CNIP3ForwardingTableTrie中的每個節(jié)點攜帶下一跳信息或者Trie結(jié)構(gòu)信息(CPA)(PA)PointArrayBitmapCompressedPA4EdgeNodesHeight=2RootNodeSubTrieBA&pNIP2NIP2NIP3&pNIP2NIP3C1101數(shù)據(jù)結(jié)構(gòu)WordFrame：大小為1個WideWord，存儲1個或者多個壓縮后的SubTrie（128,64,32,16字節(jié)）Valid(1)Subtrieheight(4)Skip(3)Segment(8)Bitmap[1:8]…….Bitmap[2subtrieheght-7,2subtrieheight]CP[1]CP[2]……..Valid(1)Subtrieheight(4)Skip(3)…….Segment(8)ASubTrieStructure128/Num_SubTrieBHeaderCPAHeader128B數(shù)據(jù)結(jié)構(gòu)對于128BWordFrame，SubTrie的最大高度被限制為9假設(shè)WordFrame中只有1個Subtrie，并且CPA=1SubTrie最大高度Heightmax=log2(128×8-2×8-16)=9Height=2,skip=3Bit-String=000Bitmap=1111&NIP2&NIP1&NP1(FailureCP)&NIP4&NIP1SubTrie#2Height=3,skip=0Bit-String=noneBitmap=11100010&NIP3&NIP1&NIP3&NIP2---SubTrie#3SubTrie#1SubTrie#3SubTrie#2Skip=3Height=2,skip=0Bit-String=noneBitmap=1111&SubTrie#2&NIP1&SubTrie#3&NIP2SubTrie#1---BNIP21*CNIP31111*DNIP311000*ENIP111001*FNIP4000001*GNIP20000000HNIP10000001ANIP1*INIP10000011HABDECFIGHeight=2,skip=3Bit-String=000Bitmap=1111&NIP2&NIP1&NP1(FailureCP)&NIP4&NIP1SubTrie#2Height=3,skip=0Bit-String=noneBitmap=11100010&NIP3&NIP1&NIP3&NIP2---SubTrie#3SubTrie#1SubTrie#3SubTrie#2Skip=3Height=2,skip=0Bit-String=noneBitmap=1111&SubTrie#2&NIP1&SubTrie#3&NIP2SubTrie#1---HABDECFIG查找目的地址為

0000010返回性能實驗結(jié)果表明130k的IPv6轉(zhuǎn)發(fā)表最差情況下每秒鐘能夠執(zhí)行22,000,000次查找，只需要440KBSRAM和不超過3KBTCAM支持增量更新，具有較好的可擴展性主要內(nèi)容概述路由查找算法交換結(jié)構(gòu)交換結(jié)構(gòu)基本概念交換結(jié)構(gòu)緩存策略Banyan交換機輸入-輸出連接建立如何快速建立輸入-輸出端口連接？通?；谝粋€固定長度的時隙對于10Gbps鏈路，時隙大約為50ns分布式輸入端口-輸出端口連接建立自路由（Self-Routing）：交換結(jié)構(gòu)具有路由分組到合適輸出端口的智能，基于每個分組前面所附的物理輸出端口地址使用集中式不可行！吞吐量和加速吞吐量（Throughput)當(dāng)所有的輸入端口以線速承載100%的業(yè)務(wù)的時候，平均匯聚輸出速率和平均匯聚輸入速率的比率如果所有空閑輸入-輸出端口對都可以傳輸數(shù)據(jù)，則可以認(rèn)為吞吐量是100%加速（Speedup）交換結(jié)構(gòu)的內(nèi)部轉(zhuǎn)發(fā)速率和單個輸入端口線速的比值如果加速超過1，則輸出端口必須使用緩存線路速率（LineSpeed）：簡稱為線速，交換機端口連接的線路所能達到的最高速率輸入端口輸出端口0101輸出競爭和阻塞多個輸入端口請求同一個輸出端口導(dǎo)致輸出競爭由IP業(yè)務(wù)的突發(fā)性導(dǎo)致交換結(jié)構(gòu)內(nèi)部競爭導(dǎo)致內(nèi)部阻塞無阻塞：空閑輸入端口和空閑輸出端口之間的連接始終可以被建立空閑端口：沒有連接或者沒有被請求連接的端口交換機輸出競爭和內(nèi)部阻塞都會降低吞吐量，但后者是可以避免的，而前者者是無法避免的輸出競爭實例輸入端口0和3同時請求輸出端口2輸出端口競爭2032輸入端口0請求輸出端口5，輸入端口2請求輸出端口4內(nèi)部阻塞實例阻塞輸出端口54信元模式和分組模式信元：具有固定長度的數(shù)據(jù)單元ATM信元和非ATM信元分組：長度在某個范圍內(nèi)變動的數(shù)據(jù)單元分組長度隨機分布，不利于交換中的并行處理以下我們討論的交換結(jié)構(gòu)采用一般假設(shè)采用信元交換模式基于信元交換的IP路由器ISM:InputSegmentationModuleORM:OutputReasemblyModuleCQ:CellQueuePF:PacketFIFOQueue調(diào)度策略1）每個信元被獨立地被發(fā)送到對應(yīng)的輸出端口2）屬于同一個分組的多個信元被連續(xù)調(diào)度到對應(yīng)的輸出端口交換結(jié)構(gòu)ISMISMCQCQORMORMPFPF交換結(jié)構(gòu)基本概念交換結(jié)構(gòu)緩存策略Banyan交換機分類時分交換共享媒介交換共享存儲交換空分交換單路徑交換多路徑交換以時分復(fù)用的方式在輸入和輸出端口之間建立連接在輸入和輸出端口之間建立不同的交換路徑PacketSwitchingTimeDivisionSharedMediumSharedMemorySpaceDivisionSinglePathMultipathCrossbarBanyanAugmentedbanyanClos交換結(jié)構(gòu)分類Banyan交換機及其許多子類可能產(chǎn)生內(nèi)部阻塞，而共享媒介交換機、共享存儲交換機和Crossbar交換機都可以避免內(nèi)部阻塞FullInterconnected共享存儲器交換也被稱為第一代交換技術(shù)交換機速率受限于共享的存儲器的訪問速度，通常匯聚容量小于0.5Gbps共享媒介交換交換機速率受限于共享的總線速率，通常匯聚容量小于5Gbps也被稱為第二代交換技術(shù)空分交換也被稱為第三代交換技術(shù)交換機速率受限于交換結(jié)構(gòu)，通常匯聚容量小于50Gbps空分交換分布式控制多級交換交換結(jié)構(gòu)更高的交換機速率空分交換單路徑交換任何輸入-輸出端口對之間只有1條路徑路由控制簡單多路徑交換任何輸入-輸出端口對之間只有多條路徑具有更好地連接靈活性和故障容忍能力總的交換容量：能夠同時發(fā)送信元的路徑數(shù)量×每條路徑的帶寬單路徑交換—Crossbar輸入輸出交叉點CrossStateBarState12341234單路徑交換—Crossbar優(yōu)點內(nèi)部無阻塞體系結(jié)構(gòu)簡單模塊化但是不能避免輸出端口競爭！對于N×NCrossbar交換機，交叉點的數(shù)量為O(N2)4個請求輸入端口1到輸出端口3輸入端口2到輸出端口4輸入端口3到輸出端口1輸入端口4到輸出端口3CrossBar舉例交叉點交換(1,3)(2,4)(3,1)(4,3)(1,3)和(4,3)競爭12342134多路徑交換—Clos三級結(jié)構(gòu)： 第一級分發(fā)輸入數(shù)據(jù) 第二級多路徑（決定路徑的數(shù)量） 第三級交換到正確的輸出端口00交換結(jié)構(gòu)基本概念交換結(jié)構(gòu)緩存策略Banyan交換機共享存儲器隊列用于共享存儲交換1）存儲器由所有的輸入和輸出共享2）存儲器被劃分為邏輯隊列，與每個輸出端口對應(yīng)輸入邏輯隊列輸出輸入隊列解決輸出競爭1）每個輸入都設(shè)置隊列2）存在著頭阻塞問題，降低了交換性能交換

結(jié)構(gòu)輸入輸入隊列輸出頭（HOL：Head-of-Line）阻塞輸入端口0與輸入端口3頭部的信元存在輸出競爭，使得后面到輸出端口1的信元無法發(fā)送，即使輸出端口1空閑均勻到達業(yè)務(wù)情況下，輸入緩存交換機的吞吐量最大為58.6%輸入目的端口為1的信元由于頭阻塞而無法發(fā)送輸出輸出隊列解決輸出端口競爭1）每個輸出端口都設(shè)置隊列2）加速大于1（最大為N）必須使用輸出緩存3）易于實現(xiàn)基于QoS調(diào)度輸入輸出輸出隊列交換

結(jié)構(gòu)交換結(jié)構(gòu)基本概念交換結(jié)構(gòu)緩存策略Banyan交換機多級交換機多級交換機一般是由較小的交換單元組成的大的交換系統(tǒng)，也稱為交換網(wǎng)絡(luò)，交換單元常用2×2CrossbarBanyan交換機為單路徑多級交換機輸入輸出輸入輸出010101010101010101010101多級交換機采用多級交換的好處比crossbar交換機更少的交叉點O(NlogN)vs.O(N2)交換路徑的多樣性中間級能夠提供交換選擇，從而獲得更低的內(nèi)部阻塞概率增加可靠性，即使某個交換單元發(fā)生故障，只會影響到故障交換單元所涉及到的交換路徑并行流水線操作（Pipeline）通過信元交換解決同步問題，每1級操作不同的信元集合Banyan交換機構(gòu)造基于2×2交換單元構(gòu)建N端口Banyan交換機共有l(wèi)og2N級，每一級都有N/2個交換單元，總交叉點數(shù)量：Nx=4×N/2×log2N1級：每個輸入最多有2個輸出可能2級：對于第1級，每個輸入最多有2個輸出可能，而這2個輸出作為第2級輸入，最多能連到2個交換單元，共有2×2個輸出可能3級：對于第2級，每個輸入最多有2×2個輸出可能，而這2×2個輸出作為第3級輸入，最多能連到2×2個交換單元，共有2×2×2個輸出可能以此類推，對于第k級，最多有2k個輸出可能，由2k>=N，得到k>=log2N，取下限，得到k=log2N如果使用b×b交換單元，同理可以得到級數(shù)k>=logbN01018×8Banyan交換機構(gòu)建共log28=3級，每級8/2=4個交換單元0101010101010