【正文】 ? 一種較自然的做法是根據(jù)二分支 Trie的 地址前綴分布來(lái)選擇合適的步寬。 ? 需要額外的數(shù)據(jù)結(jié)構(gòu)保存原始前綴。 ? 多分支 Trie的更新過(guò)程比二分支 Trie復(fù)雜： ? 插入一個(gè)前綴時(shí)，需要找到相應(yīng)的 subtrie，對(duì)前綴進(jìn)行擴(kuò)展，然后插入。 多分支 Trie的查找和更新 ? 多分支 Trie的查找過(guò)程類似于二分支 Trie。 ? 根據(jù)同一層中不同子樹(shù)的步寬是否相同，分為： ? 固定步寬多分支 Trie ? 可變步寬多分支 Trie 可變步寬與固定步寬的多分支 Trie樹(shù) 前綴擴(kuò)展 ? 前綴表中的地址前綴必須轉(zhuǎn)換成多分支 Trie查找允許的地址前綴。 （ 3）多分支 Trie ? 查找的每一步檢查地址的多個(gè)比特，以減少樹(shù)的高度（訪存次數(shù)）。 ? 研究表明，對(duì)于一個(gè)具有 47113個(gè)前綴表項(xiàng)的典型骨干網(wǎng)路由器，使用 BSD Trie會(huì)創(chuàng)建 93304個(gè)節(jié)點(diǎn)，樹(shù)的最大高度為 26，平均高度為 20。 （ 2）路徑壓縮 Trie樹(shù) ? 路徑壓縮 Trie樹(shù)壓縮單孩子分支 ? 每個(gè)節(jié)點(diǎn)需要維護(hù)一個(gè)變量，指示下一個(gè)需要檢查的比特位 ? 前綴節(jié)點(diǎn)需要保存地址前綴的比特串 路徑壓縮 Trie樹(shù)（續(xù)） ? 當(dāng)二元 Trie樹(shù)中的前綴分布較稀疏時(shí)，路徑壓縮算法能夠獲得良好的壓縮效果。 ? 若查找過(guò)程終止于葉子節(jié)點(diǎn)，除了刪除該節(jié)點(diǎn)之外，還需要根據(jù)情況刪除其它一些內(nèi)部節(jié)點(diǎn) 。 ? 若查找過(guò)程在一個(gè)中間節(jié)點(diǎn)終止，將此節(jié)點(diǎn)標(biāo)記為非前綴節(jié)點(diǎn)，刪除此節(jié)點(diǎn)的轉(zhuǎn)發(fā)信息。 例如，插入前綴 00*。例如，插入前綴 01*。 Trie樹(shù)的更新（ 1） ? 插入一個(gè)地址前綴 ? 以 該前綴為關(guān)鍵字在 Trie樹(shù)中進(jìn)行查找。 ? 當(dāng)不再有分支可以選擇時(shí)搜索過(guò)程結(jié)束，此時(shí)被記錄的最長(zhǎng)地址前綴就是查找結(jié)果。 Trie樹(shù)代表的地址空間結(jié)構(gòu) Trie樹(shù)的查找 ? 從根節(jié)點(diǎn)開(kāi)始每次一位地查找： ? 當(dāng)?shù)刂分械南鄳?yīng)位為 0時(shí)選擇左分支，為 1時(shí)選擇右分支。 ? 處于第 L層的節(jié)點(diǎn)代表了一個(gè)地址前 L比特均相同的地址空間，這 L個(gè)比特串就是由從根節(jié)點(diǎn)到這個(gè)節(jié)點(diǎn)路徑上的L比特組成。 ? 地址查找在數(shù)值和長(zhǎng)度兩個(gè)維度上進(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ú)法從目的地址本身獲得。 地址聚合的例子（ 1） 地址聚合的例子（ 2） 路由器的地址查找問(wèn)題，就是要從轉(zhuǎn)發(fā)表中查找匹配數(shù)據(jù)包目的地址的最長(zhǎng)的地址前綴。 無(wú)類域間路由（ CIDR）編址方案 ? 摒棄傳統(tǒng)的基于類的地址分配方式，允許使用任意長(zhǎng)度的地址前綴，有效提高地址空間的利用率。 轉(zhuǎn)發(fā)表舉例 基于類的編址方案 ? 地址空間利用率低，地址短缺問(wèn)題日益突顯。 總的性能改進(jìn) 2 IP路由查找 地址前綴與地址聚合 ? IP地址由兩個(gè)部分組成：網(wǎng)絡(luò)地址部分（地址前綴）和主機(jī)地址部分。性能提升 3倍。性能提升 2倍。 ? 當(dāng)有數(shù)據(jù)包到達(dá)網(wǎng)卡時(shí)，網(wǎng)卡將數(shù)據(jù)包及元數(shù)據(jù)通過(guò) DMA存放到指定位置，然后向 CPU發(fā)送中斷，返回包描述符。 數(shù)據(jù)包輸入 /輸出 ? 在目前的操作系統(tǒng)中， ? 數(shù)據(jù)包的元數(shù)據(jù)存放在 skb中，有一個(gè)指針指向數(shù)據(jù)包實(shí)際存放的位置。 優(yōu)化措施（ 1） 充分利用服務(wù)器的并行性 ? 用基于點(diǎn)到點(diǎn)連接的 Nehalem 服務(wù)器代替基于共享總線結(jié)構(gòu)的 Xeon服務(wù)器，性能提高了 23倍。 ? 采用輪詢模式收包， CPU輪詢是否有包到達(dá)，而不是在包到來(lái)后被中斷。 ? 因此，每塊網(wǎng)卡可獲得 ，服務(wù)器最高數(shù)據(jù)輸入速率為 。 服務(wù)器架構(gòu) 硬件平臺(tái) 輸入流量 ? 服務(wù)器上安裝了兩塊雙端口 10Gbps網(wǎng)卡。 集群路由器架構(gòu)圖示 設(shè)計(jì)原則（ 2） ? 僅當(dāng)單個(gè)服務(wù)器的性能能夠提高到 cR，集群路由器架構(gòu)方案才是可行的，但目前的服務(wù)器遠(yuǎn)不能達(dá)到這個(gè)速度。 ? 集群路由器架構(gòu)擴(kuò)放性好： ? 只需增加服務(wù)器的數(shù)量，就可提高路由器的容量。 ? 每個(gè)服務(wù)器承擔(dān)傳統(tǒng)路由器中線卡的功能，負(fù)責(zé)一個(gè)或幾個(gè)端口的包處理，處理速度為 kR。 ? 挑戰(zhàn)：?jiǎn)闻_(tái)服務(wù)器不可能達(dá)到 NR的處理和交換速度。 ? 路由器的功能主要是包處理和包交換： ? 包處理：典型地發(fā)生在線卡上，每塊線卡處理一個(gè)或幾個(gè)端口，線卡的處理速度為 kR（ k為端口數(shù)）。 ? [3]采用商用 PC機(jī)硬件和操作系統(tǒng)構(gòu)建路由器。 ? 擴(kuò)展性好：數(shù)據(jù)面和控制面功能可通過(guò)軟件升級(jí)來(lái)修改，免去開(kāi)發(fā)者設(shè)計(jì)硬件的負(fù)擔(dān)。 ? 利用網(wǎng)絡(luò)處理器加速時(shí)間關(guān)鍵任務(wù)的處理，具有較高程度的可編程性，但編程困難。 ? 軟件路由器利用通用平臺(tái)上的軟件執(zhí)行包處理任務(wù)，易于編程，但只適用于低速環(huán)境。 RouteBricks [3] ? 隨著網(wǎng)絡(luò)處理功能越來(lái)越復(fù)雜及 ISP競(jìng)相提供新的服務(wù)，可編程、可擴(kuò)展的網(wǎng)絡(luò)設(shè)備重新引起人們的關(guān)注。 Intel Nehalem 8核處理器內(nèi)部結(jié)構(gòu) ? 8個(gè)核，每個(gè)核自帶256KB L2 cache ? 8個(gè)核共享一個(gè) L3 cache ? 內(nèi)置內(nèi)存控制器 ? 微內(nèi)核與內(nèi)存控制器之間使用crossbar交叉互聯(lián) ? 內(nèi)置 QPI接口，允許與其它處理器進(jìn)行高速點(diǎn)對(duì)點(diǎn)連接 多個(gè)處理器互聯(lián) ? NehalemEX 的最高配置是 4 芯 32 核。 ? 通用處理器的計(jì)算能力很強(qiáng)大，存儲(chǔ)資源很豐富，能夠承擔(dān)很復(fù)雜的包處理任務(wù)。 ? 板卡之間的高速互聯(lián)： ? 更高帶寬的互聯(lián)結(jié)構(gòu)代替原先的交換結(jié)構(gòu)。 ? 使用點(diǎn)對(duì)點(diǎn)鏈路連接每一個(gè) PRE和每一塊線卡。 ? PRE（主、備各一塊）： ? RP：運(yùn)行路由協(xié)議，更新路由表，其它控制面功能。 ? RSP處理其它重要任務(wù)，如路由協(xié)議、非 IP流量、網(wǎng)絡(luò)管理等。 ? 其它維護(hù)功能，如網(wǎng)絡(luò)管理。 ? 基本包轉(zhuǎn)發(fā)之外的服務(wù)，如加密、壓縮、訪問(wèn)控制、QoS、流量統(tǒng)計(jì)等。 ? 慢路徑一般在 CPU上用軟件實(shí)現(xiàn)。 ? 快路徑的速度直接影響路由器的性能，一般在網(wǎng)絡(luò)接口上實(shí)現(xiàn)，且大多用硬件實(shí)現(xiàn)。 小結(jié) ? 路由器架構(gòu)基本上是從集中式向分布式演變： ? 將協(xié)議棧的處理功能分布到主控制板及各個(gè)網(wǎng)絡(luò)接口卡上，消除處理和訪存瓶頸 ? 使用交換結(jié)構(gòu)消除內(nèi)部總線瓶頸 ? 針對(duì)路由器結(jié)構(gòu)的各種改進(jìn)都是要消除處理、訪存、總線三個(gè)性能瓶頸。 ? 大型路由器的一個(gè)接口上可能同時(shí)存在上千萬(wàn)條活躍的并發(fā)流，硬件 cache很難實(shí)現(xiàn)，而軟件哈希表的查找性能無(wú)法得到保證。 第三代：基于交換的路由器架構(gòu) ? 控制卡、線卡和轉(zhuǎn)發(fā)引擎卡通過(guò)一個(gè)高速交換結(jié)構(gòu)連接： ? 每塊線卡包含多個(gè)網(wǎng)絡(luò)接口 ? 每塊轉(zhuǎn)發(fā)引擎卡包含路由緩存，負(fù)責(zé)包頭處理與轉(zhuǎn)發(fā) ? 控制卡提供基本的管理功能。 ? 優(yōu)點(diǎn)：提高了路由器的端口密度。 ? 轉(zhuǎn)發(fā)引擎包含自己的路由 cache，只負(fù)責(zé)解析下一跳和處理包頭。 ? 共享總線是瓶頸。 IP路由器架構(gòu)的演變 ? 第一代：基于總線和單處理器 的架構(gòu)（軟件路由器） ? CPU需要完成全部的網(wǎng)絡(luò)處理功能 ? 每個(gè)包需穿過(guò)總線兩次 ? 路由器的性能?chē)?yán)重依賴于共享總線的吞吐