DxR路由查找算法前傳

你認為現在攜帶現代操作系統的通用計算機中哪類計算看上去是且必須是超級快的，毫無疑問，答案是內存訪問。
你認為現在攜帶現代操作系統的通用計算機中哪類計算看上去是且理論上超級慢的，毫無疑問，答案是路由尋址。

提前放假真的很無聊！

你認為內存尋址為什么快？你認為它為什么必須要快？

因為現在操作系統基于虛擬內存地址尋址，在虛址和物理地址之間需要有一個映射，這個過程事實上減慢了內存訪問的速度，但是我們擁有CPU的恩賜，即地址緩存，也就是TLB！
大 神說過，現代編程技術的核心就是尋址的技術。確實是這樣。CPU核心的處理性能早就不再是瓶頸，因為CPU總是要和外設進行交流，各種總線鋪設與核心之 外，路遠勞頓，電磁影響，其效率事實上拖慢了整體的處理進度。CPU的各級緩存此時的作用就是盡可能地避免遠途尋址，包括L1/L2/L3 Cache，TLB等，其中TLB緩存的是地址轉換結果，它在數據/指令緩存L1/L2/L3未命中后最后一次努力提高效率，如果TLB也未命中，就需要 執行最慢的過程了：執行頁表查找，映射到物理地址；地址總線發射物理地址；數據總線獲取數據...

我們來把眼界放寬一點

如 今，整個IP網絡就是一臺巨大的計算機，IP地址就是你可以將其看成是內存地址，試著比較一下32位系統的內存地址和IPv4地址，你可能會想到點什么。 在如今的互聯網上，CDN已經在扮演CPU Lx Cache的角色，盡可能避免遠距離尋址，但是IP路由這一塊的性能優化很少統一起來。為題就在這里，沒有統一的解決方案是因為在網絡領域，和計算機領域 正好相反，傳輸能力不斷增強，其發展速度曾一度遠超CPU的發展，網絡傳輸技術，像爆發了一般，目前10Gbit以太網毫無壓力，這些線纜可以埋在泥土 里，彎彎曲曲走在橫梁上，和那些多層立交線路板上高大上整齊排列的性能還達不到10Gbit/s的板子總線相比，真是英雄不問出處。此時，如果再使用 CPU進行純軟件路由查找，那將會拖慢midbox的線速能力，CPU這種在同一板子上高大上的東西到了高速網絡反而成了瓶頸。

繞開CPU的硬件轉發

過 去的十幾年，網絡技術發展速度遠超CPU能力發展速度，這主要是受限于片上Cache的整合技術，總線技術，并發技術以及鎖技術，不像萬兆/十萬兆以太網 技術可以看成一個獨立的技術，通用計算機需要考慮的是各種資源的相互配合，CPU技術，內存總線，電磁兼容...因此專業做路由器的基本都拋開了CPU， 而是直接做轉發芯片。一塊卡插在通用計算機上，就變身成了專業路由器。數據通路完全在卡上完成，完全繞開了CPU，這就好像在計算機中內置了一個小計算 機。通用計算機僅僅提供管理和控制功能，比如Cisco的特快轉發就是這么玩的。

合久必分，分久必合

隨著片上技術和板 上總線技術的整合能力的提升，通用CPU的各級Cache無論從大小，效率還是使用上均有了很大的提升，訪問內存的效率也提升了。此時，CPU再次將各類 路由轉發硬件卡統一在一起的機會來了。當然，并不是說所有的硬件轉發技術均會被CPU轉發技術取代，如果想追求更高的速度，當然還是專業的硬件轉發完勝 CPU轉發，但是起碼，高速的CPU轉發技術可以淘汰并整合掉市場上的大多數硬件轉發技術。

類比虛擬地址映射技術-古老的算法

精 通Linux網絡技術的應該都知道，現有的兩種路由查找算法是HASH查找和TRIE樹算法，這兩種算法均包括復雜零散的數據結構，對于純軟件層面的構 想，它們設計地都不錯；另外精通BSD協議棧的也該知道，BSD的Radix樹算法在軟件路由查找方面也表現不俗。但是仔細想一下，這些算法幾乎都是脫胎 于硬件路由轉發技術蓬勃發展的幾十年，因此它們更像是隱秘力量的自留地里自發長出的萌芽，并非是大勢所趨的結果。這類算法在本質上是一類通用的路由查找算 法，它們并非有針對性的利用所在硬件的硬件結構，比如CPU Cache等，也不曉得自己在什么平臺上跑，這些都被OS的接口屏蔽掉了，所有的針對體系結構的優化都是以預編譯宏的形式或者補丁的形式存在。

類比虛擬地址映射技術-DxR算法

把 目標IPv4地址看成一個地址空間的虛擬內存地址，把到達該目標地址的下一跳看作是對應虛擬內存地址的物理頁面地址，是不是就能像構造頁表那樣去構造路由 表了呢？想想看，虛擬地址翻譯到物理頁面是多么地頻繁，它的效率是多么地高！遺憾的是，CPU內部沒有處理IPv4地址的MMU機制，當然作為通用 CPU，它也不該有這種機制。但是總是可以通過類比悟出一些什么。
       路由表查找的效率不在于算法本身的時間復雜度(相信很少有人用遍歷法吧，能被選中作為系統查找算法的都是可接受的時間復雜度的算法)，而是在于實現中的開 銷，如果能利用CPU的Cache，那么同樣時間復雜度的算法和不利用Cache的算法在效率上有數量級的超越。如若想利用CPU的Cache，那么對數 據結構就有嚴格的要求，必須緊湊，且不能占據太多的空間，把路由表組織成頁目錄/頁表類的結構是一個很好的想法，足夠緊湊，可以載入Cache。另外做一 點優化，IPv4地址和虛擬內存地址完全可以類比，但是路由表對應頁目錄的部分并不以固定的IPv4地址bits來做索引，而是取K>=16，索引 到哪里呢？索引到的不是頁表，而是一個range表，這個表固然也可以按照32-K來做索引，但是鑒于路由項很多都是經過聚合的，因此這里可以是一個二叉 樹組織，在組織上依然是緊湊的數組。這就是DxR算法的核心。可見，并沒有什么新的東西，只是對已有的算法的數據結構做了重新組織，核心思想完全可以參見 CPU的MMU實現。