【正文】 量以及 CPU的處理速度，不具有擴(kuò)放性。 ? 實(shí)踐發(fā)現(xiàn)，路由緩存在因特網(wǎng)邊緣比較有效，在因特網(wǎng)核心并不奏效： ? 核心路由器見(jiàn)到的目的地址數(shù)量巨大，可導(dǎo)致緩存溢出或查找速度變慢。 ? 先用目的地址查找路由 cache，不命中再查找路由表。 ? 查找算法的時(shí)間復(fù)雜度與地址長(zhǎng)度成正比。 ? 查找時(shí)使用地址前綴的每一位決定樹(shù)的分支。 ? 特殊服務(wù)： 不屬于核心路由的其它功能，包括數(shù)據(jù)包轉(zhuǎn)換、封裝、流量管理、認(rèn)證、包過(guò)濾等。IP路由器 主要內(nèi)容 ? IP路由器架構(gòu) ? 路由查找 ? 數(shù)據(jù)包分類 1 IP路由器架構(gòu) IP路由器的功能 ? IP路由器的基本功能可以分為三類： ? 路由處理： 運(yùn)行路由協(xié)議，建立并維護(hù)路由表。 ? 包轉(zhuǎn)發(fā)：與轉(zhuǎn)發(fā) IP包相關(guān)的工作，如報(bào)頭檢查、路由 查找、報(bào)頭修改、包分片等。 IP路由器的一般結(jié)構(gòu) 路由表查找 — Binary Trie ? 將路由表中的地址前綴組織在一棵二元查找樹(shù)中。 ? 與地址前綴對(duì)應(yīng)的節(jié)點(diǎn)包含了轉(zhuǎn)發(fā)信息。 路由緩存（ cache） ? 為提高路由查找速度，采用二元查找樹(shù) +路由緩存的方法： ? 路由 cache中存放最近使用過(guò)的 目的 IP地址，下一跳 ，用哈希表組織，使用精確匹配查找。 路由緩存的問(wèn)題 ? 使用路由緩存的前提是網(wǎng)絡(luò)流量具有足夠的局部性，從而 cache的命中率足夠高。 ? 頻繁的路由更新使得 cache中的路由信息很快失效。 第二代：基于總線和多處理器的架構(gòu)（ 1） ? 卸載包轉(zhuǎn)發(fā)、路由緩存和包緩存到 NIC上： ? 減少總線拷貝 ? 減輕 CPU負(fù)擔(dān) ? 減少查表時(shí)間 ? 缺點(diǎn)： ? 吞吐量依賴流量模式 ? 高速時(shí)主路由表查找仍是瓶頸。 帶路由緩存的結(jié)構(gòu) 第二代：基于總線和多處理器的架構(gòu)（ 2） 使用轉(zhuǎn)發(fā)引擎的結(jié)構(gòu) ? 轉(zhuǎn)發(fā)功能由專門(mén)的轉(zhuǎn)發(fā)引擎完成。 ? 包載荷總是直接在接口模塊間傳輸。 ? 缺點(diǎn)：共享總線仍然是瓶頸。 使用交換結(jié)構(gòu)代替共享總線 Crossbar交換結(jié)構(gòu) ? 使用 N M 個(gè)交叉開(kāi)關(guān)連接輸入與輸出端口 ? 控制器硬件處理端口競(jìng)爭(zhēng) ? 多個(gè)端口之間可以并行傳輸，集合吞吐率高 使用轉(zhuǎn)發(fā)數(shù)據(jù)庫(kù)（ FIB）代替路由緩存 ? 當(dāng)網(wǎng)絡(luò)拓?fù)漕l繁變化、流量模式高度隨機(jī)時(shí)，網(wǎng)絡(luò)流量主要通過(guò)主 CPU而不是路由緩存轉(zhuǎn)發(fā)。 ? 解決方案： ? 在每個(gè)網(wǎng)絡(luò)接口上用轉(zhuǎn)發(fā)數(shù)據(jù)庫(kù)（ Forward Information Base， IP路由表的完整鏡像）取代路由緩存。 路由器中的快路徑和慢路徑 ? 快路徑（關(guān)鍵路徑）： ? 由時(shí)間關(guān)鍵的處理任務(wù)構(gòu)成：與包轉(zhuǎn)發(fā)直接相關(guān)的任務(wù)是時(shí)間關(guān)鍵任務(wù)。 ? 慢路徑（非關(guān)鍵路徑）： ? 由非時(shí)間關(guān)鍵的處理任務(wù)構(gòu)成：與包轉(zhuǎn)發(fā)不直接相關(guān)的任務(wù)一般 是非時(shí)間關(guān)鍵任務(wù)。 快路徑 or 慢路徑？ 分布式路由器結(jié)構(gòu)中的功能劃分 Cisco路由器架構(gòu)的演變 ? RSP執(zhí)行以下任務(wù)： ? 基本包交換，使用FIB代替路由緩存。 ? 運(yùn)行路由協(xié)議。 Cisco 7500 Route Switch Processor ? Cisco 7500（ 1995年） Cisco 7500（續(xù)） ? 每個(gè) VIP有處理器，執(zhí)行 IP包交換和基本包轉(zhuǎn)發(fā)之外的服務(wù)。 Cisco Versatile Interface Processor 1996年引入 VIP接口板 Cisco 10000 ESR（邊緣服務(wù)路由器） ? 線卡（ 8塊）：管理自己的接口類型，通過(guò)背板向 PRE發(fā)送和接收數(shù)據(jù)包。 ? FP：用網(wǎng)絡(luò)處理器實(shí)現(xiàn)的轉(zhuǎn)發(fā)路徑。 Cisco ASR1000 路由器架構(gòu)的進(jìn)一步發(fā)展 ? 更多的包處理功能加到快路徑上： ? 包過(guò)濾、深度數(shù)據(jù)包檢查、流量管理等原先屬于特殊服務(wù)的功能，現(xiàn)在也加入到了快路徑上。 基于通用多核處理器的路由器 ? 通用多核處理器的出現(xiàn)為構(gòu)建高速路由器提供了一種新的可選方案： ? 通用多核處理器為線程級(jí)并行而優(yōu)化，特別適合具有天然線程級(jí)并行特性的網(wǎng)絡(luò)處理任務(wù)。 ? 設(shè)計(jì)中已經(jīng)考慮了適合網(wǎng)絡(luò)處理的有用特性。 ? 每一顆 NehalemEX 芯片都與其他 3 顆芯通過(guò)QuickPath 點(diǎn)對(duì)點(diǎn)相聯(lián)。 ? 高性能和可編程性（可擴(kuò)展性）是一對(duì)矛盾： ? 高端路由器依靠專用、封閉的硬件和軟件來(lái)獲得高速度，但很難擴(kuò)展。 構(gòu)建可擴(kuò)展高速路由器的方法（ 1） ? 從已有的高端專用設(shè)備入手，增強(qiáng)其可編程性： ? 專用設(shè)備開(kāi)放有限的 API，允許第三方修改 /擴(kuò)展設(shè)備中的軟件部分，但這些修改通常不涉及核心包處理。 構(gòu)建可擴(kuò)展高速路由器的方法（ 2） ? 從軟件路由器著手，提高其包處理速度： ? 開(kāi)發(fā)容易：可使用熟悉的計(jì)算機(jī)硬件平臺(tái)、操作系統(tǒng)和開(kāi)發(fā)工具來(lái)開(kāi)發(fā)網(wǎng)絡(luò)設(shè)備。 ? 性能差距大：軟件路由器的速率只能達(dá)到 15Gbps。 RouteBricks的設(shè)計(jì)目標(biāo)和挑戰(zhàn) ? 目標(biāo)：設(shè)計(jì)一個(gè) N端口路由器，每個(gè)端口的線速為R ， N和 R可能很大。 ? 包交換：通過(guò)一個(gè)交換結(jié)構(gòu)和集中的包調(diào)度器實(shí)現(xiàn)，交換結(jié)構(gòu) /包調(diào)度器必須以 NR的速度交換包。 設(shè)計(jì)原則（ 1） 構(gòu)建集群路由器 ? 設(shè)計(jì)原則一： ? 將路由器的功能并行化到多個(gè)服務(wù)器上，降低對(duì)單個(gè)服務(wù)器的性能要求，即設(shè)計(jì)一個(gè)集群路由器架構(gòu)。 ? 路由器中不使用任何集中式組件，任一組件的運(yùn)行速率不高于 cR（ c為 2或 3）。 ? 采用軟件路由器，功能擴(kuò)展非常方便。 ? 設(shè)計(jì)原則二： ? 在每個(gè)服務(wù)器內(nèi)部，將路由器的功能分布到多條處理路徑上，提高單臺(tái)服務(wù)器的處理能力。 ? 同一塊網(wǎng)卡上的兩個(gè)端口共享一個(gè) x8 PCIe ， 8條數(shù)據(jù)線能夠獲得的最大載荷數(shù)據(jù)速率為 。 服務(wù)器架構(gòu) 軟件環(huán)境 ? Click/Linux ， Click是一個(gè)模塊化的軟件路由器。 ? 擴(kuò)展了 Linux 10Gbps以太網(wǎng)驅(qū)動(dòng)程序。 如何將包分配到多個(gè)核上處理？ ? 原則 1：每個(gè)包隊(duì)列僅被一個(gè)核訪問(wèn) ? 原則 2：每個(gè)包僅被一個(gè)核處理 流水線方法 并行方法 優(yōu)化措施（ 2） 使用多隊(duì)列網(wǎng)卡 ? 情形一：核數(shù)多于端口數(shù)，且單個(gè)核無(wú)法處理一個(gè)端口的流量 ? 情形二：路徑重疊，如多個(gè)輸入端口向同一個(gè)輸出端口發(fā)包。 ? CPU預(yù)先在內(nèi)存中分配好以上數(shù)據(jù)結(jié)構(gòu)，并將一個(gè) skb地址（包描述符）通知給網(wǎng)卡。 優(yōu)化措施（ 3） 批處理 ? [3]通過(guò)處理來(lái)減少包的收發(fā)開(kāi)銷： ? 網(wǎng)卡驅(qū)動(dòng)的批處理：驅(qū)動(dòng)程序每次傳輸 kn個(gè)包描述符，減少在 PCIe及 I/O總線上產(chǎn)生的事務(wù)。 ? 輪詢驅(qū)動(dòng)的批處理： Click每次輪詢可最多接收kp個(gè)包。 ? 高速流量下使用批處理，低速流量下限制批處理的使用。 ? 地址前綴的兩種表示方法： ? 不大于 32比特的比特串跟上一個(gè) *，比如：1000001001010110* ? 帶點(diǎn)十進(jìn)制表示加上地址前綴長(zhǎng)度，比如： ? 地址聚合：連接到同一個(gè)網(wǎng)絡(luò)的所有主機(jī)在轉(zhuǎn)發(fā)表中對(duì)應(yīng)一個(gè)入口，即允許使用前綴表示一組地址。 ? 核心路由器的轉(zhuǎn)發(fā)表規(guī)模急劇擴(kuò)大，導(dǎo)致查表時(shí)間及內(nèi)存需求增加。 ? 允許任意地、遞歸地進(jìn)行地址聚合， 減少轉(zhuǎn)發(fā)表中的入口數(shù)目，有效