Abstract
??本文闡述了理論上的NDN轉發(fā)引擎如何在目前現(xiàn)有的計算機中工作习瑰。本文利用現(xiàn)有的已經(jīng)成熟的高速技術設計了一個轉發(fā)引擎樣例沸枯，并通過分析最新的原型實現(xiàn)來了解其性能瓶頸帝美。通過CPU管道和指令層面的微架構分析潦蝇，我們發(fā)現(xiàn)動態(tài)隨機存取存儲器（DRAM）的延遲是高速轉發(fā)引擎的一個瓶頸番捂。最后，本文設計了2個對預取友好的報文處理機制來緩解DRAM的訪問延遲渠退∶ηǎ基于這兩個機制的原型在現(xiàn)有的計算機上可以達到4千萬/s的報文轉發(fā)速率。
Introduction
??軟路由是指利用現(xiàn)有的計算機配合軟件形成路由解決方案碎乃，多核CPU和快速聯(lián)網(wǎng)技術的研究進展確保了它的可行性《現(xiàn)有計算機的低成本、節(jié)能性和靈活性使得它可以作為部署IP軟路由和NDN軟路由的平臺荠锭。快速IP報文轉發(fā)一直是一個研究熱點晨川，目前基于CPU的轉發(fā)引擎的硬件架構都是以IP轉發(fā)的數(shù)據(jù)是存儲在快速存儲設備（比如SRAM）為前提設計的证九。Dobrescu利用多核CPU或多個服務器實現(xiàn)并行處理。這個研究中所用的轉發(fā)引擎和服務器都是現(xiàn)有的商用計算機共虑，這表明使用軟路由來實現(xiàn)快速報文轉發(fā)不需要使用特定的設備（比如GPGPU）愧怜。相繼地，如何壓縮數(shù)據(jù)結構成為一個研究問題妈拌，許多基于樹的結構用于存儲數(shù)據(jù)拥坛。其中，Degermark等人設計了一個multi-bit樹的數(shù)據(jù)結構尘分，將樹中連續(xù)的元素替換為單個元素猜惋。這使得最新的SRAM可以容納日益增長的IP前綴。
??受上述方案影響培愁，由于NDN中的名字前綴空間比IP前綴空間大得多著摔，時間復雜度也更大，為了實現(xiàn)快速報文轉發(fā)定续，很多研究方案致力于設計復雜的數(shù)據(jù)結構或者算法（比如基于布隆過濾器谍咆、 基于樹禾锤、基于哈希表的數(shù)據(jù)結構和算法）來優(yōu)化時間復雜度。但是他們都以數(shù)據(jù)主要存儲在快速存儲器為前提摹察，而實際情況是恩掷，大部分數(shù)據(jù)是存儲在DRAM。即便是在IP報文轉發(fā)中供嚎，如何緩解慢速存儲器的延遲也沒有很好的解決方案黄娘。因此，設計高速NDN軟路由的數(shù)據(jù)結構和算法的時候查坪，要從訪問的DRAM的次數(shù)和它們的時間復雜度這個角度來考慮寸宏。由于基于布隆過濾器就比基于哈希表訪問DRAM的次數(shù)更多，我們主要研究基于樹和基于哈希表的數(shù)據(jù)結構和算法偿曙。
??解決DRAM延遲的一個解決方案是使用壓縮的數(shù)據(jù)結構氮凝，減少訪問DRAM的次數(shù)⊥洌基于樹的數(shù)據(jù)結構通常比基于哈希表的數(shù)據(jù)結構的存儲空間更小罩阵，因為很多公共的前綴是共用的。但是启摄，雖然基于樹的數(shù)據(jù)結構適用于NDN硬路由稿壁，但是不適用于NDN軟路由。NDN軟路由中歉备，數(shù)據(jù)不能被固定在CPU緩存中傅是，因為CPU緩存的刪除和替換是由CPU來管理，而不是由用戶空間程序和操作系統(tǒng)來管理蕾羊。也就是說喧笔，由于從DRAM取數(shù)據(jù)是不可避免的，采用壓縮數(shù)據(jù)結構的方式并不是一個好的解決方法龟再。
??為了解決這個問題书闸，本文提出隱藏DRAM的延遲和減少DRAM的訪問次數(shù)是實現(xiàn)高速NDN軟路由的關鍵。因為即便是采用復雜的數(shù)據(jù)結構和算法利凑，DRAM的訪問次數(shù)也不可能變成0浆劲。最新的CPU支持指令和數(shù)據(jù)的預取，這使得指令和數(shù)據(jù)可以在實際被使用之前就預取到CPU緩存中哀澈，隱藏了DRAM的訪問延遲牌借。由于基于樹的數(shù)據(jù)結構很難在訪問DRAM之前知道要訪問哪里，很難實現(xiàn)預取策略割按。因為樹的查找是自頂向下走哺，在取到父節(jié)點之前，不能估計下一個要取的節(jié)點的地址”铮基于哈希的數(shù)據(jù)結構是個可行的方案择示，如果提前知道哈希鍵，其訪問模式是可以預測的晒旅。
