ip路由器-資料下載頁
2024-09-01 14:46本頁面
【導(dǎo)讀】查、路由查找、報頭修改、包分片等。將路由表中的地址前。與地址前綴對應(yīng)的節(jié)。查找算法的時間復(fù)雜。度與地址長度成正比。為提高路由查找速度，采用二元查找樹+. 使用路由緩存的前提是網(wǎng)絡(luò)流量具有足夠的局。部性，從而cache的命中率足夠高。實踐發(fā)現(xiàn)，路由緩存在因特網(wǎng)邊緣比較有效，核心路由器見到的目的地址數(shù)量巨大，可導(dǎo)致。頻繁的路由更新使得cache中的路由信息很快失。CPU需要完成全部的。每個包需穿過總線。路由器的性能嚴重。共享總線是瓶頸。下一跳和處理包頭。控制卡、線卡和轉(zhuǎn)發(fā)。當網(wǎng)絡(luò)拓撲頻繁變化、流量模式高度隨機時，網(wǎng)絡(luò)。查找性能無法得到保證。針對路由器結(jié)構(gòu)的各種改進都是要消除處理、包過濾、深度數(shù)據(jù)包檢查、流量管理等原先屬。從已有的高端專用設(shè)備入手，增強其可編程。專用設(shè)備開放有限的API，允許第三方修
【正文】 3R6R3R6R1R2R5沿 X ( F 1 )方 向 分 割沿 Y ( F 2 )方 向 分 割舉例 （ 6） Recursive Flow Classification ? 包分類問題的抽象： ? 將包頭中待查找的 d個域看成長度為 S的比特串，比特串的每一種可能取值對應(yīng)一個等價類（ eqID），包分類即是根據(jù)包頭中的 S位比特串確定對應(yīng)的 eqID。 ? 從 S位比特串直接映射到 eqID需要消耗巨大的內(nèi)存空間。 ? RFC將一次映射轉(zhuǎn)變?yōu)槎嚯A段映射，實質(zhì)是將一個較大的集合映射成若干個較小的集合，以減少內(nèi)存消耗。 ? 每一階段映射稱為一次縮減（ reduction），由多階段映射構(gòu)建的數(shù)據(jù)結(jié)構(gòu)稱為縮減樹。 一個三維規(guī)則集例子 r u l e F 1 F 2R 1R 2R 3R 40 0 10 0 10 1 ** * *0 1 01 0 01 0 0* * *F 30 1 10 1 1* * ** * *A C T I O Np e r m i td e n yp e r m i tp e r m i tRFC的特點 ? RFC是目前除硬件方案之外較快的多維包分類算法。 ? 易于并行處理 ? 處于同一階段的預(yù)處理表或交叉乘積表可被并行地索引 ? 處于不同階段的表也可被并行地索引 ? 這些表各自獨立，可分布于不同的存儲單元中 ? 缺點： ? 交叉乘積表占用內(nèi)存空間較多，存儲空間 消耗隨規(guī)則集規(guī)模增大而迅速增大。 （ 7） BitmapRFC [7] …00102000891 01 11 233…1 51 61 7C r o s s p r o d u c t i n g T a b l e AC o m p a c t T a b l eE l e m e n t A r r a y100000000111100010010203B i t m a p0 0 00 0 10 1 00 1 11 0 01 0 1 Bitmap RFC的數(shù)據(jù)結(jié)構(gòu) 1 6 B i tB i t m a pE l e m e n t21 6 B i tB i t m a p ( I f e x i s t i n g )E l e m e n t1E l e m e n t3E l e m e n t4… … … …… … O r N u l lP o i n t e r ( I f e x i s t i n g )E l e m e n t1E l e m e n t2E l e m e n t3… … … …C o m p a c t T a b l eA c c e s s o r y T a b l e1 6 B i t… … … …L S BM S BOne entry 查找 O I n d e x / s i z e o f s u b C P T0 0 1 0 0 1 0 1 0 . . . 1 0 1 0 1 0e l e m e n t 1 e l e m e n t 2. . . . . .o t h e r e n t r yo t h e r e n t r yq u o t i e n tr e s i d u eC o m p a c t T a b l eE l e m e n t. . . . . .E l e m e n tA c c e s s o r y T a b l eL S BM S B（ 8） Twostage Interpreting based Classification（ TIC） [8] ? 三個觀察事實： ? 大多數(shù)分類算法只適用于前綴查找，對于端口范圍查找，必須先進行范圍 前綴轉(zhuǎn)換，增加了規(guī)則數(shù)量。 ? 前綴查找是訪存密集的操作，范圍查找是計算密集的操作，將兩者分開處理有助于提高查找的效率。 ? 對實際分類規(guī)則集統(tǒng)計特性的分析表明，在 %的情況下，匹配一對給定的 源 IP地址，目的 IP地址 的規(guī)則數(shù)不大于 5。 TIC算法 ? 算法要點： ? 將匹配一對 源 IP地址，目的 IP地址 的過程與匹配其余 3個域的過程分開，前者使用適合前綴查找的算法，后者使用適合范圍查找的算法。 ? 在預(yù)處理階段先將匹配一對 源 IP地址，目的IP地址 的規(guī)則編成代碼，查找時通過解釋執(zhí)行找到匹配的規(guī)則。 TIC的設(shè)計 ? 第一階段采用 RFC算法，找到匹配一對 源 IP地址，目的 IP地址 的規(guī)則集，實際上得到的是對應(yīng)該規(guī)則集的代碼塊的地址。（由端口號和協(xié)議組成的范圍表達式列表被預(yù)先編碼成一系列的 ALU指令） ? 一個解釋器從外部存儲器裝載代碼塊到內(nèi)部存儲器，然后解碼并順序執(zhí)行指令，以找到一個匹配。 指令編碼 ? 5種端口范圍： WC（通配）、 HI（高端）、 LO（低端）、 AR（任意范圍）、 EM（精確匹配）。 ? 兩種協(xié)議范圍： WC和 EM。 ? 采用 CISC風格的指令，總共需要約 5 5 2=50種操作符。 ? 三種指令格式，分別帶有 1個、 3個和 5個操作數(shù)。 源端口和目的端口的分布 ? 12字節(jié)的指令非常少見。 ? 平均指令長度為。 RFC與 TIC的訪存次數(shù) 4階段 RFC TIC TIC與 RFC的比較 ? 內(nèi)存空間?。? ? TIC最多可比 RFC節(jié)省 97%的存儲空間。 ? 訪問內(nèi)存次數(shù)少： ? 查找一個數(shù)據(jù)包， RFC需要 13次訪存， TIC大約需要 7+1=8次訪存。 ? %的情況下，匹配一對地址的候選范圍可以編碼成一個 64字節(jié)的代碼塊（ X86上一個 cache行大?。瑑H需訪問內(nèi)存一次。 ? 分類數(shù)據(jù)結(jié)構(gòu)基本上可以放入 4MB的 L2 cache中。 主要參考文獻 [1] IP Router Architectures: An Overview. [2] Study of Inter Router Architectures. [3] RouteBricks: Exploiting Parallelism to Scale Software Routers. [4] Survey and Taxonomy of IP Address Lookup Algorithms. [5] Highperformance IPv6 Forwarding Algorithm for Multicore and Multithreaded Network Processor. [6] Survey amp。 Taxonomy of Packet Classification Techniques. [7] Highperformance Packet Classification Algorithm for Manycore and Multithreaded Network Processor. [8] Scalable Packet Classification Using Interpreting: A Crossplatform Multicore Solution.
教學課件相關(guān)推薦
鄂ICP備17016276號-1