ip路由器-閱讀頁(yè)
2024-09-21 14:46本頁(yè)面
【正文】 ie中的空指針指向其目的地址 Trie的某個(gè)祖先對(duì)應(yīng)的源地址 Trie中的節(jié)點(diǎn)。 ? 存儲(chǔ)經(jīng)過(guò)的節(jié)點(diǎn)，代價(jià)最小的規(guī)則為最佳匹配規(guī)則。 ABCH001DR4R1EGR2R5FR6IR30000111F 1目 的 地 址 T r i e 樹F 2源 地 址 T r i e 樹查 找 路 徑111ABCH001DR4R1EGR2R5FR6IR30000111F 1目 的 地 址 T r i e 樹F 2源 地 址 T r i e 樹查 找 路 徑R5R211R61基于 Trie樹的多維包分類 ? 五元組包分類：源 IP地址，目的 IP地址，源端口，目的端口，協(xié)議號(hào)。 ? 根據(jù)目的端口和源端口的不同組合建立 4個(gè)哈希表，分別對(duì)應(yīng)（ DstPort， *）、（ DetPort， SrcPort）、（ *，SrcPort）和（ *， *）的情況。 包分類過(guò)程 ? 進(jìn)行分類時(shí)，同時(shí)查找 4個(gè)哈希表： ? 分別用協(xié)議號(hào)和端口號(hào)的某種組合（或函數(shù)）作為索引，找到相應(yīng)的 Grid of Tries樹。 （ 4）比特矢量 ? 基本思想： ? 把 d 維查找分解成 d 個(gè)一維查找； ? 每個(gè)一維查找結(jié)果用一個(gè)長(zhǎng)度為 N的比特矢量表示，其中 N為規(guī)則數(shù)，與匹配規(guī)則對(duì)應(yīng)的比特位置 “ 1”； ? 將 d個(gè)比特矢量相與，取優(yōu)先級(jí)最高的規(guī)則。 ? 算法運(yùn)行時(shí)間隨 N的增大而線性增長(zhǎng)，可擴(kuò)展性差。 ? 每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)將父節(jié)點(diǎn)包含的 d維空間按某一維平均劃分，每個(gè)節(jié)點(diǎn)保存與其 d維空間相交的規(guī)則的集合。 ? 優(yōu)點(diǎn)： ? 占用空間小，更新容易，支持范圍匹配。 0 0 00 0 1 1 1 10 1 0 1 0 01 0 11 1 00 1 1R6R5R3R11 1 11 1 01 0 11 0 00 1 10 1 00 0 10 0 0R2. HF 1F 28 * 8 , X , 42 * 8 , Y , 2R2R5R3R6R3R6R1R2R5沿 X ( F 1 )方 向 分 割沿 Y ( F 2 )方 向 分 割舉例 （ 6） Recursive Flow Classification ? 包分類問(wèn)題的抽象： ? 將包頭中待查找的 d個(gè)域看成長(zhǎng)度為 S的比特串，比特串的每一種可能取值對(duì)應(yīng)一個(gè)等價(jià)類（ eqID），包分類即是根據(jù)包頭中的 S位比特串確定對(duì)應(yīng)的 eqID。 ? RFC將一次映射轉(zhuǎn)變?yōu)槎嚯A段映射，實(shí)質(zhì)是將一個(gè)較大的集合映射成若干個(gè)較小的集合，以減少內(nèi)存消耗。 一個(gè)三維規(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的特點(diǎn) ? RFC是目前除硬件方案之外較快的多維包分類算法。 （ 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] ? 三個(gè)觀察事實(shí)： ? 大多數(shù)分類算法只適用于前綴查找，對(duì)于端口范圍查找，必須先進(jìn)行范圍 前綴轉(zhuǎn)換，增加了規(guī)則數(shù)量。 ? 對(duì)實(shí)際分類規(guī)則集統(tǒng)計(jì)特性的分析表明，在 %的情況下，匹配一對(duì)給定的 源 IP地址，目的 IP地址 的規(guī)則數(shù)不大于 5。 ? 在預(yù)處理階段先將匹配一對(duì) 源 IP地址，目的IP地址 的規(guī)則編成代碼，查找時(shí)通過(guò)解釋執(zhí)行找到匹配的規(guī)則。（由端口號(hào)和協(xié)議組成的范圍表達(dá)式列表被預(yù)先編碼成一系列的 ALU指令） ? 一個(gè)解釋器從外部存儲(chǔ)器裝載代碼塊到內(nèi)部存儲(chǔ)器，然后解碼并順序執(zhí)行指令，以找到一個(gè)匹配。 ? 兩種協(xié)議范圍： WC和 EM。 ? 三種指令格式，分別帶有 1個(gè)、 3個(gè)和 5個(gè)操作數(shù)。 ? 平均指令長(zhǎng)度為。 ? 訪問(wèn)內(nèi)存次數(shù)少： ? 查找一個(gè)數(shù)據(jù)包， RFC需要 13次訪存， TIC大約需要 7+1=8次訪存。 ? 分類數(shù)據(jù)結(jié)構(gòu)基本上可以放入 4MB的 L2 cache中。 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.
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1