LayeredTrees: Most Specific Prefix based Pipelined Design for On-Chip IP Address Lookups

課程 : 論文研討(三)
日期 : 2011.11.18
時間 : 14:00 ~ 15:30
地點 : S414
作者 : 資工產碩(一) — 00366511吳家隆
講者 : 國立成功大學資訊工程學系-張 燕 光

路由器(router)是一種電腦網路連線設備，按照各種網路通信協定，大多數是 TCP/IP，少數是 IPX，極少數是其它協定，依照目地端網路位置，以路由器(router)為單位，分辨介面內部流量與外部流量，轉接到恰當的路由器(router)介面去。

 

路由協定(routing protocol)從適用範圍可分為適用區域網路(local area network)與廣域網路(wide area network)路由通信協定，適合區域的變動性快，儲存空間較小，大多是直接交換。

路由器通常都會提供 snmp 網路管理方式，讀或寫路由器內部 counter，甚至更改設定，同長提供 mib1 mib2 供使用扯讀取，mib1 大致為 layer 2，mib2 大致為 layer 3 4，可以透過專屬的網管系統或是共享軟體來管理路由器。

http://www.godspeed.url.tw/network_A/%E8%B7%AF%E7%94%B1%E5%99%A8(router)%E7%B0%A1%E4%BB%8B.htm

 1969年有Layered， Routers封包低，速度慢

近年技術提昇封包大，速度快

查詢快分流快；網頁à影音

放在CHIP內，但無法與現實同步à硬體設備提昇à封包查詢(ON CHIP 記憶體內之作法)

Ipv4   64bit 30多萬筆  à Ipv6  128bit 7000筆

必須執行一個 IP報文轉發的決定（稱為轉發，路由查找，或IP地址查找，最長前綴匹配）

確認封包傳送及儲存位

5+1之方式

運用表示法來辨別及取代資料，節省空間，同時可反解還原資料

 

Multiway Most Specific Prefix 樹採用 (n + 1) 位元的 prefix 表示法和區段表 [10] 來降低記憶體使用量。其多元平衡搜尋樹為本篇論文所提出「受制的B 樹建立演算法」 (CBA) 下建造的 B 樹，此演算法不但提昇原本 B 樹節點的使用率，也保持了能有效率的更新的特性。

獨立之情形時可以用同型累計來擷取

特性如下：

高速（例如40 Gbps/40-byte= 128M數據包/秒）
小型存儲（例如緩存或片上內存）
低更新時間
處理大型路由表的能力
實施的靈活性
低預處理時間
IPv6規格

結論

動態路由表的分層樹，晶片上存儲器，並行和流水線架構，實現120 Gbps的吞吐量