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能力發展速度，這主要是受限于片上Cache的整合技術，總線技術，并發技術以及鎖技術，不像萬兆/十萬兆以太網 技術可以看成一個獨立的技術，通用計算機需要考慮的是各種資源的互相配合，CPU技術，記憶體總線，電磁相容...是以專業做路由器的基本都抛開了CPU， 而是直接做轉發晶片。一塊卡插在通用計算機上，就變身成了專業路由器。資料通路完全在卡上完成，完全繞開了CPU，這就好像在計算機中内置了一個小計算 機。通用計算機僅僅提供管理和控制功能，比如Cisco的特快轉發就是這麼玩的。

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

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

把 目标IPv4位址看成一個位址空間的虛拟記憶體位址，把到達該目标位址的下一跳看作是對應虛拟記憶體位址的實體頁面位址，是不是就能像構造頁表那樣去構造路由 表了呢？想想看，虛拟位址翻譯到實體頁面是多麼地頻繁，它的效率是多麼地高！遺憾的是，CPU内部沒有處理IPv4位址的MMU機制，當然作為通用 CPU，它也不該有這種機制。但是總是可以通過類比悟出一些什麼。

       路由表查找的效率不在于算法本身的時間複雜度(相信很少有人用周遊法吧，能被選中作為系統查找算法的都是可接受的時間複雜度的算法)，而是在于實作中的開 銷，如果能利用CPU的Cache，那麼同樣時間複雜度的算法和不利用Cache的算法在效率上有數量級的超越。如若想利用CPU的Cache，那麼對數 據結構就有嚴格的要求，必須緊湊，且不能占據太多的空間，把路由表組織成頁目錄/頁表類的結構是一個很好的想法，足夠緊湊，可以載入Cache。另外做一 點優化，IPv4位址和虛拟記憶體位址完全可以類比，但是路由表對應頁目錄的部分并不以固定的IPv4位址bits來做索引，而是取K>=16，索引 到哪裡呢？索引到的不是頁表，而是一個range表，這個表固然也可以按照32-K來做索引，但是鑒于路由項很多都是經過聚合的，是以這裡可以是一個二叉 樹組織，在組織上依然是緊湊的數組。這就是DxR算法的核心。可見，并沒有什麼新的東西，隻是對已有的算法的資料結構做了重新組織，核心思想完全可以參見 CPU的MMU實作。

 本文轉自 dog250 51CTO部落格，原文連結:http://blog.51cto.com/dog250/1614550