ip路由器(編輯修改稿)

　

【文章內容簡介】 需要維護一個變量，指示下一個需要檢查的比特位 ? 前綴節點需要保存地址前綴的比特串 路徑壓縮 Trie樹（續） ? 當二元 Trie樹中的前綴分布較稀疏時，路徑壓縮算法能夠獲得良好的壓縮效果。 ? 二元 Trie樹和路徑壓縮 Trie樹的不足是查找過程需要大量的存儲器訪問操作。 ? 研究表明，對于一個具有 47113個前綴表項的典型骨干網路由器，使用 BSD Trie會創建 93304個節點，樹的最大高度為 26，平均高度為 20。而對于同樣的前綴表，二元 Trie樹的最大高度為 30，平均高度為 22。 （ 3）多分支 Trie ? 查找的每一步檢查地址的多個比特，以減少樹的高度（訪存次數）。 ? 查找步寬：每次檢查的比特數稱為查找步寬。 ? 根據同一層中不同子樹的步寬是否相同，分為： ? 固定步寬多分支 Trie ? 可變步寬多分支 Trie 可變步寬與固定步寬的多分支 Trie樹 前綴擴展 ? 前綴表中的地址前綴必須轉換成多分支 Trie查找允許的地址前綴。 前綴擴展例 2 在前綴擴展過程中，如果擴展的地址前綴與原來的地址前綴沖突，應保留原來的地址前綴。 多分支 Trie的查找和更新 ? 多分支 Trie的查找過程類似于二分支 Trie。 ? 多分支 Trie可以看成是由單層 subtrie構成的樹，在每個 subtrie所做的前綴擴展是局部的。 ? 多分支 Trie的更新過程比二分支 Trie復雜： ? 插入一個前綴時，需要找到相應的 subtrie，對前綴進行擴展，然后插入。 ? 刪除一個前綴時，需要刪除所有擴展的前綴。 ? 需要額外的數據結構保存原始前綴。 多分支 Trie的優化 ? 步寬的選擇 ? 步寬的選擇是在算法查找速度、存儲空間和更新復雜度之間的折衷。 ? 一種較自然的做法是根據二分支 Trie的 地址前綴分布來選擇合適的步寬。 ? 使用某種優化策略，使在搜索深度固定的情況下整個樹的存儲空間最小。 （ 4） Stanford算法 ? 據統計，因特網中 %的前綴長度分布在 24或小于 24的范圍內。 ? 提出一種 248的多分支 Trie快速查找算法： ? 第一層步寬 24比特：絕大多數情況下訪問這一層就可以找到最佳匹配前綴。 ? 第二層步寬 8比特：少數情況下需要查找這一層。 ? 查找速度快，要求較大的存儲空間。 Stanford算法的硬件實現 TBL24 TBLlong （ 5）基于 TCAM的地址查找 ? 內容可尋址存儲器（ Content Addressable Memory）是一種支持快速搜索和數據存儲的存儲機制，主要用于提高查表速度。 ? CAM被組織成一個二維陣列，每一行長度固定，稱為一個槽。 ? 處理器提供一個查找關鍵字，CAM返回匹配該關鍵字的一組槽。 CAM的組織 TCAM（三態 CAM） ? 每個 TCAM條目存儲一個二進制數和一個掩碼。 ? 掩碼長度等于槽長度，指示哪些比特要和關鍵字的相應比特比較。 ? 若有多個條目匹配，選擇地址最低的條目。 ? TCAM適合于查找帶通配符的關鍵字。 （ 5）基于 TCAM的地址查找 ? 優點：查找速度快，實現簡單。采用流水線技術可以進一步提高查找速度。 ? 缺點： TCAM容量小、代價高、功耗大、更新復雜（關鍵字需要排序）。 T C A M 芯片 NextHop索 引表 NextHop映 射表目的I P 地址下一跳地址和端口（ 6） IPv6地址查找 ? IPv6路由表的特點： ? 前綴更長： IPv6地址長 128比特。 ? 由路由器轉發的一類地址（可聚合的全局單播地址），前 3比特（格式前綴）總是 001，最后 64比特用于標識網絡接口。 ? 規模更大：大規模應用后，前綴項估計在 50萬條左右。 ? IPv4地址查找算法不能直接應用于 IPv6： ? 基于 Trie的算法訪存次數很多，或內存需求很大。 ? 基于 TCAM的方法不適用于規模巨大的表。 采用多分支 Trie樹構造查找表 [5] ? 采用改進的 Stanford算法，保留其查找快速、易于更新及硬件實現容易等優點，并壓縮算法所需的存儲空間。 ? 根據統計結果及 IPv6地址分配策略，長度大于 48比特的前綴僅為 5%左右。 ? 構造查找步寬為 2488816的五層多分支 Trie樹，限制最壞情況下路由查找的訪存次數。 前綴擴展產生許多冗余 （ 2020:4*::/18, A）和（ 2020:5*::/20, B）擴展出來的表項 TrieC的算法思想 ? 具有相同下一跳的前綴項組成一個數據塊，下一跳信息只在表中存儲一次。 ? 采用一個位向量記錄每個數據塊的起始位置。 ? 64條前綴壓縮成一個表項，高 18比特作為表項索引，低 6比特用作位向量索引。 ? 統計位向量中從起始位置到當前位置 “ 1”的個數，作為數組下標。 TrieC樹結構 ? 建立 2488816多分支 TrieC樹： ? 根節點采用 TrieC15/6數據結構，存儲長度為 [1, 24]比特的地址前綴。 ? 第二層至第四層均采用 TrieC4/4數據結構，分別存儲長度為 [25, 32]、 [33, 40]、 [41, 48]比特的地址前綴。 ? 第五層為基于 CRC的哈希表，存儲長度為 [49, 64]比特的地址前綴。 ? 每一層節點的數據結構中都有一個標志位用于指示是否需要繼續查找下一層節點。 網絡處理器中的實現優化 ? 位操作指令 ? POP_COUNT指令：可在 3個時鐘周期內計算 32位寄存器中 1的個數。在 RISC結構上通常需要 100多條指令。 ? 分支跳轉指令：可在 1條指令中完成分支跳轉操作。在RISC體系結構上通常至少需要 3條指令。 ? 硬件 CRC指令： ? 5個時鐘周期完成計算。 ? 數據分布 ? TrieC表按照 TrieC樹的層次存儲在四個 SRAM控制器中 3 數據包分類 包分類的術語 ? 包頭 H：有 K個域的實體，第 i個域表示為一個比特串 H[i]。 ? 過濾規則 f ：具有 K個域，第 i個域表示為 f[i]。 ? 與每個 f[i]相關聯有一個匹配方式，可以是： ? 精確匹配： f[i]用一個值表示，若 H[i]=f[i]，稱 H[i]與 f[i]精確匹配。 ? 前綴匹配： f[i]通過一個前綴指定，若 H[i]與 f[i]表示的前綴匹配，稱 H[i]與 f[i]前綴匹配。 ? 范圍匹配： f[i]通過一個范圍 [val1, val2]指定，若滿足val1≤ H[i] ≤ val2，稱 H[i]與 f[i]范圍匹配。 ? 規則 f 與包頭 H匹配，當且僅當每個 H[i]匹配 f[i]。 IP分類問題的定義 ? 給定一個具有 N條規則的規則集 F，與每條規則 f 相聯系有一個代價函數 cost(f)，給定一個包頭 H，最佳規則匹配問題為在 F 中查找滿足下列條件的規則 fbest： ? Fbest 匹配 H ? 在 F 中不存在其它的規則 f ，使得 f 匹配 H且滿足 cost(f)cost(fbest)。 IP分類與多維空間的點定位 ? 多維空間的點定位問題： ? 給定多維空間中一些互不相交的區域，找出包含指定點的區域。 ? IP分類問題與多維空間中的點定位問題相似： ? 每條規則對應多維空間中的一個